| Fişierul intrare/ieşire: | marioneta.in, marioneta.out | Sursă | Baraj Shumen Juniori ICHB-Vianu - 2022 |
| Autor | Adăugată de |  Comisie Juniori Vianu - ICHB •comisie_baraj_shumen_ichb_vianu_juniori | |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Marioneta
Papusa, Comunism, Controlat
L'o
Dupa o vara apriga de cules castraveti murati, au ramas de redistribuit recoltele la Bastion. Sunt un numar infinit de ferme de castraveti murati, doar N dintre care au avut recolte nenule in acest an. Acestea sunt puse in mod convenient pe o linie, astfel ca ferma cu numarul i este pusa la i unitati agricole la dreapta de Bastion. A i-a ferma isi poate redistribui recoltele in urmatorul mod: daca are exact i castraveti murati, acestia vor fi impartiti in mod egal intre toate fermele aflate intre Bastion si ferma i-1 (i.e. fiecare primeste cate un castravete murat, pe cand ferma i ii pierde pe toti)
Scopul programului de Consolidare a Actiuniilor de Redistributie Nationala a Exploatariilor Agricole e de a aduce toti castravetii murati din provincie in Bastion pentru o ulterioara reredistributie. Programul esueaza daca un numar de castraveti murati raman in provincie fara a putea fi redistribuiti in modul convenit. Determinati daca programul guvernului Ghoberman esueaza sau va reusi.
Date de intrare
Fişierul de intrare marioneta.in contine pe primul test un numar, T, indicand ca vor fi de rezolvat T scenarii diferite. Fiecare scenariu va avea urmatoarea forma:
Pe prima linie contine N, reprezentand numarul de ferme cu recolta nenula. Urmeaza N linii, pe fiecare din ele aflandu-se doua numere Pi si Ci, reprezentand ca ferma numarul Pi a strans o recolta de Ci castraveti murati
Date de ieşire
În fişierul de ieşire marioneta.out se va afisa, pentru fiecare scenariu, 1 daca programul guvernului va functiona, 0 daca nu
Restricţii și subtask-uri
- 1 ≤ T ≤ 20
- 0 ≤ Ci ≤ 109
- 1 ≤ N
- 1 ≤ Pi ≤ 1.000.000
- Fie S = C1 + C2 + ...
| Subtask | Punctaj | Restricții |
|---|---|---|
| 1 | 11 puncte | N ≤ 400 și S ≤ 5000 |
| 2 | 14 puncte | N ≤ 1.000 |
| 3 | 21 puncte | N ≤ 6.000 și S ≤ 107 |
| 4 | 26 puncte | N ≤ 10.000 |
| 5 | 28 puncte | N ≤ 50.000 |
Exemplu
| marioneta.in | marioneta.out |
|---|---|
| 3 1 2 2 2 3 2 4 4 1 3 3 | 1 1 0 |
