1444 Peluza Sud

[•wefgef]

Aici puteţi discuta despre problema Peluza Sud.

[•Mihai22e]

Cum se face problema asta corect?

[•klamathix]

Ce înseamnă corect?

[•PlayLikeNeverB4]

Trebuie doar sa fii atent la restrictiile problemei 

[•Mihai22e]

Pai eu afisam 10^14 + 1 si luam 100. Nu pare prea corect. De exemplu, daca N e mai mare de 30, cum s-ar rezolva?

[•harababurel]

Peluza Sud are doar 10¹⁵ locuri. Astfel, vă rugăm ca locurile pe care le alegeÅ£i să se afle în intervalul [X + 1, 10¹⁵].

Restrictia asta iti permite sa afisezi o solutie <universala>, care poate fi gasita destul de usor (http://en.wikipedia.org/wiki/Prime_gap).
Solutia ramane corecta.

[•Mihai22e]

Am inteles asta, asa am rezolvat si eu problema in timpul concursului. Dar vreau sa stiu cum s-ar rezolva problema daca limitele ar fi mai mari (peluza infinita si N = 50, de exemplu).

[•harababurel]

In cazul in care se cerea intervalul cel mai apropiat de X care sa fie valid, cred ca ar functiona o solutie bazata pe ciurul lui Eratostene.
Pentru peluza infinita poti sa te folosesti de aproximarea densitatii numerelor prime: alegand la intamplare un numar din intervalul [1, N], probabilitatea ca el sa fie prim ii de aprox. 1 / ln(N). Pentru N foarte mare, ai sanse bune sa gasesti solutia cu un random.

Momentan nu gasesc nimic mai bun; ma astept ca solutia oficiala sa coincida cu ce am facut noi in concurs. Ramane de vazut.