5. Zázračné karty vzorové riešenie

5 4
7 8 9 1 2
D D H R

1 9 8 7 2

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

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 si 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\) až \(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]))