Fişierul intrare/ieşire:purice2.in, purice2.outSursăAlgoritmiada 2015, Runda 2
AutorMihai CalanceaAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Purice2

Până şi puricii au devenit deranjaţi de cât de mult vorbeşte Trăncănici. De aceea au decis să se strângă toţi în camera lui. Camera lui Trăncănici este o axă Ox pe care este marcat fiecare număr întreg, din intervalul (-inf, +inf). În total sunt N purici, iar fiecare purice i din cei N are o poziţie iniţială P[i] pe această axă. Doi purici i şi j, având P[i] < P[j] pot aplica următoarea operaţie:

  • Puricele i sare peste puricele j, ajungând la poziţia P[j] + (P[j] - P[i]), iar puricele j stă pe loc.
  • Puricele i stă pe loc, iar puricele j sare peste puricele i, ajungând la poziţia P[i] - (P[j] - P[i]).

Altfel spus, unul dintre purici va sări peste celălalt, păstrând distanţa dintre ei.

Puricii şi-ar dori să acopere toată camera lui Trăncănici prin aceste operaţii. Cu alte cuvinte, puricii vor să fii atins fiecare punct marcat de pe axa Ox din camera lui Trăncănici cel puţin o dată. Misiunea voastră este să le spuneţi puricilor dacă acest lucru este sau nu posibil.

Date de intrare

Fişierul de intrare purice2.in conţine pe prima linie numărul natural T, reprezentând numărul de teste. Pentru fiecare test, pe prima linie se va găsi numărul natural N, reprezentând numărul de purici. Pe cea de-a doua linie se vor găsi N numere întregi, reprezentând coordonatele iniţiale ale puricilor.

Date de ieşire

În fişierul de ieşire purice2.out se vor găsi T linii, fiecare linie i din cele T conţinând răspunsul pentru al i-lea test: 1 dacă puricii pot acoperi axa Ox în totalitate, 0 altfel.

Restricţii

  • 1 ≤ T ≤ 100
  • 3 ≤ N ≤ 50
  • -109 ≤ P[i] ≤ 109
  • Pentru 30% din teste are loc N = 3

Exemplu

purice2.inpurice2.out
2
3
1 2 3
3
1 3 5
1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?