015 Permutari II

[•fluffy]

Aici puteţi discuta despre problema Permutari II.

[•greco]

am trimis rezolvarea la problema asta si am luat 95 p. (am ratat testul 1 ). Am mai trimis-o o data ca sa ma conving, si, in loc de 100 p., sau macar tot de 95, am luat 85. (nu am modificat nimic). Am mai trimis apoi de cateva ori, si nu am luat acelasi punctaj de 2 ori la rand. (intre 85-95).

destul de ciudat, nu ?

[•wickedman]

da. ai dreptate. exista o mica problema la evaluator. din fericire am observat`o de ceva timp si va aparea o rezolvare in curand. banuiesc ca diferenta de punctaj era data de niste TLE-uri, nu? (vezi raport de evaluare)

[•LordAnta]

Te superi daca iti cer primul test, ca habar nu am unde am putut gresi!!!

[•LordAnta]

data de niste TLE-uri

Ce sunt alea TLE-uri?

[•DeadStar]

TLE= TIme Limit Exceeded

Oricum acum merge la iei accepted. Trebuie doar sa observi o chichita:D

[•LordAnta]

Va rog da-ti unui sarman primul test de al aceasta problema!!!

[cristi8]

...nici mie nu imi ia primul test...
puteti totusi sa dati un indiciu despre primul test ?

[•wickedman]

lumea e pe la ONI asa ca intrebarile de acest gen trebuie sa-si mai astepte putin raspunsul.
10x

[•pirosl]

Sa traiasca evaluatorul si la mai mare
Uitati ce am obtinut eu:
TEST 1   ...[0.13s]...   Time limit exceeded
TEST 2   ...[0.01s]...   Corect!
TEST 3   ...[0.01s]...   Corect!
TEST 4   ...[0.01s]...   Corect!
TEST 5   ...[0.22s]...   Corect!
TEST 6   ...[0.01s]...   Corect!
TEST 7   ...[0.01s]...   Corect!
TEST 8   ...[0.01s]...   Corect!
TEST 9   ...[0.01s]...   Corect!
TEST 10   ...[0.13s]...   Time limit exceeded
TEST 11   ...[0.01s]...   Corect!
TEST 12   ...[0.07s]...   Corect!
TEST 13   ...[0.01s]...   Corect!
TEST 14   ...[0.01s]...   Corect!
TEST 15   ...[0.01s]...   Corect!
TEST 16   ...[0.01s]...   Corect!
TEST 17   ...[0.01s]...   Corect!
TEST 18   ...[0.02s]...   Corect!
TEST 19   ...[0.01s]...   Corect!
TEST 20   ...[0.01s]...   Corect!

Test 5 - 0.22s trece.....test1 - 0.13s pica test10 - 0.13s pica.
Sa fie oare 22<13    !?!?!!?

[•ParrAzitU]

Si eu am obtinut ceva asemanator daca te uiti aici : http://info.devnet.ro/forum/viewtopic.php?t=306&highlight=
.. Oricum ideea e ca aia nu sunt timpii reali, sunt doar orientativi  

[•wickedman]

Sa fie oare 22<13    !?!?!!?

Nu e nevoie sa te dai cu capul de pereti.
In raport scrie:

Timpii de executie prezentati aici sunt orientativi. Evaluatorul foloseste un alt timer (mult mai exact) pentru a cronometra sursele compilate. Timpii reali pe configuratia curenta sunt cu ~0.015s mai mici decat cei raportati aici.

[cristi8]

...nici mie nu imi ia primul test...
puteti totusi sa dati un indiciu despre primul test ?

lumea e pe la ONI asa ca intrebarile de acest gen trebuie sa-si mai astepte putin raspunsul.
10x

..puteti totusi da un indiciu la primu test ? a trecut ONI..

[•pirosl]

Eu cred ca primul test e ceva de genul

100000
2 3 4 5 6 7 8 ..... 100000 1

sau

100000
2 3 4 5 6 7 8...49999 1 50001 50002 50003 .... 100000 50000

[u-92]

nici mie nu-mi merge primul test.. pe exemplele alea cred ca "k"-ul e mult mai mare de 100.000.. dar totusi.. ce chichita trebuie sa observi?  

[•pirosl]

Chichita........ = ciclu intr-o permutare

[u-92]

pai asa am facut.. dar cum am mai zis, iau TLE la primul test

[cristi8]

mie imi da raspuns incorect. poate cineva sa dea un indiciu despre testul asta ?

( pe timus am luat accepted cu aceasi sursa )

EDIT: am rescris cmmmc-ul si am luat 100... ma complicasem sa calculez factorii primi comuni si necomuni la puterea cea mai mare si dupa aia construiam raspunsul din ei

[•vladcyb1]

 Eu nu inteleg problema asta !!
 In exemplul 1.
 

Cod:

perm2.in 
 6
 1 2 3 4 5 6
perm2.out
1

In enunt e dat un tabel unde arata cum se face P^1(i).
Dupa tabel P^1(1,2,3,4,5,6)=(2,3,4,5,6,1)
  (2,3,4,5,6,1) este diferit de (1,2,3,4,5,6), deci nu e permutare identica.
Explicati-mi va rog exemplul asta si daca se poate si inca unul.  

[cristi8]

ok.. sa zicem ca tu citesti din perm2.in N-ul si vectorul a (a[1], a[2], .. a[n])
si sa zicem ca ai p[k][i ] cu semnificatia "valoarea de pe pozitia i din permutarea p^k"

o sa ai p[0][i ] = i, si in rest, p[k][i ] = a[p[k-1][i ]]
(gandeste-te la asta si fa eventual pe hartie sa-ti dai seama cum vine)

--------------------
tabelul din enunt era DOAR UN EXEMPLU de vector a  (acolo e notat cu P mare)
--------------------
..pentru exemplul care nu-l intelegi tu, ai a[i ] = i... deci evident, p[1][i ] = i, adica permutare identica dupa 1 pas

[•Adriana_S]

pt exemplul n = 8 si 1 5 2 3 4 8 6 7, daca am facut eu bine pe hartie, raspunsul n-ar trebui sa fie 13?

Cod:

p^1    1 5 2 3 4 8 6 7
p^2    1 4 5 2 3 7 8 6
p^3    1 3 4 5 2 6 7 8
p^4    1 2 3 4 5 8 6 7
p^5    1 5 2 3 4 7 8 6
p^6    1 4 5 2 3 6 7 8
p^7    1 3 4 5 2 8 6 7
p^8    1 2 3 4 5 7 8 6
p^9    1 5 2 3 4 6 7 8
p^10   1 4 5 2 3 8 6 7
p^11   1 3 4 5 2 7 8 6
p^12   1 2 3 4 5 6 7 8
p^13   1 5 2 3 4 8 6 7

cam asa ar arata permutarile....si sunt 13. Daca n-am dreptate, sorry

[ditzone]

Trbuie aflat K astfel incat p^K este permutarea identica (1,2,3,...,n)... adica.. raspunsul pe exemplul acesta va fi 12 ..

[•Adriana_S]

aaaa...acum pricep   ...sorry, am inteles eu gresit enuntu

[•alex_prg]

sigur e bun exemplu 2 ? eu primesc 3 ... cred ca acolo calculeaza p(p^1)

[ditzone]

Nu inteleg exact la ce te referi, dar exemplele sunt bune