# PBinfo #3747 – Bile4 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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ă:

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ă;
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;
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.

## Cod sursă C++

```cpp
/** Diana
	complexitate timp: O(K)
	memorie suplimentară: O(K)
**/
#include <fstream>
using namespace std;
ifstream fin("bile4.in");
ofstream fout("bile4.out");
const int NMAX = 100000;
const int KMAX = NMAX / 2;
int C, N, K;
int s[KMAX];
void scrie() {
	for (int i = 0; i < K; i++)
		fout << s[i] << ' ';
	fout << '\n';
}
// numărul X al bilei speciale din cutia A
void c1() {
	if (N % 2 == 1) fout << (N - 1) / 2 << '\n';
	else fout << -1 << '\n';
}
// cel mai mic șir lexicografic
void c2() {
	long long K_patrat = (long long)K * (long long)K;
	long long S = 0;
	for (int i = 0; i < K - 1; i++) {
		s[i] = i;
		S += s[i];
	}
	if (K_patrat - S <= N - 1) {
		s[K - 1] = K_patrat - S;
		scrie();
		return;
	}
	s[K - 1] = K - 1;
	S += s[K - 1];
	int dif = K_patrat - S;
	int g = dif / (N - K);
	int rest = dif % (N - K);
	for (int i = 1; i <= g; i++)
		s[K - i] += (N - K);
	if (s[K - (g + 1)] + rest != K)
		s[K - (g + 1)] += rest;
	else {
		s[K - (g + 1)] += (rest + 1);
		s[K - g] -= 1;
	}
	scrie();
}
void c3() {
	if (K % 2 == 0) {
		// K par
		int m = K / 2;
		for (int i = 0; i < K; ++i) {
			s[i] = m;
			++m;
			if (m == K) ++m;
		}
		scrie();
		return;
	}
	// K impar
	int M = K / 2;
	s[0] = M;
	s[K - 1] = 2 * K + 1 - s[0];
	s[M] = K - 1;
	for (int i = 1, j = K - 2; i < M; ++i, --j) {
		s[i] = M + i;
		s[j] = 2 * K - s[i];
	}
	scrie();
}
int main() {
	fin >> C >> N >> K;
	if (C == 1) c1();
	else if (C == 2) c2();
	else if (C == 3) c3();
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3747)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3747/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3747/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)