Zadanie

Žaba má zázračné karty. Aspoň to tak tvrdí. V skutočnosti má úplne obyčajný balíček kariet, s ktorými robí všakovaké triky. Minule stretol Kozzu a jeden takýto trik mu predviedol. Karty premiešal, balíček párkrát prevrátil hore nohami, znovu premiešal… A na koniec Kozzu ohúril tým, že vedel presne povedať poradie, v akom karty sú. Kozza bol úplne nadšený. Hneď chcel, aby ho Žaba trik s kartami naučil. Žaba mu teda prezradil tajomstvo svojho úspechu: totiž, že na začiatku vedel, v akom poradí karty sú a keď ich miešal, vždy len zobral kartu zvrchu a dal ju na spodok, alebo zobral kartu zospodu a dal ju navrch, alebo celú kopu otočil hore nohami. Ako ale vedel tak rýchlo povedať, ako bude vyzerať finálne poradie? To si teraz naprogramujete!

Úloha

Každá karta je označená nejakým (nie nutne jedinečným) prirodzeným číslom. Máte zadaných \(n\) kariet, v poradí, v akom boli na začiatku v kope kariet, od spodku po vrch. Ďalej máme zadanú postupnosť \(q\) krokov: D – zoberieme kartu z vrchu kopy a presunieme ju dole, H – zoberieme kartu zospodu kopy a presunieme ju hore, a R – otočenie kopy (reverz). Pre dané poradie kariet na začiatku a postupnosť krokov zistite, v akom poradí budú karty na konci.

Formát vstupu

Na prvom riadku vstupu sú čísla \(n\) (\(1 \leq n \leq 1\,000\,000\)) a \(q\) (\(1 \leq q \leq 1\,000\,000\)) oddelené medzerou – počet kariet v kope a počet krokov miešania. Na ďalšom riadku je \(n\) medzerami oddelených čísel – čísla kariet v poradí, v akom boli na začiatku v kope od spodku po vrch. Čísla nepresiahnu \(1\,000\,000\) a môžu sa opakovať. Nasleduje riadok s \(q\) znakmi oddelenými medzerami. Každý znak popisuje jeden krok miešania – D (presun dole), H (presun hore) a R (reverz kopy).

Formát výstupu

Na výstup vypíšte \(n\) čísel – čísla kariet v poradí, v akom budú karty na konci triku v kope, odspodu po vrch.

Príklad

Input:

5 4
7 8 9 1 2
D D H R

Output:

1 9 8 7 2

Vykonávaním jednotlivých krokov sa bude poradie kariet v kope meniť nasledovne: \(7 8 9 1 2 \rightarrow 2 7 8 9 1 \rightarrow 1 2 7 8 9 \rightarrow 2 7 8 9 1 \rightarrow 1 9 8 7 2\)

Input:

3 7
1 2 3
R D D R H H R

Output:

1 3 2

Na začiatok je dôležité si všimnúť niekoľko vecí. Prvé pozorovanie je, že keď \(x\) kariet presunieme na vrch a potom \(x\) kariet presunieme na spodok, budú v rovnakom poradí, ako na začiatku. Podobne môžeme vidieť, že ak presunieme \(n\) kariet jedným smerom, budú opäť všetky na pôvodnom mieste.

Predstavme si, že karty rozložíme do kruhu a medzi vrchnú a spodnú kartu vložíme zarážku tak, aby vrchná karta bola napravo od zarážky. Čo sa stane, ak presunieme vrchnú kartu na spodok balíčka a opäť ich rozložíme do kruhu? Jediné, čo sa zmení je pozícia zarážky, ktorá bude mať naľavo od seba vrchnú kartu, ktorá sa posunula a napravo bude druhá karta zvrchu. To znamená, že zarážka sa nám po kruhu posunula o jedno miesto doprava. A samozrejme, presunutie spodnej karty navrch je len posunutie zarážky o jedno miesto doľava.

Ak teda iba presúvame karty zvrchu naspodok a naopak, stačí si pamätať, kam sme presunuli našu zarážku. A keď máme následne vypísať aktuálny stav balíčka, tak pôjdeme postupne po kruhu kariet, pričom začínať budeme na karte napravo od zarážky (aktuálna vrchná karta) až kým nenarazíme opäť na zarážku.

