== include(page="template/taskheader" task_id="shuffle") ==
Poveste şi cerinţă...
Dupa ce a epuizat toate resursele financiare din tara sa, Victoria se gindeste sa pacaleasca aparatele de amestecat carti de joc din Las Vegas. Pe Masa Verde din casino se afla asezate in linie $N$ carti, numerotate in ordine de la stinga la dreapta (prima carte are valoarea $1$, ..., ultima carte are valoarea $N$). Aparatul de amestecat se aseaza in fata mesei si efectueaza $K$ shuffleuri. Un shuffle se efectueaza in modul urmator:
* la primul pas, aparatul ia prima jumatate a sirului de carti, iar a doua jumatate se muta la inceput (prima jumatate ramine intr-o zona rezervata speciala a masinii)
* la pasul doi, masina ia cea de-a doua jumatate din cartile pe care le are in zona rezervata si le pune la sfarsitul sirului de carti
* repeta pasul doi pina cind nu mai ramine nicio carte in zona rezervata.
Victoria se intreaba care este sirul de carti dupa $K$ astfel de shuffleuri, asa ca sunteti obligati sa ii oferiti raspunsul!
Pentru a evita fisierele de output foarte mari, sirul obtinut dupa $K$ shuffleuri va fi encodat folosind urmatorul algoritm:
== code(cpp) |
int encode(int N, int S[]) {
// N = numarul de carti din sir
// S[i] = cartea care se afla pe pozitia i, (1 <= i <= N)
int ret = 0;
for(int i=1; i<=N; i++) {
ret = (ret * 13 + S[i]) % 1299827;
}
return ret; // variabila ret va trebui afisata in fisierul de output
}
==
h2. Date de intrare
Fişierul de intrare $shuffle.in$ ...
Fişierul de intrare $shuffle.in$ contine pe prima linie, separate prin cate un spatiu, doua numere naturale $N$ si $K$, reprezentind numarul de carti aflate pe masa, respectiv numarul de shuffleuri efectuate.
h2. Date de ieşire
În fişierul de ieşire $shuffle.out$ ...
În fişierul de ieşire $shuffle.out$ se va afla pe prima linie un singur numar natural reprezentind sirul de carti de pe masa dupa $K$ shuffleuri, encodat dupa algoritmul prezentat in enunt.
h2. Restricţii
h2. Restricţii si precizari
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 2 000 000$
* $0 ≤ K ≤ 10^18^$
* Shuffleul numarul $i$ se efectueaza asupra sirului de carti obtinut in urma primelor $i-1$ shuffleuri, pentru orice $i$ nenul
* Daca un sir de elemente are lungimea $P$, atunci prima jumatate a sirului este reprezentata de primele $[P/2]$ elemente din sir (posibil $0$), restul elementelor constituind cea de-a doua jumatate (adica urmatoarele $P - [P/2]$ elemente)
* $[x]$, unde $x$ este un numar real semnifica partea intreaga a numarului $x$
* Algoritmul de encodare a sirului nu prezinta nicio particularitate ce ar putea influenta rezolvarea problemei.
h2. Exemplu
table(example). |_. shuffle.in |_. shuffle.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7 2
| 823554
|
h3. Explicaţie
...
Initial pe masa se afla sirul de carti $1 2 3 4 5 6 7$. Se efectueaza primul shuffle:
- cea de-a doua jumatate a sirului se muta la inceput, iar prima jumatate se salveaza in zona rezervata. Pe masa vom avea: $4 5 6 7$, iar in zona rezervata: $1 2 3$. A doua jumatate din zona rezervata se muta la sfarsitul sirului, deci pe masa vom avea: $4 5 6 7 2 3$, iar in zona rezervata $1$. A doua jumatate din zona rezervata se muta la sfarsitul sirului, deci pe masa vom avea: $4 5 6 7 2 3 1$, iar in zona rezervata nu vom mai avea nicio carte, deci primul shuffle se termina.
Pe masa se afla sirul $4 5 6 7 2 3 1$ si se incepe efectuarea celui de-al doilea shuffle:
- cea de-a doua jumatate a sirului se muta la inceput, iar prima jumatate se salveaza in zona rezervata. Pe masa vom avea: $7 2 3 1$, iar in zona rezervata: $4 5 6$. A doua jumatate din zona rezervata se muta la sfarsitul sirului, deci pe masa vom avea: $7 2 3 1 5 6$, iar in zona rezervata $4$. A doua jumatate din zona rezervata se muta la sfarsitul sirului, deci pe masa vom avea: $7 2 3 1 5 6 4$, iar in zona rezervata nu vom mai avea nicio carte, deci al doilea shuffle se termina.
Pe masa, la final, se afla sirul $7 2 3 1 5 6 4$, care encodat devine: $823554$.
== include(page="template/taskfooter" task_id="shuffle") ==
