Jakość kontra ilość
Zadanie - poziom Olimpiada Informatyczna Juniorów
- limit czasu na test: 2 sekundy
- limit pamięci na test: 256 megabajtów
- wejście: standardowe wejście
- wyjście: standardowe wyjście
Zaprogramuj:
Masz daną sekwencję
n nieujemnych liczb całkowitych n nieujemnych liczb całkowitych a1, a2, … an.
Początkowo wszystkie elementy sekwencji są niepomalowane. Możesz pomalować każdą liczbę na czerwono lub na niebiesko (ale nie oba kolory jednocześnie) lub zostawić ją niepomalowaną.
Dla koloru c,
Count(c) to liczba elementów w sekwencji pomalowanych tym kolorem, a
Sum(c) to suma elementów w sekwencji pomalowanych tym kolorem.
Na przykład, jeśli dana sekwencja to [2,8,6,3,1] i jest pomalowana w ten sposób: [2 (niebiesko), 8 (bez koloru), 6 (czerwono), 3 (niebiesko), 1 (bez koloru)] to
Sum(Czerwony)=6, Sum(Niebieski)=2+3=5, Count(Czerwony)=1 i Count(Niebieski)=2.
Oszacuj, czy możliwe jest pomalowanie sekwencji tak, że:
Sum(Czerwony)>Sum(Niebieski) i Count(Czerwony)<Count(Niebieski).
Wejście: Każdy test zawiera kilka przypadków testowych. Pierwsza linia zawiera liczbę przypadków testowych
t (1≤t≤1000). Opis przypadków testowych następuje po niej.
Pierwsza linia każdego przypadku testowego zawiera: n (3≤n≤2⋅10^5) – długość danej sekwencji.
Druga linia każdego przypadku testowego zawiera n liczb całkowitych a1, a2, …, an (0≤a_i≤10^9) – daną sekwencję.
Gwarantowane jest, że suma n we wszystkich przypadkach testowych nie przekracza 2⋅10^5.
Wyjście: Dla każdego przypadku testowego wypisz TAK, jeśli możliwe jest pomalowanie danej sekwencji spełniając powyższe wymagania, w przeciwnym wypadku wypisz NIE.
Możesz wypisać TAK i NIE w dowolny sposób (na przykład napisy TAK, taK, TaK i tak będą rozpoznawane jako pozytywna odpowiedź).
Przykład: wejście:
4
3
1 2 3
5
2 8 6 3 1
4
3 5 4 2
5
1000000000 1000000000 1000000000 1000000000 1000000000
wyjście:
NIE
TAK
NIE
NIE
Uwagi: W pierwszym przypadku testowym nie ma możliwości pomalowania sekwencji w żaden sposób spełniający warunki.
Na przykład, jeśli namalujesz sekwencję w ten sposób: [1, 2 , 3]
(gdzie 3 jest pomalowany na czerwono, 1 i 2 są pomalowane na niebiesko), to Count(Czerwony)=1<Count(Niebieski), ale Sum(Czerwony)=3 ≯ Sum(Niebieski)=3.
W drugim przypadku testowym, możliwy sposób pomalowania sekwencji jest opisany w treści. Możemy zobaczyć, że
Sum(Czerwony)=6>Sum(Niebieski)=5 i
Count(Czerwony)=1<Count(Niebieski)=2.
W trzecim przypadku testowym nie ma możliwości pomalowania sekwencji w żaden sposób spełniający warunki. Na przykład, jeśli namalujesz sekwencję w ten sposób: [3, 5, 4, 2]
(gdzie 3 i 5 są pomalowane na czerwono, 4 i 2 są pomalowane na niebiesko), następnie Sum(Czerwony)=8>Sum(Niebieski)=6, ale Count(Czerwony)=2≮Count(Niebieski)=2. Nie jest to więc możliwy sposób namalowania sekwencji.
W czwartym przypadku testowym można udowodnić, że nie ma możliwości pomalowania sekwencji spełniając warunki dotyczące sumy i liczby elementów.
Zadanie przetłumaczone. Tekst oryginalny: https://codeforces.com/problemset/problem/1646/B