Fişierul intrare/ieşire:sate2.in, sate2.outSursăACM ICPC - Romanian Programming Contest 2016
AutorClementin CercelAdăugată detrebedeaTraian Rebedea trebedea
Timp execuţie pe test2 secLimită de memorie100000 kbytes
Scorul tăuN/ADificultateN/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.insate2.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?