Fişierul intrare/ieşire:aliniate.in, aliniate.outSursăAlgoritmiada 2019 Runda Finala
AutorAlexandru Petrescu, Tamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aliniate

In arhitectura sistemelor, conceptul de "aliniare" a tipurilor de date este relevant; mai exact, un tip de date primitiv trebuie sa fie pozitionat la o adresa multiplu a lungimii sale (de exemplu, un intreg de 4 bytes trebuie sa fie pe o pozitie multiplu de 4). Asta e chiar util in unele implementari (de exemplu, un nod dintr-un std::set trebuie sa se gaseasca pe o pozitie multiplu de 8; astfel, pointerii din acel nod catre alti fii mereu au 0 pe ultimii 3 biti, iar implementarea din stl al acestui container foloseste acei biti pentru a stoca informatii). Aceasta problema foloseste acest concept.

Patronul firmei GazAliniat vede valoare doar in lucrurile aliniate. El considera ca o subsecventa [x, y], de lungime putere a lui 2, este aliniata daca si numai daca y - x + 1 il divide pe x. El are in fata lui un sir de 109 valori intregi, indexate de la 0. El alege cel mult 100.000 subsecvente aliniate, si calculeaza produsul valorilor din din acele subsecvente, modulo 232, notand aceste valori. Din nefericire, adversarul sau Hideyoshi, seful Universitatii Petrol si Gaze a metropolei B i-a furat secventa, si a modificat cateva dintre produsele notate. Patronul se intreaba acum: "Boss, oare exista un mod de a alege cele 109 valori astfel incat produsele sa coincida cu cele notate?"

Date de intrare

Fişierul de intrare aliniate.in contine, pe primul rand, numarul T de teste din fisierul dat. Urmeaza cele T teste.
Un test va contine, pe primul rand, numarul N de produse notate.
Vor urma pe urmatoarele N numere cate un triplet x y z care semnifica: "produsul valorilor de la x la y, modulo 232, este z".

Date de ieşire

În fişierul de ieşire aliniate.out va contine T randuri, fiecare continand rezultatul pentru cate un test, in ordine.
Pentru fiecare test, daca exista un sir de 109 valori care satisfac restrictiile date, sa se afiseze 1; altfel, sa se afiseze 0.

Restricţii

  • 1 ≤ T ≤ 10.
  • 0 ≤ x ≤ y ≤ 109
  • Subsecventele date sunt aliniate.
  • 0 ≤ z < 232.
  • 1 ≤ N ≤ 50.000.
  • Suma N-urilor in toate testele dintr-un fisier este cel mult 100.000.
  • Pentru 5 puncte, subsecventele din input nu se intersecteaza, si N ≤ 100.
  • Pentru alte 15 puncte, N ≤ 100.
  • Pentru alte 30 puncte, valorile din sir sunt impare.
  • Primul test din feedback corespunde primului subtask, cel de al doilea test din feedback corespunde celui de al doilea subtask, cel de al treilea si cel de al patrulea test din feedback corespunde celui de al treilea subtask.

Exemplu

aliniate.inaliniate.out
3
2
0 1 2
0 0 1
2
0 1 2
0 0 4
2
0 0 1
0 0 2
1
0
0

Explicaţie

Restrictiile din primul test sunt satisfacute prin a alege valorile 1, 2, 1, ....

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?