Fişierul intrare/ieşire:	shuffle.in, shuffle.out	Sursă	Infoarena Monthly 2012, Runda 7
Autor	Tiberiu Savin	Adăugată de	Ionescu Vlad •vladii
Timp execuţie pe test	0.3 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Shuffle

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 cum va arata sirul de carti dupa K astfel de shuffleuri, asa ca sunteti obligati sa ii oferiti raspunsul!

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
}

Date de intrare

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.

Date de ieşire

Î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.

Restricţii si precizari

• 2 ≤ N ≤ 2 000 000
• 0 ≤ K ≤ 1 000 000 000
• 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.

Exemplu

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.

Cum se trimit solutii?