Fişierul intrare/ieşire:shuffle.in, shuffle.outSursăInfoarena Monthly 2012, Runda 7
AutorTiberiu SavinAdăugată devladiiIonescu Vlad vladii
Timp execuţie pe test0.6 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultateN/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 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:

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 ≤ 1018
  • 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

shuffle.inshuffle.out
7 2
823554

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content