Rezolvare PBinfo #3747

Enunț

Presupunem că avem două cutii notate A și B. Cutia A conține N bile numerotate cu numerele naturale distincte: 0, 1, 2, . . . , N − 1. Cutia B este goală.

Spunem că o bilă dintr-o cutie este bila specială a acestei cutii dacă numărul X cu care este numerotată această bilă este egal cu media aritmetică a numerelor celorlalte bile din cutie.

La un moment dat, cineva mută bila cu numărul K din cutia A în cutia B.

Vi se cere să alegeți alte K bile, din cutia A, pe care să le mutați în cutia B astfel încât cutia B să conțină K + 1 bile, iar bila cu numărul K să fie bila specială a cutiei B.

Cerința

Scrieți un program care citește numerele N și K, apoi determină:

1. dacă, înainte să fie mutate bile din cutia A în cutia B, există o bilă specială în cutia A; în caz afirmativ, programul determină numărul X cu care este numerotată această bilă specială;
2. cel mai mic (în sens lexicografic) șir strict crescător al numerelor celor K bile care pot fi mutate din cutia A în cutia B astfel încât bila cu numărul K să fie bila specială a cutiei B;
3. cel mai mare (în sens lexicografic) șir strict crescător al numerelor celor K bile care pot fi mutate din cutia A în cutia B astfel încât bila cu numărul K să fie bila specială a cutiei B.

Date de intrare

Fișierul de intrare bile4.in conține pe prima linie trei numere naturale C, N și K, separate prin câte un spațiu. C reprezintă cerința care trebuie rezolvată (1, 2 sau 3), iar N și K au semnificația din enunț.

Date de ieșire

Fișierul de ieșire bile4.out va conține:

• dacă C = 1, pe prima linie, numărul natural X reprezentând numârul bilei speciale din cutia A sau valoarea −1 dacă cutia A nu conține o astfel de bilă (reprezentând răspunsul la cerința 1);
• dacă C = 2, pe prima linie, un șir strict crescător de K numere naturale, separate prin câte un spațiu (reprezentând răspunsul la cerința 2);
• dacă C = 3, pe prima linie, un șir strict crescător de K numere naturale, separate prin câte un spațiu (reprezentând răspunsul la cerința 3).

Restricții și precizări

• 1 ≤ n ≤ 1000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
• N număr natural, 4 ≤ N ≤ 100000
• K număr natural, 2 ≤ K ≤ N/2
• Șirul y1, y2, . . . , yk este mai mic în sens lexicografic decât șirul z1, z2, . . . , zk dacă există un indice p, 1 ≤ p ≤ K, astfel încât:
  y1 = z1, y2 = z2, . . . , yp-1 = zp-1 și yp = zp
• Pentru cerința 1 se acordă 20p, iar pentru fiecare dintre cerințele 2 și 3 se acordă câte 40p.

Exemplul 1:

bile4.in

1 9 3

bile4.out

4

Explicație

Se rezolvă cerința 1.
N = 9. Avem 9 bile inscript, ionate cu 0, 1, 2, 3, 4, 5, 6, 7, 8.
Bila specială este X = 4 deoarece: X = (0 + 1 + 2 + 3 + 5 + 6 + 7 + 8)/8 = 32/8 = 4

Exemplul 2:

bile4.in

1 8 3

bile4.out

-1

Explicație

Se rezolvă cerința 1.
N = 8. Se va scrie în fișierul de ieșire valoarea −1 deoarece cutia A nu conține nicio bilă specială.

Exemplul 3:

bile4.in

2 8 3

bile4.out

0 2 7

Explicație

Se rezolvă cerința 2.
N = 8. Avem 8 bile inscripționate cu 0, 1, 2, 3, 4, 5, 6, 7.
Șirurile strict crescătoare ale numerelor bilelor care pot fi mutate în cutia B, lângă bila specială K = 3, sunt: 0, 2, 7 sau 0, 4, 5 sau 1, 2, 6, deoarece: 3 = (0 + 2 + 7)/3 = (0 + 4 + 5)/3 = (1 + 2 + 6)/3.
Cel mai mic șir în sens lexicografic, crescător, este: 0, 2, 7.

Exemplul 4:

bile4.in

3 8 3

bile4.out

1 2 6

Explicație

Se rezolvă cerința 3.
Șirurile strict crescătoare ale numerelor bilelor care pot fi mutate în cutia B, lângă bila specială K = 3, sunt: 0, 2, 7 sau 0, 4, 5 sau 1, 2, 6, deoarece: 3 = (0 + 2 + 7)/3 = (0 + 4 + 5)/3 = (1 + 2 + 6)/3.
Cel mai mare șir în sens lexicografic, crescător, este: 1, 2, 6.