Fișierul intrare/ieșire uniform.in, uniform.out Sursă Concurs IQ Academy clasa a 7-a
Autor Matteo Verzotti Adăugată de avatar Matteoalexandru Matteo.Verz Matteoalexandru
Timp de execuție pe test 0.3 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Uniform (clasa a 7-a)

Costel este un copil cu niște trăsături mai ciudate... el vrea ca totul să fie perfect și uniform în viața lui, dar nu vrea să facă prea multe pentru asta. Acesta a primit de ziua lui un set de cuburi, care pot fi așezate unul peste altul. Sora acestuia, Mirela, s-a jucat cu cadoul lui Costel și a format N turnuri de înălțimi diferite. Costel s-a enervat, deoarece el vrea ca turnurile lui să fie uniforme, adică să aibă aceeași înălțime. De aceea, s-a apucat să mute cuburi de la un turn la altul, astfel încât toate turnurile vor fi uniforme. La final, dacă rămân cuburi în plus, el le va pune înapoi în cutie. Totuși, Costel este leneș și nu vrea să mute în total mai mult de K cuburi de la un turn la altul. De asemenea, cu cât un turn este mai înalt, cu atât este mai instabil. Costel nu vrea să riște să i se dărâme turnurile, așa că a luat o măsură de precauție: va muta cuburile dintr-un turn în altul dacă și numai dacă înălțimea turnului din care mută este strict mai mare decât înălțimea turnului în care mută. Cu alte cuvinte, dacă înălțimea turnului i este Hi și înălțimea turnului j este Hj, atunci Costel mută un cub din turnul i în turnul j dacă și numai dacă Hi > Hj.
Numim o secvență aproape-uniformă de înălțime X o secvență în care strict mai mult de jumătate din turnuri au cel puțin înălțimea X.

De exemplu, pentru N = 7, K = 4, iar înălțimile turnurilor {6, 4, 2, 7, 3, 5, 4}, avem:

  • În Figura 1 se află configurația inițială a turnurilor, realizată de Mirela.
  • În Figura 2 se află o secvență aproape-uniformă de înălțime 5. Aceasta poate fi obținută din configurația inițială prin mutarea unui cub din turnul 4 în turnul 2. Acesta nu este singurul exemplu, de pildă, ar mai putea muta un cub din turnul 1 în turnul 2 pentru același rezultat.
  • În Figura 3 se află o secvență uniformă de înălțime 4. Aceasta poate fi obținută din configurația inițială prin mutarea a 2 cuburi din turnul 4 în turnul 3 și a unui cub din turnul 1 în turnul 5.

Cerință

Costel dorește să afle 2 lucruri:
1. Care este înălțimea maximă a unei secvențe aproape-uniformă, mutând în total maxim K cuburi de la un turn la altul, și numărul minim de cuburi care trebuie mutate.
2. Care este înălțimea maximă pe care o pot avea turnurile uniforme, mutând în total maxim K cuburi de la un turn la altul, și numărul minim de cuburi care trebuie mutate.

Date de intrare

Fișierul de intrare uniform.in va conține pe prima linie numărul natural P, reprezentând cerința care trebuie rezolvată (1 sau 2). Pe următoarea linie se află numerele naturale N și K cu semnificația din enunț. Pe a treia linie se află N numere naturale, reprezentând înălțimile turnurilor după ce Mirela s-a jucat cu setul de cuburi al lui Costel.

Date de ieșire

Dacă cerința este 1, pe prima linie a fișierului de ieșire uniform.out se vor afla 2 numere, separate printr-un spațiu, reprezentând înălțimea maximă a unei secvențe aproape-uniformă și numărul minim de cuburi ce trebuie mutate pentru a se forma o astfel de secvență de înălțime maximă.
Dacă cerința este 2, pe prima linie a fișierului de ieșire uniform.out se va afla 2 numere, separate printr-un spațiu, reprezentând înălțimea maximă a unei secvențe uniforme și numărul minim de cuburi ce trebuie mutate pentru a se forma o astfel de secvență de înălțime maximă.

Restricții

  • 1 ≤ N ≤ 105
  • 1 ≤ K ≤ 1011
  • 1 ≤ înălțimea maximă inițială a unui turn ≤ 106
  • Se acordă 60p pentru prima cerință și 40p pentru a doua cerință

Exemplu

uniform.in uniform.out
1
7 4
6 4 2 7 3 5 4
5 1
2
7 4
6 4 2 7 3 5 4
4 3

Explicație

Exemplele aparțin figurilor de mai sus.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii