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

Poveste şi cerinţă...

După ce a primit de la Simonet, profesorul său de studii sociale, tema pentru proiect, tânărului Trevor i-a venit ideea jocului ”Pay it forward”. Pentru cei care nu ştiu acest joc, el constă în ajutarea de către Trevor a oamenilor aflaţi la ananghie. Aceştia la rândul lor vor ajuta alţi oameni şi aşa mai departe.
Fiecare participant (inclusiv Trevor) trebuie să realizeze câte $k$ fapte bune prin care să ajute oamenii. Vârstnicii şi tinerii îşi îndeplinesc în mod diferit această sarcină. Vârstnicii au nevoie de $zv$ zile pentru a introduce în joc o altă persoană, iar tinerii au nevoie de $zt$ zile. Astfel dacă un vârstnic, respectiv un tânăr, intră în joc în ziua $i$, el va introduce la rândul lui în joc prima persoană în ziua $i+zv$, respectiv în ziua $i+zt$ tânărul, a doua persoană în ziua $i+2*zv$, respectiv în ziua $i+2*zt$ tânărul şi aşa mai departe. Astfel numărul de persoane care participă la joc poate fi diferit în funcţie de cum sunt alese persoanele vârstnice şi cele tinere. Trevor doreşte ca în joc să fie realizate în total cât mai multe fapte bune, dar fiecare participant să aducă în joc maximum $(k+1)/2$ tineri şi maximum $(k+1)/2$ vârstnici. Participanţii pot aduce mai puţine persoane de un anumit tip, dar nu au voie să depăşească numărul de $(k+1)/2$ persoane de acelaşi tip.
 
h2. Cerinţe
 
Care este numărul $fb$ de fapte bune care mai sunt de realizat, după trecerea a $n$ zile, de către persoanele intrate deja în joc, astfel încât numărul total de fapte bune aşteptate (şi cele realizate şi cele nerealizate) să fie maxim?\

h2. Date de intrare

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

Fişierul de intrare $pif.in$ conţine pe prima linie numărul natural $n$, pe a doua linie numărul $k$ şi pe a treia linie numerele $zv$ şi $zt$ separate printr-un spaţiu.

h2. Date de ieşire

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

În fişierul de ieşire $pif.out$ se va scrie restul împărţirii lui $fb$, cu semnificaţia din enunţ, la $1234567$ ($fb modulo 1234567$).\

h2. Restricţii

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

* $1 ≤ n ≤ 10^6^$
* $1 ≤ k, zt, zv ≤ n$
* Pentru teste în valoare de $30$ de puncte $fb ≤ 106$
* Pentru teste în valoare de $30$ de puncte $zv = zt = 1$
* Pentru teste în valoare de $20$ de puncte $zv = zt ≠ 1$
* Pentru teste în valoare de $70$ de puncte $k*n ≤ 106$
 
Exemplu
pif.in
pif.out
Explicaţie
4
2
1 2
7
n=4, k=2, zv=1, zt=2
Avem 16 moduri posibile în care se pot alege persoanele vârstnice şi tinere .
Dintre ele doar 5 respectă condiţia ca numărul vârstnicilor şi al tinerilor să fie maxim 1. Dintre cele 5 doar două obţin un număr maxim de fapte bune aşteptate.
Notăm cu T pe Trevor, cu Vn persoanele vârstnice şi cu Tn persoanele tinere.
Unul dintre cele 2 cazuri cu număr maxim de fapte bune este următorul:
Ziua
Persoane datoare să ajute
Persoane ajutate
Explicaţie
0
T
-
T începe jocul (intră în joc)
1
T
-
T nu ajută pe nimeni (nu au trecut 2 zile)
2
T
V1
T ajută V1
3
T
-
T nu ajută pe nimeni (nu au trecut 4 zile)
V1
V2
V1 ajută V2
4
T
T1
T ajută T1
V1
T2
V1 ajută T2
V2
V3
V2 ajută V3
Ministerul Educaţiei Naţionale
Centrul Naţional de Evaluare şi Examinare
Etapa judeţeană/sectoarelor municipiului Bucureşti a olimpiadelor naţionale şcolare 9 martie 2019
INFORMATICĂ Clasa a X-a
Toate subiectele sunt obligatorii. Timpul de lucru efectiv alocat probei este de 4 ore.
Punctajul maxim cumulat este de 300 de puncte, dintre care 30 de puncte sunt acordate din oficiu.
pif.in
pif.out
Explicaţie
În zilele următoare:
V2 ar trebui să mai ajute încă un tânăr.
V3 ar trebui să mai ajute încă două persoane, un tânăr şi un vârstnic.
T1 ar trebui să mai ajute încă două persoane, un tânăr şi un vârstnic.
T2 ar trebui să mai ajute încă două persoane, un tânăr şi un vârstnic.
Deci au mai rămas 7 fapte bune de realizat.
Celălalt caz cu număr maxim de fapte bune este următorul:
Ziua
Persoane datoare să ajute
Persoane ajutate
Explicaţie
0
T
-
T începe jocul (intră în joc)
1
T
-
T nu ajută pe nimeni (nu au trecut 2 zile)
2
T
V1
T ajută V1
3
T
-
T nu ajută pe nimeni (nu au trecut 4 zile)
V1
V2
V1 ajută V2
4
T
T1
T ajută T1
V1
T2
V1 ajută T2
V2
T3
V2 ajută T3
În zilele următoare:
V2 ar trebui să mai ajute încă un tânăr.
T1 ar trebui să mai ajute încă două persoane, un tânăr şi un vârstnic.
T2 ar trebui să mai ajute încă două persoane, un tânăr şi un vârstnic.
T3 ar trebui să mai ajute încă două persoane, un tânăr şi un vârstnic.
În total au mai rămas 7 fapte bune de realizat.
Timp maxim de executare/test: 1 sec
Memorie total 64 MB din care pentru stivă 8 MB
Dimensiune maximă a sursei: 15 KB
Sursa: pif.cpp, pif.c sau pif.pas va fi salvată în folderul care are drept nume ID-ul tău.

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