1. Dalo by sa?! vzorové riešenie

><><

4

<=>

0

>>=<><

5

>>><><<><<>>==<>==<><<>><><>=><=

26

Našou úlohou bolo spočítať počet zrážok, ktoré nastanú. Vieme, že za zrážku sa ráta všetko, kde idúce auto narazí do niečoho. Vieme tiež, že všetky autá po zrážke ostanú stáť.

Pomalé riešenie

Prvou možnosťou je pre každé auto, ktoré sa niektorým smerom hýbe (doprava alebo doľava) sa pozrieť, či má do čoho naraziť. Naraziť má do čoho vtedy, keď sa tým smerom, ktorým sa hýbe, nachádza auto, ktoré stojí, alebo smeruje opačne. Takže pre každé auto sa pozrieme, či má do čoho naraziť a spočítame tieto zrážky.

Pre každé auto (ktorých je \(n\)), pozrieme prinajhoršom všetky ostatné autá (ktorých je \(n\)), takže spolu urobíme \(O(n^2)\) operácií.

Časová zložitosť je \(O(n^2)\), a pamäťová \(O(n)\), lebo okrem vstupného poľa si nič nemusíme pamätať.

auta = input()

zrazky = 0

for i in range(len(auta)):
	if auta[i]=='>':
		for j in range(i+1, len(auta)):
			if auta[j]!='>':
				zrazky+=1
				break
	elif auta[i]=='<':
		for j in range(i-1, -1, -1):
			if auta[j]!='<':
				zrazky+=1
				break

print(zrazky)

#include<iostream>
#include<string>

using namespace std;

int main(){
	string auta;
	cin >> auta;
	
	long long zaciatok, koniec, zrazky=0;
	
	for(long long i=0; i<=auta.size(); i++){
        int smer = 0;
        if(auta[i]=='<')
            smer = -1;
        if(auta[i]=='>')
            smer = 1;
        
        long long j=i+smer;
        while(smer!=0 && j>=0 && j<auta.size()){
            if(auta[i]!=auta[j]){
                zrazky++;
                break;
            }
            j += smer;
        }
	}
	
	cout<<zrazky<<endl;
	
	return 0;
}

Vzorové riešenie

Je pomerne jasné, že ak auto, ktoré je na ľavej strane, smeruje doľava, tak do ničho nenarazí. Rovnako je to aj na pravej strane s autom, ktoré smeruje doprava. Môžeme si uvedomiť, že to ale neplatí len pre autá, ktoré sú úplne na kraji, ale aj pre všetky autá, ktoré sú naľavo (tým myslíme také, že naľavo od nich sú len autá, ktoré smerujú doľava), a smerujú doľava. Analogicky to platí aj pre autá, ktoré sú napravo. Napríklad, ak máme autá:

<<<>=<>>

Tak vieme povedať, že ľavé 3 autá a pravé 2 autá určite do ničoho nenarazia, iba pekne za sebou odídu preč.

To znamená, že nás nezaujíma súvislý úsek áut, ktoré sú naľavo a smerujú doľava, a súvislý úsek áut napravo, ktoré smerujú doprava.

Z nášho príkladu vyššie nás teda zaujímajú iba tieto autá:

>=<

Čo vieme povedať, o zrážkach, ktoré nastanú v tejto strednej časti?

Vieme, že každé auto, ktoré nestojí musí do niečoho naraziť. Prečo? Lebo jediná iná možnosť je, že by odišlo preč, a nikdy do ničoho nenarazilo, ale to sa nemôže stať, keďže také autá sú naľavo, a smerujú doľava, alebo napravo a smerujú doprava, a tie ignorujeme.

Vzorové riešenie teda najprv zistí, ktorý úsek áut nás presne zaujíma, teda zistí aký dlhý je úsek áut, ktoré sú naľavo a smerujú doľava. To isté urobí aj pre pravú stranu. Následne pre každé auto v strednej časti, ktoré nestojí, pripočíta \(1\) k výslednému počtu zrážok, a vypíše tento výsledok.

Toto riešenie prejde celé pole práve raz, a teda jeho časová zložitosť je \(O(n)\). Pamätať si stále musíme len celé pole, teda pamäťová zložitosť je tiež \(O(n)\).

auta = input()

for zaciatok in range(len(auta)):
    if auta[zaciatok]!='<':
        break

for koniec in range(len(auta)-1, -1, -1):
    if auta[koniec]!='>':
        break

zrazky = 0

for i in range(zaciatok, koniec+1):
    if auta[i]!='=':
	    zrazky += 1

print(zrazky)

#include<iostream>
#include<string>

using namespace std;

int main(){
	string auta;
	cin >> auta;
	
	long long zaciatok, koniec, zrazky=0;
	
	for(zaciatok=0; zaciatok<auta.size(); zaciatok++){
		if(auta[zaciatok]!='<')
			break;
	}
	
	for(koniec=auta.size()-1; koniec>=0; koniec--){
		if(auta[koniec]!='>')
			break;
	}
	
	for(long long i=zaciatok; i<=koniec; i++){
        if(auta[i]!='=')
            zrazky++;
	}
	
	cout<<zrazky<<endl;
	
	return 0;
}

Vzorovejšie riešenie (v konštantnej pamäti)

Existuje aj riešenie v konštantnej pamäti. Jeho kľúčovou myšlienkou je, že ak ideme po vstupom poli áut, tak vždy keď nájdeme auto, ktoré smeruje doľava (<), tak vieme, že všetky autá naľavo od neho, ktoré idú doprava do niečoho narazia. V prípade, že nájdeme auto, ktoré smeruje doprava, tak si iba musíme poznačiť, že sme ho niekde videli. No a v prípade, že nájdeme auto, ktoré stojí na mieste, tak vieme, že všetky autá, čo sme videli, a smerovali doprava tiež majú do čoho naraziť.