4. Len tak ďalej Adam
Zadanie
Adama už nebaví, ako si z neho všetci robia srandu, že je malý. Preto sa rozhodol to zmeniť – začne posilovať. Tak sa jedného dňa dotrepal do posilovne. Už už išiel robiť prvý set, keď sa pri ňom zastavil tréner: “Servus mladý! Vieš, ako sa to tu robí?”
Adam mu vraví: “Dobrý! Nie, som tu po prvýkrát.”
Tak sa tréner pustil do vysvetľovania: “U nás máme špeciálny cvičiaci plán. Aby si mal dobrý workout, odcvičíš so všetkými činkami, ktoré máme. Ale musíš cvičiť v špeciálnom poradí. Každá činka je zavesená na nejakej inej činke, teda okrem poslednej, tá visí na stojane. Vždy, keď ideš cvičiť, tak si musíš zobrať činku, na ktorej nie sú zavesené žiadne iné. Keď máš na výber, musíš zobrať najľahšiu takú. Keď s činkou docvičíš, nevracaj ju tam kde visela, proste ju polož na kopu na zem. A nezabudni si zapisovať, v akom poradí si cvičil, aby som to mohol skontrolovať.”
Adam je však známy tým, že je veľmi zábudlivý, takže si vždy spomenul na to, že si to má zapisovať, až keď držal činku v ruke. Keďže sa mu nechcelo zdvihnúť činku ku očiam, aby dovidel na číslo hmotnosti, tak si zakaždým zapísal na lepiaci papierik iba váhu tej činky, z ktorej tú svoju odvesil. Potom tento papierik nalepil na stenu. Aby ušetril miesto na stene, ďaľší papierik nalepil vždy na ten predchádzajúci.
Keď nakoniec prišiel tréner a uvidel Adamove zápisky, vôbec nebol spokojný! Chce od neho, aby mu povedal, v akom poradí s činkami cvičil. Chudák Adam teda postupne odlepuje papieriky zo steny, a snaží sa podľa toho zistiť v akom poradí činky používal. Aby upokojil netrpezlivého trénera, potrebuje to rýchlo, teda musí po každom papieriku povedať dalšiu činku, ktorú použil.
Úloha
Máme $n$ činiek s váhami $1,\dots,n$. Na začiatku boli usporiadané tak, že jedna bola na stojane, a všetky ostatné viseli na nejakej inej činke. Činky môžu byť zavesené bez ohľadu na váhu, aj ľahšia na ťažšej, aj ťažšia na ľahšej.
Keď Adam ide cvičiť s činkou, dodržiava nasledovné:
-
môže cvičiť len s činkami, na ktorých nie je nič zavesené
-
vždy cvičí s najľahšou dostupnou činkou
Zakaždým si na nový papierik napíše číslo činky, z ktorej túto činku zvesil, a ten potom nalepí na predchádzajúci papierik na stene.
Ako poslednú činku zoberie tú, čo visí na stojane. Keďže nevisí na inej činke, o nej si nezapíše žiaden papierik.
Teraz sú papieriky nalepené na stene – v opačnom poradí ako s nimi Adam cvičil. Adam teraz musí povedať v akom poradí s činkami cvičil od poslednej po prvú, a to tak, že postupne odliepa všetky papieriky a s každým odlepeným musí povedať ďalšiu aspoň jednu činku z tohoto poradia.
Formát vstupu
V prvom riadku vstupu je čislo $n$ - počet činiek, s ktorými Adam cvičil.
Nasleduje $n-1$ riadkov. Na každom je číslo od $1$ po $n$ zodpovedajúce papieriku na stene, teda o každej činke, s ktorou Adam vtedy cvičil, váha tej činky, na ktorej bola zavesená. Riadkov je $n-1$ kvôli tomu, že činka na stojane nemá papierik.
Tieto čísla sú napísané v opačnom poradí v akom s nimi Adam cvičil.
Pre $n$ platia nasledovné obmedzenia:
| Sada | 1, 5 | 2, 6 | 3, 7 | 4, 8 |
|---|---|---|---|---|
| $1 \leq n \leq$ | $10$ | $1000$ | $10^5$ | $10^5$ |
Formát výstupu
Vypíšte $n$ riadkov, na $i$-tom z nich váhu činky, s ktorou Adam cvičil ako $i$-tou poslednou. Teda najprv vypíšte váhu činky, čo bola na stojane, a ako poslednú vypíšte váhu činky, s ktorou Adam cvičil úplne na začiatku.
V sadách 1 až 4 máte dovolené najprv načítať všetky papieriky, a až potom odpovedať. V sadách 5 až 8 musíte hneď po prečítaní každého papierika vypísať aspoň jeden riadok výstupu.
Aby testovanie fungovalo ako má, je nutné po
vypísaní každého riadku flushnúť váš výstup, aby ho testovač uvidel. V
C++ by malo stačiť cout << nieco << endl;, ale
môžete explicitne použiť príkaz cout.flush();. V Pythone
vypisujte príkazom print(cislo, flush=True) alebo po
vypísaní spravte sys.stdout.flush(). Pre iné jazyky
hľadajte ekvivalent k príkazu flush.
Príklady
Takýto vstup môže byť v 5. sade:
>>> 4 #počet činiek
>>> 2 #prvý papier
<<< 2 #posledná činka mala váhu 2
>>> 1
<<< 1
>>> 2
<<< 4
<<< 3 #na konci vypíš uplne prvú činku
v tomto prípade na začiatku boli činky odložené takto:
Adam cvičil s činkami v poradí 3, 4, 1, 2. Na papieriky postupne napísal 2, 1, 2.
Takýto vstup by mohol byť v 1. sade:
>>> 5 #počet činiek
>>> 5 #činky
>>> 1
>>> 1
>>> 1
<<< 5 #posledná činka
<<< 1
<<< 4
<<< 3
<<< 2 #prvá činka
v tomto prípade na začiatku boli činky odložené takto:
Adam cvičil s činkami v poradí 2, 3, 4, 1, 5. Na papieriky postupne napísal 5, 1, 1, 1.
Offline riešenie
Nejaké body ste dostali, ak ste úlohu vyriešili offline, avšak tento postup je aj programátorsky skoro náročnejší ako postup na plný počet bodov, preto veľmi odporúčam rovno preskočiť na ďalší odstavec, kde sa dozviete ako túto úlohu riešiť online.
Úlohu budeme riešiť odsimulovaním si Adamovho cvičenia. Najskôr načítame všetky čísla zo vstupu (váhy činiek, na ktorých boli zavesené činky s ktorými Adam cvičil). Na to, aby sme odsimulovali Adamove cvičenie, si musíme čísla na vstupe uložiť v opačnom poradí v akom sme ich dostávali napríklad do poľa $C$. Takto budeme mať na mieste $C[0]$ uloženú váhu činky, na ktorej bola zavesená činka, s ktorou cvičil Adam ako prvou.
Keď už máme vhodne uložený vstup, tak sa môžeme pustiť do simulovania Adamovho cvičenia. Keď chceme zistiť, s ktorou činkou cvičil Adam ako $i$-tou, tak potrebujeme vedieť, na ktorých čínkách nie je nič zavesené a ktoré sú už zobraté. Činky, na ktorých nie je nič zavesené sú tie, ktoré sa už nevyskytujú na vstupe. Činky, s ktorými už Adam cvičil si budeme ukladať do poľa. Takže, keď chceme zistiť, s ktorou činkom cvičil Adam ako $i$-tou, tak si vytvorím pole $A$ veľkosti $n+1$. Na $j$-tom indexe bude 1 vtedy, keď je možné danú činku použiť. Potom si do poľa pridáme 0 na miesta, ktorých váhy už boli zobrané. Potom prejdeme $C$ od $i-1$-tého indexu a zaznačíme si do príslušných miest v $A$ nuly. Nakoniec nám už iba stačí nájsť najmenšie miesto, kde je 1 a pridať túto váhu do už použitých váh.
Toto riešenie je dosť dobré na to, aby prešlo prvými dvomi sadami na vstupe. Riešenie, pri ktorých potrebujeme poznať celý vstup vzhľadom na charakter úlohy môžu dostať iba polovicu bodov, takže sa nimi už nebudeme viacej zaoberať.
Poďme na to online
Postupne spracúvame vstup, teda určujeme v akom poradí idú činky, ale odzadu. Keď sa teda pozeráme na $i$-te číslo, vieme už posledných $i-1$ činiek. Nech je $i$-te číslo na vstupe $x$. Môžu nastať 2 prípady:
-
Adam ešte necvičil s činoku $x$. To znamená, že Adam s ňou musel cvičiť ako $i$-tou od konca. Neskôr s ňou nemohol cvičiť, pretože tie už poznáme. Skôr s ňou nemohol taktiež cvičiť, pretože na nej je neskôr niečo zavesené.
-
Adam už cvičil s činkou $x$. V tomto prípade Adam cvičil s najťažšou činkou, s ktorou necvičil neskôr. Označme si túto činku $p$.Musíme sa však zamyslieť nad tým, či táto činka už nebola na vstupe. To by znamenalo, že s ňou Adam nemohol cvičiť ako $i$-tou od konca, pretože na nej neskôr bolo niečo zavesené. Ideme to dokázať sporom. Vieme, že Adam ešte necvičil s činkou $p$. Pozrime sa na prvý výskyt činky $p$ na vstupe. Vieme, že pred tým s ňou necvičil. To znamená, že sa jedná o prípad číslo 1 a tým pádom s ňou Adam vtedy cvičil. To je ale v spore s predpokladom a to znamená, že činka $p$ ešte nebola na vstupe a Adam s ňou môže cvičiť.
To znamená, že každé číslo zo vstupu nám jednoznačne povie, s ktorou činkou Adam cvičil ako $i$-tou od konca. Na konci zostane jedna činka nepoužitá (keďže na vstupe je $n-1$ činiek - s ňou cvičil Adam ako prvou).
Teraz to nakódime
Spravíme si pole $U$ veľkosti $n+1$. V tomto poli bude na políčku $j$ jednotka, ak už Adam cvičil s činkou s váhou $j$. Pozrime sa na $i$-te číslo na vstupe. Nech je to číslo $x$. Ak Adam ešte necvičil s činkou $x$, tak s ňou musel cvičiť ako $i$-tou a vypíšeme ju. Do poľa $U$ si zapíšeme na pozíciu $x$ jednotku. Ak už Adam cvičil s činkou $x$, tak na vstup vypíšeme najťažšiu činku, s ktorou ešte necvičil. Túto nájdeme tak, že budeme prechádzať pole $U$ od najväčších indexov k najmenším a budeme hľadať 0. Povedzme, že ju nájdeme na indexe $u$. Vypíšeme $u$, zapíšeme do poľa na $u$-ty index 1. Keď neskôr hľadamé najťažšiu činku, stačí nám pokračovať od indexu $u$.
#!/usr/bin/python3
n = int(input())
uz = [0] * (n+1)
t = n
for i in range(n-1):
x = int(input())
if uz[x] == 1:
while uz[t] == 1:
t -= 1
uz[t] = 1
print(t, flush=True)
else:
uz[x] = 1
print(x, flush=True)
while uz[t] == 1:
t -= 1
uz[t] = 1
print(t)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int t = n;
vector<int> uz(n+1, 0);
for(int i = 1; i < n; i++)
{
int x;
cin >> x;
if(uz[x])
{
while(uz[t]) t--;
uz[t] = 1;
cout << t << endl;
continue;
}
uz[x] = 1;
cout << x << endl;
}
while(uz[t]) t--;
cout << t << endl;
}
