Zadanie
Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Kubovi na [email protected]
Andrej má doma záhradu na ktorej mu rastú jablká a hrušky. Tento rok mu ich narástlo veľmi veľa a on má rád iba tie naozaj kvalitné. Aby zistil ktoré z nich sú kvalitné a ktoré nie, by ich chcel zoradiť podľa kvality. Andreja už ale po mnohých rokoch klasické triedenie omrzelo. Chcel by preto vyskúšať nejaký nový spôsob triedenia a rozhodol sa, že tento rok bude triediť tak, že nebude vymienať ovocie rovnakého druhu. Nie je si ale istý, či takýmto spôsobom vie jablká a hrušky zoradiť. Vedeli by ste mu pomôcť?
Úloha
Máme rad ovocia. Každé z nich je opísané dvoma číslami: \(a_i\) - jeho kvalita a \(b_i\) - jeho typ. Chceme zistiť, či vieme
zoradiť tento rad podľa kvality ovocia (\(a_i\)) tak, aby sme vymieňali iba ovocie
rôzneho typu (s rôznym \(b_i\)).
Hodnota \(b_i\) je buď 0 (jablko) alebo
1 (hruška).
Vstup sa skladá z viacerých testov. Každý test je samostatným radom ovocí a nie je žiadnym spôsobom závislý od predchádzajúcich alebo nasledujúcich testov.
Formát vstupu
Na prvom riadku vstupu dostanete číslo \(t\), označujúce počet testov.
Každý test sa skladá z troch riadkov vstupu. Na prvom riadku dostanete
číslo \(n\), označujúce počet ovocí v
rade. Na druhom riadku dostanete \(n\)
čísel \(a_i\), označujúcich kvalitu
ovocia. Na poslednom riadku testu dostanete \(n\) čísel \(b_i\), označujúcich typ ovocia.
Formát výstupu
Pre každý test vypíšte Ano
, ak je možné ovocie možné
zoradiť tak, že vymieňame iba ovocie rôzneho typu alebo
Nie
, ak ich tak zoradiť nevieme.
Hodnotenie
Existuje 5 sád vstupov. Za každú správne vyriešenú sadu získate 20
bodov.
Pre jednotlivé sady vstupov platia nasledovné obmedzenia:
Sada. | 1. | 2. | 3. | 4. | 5. |
---|---|---|---|---|---|
\(5 \leq t \leq\) | \(15\) | \(150\) | \(150\) | \(700\) | \(1000\) |
\(10 \leq n \leq\) | \(100\) | \(100\) | \(500\) | \(1000\) | \(4000\) |
V každej sade platí, že \(0 \leq a_i \leq 10^6\) a \(b_i \in \{0, 1\}\).
Príklad
Input:
5
8
10 20 30 40 50 60 60 80
1 0 1 1 0 0 1 0
5
39 25 77 91 95
1 0 0 1 1
3
5 71 57
0 0 0
6
0 1 1 2 3 5
1 1 1 1 1 1
4
22 11 113 50
1 0 0 1
Output:
Ano
Ano
Nie
Ano
Ano
- V prvom prípade už je ovocie zoradené podľa kvality.
- V druhom prípade nám stačí vymeniť prvú hrušku s prvým jablkom.
- V treťom prípade nevieme ovocie zoradiť, keďže nemôžeme žiadnu dvojicu vymeniť.
- Vo štvrtom prípade už je ovocie zoradené.
- V piatom prípade vieme vymeniť prvú hrušku a prvé jablko a potom druhé jablko a druhú hrušku.
Jednoduché prípady
Ak máme ovocie na vstupe už zoradené podľa kvality, tak nemusíme nič
riešiť a vieme nezávisiac od typov ovocí proste odpovedať
Ano
(už sme v usporiadanom stave, čiže aj s 0 výmenami sa
vieme dostať do usporiadaného stavu).
Ak by sme mali iba ovocie jedného typu, tak vieme odpovedať
Ano
iba vtedy, ak už je usporiadané podľa kvality a v
každom inom prípade Nie
. Je to tak preto, lebo ak máme iba
ovocie jedného typu, nedokážeme vymeniť žiadnu dvojicu ovocí. Čiže ak
nie je usporiadané podľa kvality na začiatku, tak s ním nevieme nič
spraviť.
Ostatné prípady
Zostávajú nám prípady, kedy máme ovocia rôznych typov a nie sú
usporiadané podľa kvality. Verte či neverte, ale v každom takom prípade
vieme odpovedať Ano
. Teraz si ale musíme aj zdôvodniť,
prečo to tak naozaj je.
Jedno iné ovocie
Ak by sme mali skoro všetky ovocia typu 0 a presne jedno ovocie typu
1 (alebo naopak), tak určite vieme nejakými výmenami usporiadať celý rad
ovocí typu 0 podľa kvality. Na to si úplne vystačíme s jedným ovocím
druhého typu.
Postup ktorým to vieme dosiahnuť môže byť napr. takýto:
- Ak ovocie typu 1 nie je prvým ovocím v rade, tak ho vymeníme s prvým ovocím v rade.
- Ovocie typu 1 vymeníme s ovocím typu 0, ktoré má spomedzi všetkých ovocí typu 0 najnižšiu kvalitu.
- Opakujeme kroky
1
a2
s postupne sa zvyšujúcou pozíciou ovocia typu 1 v rade (začali sme s 0, teraz budeme s 1, potom s 2, …).
Teraz sme skončili s usporiadaným radom ovocí typu 0 a jedným ovocím typu 1 na konci. Ešte ale potrebujeme dostať ovocie typu 1 na správnu pozíciu. To dosiahneme tak, že ho postupne budeme vymienať s ovocím typu 0, ktoré je v rade hneď pred ním, až kým sa nedostane tam kam patrí.
Takže rad s jedným ovocím iného typu vieme vždy usporiadať podľa kvality.
Viac ovocí iného typu
Ak by sme mali viac ovocí iného typu, tak vieme postupovať veľmi podobne ako v predchádzajúcom prípade. Začneme s tým, že si s pomocou jedného z ovocí typu 1 usporiadame všetky ovocia typu 0 podľa kvality na začiatok našeho radu. Následne použijeme posledné ovocie typu 0 z už usporiadaného radu ako pomocné ovocie, ktorým budeme vymieňať ovocia typu 1 na správne pozície. Ako posledný krok vrátime pomocné ovocie na jeho pôvodnú pozíciu, podobne ako v predchádzajúcom prípade.
Teraz sme sa ocitli v stave, kedy máme usporiadané všetky ovocia typu 0 na začiatku radu a všetky ovocia typu 1 za nimi. Čo ale teraz potrebujeme urobiť je, premiešať ich navzájom tak, aby zostali usporiadané podľa kvality. To urobíme v podstate rovnako ako v predchádzajúcom prípade, ale namiesto jedného ovocia typu 1 budeme postupne presúvať všetky ovocia typu 1 na správne pozície.
Takže aj rad s viacerými ovociami iného typu vieme vždy usporiadať podľa kvality.
Typy ovocia ktoré boli použité v tejto časti sú vymeniteľné, nezáleží na tom či budeme mať na začiatku typ 0 a na konci typ 1 alebo naopak.
Zhrnutie
Keď sa pozrieme na to čo sme si práve povedali, môžeme si všimnúť, že
jediný prípad s výstupom Nie
nastane vtedy, ak máme ovocie
rovnakého typu a nie je usporiadané. V každom inom prípade vieme
odpovedať Ano
.
Implementácia
Implementácia bude opísaná v jazyku Python, ale dá sa veľmi ľahko aplikovať aj na C++.
Začnime časťou kódu, ktorá sa postará o načítanie vstupu. Tým, že sa v tejto úlohe jeden vstup skladá z viacerých testov sa zatiaľ nebudeme trápiť.
= int(input())
n
= list(map(int, input().split()))
a = set(map(int, input().split())) b
Tu si môžeme všimnúť, že prvky v polliach a
a
b
sme načítali trošku odlišne. Zatiaľ čo prvky v poli
a
sme načítali ako štruktúru list
, prvky v
poli b
sme načítali ako štruktúru set
. Dôvodom
prečo sme to tak urobili je, že pre a
nám záleží na presnom
poradí hodnôt \(a_i\) na vstupe, zatiaľ
čo pri b
nám záleží iba na tom, či sa objavili oba typy
ovocia alebo iba jeden.
set
je štruktúra, ktorá uchováva iba rôzne hodnoty.
Ak by sme sa pokúsili doset
u pridať hodnotu, ktorá sa v ňom
už nachádza, tak sa nič nestane.
Teraz môžme pridať jednoduchú kontrolu, či sa v poli b
nachádzajú oba typy ovocia.
if len(b) == 2:
print("Ano")
else:
...
Zostáva nám overiť tú zložitejšiu vec, a to či je rad ovocia
usporiadaný podľa kvality. To vieme urobiť tak, že budeme postupne
prechádzať radom kvalít a budeme si pamätať predchádzajúcu hodnotu. Ak
sa nám stane, že aktuálna hodnota je menšia ako predchádzajúca, tak
vieme, že rad nie je usporiadaný a môžme odpovedať Nie
.
if len(b) == 2:
print("Ano")
else:
= a[0]
pred for i in range(1, n): # index 0 sme už spracovali, takže začíname od 1
if a[i] < pred:
print("Nie")
break
= a[i]
pred else:
print("Ano")
A toto je celá implementácia hotová!
Finálny kód, ktorý berie do úvahy aj viacero testov na vstupe vyzerá takto:
= int(input())
t
for _ in range(t):
= int(input())
n
= list(map(int, input().split()))
a = set(map(int, input().split()))
b
if len(b) == 2:
print("Ano")
else:
= a[0]
pred for i in range(1, n):
if a[i] < pred:
print("Nie")
break
= a[i]
pred else:
print("Ano")
Implementácia v C++
#include<bits/stdc++.h>
using namespace std;
int main() {
int t, n;
>> t;
cin
for(int i = 0; i < t; i++) {
>> n;
cin
int lastA = 0, is_sorted = true;
>> lastA;
cin for(int j = 1; j < n; j++) {
int a;
>> a;
cin if(a < lastA) {
= false;
is_sorted // Nemôžeme použiť break, lebo by sme nenačítali hodnoty zostávajúce na vstupe
}
= a;
lastA }
int bhas0 = false, bhas1 = false;
for(int j = 0; j < n; j++) {
int b;
>> b;
cin if(b == 0) bhas0 = true;
if(b == 1) bhas1 = true;
}
// Ano je buď ak sme videli typ 0 aj 1 alebo ak je rad usporiadaný
if((bhas0 && bhas1) || is_sorted) {
<< "Ano\n";
cout } else {
<< "Nie\n";
cout }
}
}
Časová a pamäťová zložitosť
Časová zložitosť pre jeden test je \(O(n)\), kde \(n\) je počet ovocí v rade, keďže pri najdlhšom overovaní budeme musieť raz prejsť celý rad.
Najlepšia dosiahnuteľná pamäťová zložitosť je \(O(1)\), keďže pri prechádzaní radu
a
nám stačí si pamätať predchádzajúcu hodnotu a hodnotu na
aktuálnej pozícii. Pri prechádzaní radu b
nám stačí pamätať
si iba to, či sme v ňom videli jednotlivé typy ovocia. Dokopy je to teda
konštantne veľa pamäte.
Je treba poznamenať, že v Python kóde ukázanom vyššie si pamätáme
naraz celý rad a
a b
. Takže v tejto
implementácii je pamäťová zložitosť \(O(n)\). V Pythone je o niečo
komplikovanejšie čítať zo vstupu medzerami oddelené hodnoty
postupne.
Finálnu časovú zložitosť ale ešte musíme prenásobiť počtom testov, čo
nám dáva celkovú časovú zložitosť \(O(t \cdot
n)\), kde \(t\) je počet
testov.
Pamäťovú zložitosť takto upravovať nepotrebujeme a tedá je stále \(O(1)\).
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ť.