În
timpul liber Ionela lucreaza la o gradinita, unde are grija de N
bebelusi (sa-i numerotam de la 1
la N).
Pe parcursul zilei bebelusii trebuie sa doarma. Pentru a-l adormi pe bebelusul
cu numarul i Ionela are nevoie
de A[i] minute, dupa care el
doarme exact B[i] minute. Atunci
când toti bebelusii dorm, se odihneste si Ionela.
De
exemplu, sa consideram ca la gradinita sunt doi bebelusi, A[1]=10,
B[1]=10, A[2]=10,
B[2]=20. Daca Ionela îl
adoarme mai întâi pe primul, apoi pe al doilea, ea nu are posibilitatea
sa se odihneasca, dar daca primul e adormit bebelusul al doilea, ea se va odihni
10 minute dupa ce îl adoarme si pe primul.
Cerinta
Scrieti un program care sa stabileasca daca se poate determina o ordine de adormire
a bebelusilor astfel incat Ionela sa se poata odihni cel putin un minut.
Date de
intrare
Fisierul de intrare baby.in contine
pe prima linie un numar natural T
reprezentand numarul de seturi de date de test din fisierul de intrare. Urmeaza
liniile care descriu cele T seturi
de date. Pentru fiecare set de date se va scrie o linie ce contine un numar
natural N, reprezentand numarul
de bebelusi. Urmeaza apoi doua linii care contin cate N
numere naturale separate prin spatii; prima dintre acestea contine valorile
A[1] A[2] ... A[N], iar cea de
a doua contine valorile B[1] B[2] ...
B[N], cu semnificatia din enunt.
Date
de iesire
Fisierul de iesire baby.out va
contine T linii, cate una pentru
fiecare set de date de test. Pe linia i
va fi scrisa valoarea 1, daca
Ionela se poate odihni pentru configuratia descrisa de setul de date de test
i, respectiv valoarea 0
in caz contrar.
Restrictii si precizari 1 <= N <= 100 000
1 <= A[i], B[i] <= 109
Exemplu
baby.in
baby.out
2
2
1 10
10 20
2
10 10
10 10
1
0
prof. Sergiu Corlat
Liceul Moldo-Turc
Chisinau
Contact:scorlat@gmail.com