Finále

E: Stavba portálu

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Obyvatelé planety S2 se s výzkumníky Ústředí Kasiopey podělili o znalost speciálních uraniovo-epistemologických tyčí. Na planetě Ma-stra chtějí z těchto tyčí vytvořit teleportační portál.

Každá tyč má délku a jednu základní příměs.

Vědci však přišli na to, že ne ze všech tyčí lze vytvořit portál. Portál musí tvořit trojice tyčí, které tvoří trojúhelník nenulového obsahu a zároveň ve všech tyčích musí být jiná příměs.

Zjistěte, jestli lze z daných tyčí vytvořit funkční portál.

Tvar vstupu

Na prvním řádku je číslo T, počet testovacích vstupů.
Každý vstup má na prvním řádku číslo N, počet tyčí v daném vstupu.
Na dalších N řádcích je vždy dvojice čísel, delka tyče a číslo její příměsi.
Délka tyče je v každém vstupu nejvýše 109.
V každém vstupu jsou alespoň tři různé příměsi.

Tvar výstupu

Pokud existuje trojice tvořící trojúhelník, napište ANO a pokud ne, napište NE.

Lehká verze

  • T ≤ 10
  • N ≤ 100
  • Čísla příměsí jsou od 1 do 30.

Těžká verze

  • T ≤ 10
  • N ≤ 106
  • Čísla příměsí jsou od 1 do 1000

Ukázkový vstup

3
3
2 1
3 2
4 3
5
1 1
2 2
3 3
4 2
8 3
5
5 1
6 1
15 1
3 2
8 3

Ukázkový výstup

ANO
NE
ANO

Vysvětlení ukázkového vstupu a výstupu

V prvním případě jsou všechny přísady v tyčích různé a mohu z nich vytvořit trojúhelník.

V druhém případě sice můžeme vytvořit trojúhelník z délek 2,3,4, ale tyče délky 2 a 4 mají stejnou příměs, tedy nemůžeme vytvořit požadovaný trojúhelník.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)