Diferente pentru problema/mostenire3 intre reviziile #1 si #8

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="mostenire3") ==

Poveste şi cerinţă...

Împăratul cel bătrân vrea să împartă sacii cu galbeni din vistieria palatului celor $K$ feciori ai săi, numerotați de la $1$ la $K$ în ordinea vârstei. Feciorul cu numărul $1$ este cel mai mare, iar mezinul are numărul $K$.
În vistierie sunt $N$ saci plini cu galbeni, așezați în linie, atât de grei încât nu li se poate schimba ordinea, iar pe fiecare sac este scris numărul de galbeni pe care îi conține.
Împăratul îl cheamă pe unul dintre feciori și îi spune: “Fiule, a ta este averea primilor $x{~1~}$ saci!”. Feciorul ia sacii și pleacă fericit. Apoi, împăratul cheamă alt fecior și îi spune: “Fiule, a ta este averea primilor $x{~2~}$ saci dintre cei rămași!”. Și așa mai departe, până ajunge la ultimul fecior chemat, căruia îi dă toți sacii rămași.
El nu are o ordine anume în care își cheamă feciorii dar are grijă să cheme fiecare fecior exact o dată. Totodată, pentru a evita certurile între ei, este atent ca fiecare fecior să primească cel puțin un sac cu galbeni, dar să **NU** primească în total mai mulți galbeni ca un frate mai mare decât el. Cel mai mic dintre feciorii împăratului este și cel mai viteaz, așa că împăratul ar vrea să îi dea lui o sumă de bani cât mai mare, fără a-i supăra pe ceilalți feciori ai săi.
Cum ar putea împărți împăratul sacii?

h2. Date de intrare

Fişierul de intrare $mostenire3.in$ ...

Fișierul de intrare $mostenire3.in$ conține pe prima linie numerele naturale $N$, $K$, separate de un spațiu, cu semnificația din enunț. Pe următoarele $N$ linii se găsește câte un număr natural, reprezentând numărul de galbeni din fiecare sac, în ordinea în care aceștia urmează să fie distribuiți fiilor.

h2. Date de ieşire

h2. Date de ieșire

În fişierul de ieşire $mostenire3.out$ ...

Fișierul de ieșire mostenire3.out va conține pe prima linie suma de galbeni pe care o va primi fiul cel mic de la împărat. Pe următoarele $K$ linii se vor afla câte două numere naturale ce reprezintă numărul de ordine al feciorului, respectiv numărul de saci xi pe care îi primește acesta, în ordinea în care au fost chemați de împărat.

h2. Restricţii

h2. Restricții și precizări

* $... &le; ... &le; ...$

* $2 ≤ K ≤ 100$
* $K ≤ N ≤ 100000$
* $1 ≤ Numărul de galbeni din fiecare sac ≤ 100000$
* Galbenii din oricare dintre saci nu pot fi împărțiți mai multor frați
* Numărul total de galbeni aflați în vistierie este mai mic sau egal cu $10^9^$
* Împăratul cel bătrân nu are doi feciori cu aceeași vârstă
* Puteți afișa orice soluție în care mezinul primește numărul maxim posibil de galbeni
* Pentru fiecare test, afișarea corectă a numărului maxim de galbeni primiți de mezin este notată cu $40%$ din punctajul alocat testului
* Pentru teste valorând $10$ puncte $N = K, N ≤ 100$
* Pentru teste valorând $30$ de puncte $2 ≤ K < N ≤ 15$
* Pentru teste valorând $50$ de puncte $2 ≤ K < N ≤ 100$
* $10$ puncte sunt din oficiu. Ele corespund unor teste egale cu primul exemplul.
 
h2. Exemple
 
table(example).
|_. mostenire3.in
|_. mostenire3.out
|_. Explicație
|
| 8 3
1
2
3
4
5
6
7
8
| 10
3 4
2 2
1 2
| Fiul cel mic este chemat primul și ia primii 4 saci, primind astfel 1+2+3+4=10 galbeni.
Fiul cel mijlociu este chemat al doilea și ia următorii 2 saci, primind astfel 5+6=11 galbeni.
Fiul cel mare este chemat ultimul și ia restul de 2 saci, primind astfel 7+8=15 galbeni.
|
| 12 4
10
5
23
1
20
4
10
12
6
23
18
17
| 35
2 3
4 4
1 3
3 2
| Al doilea fiu în ordinea vârstei este chemat primul și ia primii 3 saci, primind astfel 10+5+23=38 de galbeni.
Fiul cel mic este chemat al doilea și ia următorii 4 saci, primind astfel 1+20+4+10=35 de galbeni.
Fiul cel mare este chemat al treilea și ia următorii 3 saci, primind astfel 12+6+23=41 de galbeni.
Al treilea fiu în ordinea vârstei este chemat ultimul și ia restul de 2 saci, primind astfel 18+17=35 de galbeni.
O altă soluție corectă este:
35 23 34 13 42
|

h2. Exemplu
 
table(example). |_. mostenire3.in |_. mostenire3.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="mostenire3") ==

infoarena informatica de performanta

Diferente pentru problema/mostenire3 intre reviziile #1 si #8

Nu exista diferente intre titluri.

Diferente intre continut:

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.