#2145. Prosjek

    ID: 2145 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1269来源:qoj.ac数据:公开样例贪心

Prosjek

Prosjek

题目描述

Izborne pripreme – prvi izborni ispit Zadatak Prosjek 9. lipnja 2023. 3 sekunde / 512 MiB / 100 bodova Zadatak Prosjek Na ploči je zapisano N nenegativnih cijelih brojeva. U jednoj operaciji dozvoljeno je odabrati bilo koja dva broja s ploče čiji je zbroj djeljiv s 2, odabrane brojeve obrisati te dopisati novi broj na ploču - aritmetičku sredinu odabranih brojeva. Uočite da je nakon svake takve operacije novi broj na ploči također cijeli broj. Odredite je li moguće nizom opisanih poteza doći do situacije da na ploči piše točno jedan broj. Dodatno, ako je to moguće, odredite jedan mogući niz poteza kojim se to postiže. Također, potrebno je odrediti tražene poteze u T različitih situacija, svaka sa svojom zadanom pločom. Ulazni podaci U prvom je retku prirodni broj T, broj različitih situacija. U sljedećim retcima slijede redom opisi situacija. Svaki opis zadan je u sljedećem formatu. U prvom je retku prirodni broj N. U drugom je retku niz nenegativnih cijelih brojeva a1, a2, . . . , aN koji predstavljaju brojeve zapisane na ploči. Navedeni brojevi nisu nužno različiti. Izlazni podaci Za svaku situaciju ispišite sljedeće. Ukoliko ne postoji traženi niz poteza, u jedinom retku ispišite -1. Inače, u i-tom od sljedećih N −1 redaka ispišite dva nenegativna cijela broja xi i yi koji predstavljaju odabir brojeva na ploči u i-toj operaciji. Odabrani se brojevi moraju u tom trenutku nalaziti na ploči te njihov zbroj mora biti djeljiv s 2. Bodovanje U svim podzadacima vrijedi 1 ≤T ≤105, 2 ≤N ≤106 i 0 ≤ai ≤1018 za sve i = 1, 2, . . . , N. Suma svih vrijednosti N po svim situacijama iznosi najviše 106. Podzadatak Broj bodova Ograničenja T ≤100, N ≤7 1 9 T ≤100, ai ≤10 za sve i = 1, 2, . . . , N 2 23 3 16 Svi brojevi na svim pločama su parni. 4 52 Nema dodatnih ograničenja. 3 od 6 Izborne pripreme – prvi izborni ispit Zadatak Prosjek 9. lipnja 2023. 3 sekunde / 512 MiB / 100 bodova Probni primjeri ulaz ulaz 2 1 3 6 1 4 5 1 2 3 4 5 6 4 izlaz 1 4 5 5 1 5 izlaz 3 3 -1 4 6 1 5 3 5 3 5 2 4 4 4 Pojašnjenje drugog probnog primjera: Brojevi na ploči na početku su 1, 2, 3, 4, 5 i 6. Brojevi na ploči nakon prvog poteza su 2, 3, 4, 6, 3. Brojevi na ploči nakon drugog poteza su 2, 4, 6, 3. Brojevi na ploči nakon trećeg poteza su 2, 3, 5. Brojevi na ploči nakon četvrtog poteza su 2, 4. Konačni broj na ploči je 3. 4 od 6

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2
3
1 4 5
4
1 4 5 5
-1
1 5
3 5
4 4

样例 2

1
6
1 2 3 4 5 6
1 5
3 3
4 6
3 5
2 4