Čo sa ale stane ak otočíme celý balíček? Vrchná karta bude zrazu naľavo od zarážky, kým spodná bude napravo. Samotné usporiadanie kariet sa teda nezmenilo a dokonca ani zarážka sa neposunula, iba sa zmenila strana, na ktorej je vrchná karta. Je jasné, že ak v takomto stave budeme presúvať vrchnú kartu naspodok, zarážka sa posunie o jedno miesto doľava. Takisto výsledok sa bude vypisovať v opačnom smere ako predtým, lebo vrchná karta je na opačnej strane zarážky.

A ako to naprogramujeme? Budeme si pamätať dve premenné. Premenná \(reverz\) určuje, na ktorej strane od zarážky sa nachádza vrchná karta. Premenná \(zarazka\) potom hovorí pozíciu zarážky v našom kruhu. My ale nemáme kruh, iba obyčajné pole. To nevadí. Hodnota \(zarazka=0\) bude znamenať, že zarážka sa nachádza medzi prvou a \(n\)-tou kartou balíčka. \(zarazka=1\) znamená, že zarážka je medzi prvou a druhou kartou atď. Ak teda budeme musieť otočiť balíček, jednoducho upravíme hodnotu \(reverz\) a keď budeme musieť presunúť kartu, tak podľa hodnoty \(reverz\) zmeníme hodnotu \(zarazka\) – ak je vrchná karta napravo od zarážky a presúvame túto kartu naspodok, k hodnote \(zarazka\) pričítame číslo 1, ak je vrchná karta naľavo, tak k hodnote \(zarazka\) pričítame \(-1\). A naopak pri presúvaní spodnej karty.

Samozrejme, môže sa nám stať, že hodnota \(zarazka\) bude záporná, alebo privysoká. Vtedy však využijeme naše prvé pozorovanie – ak posunieme \(n\) kariet jedným smerom, dostaneme rovnakú situáciu. To znamená, že k hodnote \(zarazka\) môžeme kedykoľvek pričítať alebo odčítať číslo \(n\) bez toho, aby sme zmenili situáciu, ktorú popisujeme. Vďaka tomu bude hodnota \(zarazka\) vždy v intervale \(0\)\(n-1\).

Nakoniec, keď budeme chcieť vypísať výsledok, tak si z hodnôt \(reverz\) a \(zarazka\) zistíme, kde sa nachádza vrchná karta a v správnom smere (závislom od \(reverz\)) vypíšeme postupne všetky čísla. Časová aj pamäťová zložitosť bude lineárna od \(n\), čo zapíšeme ako \(O(n)\).

#include<bits/stdc++.h>

using namespace std;

int main() {
  int n, q;
  cin >> n >> q;
  vector<int> karty(n);
  for(int i = 0; i < n; i++) {
    cin >> karty [i];
  }

  char op;
  int reverz = 1, zarazka = 0;
  for(int i = 0; i < q; i++) {
    cin >> op;
    if (op == 'D')
      zarazka -= reverz;
    else if (op == 'H')
      zarazka += reverz;
    else if (op == 'R')
        reverz *= -1;
  }

  if (reverz == -1) {
    reverse(karty.begin(), karty.end());
    zarazka *= -1;
  }
  
  zarazka = ((zarazka % n) + n) % n;
  
  for (int i = zarazka; i < n; i++) 
    printf("%d%c", karty[i], (zarazka==0 && i==n-1) ? '\n' : ' ');
    
  for (int i = 0; i < zarazka; i++)
    printf("%d%c", karty[i], (i == zarazka-1) ? '\n' : ' ');
}
n, q = map(int, input().split())
karty = input().split()
kroky = input().split()

zarazka, reverz = 0, 1

for k in kroky:
    if k == 'D':
        zarazka -= reverz
    if k == 'H':
        zarazka += reverz
    if k == 'R':
        reverz = -reverz

if reverz == -1:
    karty = list(reversed(karty))
    zarazka = -zarazka

zarazka = ((zarazka % n) + n) % n

print(" ".join(karty[zarazka:] + karty[:zarazka]))

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.