Fişierul intrare/ieşire:fraud.in, fraud.outSursăACM-ICPC Faza Nationala 2018
AutorMihai CalanceaAdăugată de
Timp execuţie pe test0.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Fraud

Unchiul tău Reginaldius este foarte bogat. Fiind foarte bogat, are acces la produse şi servicii rar întâlnite, ca de exemplu primii roboţi de pe piaţă care joacă rol de servitori. Unchiul Reginaldius are un astfel de robot, care, printre altele, are sarcina de a cumpăra brânzeturi pentru bucătăria unchiului. Astăzi, unchiul tău te-a sunat şi ţi-a spus că el este destul de convins că robotul îl fură atunci când cumpără brânzeturile. Bineînţeles, asta nu e o problemă reală pentru el, fiindcă este foarte bogat, dar este foarte interesat de perspectiva publicării unui paper pe această tema, pentru care deja a ales un nume:

"Tu ştii cu ce seturi de date se antrenează robotul tău când nu eşti acasă?".

Înainte de a face acest lucru, el trebuie să se asigure de ipoteza sa, iar aici îi vii tu în ajutor. În continuare vom formaliza situaţia din bucătăria unchiului Reginaldius şi cerinţa sa:

- Bucătăria unchiului Reginaldius conţine 9 tipuri diferite de brânză.
- Fiecare tip de brânză poate fi cumpărat la kg. Pentru fiecare tip de brânză, preţul unui kilogram din tipul respectiv este un numar natural ales aleator uniform din intervalul [1, 1000].
- În fiecare zi, robotul merge la cumpărături. El alege o submulţime a celor 9 tipuri şi cumpără un kilogram din fiecare. Submulţimea este aleasă aleator uniform din mulţimea tuturor submulţimilor de brânzeturi, inclusiv mulţimea vidă.
- Robotul face apoi suma preţurilor per kilogram pentru brânzeturile din ziua respectivă, fie ea egală cu S.
- Dacă robotul este corect, el îi va spune întotdeauna unchiului că a cheltuit o sumă egală cu S.
- Dacă robotul este incorect (a se citi hoţ), el îi va spune unchiului că a cheltuit o sumă egală cu ceil(S + X * S) unde X este un număr din mulţimea {0.01, 0.02, 0.03, 0.04, 0.05}. X este ales aleator uniform din această mulţime. X este regenerat în fiecare zi. Cu alte cuvinte, robotul va mări suma arătată unchiului cu un procent ales aleator între 1 şi 5 şi apoi o va rotunji superior la un întreg.
- Unchiul îţi oferă sumele arătate de robot pentru ultimele 365 de zile şi atât. Nu ştie nici ce preţuri au brânzeturile, nici ce submulţimi a ales robotul în fiecare zi, ci presupune doar că acestea au fost generate conform algoritmului de mai sus.

Poţi ghici doar din sumele arătate de robot dacă acesta este corect sau incorect? Mai exact, vei primi 200 de seturi de date, fiecare conţinând 365 de sume. Fiecare set a fost generat folosind algoritmul de mai sus şi pentru fiecare s-a ales aleator uniform dacă setul este generat cu un robot corect sau unul incorect. În particular, te rugăm să notezi că preţurile brânzeturilor sunt generate independent în fiecare set. Tu trebuie să analizezi datele şi să afişezi pentru fiecare set dacă crezi că robotul care a produs sumele respective este corect sau incorect. Pentru a rezolva această problemă trebuie să ghiceşti răspunsul corect pentru cel puţin 196/200 din seturi.

Date de intrare

Fişierul de intrare fraud.in va conţine 200 de seturi de date. Fiecare set de date este descris pe o singură linie şi conţine exact 365 de numere naturale, reprezentând sumele arătate de robot unchiului în fiecare zi din ultimul an.

Date de ieşire

În fişierul de ieşire fraud.out se vor afla 200 de linii, fiecare conţinând fie şirul "Corect", fie şirul "Incorect", în funcţie de concluzia trasă de tine pentru fiecare set în parte.

Restricţii

  • Va exista un singur fişier de test, acesta conţinând 200 de seturi, conform descrierii de mai sus. Fişierul este acelaşi pentru toţi participanţii concursului şi rămâne fix pe perioada acestuia.
  • Fiindcă problema implică multiple elemente aleatoare, se poate argumenta că orice soluţie a unui concurent, oricât de performantă, poate ghici mai puţin de 196 de seturi din "ghinion". Garantăm că există cel puţin o soluţie pentru care "ghinionul" are un efect minor. În particular, soluţia oficială a fost rulată pe 10.000 de fişiere diferite generate conform enunţului, rezolvându-le corect pe toate. 

Exemplu

fraud.infraud.out
123 45 6 100 45 ... (alte 360 de valori)
100 35 40 510 300 ... (alte 360 de valori)
... (alte 198 de linii)
Corect
Incorect
Corect
...(alte 197 de linii)

Explicaţie

Nu putem reda un exemplu complet, din cauza dimensiunilor prea mari ale fişierului. Exemplul de mai sus este ales să ilustreze formatul fişierului şi nu este neaparat un fragment dintr-un fişier generat prin algoritmul din enunţ. Valorile afişate în fişierul de ieşire sunt de asemenea lipsite de semnificaţie.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?