|
Titlul: 1444 Peluza Sud Scris de: Andrei Grigorean din Noiembrie 17, 2013, 18:17:18 Aici puteţi discuta despre problema Peluza Sud (http://infoarena.ro/problema/peluzasud).
Titlul: Răspuns: 1444 Peluza Sud Scris de: Mihai Ionut Enache din Noiembrie 17, 2013, 22:56:56 Cum se face problema asta corect?
Titlul: Răspuns: 1444 Peluza Sud Scris de: Mihai Calancea din Noiembrie 18, 2013, 15:39:28 Ce înseamnă corect?
Titlul: Răspuns: 1444 Peluza Sud Scris de: George Marcus din Noiembrie 18, 2013, 16:14:12 Trebuie doar sa fii atent la restrictiile problemei :wink:
Titlul: Răspuns: 1444 Peluza Sud Scris de: Mihai Ionut Enache din Noiembrie 18, 2013, 16:50:55 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?
Titlul: Răspuns: 1444 Peluza Sud Scris de: Puscas Sergiu din Noiembrie 18, 2013, 17:03:51 Citat Peluza Sud are doar 1015 locuri. Astfel, vă rugăm ca locurile pe care le alegeţi să se afle în intervalul [X + 1, 1015]. 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. :-' Titlul: Răspuns: 1444 Peluza Sud Scris de: Mihai Ionut Enache din Noiembrie 18, 2013, 18:55:23 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).
Titlul: Răspuns: 1444 Peluza Sud Scris de: Puscas Sergiu din Noiembrie 18, 2013, 19:58:46 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. :D |