Zadanie
Niektorí riešitelia KSP sa po maturite rozutekajú do sveta. Napríklad do Dánska. Nechcú si ale so sebou brať svoje autá a keďže sú dobré duše, požičajú ich Trojstenu.
Toto má ale nežiadúce vedľajšie efekty: matfyzácke parkovisko sa rýchlo plní a bezradní šoféri sa hádajú o prázdne miesta. Preto sa vedenie rozhodlo zaviesť nový systém prideľovania parkovacích miest, ktorý bude férový ku všetkým.
Úloha
Máme parkovisko, kde je \(m\) parkovacích miest, očíslovaných číslami od \(0\) po \(m-1\).
Na parkovisko prichádzajú a odchádzajú autá s unikátnou ŠPZ (teda na parkovisku nebudú naraz dve autá s rovnakou ŠPZ, ale jedno auto môže prísť a odísť aj viackrát).
Vašou úlohou je prideľovať autám parkovacie miesta. Každému autu, ktoré príde, prideľte ľubovoľné voľné parkovacie miesto. Ak sú všetky miesta plné, miesto prideľovať nemusíte a auto neobslúžite (ide parkovať inam).
Formát vstupu
V prvom riadku vstupu sú čísla \(m\) (\(1 \leq m \leq 10^5\)) a \(n\) (\(1 \leq n \leq 10^6\)). Číslo \(m\) je počet miest na parkovisku a \(n\) je počet príchodov a odchodov áut dokopy.
V každom z ďalších \(n\) riadkov je číslo ŠPZ (\(1 \leq SPZ \leq 10^6\)) auta, ktoré prišlo alebo odišlo. Ak sa auto s touto ŠPZ nachádza na parkovisku, práve odišlo. V opačnom prípade práve prichádza.
Formát výstupu
Pre každé auto, ktoré prišlo alebo odišlo, vypíšte jeden riadok a na ňom číslo parkovacieho miesta, ktoré obsadilo alebo uvoľnilo (číslované od \(0\) po \(m-1\)). Ak príde auto na plné parkovisko, vypíšte jeden riadok a na ňom reťazec "plne"
.
Správny výstup je ľubovoľné prideľovanie miest, pri ktorom žiadnemu autu nebude pridelené už obsadené miesto a každé auto pri odchode uvoľnilo miesto, ktoré mu bolo pridelené.
Príklad
Input:
3 7
4
9039
103
19
4
103
47
Output:
0
1
2
plne
0
2
2
Pre každý riadok vstupu (ŠPZ auta) riešime jednu z dvoch úloh: parkovanie (nájdi voľné miesto) alebo vyparkovanie (nájdi miesto, na ktorom auto bolo).
Obe sa dajú jednoducho vyriešiť napríklad takto: parkovisko si budeme pamätať ako pole, kde parkovisko[i]
bude obsahovať buď ŠPZ auta, ktoré stojí na mieste \(i\), alebo špeciálnu hodnotu, ak je miesto prázdne. Na zodpovedanie otázky prezeráme parkovisko miesto po mieste, kým nenájdeme dané auto a potom ho vyparkujeme. Ak auto nenájdeme, vyhľadáme mu voľné miesto. Toto riešenie je ale zjavne veľmi pomalé, pretože pre každé auto musíme prehľadať prinajhoršom celé parkovisko. Časová zložitosť takéhoto riešenia je potom \(O(mn)\).
Malým, ale v niektorých prípadoch významným, zlepšením jednoduchého riešenia je nezačínať hľadanie prázdneho miesta vždy odznova. Budeme ho hľadať od miesta, kam zaparkovalo posledné auto. Týmto zrýchlime hľadanie miesta, samozrejme, len pokiaľ sa nezaplní posledné miesto parkoviska. Zvyšok výpočtu sa nespomalí, a preto je toto riešenie lepšie, hlavne ak prichádzajúcich áut je málo a parkovisko veľké.
Toto ale nestačí. Ak by po zaplnení parkoviska stále prichádzali autá na miesta s číslami \(m\) a \(m/2\), pre každú otázku zo vstupu prehľadávame stále \(O(m)\) miest. Chceme teda nájsť buď voľné miesto, alebo miesto, kde je auto zaparkované bez nutnosti prehľadať parkovisko. Na to si ukážeme dva zlepšováky:
Keď auto zaparkuje, jeho miesto sa už meniť nebude. Preto môžeme vyparkovanie zrýchliť na konštantný počet operácií tým, že pre každé zaparkované auto si budeme pamätať miesto, na ktorom stojí a pri vyparkovaní ho uvoľníme. Toto dosiahneme napríklad tým, že budeme mať pole a v ňom políčko pre každú možnú ŠPZ. Keď auto nie je zaparkované, pamätáme si v tomto políčku hodnotu \(-1\) (alebo inú, ktorá nie je platné číslo parkovacieho miesta). Ak príde auto zaparkovať a nájdeme mu miesto, do tohto políčka uložíme číslo miesta, kam zaparkovalo. Keď bude odchádzať, stačí sa pozrieť na toto políčko a hneď vieme, ktoré miesto treba uvoľniť.
Druhým zlepšovákom chceme zrýchliť hľadanie voľného miesta. Uvedomte si, že je nám jedno, na ktoré voľné miesto prichádzajúce auto zaparkujeme. Dôležité je len, aby sme to robili rýchlo. Pamätajme si preto všetky voľné miesta v jednom poli. Na začiatku toto pole obsahuje všetky čísla od 1 po \(m\).
Ak príde auto a chceme mu priradiť voľné miesto, pozrieme sa jednoducho na posledné miesto tohto poľa. Tam sa nachádza nejaké voľné miesto, ktoré mu priradíme. V tomto momente však toto miesto už nie je voľné – potrebovali by sme ho z tohto poľa vyškrtnúť a pole skrátiť. To vieme robiť rýchlo buď pomocou dynamických polí1 alebo len použijeme jednu premennú posledneVolne
, ktorá nám hovorí, koľko voľných parkovacích miest máme. Namiesto skracovania poľa nám preto bude stačiť zmenšiť túto premennú o 1.
Ak auto odchádza, vyššie uvedeným spôsobom zistíme, ktoré miesto uvoľnilo. Toto voľné miesto si zapíšeme do nášho poľa voľných miest, a to tak, že zväčšíme premennú posledneVolne
a do poľa si na toto miesto zapíšeme uvoľnené parkovacie miesto.
Takto máme celý čas k dispozícii zoznam voľných miest a nemusíme sa preto pozerať na všetky ostatné (aj obsadené) parkovacie miesta. Dátová štruktúra, do ktorej vieme na koniec vkladať a z jej konca vyberať prvky sa často používa a tak dostala aj názov – zásobník, po anglicky stack
. V predošlých odsekoch sme si vlastne popísali, ako taký zásobník naprogramovať.
Keď použijeme oba zlepšováky, na parkovanie alebo vyparkovanie jedného auta potrebujeme iba konštantný počet operácií. Obslúžiť \(n\) príchodov alebo odchodov bude teda trvať \(O(n)\) operácií.
V pamäti si musíme držať voľné miesta, ktorých je nanajvýš \(m\) a parkovacie miesta pre všetky ŠPZky2. Napriek tomu, že v našej úlohe sú tieto hodnoty len do \(1\,000\,000\), nie je slušné povedať, že pamäťová zložitosť je konštantná. Omnoho viac prezradíme, ak si označíme maximálnu hodnotu ŠPZ ako napríklad \(S\) a potom môžeme povedať, že pamäťová zložitosť algoritmu je \(O(m + S)\).
#include <iostream>
#define MAXSPZ 1000042
using namespace std;
int parkovacie_miesto[MAXSPZ]; // -1 ak auto s danou SPZ nie je na parkovisku
int main() {
int n, m;
cin >> m >> n;
int volne[m];
//inicializujeme polia
for (int i = 0; i < MAXSPZ; i++) {
parkovacie_miesto[i] = -1;
}
int posledneVolne = m-1;
for (int i = 0; i < m; i++) {
volne[i] = i;
}
for (int i = 0; i < n; i++) {
int spz;
cin >> spz;
if (parkovacie_miesto[spz] != -1) { // ak auto je uz zaparkovanie
int praveUvolnene = parkovacie_miesto[spz];
parkovacie_miesto[spz] = -1;
posledneVolne++;
volne[posledneVolne] = praveUvolnene;
cout << praveUvolnene << endl;
} else {
if (posledneVolne == -1) { // ak chcem parkovat ale nie je volne miesto
cout << "plne" << endl;
} else { // ak parkujem a mam kam
int praveZaplnene = volne[posledneVolne];
posledneVolne--;
parkovacie_miesto[spz] = praveZaplnene;
cout << praveZaplnene << endl;
}
}
}
return 0;
}
m, n = [int(x) for x in input().split(' ')]
parkovacie_miesto = [-1] * 1000047 # -1 ak auto s danou SPZ nie je na parkovisku
volne = [x for x in range(0, m)]
for i in range(n):
spz = int(input())
if (parkovacie_miesto[spz] != -1): # ak auto je uz zaparkovane
miesto = parkovacie_miesto[spz]
volne.append(miesto)
parkovacie_miesto[spz] = -1
print(miesto)
else:
if (len(volne) == 0): # ak chcem parkovat ale nie je volne
print('plne')
else: # ak chcem parkovat a mam kam
miesto = volne.pop()
parkovacie_miesto[spz] = miesto
print(miesto)
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ť.
-
dasdas dasdas
odoslané 2. december 2016 19:08ahoj, vie mi niekto poradit preco moj kod:
http://pastebin.com/KLR6B43F
nefunguje tak ako by mal? funguje to az po posledny input, a nejde mi do hlavy ani preco to tak vlastne nema byt.. vdaka moc-
Lukáš Gáborik
odoslané 4. marec 2017 20:54Pravdepodobne je v poslednom inpute číslo väčšie ako 2 147 483 647 a preto sa nezmestí do premennej typu int. Skús namiesto int napísať long long - to má rozsah až do 9 223 372 036 854 775 807.
-
dasdas dasdas
ahoj, vie mi niekto poradit preco moj kod:
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
int main()
{
//std::ifstream fin("parkovisko.txt");
//if (!fin) return 1;
int prichody, miesta;
std::cin >> miesta >> prichody;
std::vector<bool> used(miesta-1);
std::map<int, int> map;
int n;
while(std::cin >> n)
{
const auto it = map.find(n);
const auto pouzite = std::count(used.begin(), used.end(), true);
//naslo sa
if (it != map.end())
{
std::cout << it->second << '\n';
map.erase(it);
used.pop_back();
}
else
{
if(pouzite == miesta)
{
std::cout << "plne\n";
continue;
}
// hodnota mapy n je pocet pouzitych miest
std::cout << pouzite << '\n';
map[n] = pouzite;
used.push_back(true);
}
}
return 0;
}
nefunguje tak ako by mal? funguje to az po posledny input, a nejde mi do hlavy ani preco to tak vlastne nema byt.. vdaka moc
Lukáš Gáborik
Pravdepodobne je v poslednom inpute číslo väčšie ako 2147483647 a preto sa nezmestí do premennej typu int. Skús namiesto int napísať long long(to má rozsah až do 9223372036854775807).