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ă?"._
Î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 $K$ 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 a fost ales aleator uniform din intervalul CARE_INTERVAL.
- În fiecare zi, robotul merge la cumpărături. El alege o submulţime a celor $K$ 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ă.

- 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 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 în cazul a cel puţin $195/200$ de 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

Fişierul de intrare $fraud.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $fraud.out$ ...

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

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 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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