| Fişierul intrare/ieşire: | sate2.in, sate2.out | Sursă | ACM ICPC - Romanian Programming Contest 2016 |
| Autor | Clementin Cercel | Adăugată de |  Traian Rebedea •trebedea |
| Timp execuţie pe test | 1 sec | Limită de memorie | 100000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sate2
Se cunoaşte un regat feudal organizat sub forma a N cătune. În fiecare cătun trăiesc locuitori astfel încât numărul total de locuitori din regatul feudal este M. După invazia poporului migrator vecin, se doreşte reorganizarea celor N cătune în K sate astfel: a) fiecare sat să conţină câtul împărţirii lui M la K locuitori b) fiecare cătun să fie inclus într-un singur sat. Un cătun este inclus într-un sat dacă toţi locuitorii cătunului respectiv aparţin satului. Odată ce un cătun va aparţine unui sat, acesta nu poate sa mai aparţina şi unui alt sat. Decideţi dacă este posibilă reorganizarea regatului feudal.
Date de intrare
Datele de intrare se citesc din fişierul sate2.in.
Pe prima linie se află numărul de teste T.
Fiecare test conţine pe prima linie 3 numere naturale:
- N - numărul de cătune,
- M – numărul total de locuitori din regatul feudal,
- K – numărul de sate care se doresc formate.
Pe următoarea linie se află N numere naturale reprezentând numărul de locuitori din fiecare cătun.
Date de ieşire
Fişierul de ieşire sate2.out cuprinde, pentru fiecare test, o singură linie conţinând raspunsul "DA" sau "NU" (fără ghilimele), atunci când se poate reorganiza regatul feudal sau nu.
Restricţii
- 1 ≤ T ≤ 11
- 1 ≤ N ≤ 3000
- 1 ≤ M ≤ 90000
- K = 3 sau 4
- Valorile pentru numărul de locuitori din fiecare cătun sunt numere naturale din intervalul [1, 10.000]. Pot exista mai multe cătune cu acelaşi număr de locuitori.
Exemplu
| sate2.in | sate2.out |
|---|---|
| 2 9 60 3 2 2 10 6 1 10 14 11 4 9 60 4 2 2 10 6 1 10 14 11 4 | DA NU |
