Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal(a) bodov. Ak si takýto typ úloh ešte nikdy neriešil(a), skús sa pozrieť ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel(a) by si sa naučiť, môžeš skúsiť našu KSP School.
Ak máš akékoľvek otázky ohľadom tejto úlohy, napíš Kubovi ([email protected]) alebo Soni ([email protected]).
Nová doručovacia spoločnosť PRA.sk prinesie revolúciu v rámci doručovania. Vyvinuli robotov, ktorí budú vedieť automaticky doručovať balíky, a teraz ich idú testovať na jednej ulici.
Na ulici je v rade vedľa seba niekoľko domov. Roboti sú zatiaľ veľmi hlúpi, a jediné čo dokážu je, že zoberú balík z nejakého domu, odnesú ho o nejaký počet domov doľava a vrátia sa naspäť. Každý robot nosí vždy na tú istú vzdialenosť, ktorú má vopred naprogramovanú. Rôzni roboti môžu ale nosiť na rôzne vzdialenosti.
Ak je napríklad v prvom dome (najviac vľavo) robot, ktorý nosí na vzdialenosť $3$, tak balíček spokojne odnesie do poľa o $3$ miesta vľavo od prvého domu, aj keď tam žiadny dom nie je.
Na testovanie robotov by firma chcela zariadiť, aby sa dali z každého domu posielať balíky do prvého (toho na ľavom konci ulice). Posielanie balíkov funguje tak, že keď z nejakého domu chcú poslať balík, tak ho dajú svojmu robotovi, ktorý ho odnesie o niekoľko domov doľava. Tam balík predajú ich robotovi, ktorý ho odnesie zase doľava, a tak ďalej, až kým sa buď nedostanú do prvého domu (kde si balík nechajú), alebo sa balík stratí niekde mimo ulice (ak ho robot doručí pred prvý dom).
Firma už má vyrobených presne toľko robotov, koľko je na ulici domov, a títo roboti majú určené vzdialenosti, na ktoré doručujú. Zisti, či sa dá rozdať robotov do domov (do každého domu jeden robot) tak, aby sa balík z hociktorého domu vždy dostal do toho prvého.
Na vstupe dostaneš niekoľko takýchto otázok. Na prvom riadku je počet otázok, ktoré máš vyriešiť. Potom sú pre každú otázku dva riadky:
Budú dve sady vstupov. V prvej sade je najviac $10$ otázok a najviac $10$ domov. V druhej sade môže byť až $20$ otázok a až $1\,000\,000$ domov.
Vzdialenosti pre robotov sú vždy kladné (robot nosí vždy smerom doľava a nikdy neostane tam, kde je) a môžu byť najviac $10\,000\,000$.
Za každú otázku vypíš ANO
alebo NIE
podľa toho, či je možné robotov
rozostaviť tak, aby balíček mohol doraziť od každého domu presne k prvému domu.
2
2
3 3
5
3 3 1 12 2
NIE
ANO
V tomto vstupe máme dve otázky.
V prvej otázke máme dva domy, a obaja roboti doručujú na vzdialenosť $3$,
takže z druhého domu sa balík určite dostane do domu o $2$ domy pred prvým.
Balík sa teda stratí a odpoveď je NIE
.
V druhej otázke máme $5$ robotov a môžeme ich rozostaviť napríklad v poradí
(podľa vzdialeností) $12, 1, 2, 3, 3$.
Potom napríklad z posledného domu sa balík dostane (o $3$ doľava) do druhého,
a odtiaľ (o $1$ doľava) do prvého.
Môžeš si vyskúšať, že aj z ostatných domov sa v tomto prípade balík dostane do prvého, odpoveď je teda ANO
.