(Úlohu najdete i jako příklad ve FIKSu.)
Časový limit: 1s, paměťový limit: 512 MB
Pepíček se celý opálený a spokojený vrací z dovolené v Tramtárii. Na letišti si ale vzpomněl, že zapomněl mamince a tatínkovi přivést suvenýry! Naštěstí má posledních k tramtárských liber. Ty jsou mu v rodném Kocourkově k ničemu, takže je chce všechny utratit. V místním obchodu prodávají n suvenýrů očíslovaných 1 až n, z nichž i-tý stojí a_i.
Prodavač je podivín, proto každý má každý suvenýr jinou cenu a navíc jsou na poličce uspořádané podle ceny, tj. pro i od 1 do n-1 platí a_i < a_{i+1}.
Pomozte Pepíčkovi najít dvojici suvenýrů, za které by utratil zbylé tramtárské libry, tj. dva různé indexy i a j takové, že a_i + a_j = k, nebo určete, že taková dvojice neexistuje. Pokud existuje víc řešení, vypište libovolné z nich.
Na prvním řádku vstupu je počet suvenýrů n a kolik tramtárských liber Pepíček vlastní, k. Na dalším řádku vstupu jsou ceny suvenýrů: celá čísla a_1, \ldots, a_n. Pro i od 1 do n-1 platí a_i < a_{i+1}.
Na výstup vypište na jednom řádku dvě čísla i a j
taková, že a_i + a_j = k, nebo vypište
reseni neexistuje v případě, že řešení neexistuje.
V každé sadě platí 1 \leq a_i \leq 10^9, 1 \leq k \leq 10^9. V jednotlivých sadách platí:
Vstup:
4 10
2 3 5 7Výstup:
2 4Výstup znamená, že volíme dvojici (a_2, a_4). A vskutku, a_2 + a_4 = 3 + 7 = 10 = k.
Vstup:
4 14
2 3 5 7Výstup:
reseni neexistujePro k=14 neexistuje vhodná dvojice
suvenýrů. 4 4 není platné řešení, protože používá dvakrát
stejný suvenýr (koupit ho můžeme pouze jednou).
Rychle nás napadne přímočarý algoritmus: zkusíme všechny dvojice suvenýrů, a pokud se ceny nějakých dvou sečtou na k, máme řešení. Nyní si ukážeme, jak bychom jej mohli zapsat jako řešení teoretické úlohy a jako řešení praktické úlohy.
Projdeme všechny dvojice suvenýrů a pro každou dvojici zkontrolujeme, zda je součet cen roven k. Dvojici pak vypíšeme jako výsledek. Protože projdeme všechny dvojice, nemůže se stát, že bychom řešení nenašli, i když existuje; pokud tedy žádnou dvojici nenajdeme, vypíšeme
reseni neexistuje. Dvojic suvenýrů je nejvýše n^2, projít všechny tedy trvá O(n^2) času. (Protože nezáleží na pořadí v rámci dvojice, stačilo by vyzkoušet pouze \binom{n}{2} = \frac{n(n-1)}{2} unikátních dvojic, ale na tom z hlediska asymptotické složitosti nezáleží.) Potřebujeme si kromě vstupu udržovat pouze konstantně mnoho proměnných, paměťová složitost je tedy O(n).
Kód si můžete zkusit spustit online zde.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int vysledek_i = -1, vysledek_j = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// Nemuzeme koupit dvakrat stejny suvenyr
if (i != j) {
if (a[i] + a[j] == k) {
vysledek_i = i;
vysledek_j = j;
}
}
}
}
if (vysledek_i == -1) {
// Nikdy jsme nenastavili vysledek_i, takze jsme nenasli reseni
cout << "reseni neexistuje" << endl;
} else {
// Musime pricist 1, protoze v zadani se indexuje od 1,
// kdezto v C++ od 0
cout << (vysledek_i+1) << " " << (vysledek_j+1) << endl;
}
}Všimněte si, že v praktickém řešení jsme museli řešit různé detaily,
které jsme vynechali v teoretickém, například počítači musíme říct, aby
přeskočil situace, kdy i=j, ale v
teoretickém stačilo napsat všechny dvojice
. Také jsme museli na
konci k indexům přičíst jedna, protože C++ indexuje pole od nuly. To v
teoretickém také není třeba zmiňovat.
Toto řešení by získalo 3 body. Běžný počítač zvládne za sekundu
provést řádově 10^8 až 10^9 operací (slovo operace
je zde
použito v intuitivním nepřesném smyslu), a vyzkoušet všechny dvojice pro
n=1000 je asi 10^6 operací, což se do časového limitu
vejde. Pro n=100\,000=10^5 už bychom
ale museli provést asi 10^{10} operací,
což je příliš mnoho.
Nyní zkusíme vymyslet chytřejší řešení. Zatím jsme nevyužili to, že je seznam suvenýrů seřazený. V seřazeném seznamu můžeme použít tzv. binární vyhledávání:
Projdeme všechny indexy i a pro každé i se pokusíme najít j takové, že a_i+a_j=k. Díky tomu, že je seznam seřazený, platí, že pokud pro nějaké j_1: a_i + a_{j_1} \gt k, pak pro všechna j_2 > j_1 také platí a_i + a_{j_2} > k. Jakmile tedy nějaké takové j_1 najdeme, nemusíme zkoušet j > j_1. Obdobně pokud najdeme j_1 takové, že a_i + a_{j_1} < k, nemusíme zkoušet j<j_1.
To nám umožní použít binární vyhledávání. Budeme si udržovat interval [j_{min}, j_{max}] hodnot j, které má ještě cenu zkoušet. Vyzkoušíme j uprostřed tohoto intervalu, tj. za j zvolíme zaokrouhlený průměr j_{min} a j_{max}. Pokud a_i+a_j=k, nalezli jsme řešení. Pokud a_i + a_j < k, nemá cenu zkoušet menší hodnoty j, omezíme tedy náš interval na [j+1,j_{max}]. Obdobně pokud a_i+a_j > k, omezíme interval na [j_{min}, j-1]. Ve chvíli, kdy je interval prázdný, neexistuje pro toto i vhodné j. Protože v každém kroku se zmenší interval alespoň na polovinu, zabere pouze \log_2 n kroků, než bude interval prázdný. Jedno hledání tedy zabere O(\log n) kroků.
Binární vyhledávání provedeme pro každé i, pokud pro nějaké najdeme vhodné j, vypíšeme výsledek. Jinak řešení neexistuje. Časová složitost je O(n \log n), paměťová složitost O(n).
Detailnější popis binárního vyhledávání najdete v Průvodci. Stačilo by řešení napsat ještě o něco stručněji; můžete předpokládat, že opravovatelé vědí, co je to binární vyhledávání, což jsme zde nepředpokládali. Obecně můžete předpokládat, že pojmy, techniky a algoritmy popsané v IOI Syllabu není potřeba blíže rozepisovat.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int vysledek_i = -1;
int vysledek_j = -1;
for (int i = 0; i < n; i++) {
int j_min = 0;
int j_max = n - 1;
// Dokud mame platny interval [j_min, j_max]
while (j_min <= j_max) {
int j = (j_min + j_max) / 2;
if (a[i] + a[j] < k) {
// Suvenyry s cenou mensi nebo rovnou a[j] uz nemusime zkouset
j_min = j + 1;
} else if (a[i] + a[j] > k) {
// Suvenyry s cenou vetsi nebo rovnou a[j] uz nemusime zkouset
j_max = j - 1;
} else if (i != j) {
// Spravny soucet a zaroven nekupujeme dvakrat stejny suvenyr
vysledek_i = i;
vysledek_j = j;
break;
}
}
}
if (vysledek_i == -1) {
cout << "reseni neexistuje" << endl;
} else {
cout << (vysledek_i+1) << " " << (vysledek_j+1) << endl;
}
}Toto řešení by získalo 7 bodů. Platí, že \log_2 10^5 \approx 17, takže operací bude zhruba 2 \cdot 10^6. Pro n=10^7 by řešení nebylo dost rychlé.
Dodejme, že i kdyby seznam na vstupu nebyl seřazený, mohli bychom si ho seřadit sami a protože řazení trvá O(n \log n), celková časová složitost by byla pořád O(n \log n). Ukážeme si ale rychlejší řešení, které používá metodu dvou ukazatelů (two pointers) a běží v čase O(n). To už musí předpokládat, že je seznam seřazený, jinak by se časová složitost zhoršila.
Budeme procházet všechny suvenýry i od 1 do n. Pro dané i budeme hledat vhodné j. Začneme s j=n a dokud je součet cen suvenýrů i a j moc velký, znamená to, že správné j pro toto i (pokud existuje) musí být někde
nalevo, tj. musí být menší. Dokud je tedy součet moc velký, budeme snižovat j.
Buď skutečně najdeme j, pro které a_i + a_j = k, nebo se dostaneme do situace, kdy už nám posouvání j nepomůže (součet už je menší než k) nebo ani j posouvat nemůžeme (když j=1). Pokud jsme nenašli vhodnou dvojici pro toto i, zkusíme i zvýšit.
Označme starou hodnotu i_1 a novou hodnotu i_2. Nejdůležitější pozorování je, že pokud a_{i_1} + a_j > k, pak a_{i_2} + a_j > k. To proto, že seznam je seřazený a tedy a_{i_2} > a_{i_1}. To znamená, že nemusíme zkoušet žádné hodnoty j, které jsme už vyřadili pro i_1. Místo od n tedy začneme tam, kde jsme přestali.
Časová složitost tohoto algoritmu je O(n); pro fixní j vyzkoušíme dvojici jen s jedním i, pak už ho vyřadíme. Kromě toho uděláme O(n) kroků při posouvání i, dohromady tedy pořád O(n). Potřebujeme si kromě vstupu udržovat pouze konstantně mnoho paměti, paměťová složitost je tedy O(n).
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int vysledek_i = -1, vysledek_j = -1;
int j = n - 1;
for (int i = 0; i < n; i++) {
while (j >= 0 && a[i] + a[j] > k) {
j--;
}
if (i != j && a[i] + a[j] == k) {
vysledek_i = i;
vysledek_j = j;
break;
}
}
if (vysledek_i == -1) {
cout << "reseni neexistuje" << endl;
} else {
cout << (vysledek_i+1) << " " << (vysledek_j+1) << endl;
}
}Řešení by získalo plný počet bodů. Poznamenejme ještě, že v praktických úlohách je pro zadavatele často obtížné nastavit úlohu tak, aby O(n) řešení získalo plný počet bodů, ale chytře optimalizované O(n \log n) řešení neprošlo. Ve skutečnosti by tedy dost možná praktické řešení využívající binární vyhledávání bylo dost rychlé, aby také získalo 10 bodů. V teoretické úloze by se to pochopitelně stát nemohlo.