Infoarena Monthly 2014, Runda 4

[•Teodor94]

Runda 4 va avea loc astazi, 24 Aprilie la ora 19⁰⁰.
Va uram mult succes!  

LE: La aceasta runda, problemele vor fi afisate in ordinea dificultatii lor.

[•Teodor94]

Runda s-a terminat! Clasamentul este public. Asteptam feedback

[•SebiSebi]

La problema bacterii am stat 1h sa imi dau seama ce gresesc. Iau incorect pe primele 3 teste. Eu afisez (n-1)^2^k + 1%m. Ca sa calculez asta fac mai intai sol = (2^k)%(m-1) si apoi afisez (n-1)^sol +1 %m.
Altfel, felicitari pentru concurs!  

[•tudorv96]

Foarte grele problemele. 27/85 au scos mai mult de zero.

Cat legat de problema Bacterii, pentru orice numar prim P = 2 ^ x + 1 nu functioneaza teorema lui Fermat. (m = 3 cazul cel mai evident)

[•freak93]

Hmm. Din cate vad eu 1^2 mod 3 = 1 si 2^2 mod 3 = 1. Pare ca functioneaza.

[•SebiSebi]

Da, asa se pare  Atunci care sa fie problema?

[•visanr]

Pentru testul 4 3 3 trebuie sa dea 1, mie imi dadea 2 cand luam incorect pe primele 3 teste.

[•tudorv96]

pentru m = 3, trebuie calculat (2 ^ k) % (m - 1), adica (2 ^ k) % 2 = 0. rezulta ca oricat ar fi a, am calcula (a ^ 0 + 1) % m = 2. Asta nu e valabil pentru testul 4 1 3

[•freak93]

Acela e un caz special. Vei ajunge sa calculezi X^0 mod M unde X congruent cu 0 mod M. In acest caz raspunsul e 0 si nu 1. Mica teorema lui fermat se aplcia doar la numerele prime cu modulo.

[•VisanCosmin]

Am observat ca la problema bacterii era o perioada dupa care se repetau resturile asa ca trebuia sa gasesti perioada si dupa era foarte usor,ar fi fost bine daca mi-as fi dat seama mai devreme dar tot mi-a placut concursul si de acum o sa particip incontinuare.

[•harababurel]

Nu cred ca te ajuta prea mult observatia asta, pentru ca se obtin cel mult 10^9 resturi modulo M. Ai avea complexitatea O(M * T).

[•Teodor94]

Am adaugat problemele in arhiva si am publicat pagina cu solutii! O sa adaugam solutiile oficiale cat mai curand.

[•PlayLikeNeverB4]

Am observat ca la problema bacterii era o perioada dupa care se repetau resturile asa ca trebuia sa gasesti perioada si dupa era foarte usor,ar fi fost bine daca mi-as fi dat seama mai devreme dar tot mi-a placut concursul si de acum o sa particip incontinuare.

Am incercat eu asa si nu merge. In medie, perioada e undeva pe la 300000.