Zadanie

V jednej malej dedinke, nazývanej Štvorečkovo, žila mačka Micka s jej mačiatkom Cickou. Cicka ešte nevie, ako Štvorečkovo vyzerá, tak Micka s ňou chodí každý deň na krátku obchádzku po dedinke. Ľudia v Štvorčekove bývajú v kockatých domoch so štvorčekovým pozemkom a Micka ich rada navštevuje. Micka s Cickou rady chodia po susedoch a stretávajú známe tváre. Vždy sa ale vrátia domov, kde si po prechádzke dajú poriadnu siestu. Raz sa Micka dala viesť, aby vyskúšala, ako sa Cicka naučila chodiť po dedine. Po tejto prechádzke chce Micka povedať Cicke koľko krokov spravila zle, ale nevie koľko. Pomôž Micke nájsť, koľko krokov spravila Cicka zle.

Úloha

Máme nekonečnú štvorčekovú mapu a vieme sa pohybovať po nej zvislo a vodorovne. Dostaneme záznam cesty, ktorou Cicka šla po dedinke. Jeden znak reprezentuje posun na mape o jeden štvorček. Cicka sa chcela vrátiť do bodu, v ktorom začínala, ale niekoľkokrát sa pomýlila. Zistite, koľko najmenejkrát sa mohla Cicka na svojej predchádzke pomýliť. Môžete predpokladať, že Cicka spravila párny počet krokov.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 10^6\)) dĺžku cesty mačiatka. V druhom riadku vstupu je popis cesty - reťazec dĺžky \(n\) skladajúci sa so znakov L, P, H a D (doľava, doprava, hore a dole).

Pre jednotlivé sady platia takéto obmedzenia:

Sada 1 2 3 4
\(1 \leq n \leq\) \(100\) \(10\,000\) \(100\,000\) \(1\,000\,000\)

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo, ktoré znázorňuje najmenší počet chýb v prechadzke.

Príklady

Input:

6
DDLLHH

Output:

1

Pre tento prípad, ak by sme chceli sa vrátiť na pôvodné miesto, tak namiesto jedného kroku doľava by sme mali ísť doprava.

Input:

8
DDLLHHPP

Output:

0

Urobili sme jeden okruh a vrátili sme sa naspäť, odkiaľ sme začali.

Pre naše riešenie sa najprv musíme pozrieť na prípad, kedy prídeme odkiaľ sme priśli. To dovŕšime iba tým, že sa posunieme rovnako hore-dole a doprava-dolava. Súradnice si môžeme zapisovať do dvoch premennych \(x,y\) korešpondujúce s dannými osami a pre jednoduchosť výpočtu začnime na súradnici \(x=0,y=0\).

Kroky môžeme hodnotiť následovne:

  1. H=y+1
  2. D=y-1
  3. P=x+1
  4. L=x-1

Zaujímavá myšlienka

Musíme zadefinovať vzdialenosť od začiatočného bodu. Bude to je súčet absolútnych hodnôt našich súradnic (\(|x| + |y|\)). Napríklad by sme mali cestu “DP”. Vzdialenosť od začiatku by bola 2, lebo \(|1|+|-1|=2\). Nemusíme kontrolovať a počitať kombinácie možností, kde sme sa mohli pomýliť (to by sme sa zbytočne narobili). Keď v ceste urobíme nejakú chybu a zle zabočíme, tak na konci cesty budeme nejako vzdialený od začiatku.

Zamyslime sa nad tým, že čo ak by sme spravili nejaký krok zle. Jedna vec je istá a to, že sme sa nepriblížili ku koncu o jendo políčko, ćiže sme ho “stratili” a pripočíta sa ku vzdialenosti od začiatku. Druhá vec je, že sa ešte vzdialime od začiatku o jedno políčko iným smerom ako ku koncu a pripočíta sa k vzdialenosti od začiatku.

Optimálne riešenie

Z tohto uváženia nám vyplýva, že keď spravíme zlý krok, tak sa náš koncový bod vzdiali o 2 políčka od začiatočného bodu. Čiže celkový počet zlých krokov vypočítame ako vzdialenosť od začiatku predelenú 2 (\(\frac{(|x|+|y|)}{2}\)).

Takéto riešenie bude mať časovú zložitosť \(O(n)\) a pamäťovú zložitosť \(O(n)\)

n = int(input())
x = y = 0

for c in input():
    if c == "H":
        y += 1
    elif c == "D":
        y -= 1
    elif c == "L":
        x -= 1
    elif c == "P":
        x += 1

print((abs(x) + abs(y)) // 2)
#include "iostream"
using namespace std;

int main() {
    int n, x = 0, y = 0;
    char character;

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> character;
        switch (character) {
            case 'H':
                y++;
                break;
            case 'D':
                y--;
                break;
            case 'L':
                x--;
                break;
            case 'P':
                x++;
                break;
            default:
                continue;
        }
    }

    cout << (abs(x) + abs(y)) / 2 << endl;
}

Ale pamäťovú zložitosť dokážeme zmenšiť na \(O(1)\), lebo si nepotrebujeme pamätať celú cestu naraz, stačí nám poznať iba jednotlivé znaky.

import sys

n = int(input())
x = y = 0

for i in range(n):
    c = sys.stdin.read(1)
    if c == "H":
        y += 1
    elif c == "D":
        y -= 1
    elif c == "L":
        x -= 1
    elif c == "P":
        x += 1

print((abs(x) + abs(y)) // 2)
#include "iostream"
using namespace std;

int main() {
    int n, x = 0, y = 0;
    char character;

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> character;
        switch (character) {
            case 'H':
                y++;
                break;
            case 'D':
                y--;
                break;
            case 'L':
                x--;
                break;
            case 'P':
                x++;
                break;
            default:
                continue;
        }
    }

    cout << (abs(x) + abs(y)) / 2 << endl;
}

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