Fraud

F. Fraud

== include(page="template/taskheader" task_id="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 perspectivă publicării unui paper pe această tema, pentru care deja a ales un nume:

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ă?"._

- 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 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 *î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.

- 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. Pentru fiecare set, algoritmul de generare a fost rulat independent şi s-a ales aleator uniform dacă setul este generat cu un robot corect sau unul incorect. Tu trebuie să analizezi datele şi să afişezi pentru fiecare set dacă crezi că este corect sau incorect. Pentru a rezolva această problemă trebuie să răspunzi corect pentru cel puţin $195/200$ din seturi.

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.

h2. Date de intrare

h2. 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.

h2. Exemplu
table(example). |_. fraud.in |_. fraud.out |

| 123 45 6 100 45 ...
100 400 500 300 ...
...

| 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)

|
h3. 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.

== include(page="template/taskfooter" task_id="fraud") ==