Zadanie
Kristíne sa podarilo byť úspešným riešiteľom jej obľúbeného Trojsten korešpondenčného semináru, čím si zaslúžila účasť na jeho letnom sústredení. V rámci štandardného týrania detí na Lesnej Omege je potrava iba na prídel za dobré správanie. Účastníci za dobré skutky ako pomáhanie pri budíčkoch, zúčastňovanie sa rozcvičiek, aktivitu na prednáškach, čistenie záchodov a iné získavajú jednorázové stravné lístky.
Niekoľko svedkov pozorovalo Kristínu nekalo sa škeriť.
Úloha
Lístok môže vyzerať napríklad takto:
+-------+
| 0247g |
| 11% |
+-------+
Všetky lístky vyzerajú rovnako, líšia sa iba v číselných hodnotách.
Môžeme vidieť, že na každom lístku sú dve čísla, jedno končiace sa
g
a druhé ukončené \%
. Lístok sa dá teda
využiť buď tak, že účastník dostane určité množstvo gramov, alebo určité
percento zostávajúceho jedla v hrnci.
Kristína vie, že dnešná večera je granadír. Celé sústredenie si odkladala stravné lístky a podarilo sa jej ich nahrabať až \(N\). Cieľ je jasný a nenechá sa ničím a nikým zastaviť - získať všetok granadír pre seba.
Ale dá sa to vôbec? Lístky vie použiť v ľubovoľnom poradí a pre každý si vie samozrejme vybrať, akým z daných dvoch spôsobov ho chce uplatniť. Pomôžte jej zistiť, ako má lístky použiť aby nahonobila najmasívnejšie množstvo granadíru. Krisína pevne verí, že kuchyňa je čestná a prípadné dlhy jej budú vyplatené na ďalšom sústredení. Jej cieľom je teda maximalizovať zisk granadíru a výsledný zostatok kuchyne môže byť záporný.
Formát vstupu
Na prvom riadku je jedno číslo \(V\) (\(1 \leq V \leq 10\)) udávajúce počet večerí. Nasleduje \(V\) popisov večerí, pričom všetky sú navzájom nezávislé. Pre každú večeru je na vstupe nasledovné:
V prvom riadku sú dve čísla \(N_v\) (\(1 \leq N_v \leq 40\)) a \(H_v\) (\(0 \leq H_v \leq 10^9\)) udávajúce počet kartičiek a hmotnosť navareného granadíru.
Nasleduje \(N_v\) riadkov, každý
tvaru <A>g <B>%
kde <A>
(\(0 \leq A \leq 10^4\)) a
<B>
(\(0 \leq B \leq
100\)) sú už spomínané dve čísla napísané na kartičke.
V jednotlivých sadách platia nasledujúce obmedzenia:
Sada | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1 \leq N_v \leq\) | \(10\) | \(20\) | \(30\) | \(40\) |
Formát výstupu
Na výstup vypíšte \(V\) odpovedí ako
postupovať pri jednotlivých večeriach. V každej odpovedi vypíšte \(N_i\) riadkov, každý vo formáte
<L> <T>
, kde <L>
je číslo
lístku indexované od jednotky a <T>
je spôsob akým
tento lístok chceme použiť, teda buď g
alebo
%
. Poradie lístkov na výstupe určuje v akom poradí ich
chcete uplatniť.
Riešenie je považované za správne ak sa od optimálneho riešenia líši maximálne o \(10^{-9}\) v absolútnej alebo relatívnej hodnote.
Príklady
Input:
1
3 1000
10g 2%
20g 1%
30g 1%
Output:
1 %
2 g
3 g
Po uplatnení prvého lístku máme 20g a zostáva 980g, po uplatnení zvyšnych dvoch máme 70g a zostáva 930g.
Input:
1
3 1010
9g 1%
20g 1%
99g 10%
Output:
3 %
1 %
2 g
Dokopy získame 130.09g.
Input:
1
3 1010
9g 1%
20g 1%
100g 10%
Output:
1 %
2 g
3 g
Dokopy získame 130.10g.
Input:
1
3 10
10g 1%
10g 1%
10g 1%
Output:
3 g
1 g
2 g
Dokopy “získame” 30g, aj keď je to viac ako je reálne k dispozícii.
Načítavanie
Prvý krok nutný na vyriešenie úlohy je načítanie vstupu. Keďže je to 7. úloha, aj trošku neštandardný formát vstupu by nám nemal robiť problém. Najťažšie je načítať parametre kartičiek – chceme načítať dve čísla na jednom riadku, ale odignorovať posledný znak.
V Pythone vieme tento riadok načítať napríklad nasledovne:
gram, perc = input().split()
gram, perc = int(gram[:-1]), int(perc[:-1])
# alebo kompaktnejšie
gram, perc = map(lambda s: int(s[:-1]), input().split())
V C++ zase takto:
int gram, perc;
// pomocou scanf
scanf("%dg %d%% ", &gram, &perc);
// alebo, keďže `cin`:
// - číselné typy načítava pokým nenarazí na nečíselný znak
// - ignoruje vedúce whitespace
// stačí načítať do čísla a následne načítať koncový znak do typu `char`
char koncovy;
cin >> gram >> koncovy >> perc >> koncovy;
Aby sa nám uľahčil život, ďalej vo vzorovom riešení, pod hodnotou ‘x%’-kartičky myslíme zlomok granadíru ktorý ešte ostane po použití tejto kartičky, teda \(1-x/100\).
Bruteforce
Najprv si uvedomme, že ak vo výsledku máme dve po sebe idúce kartičky
použité rovnakým spôsobom (teda obe g
alebo obe
%
), nezáleží na ich poradí.
Ďalej si uvedomme, že sa nám nikdy neoplatí použiť
%
-kartičku po g
-kartičke. Bez ujmy na
všeobecnosti nech ide o posledné dve kartičky a nech množstvo granadíru
zostávajúceho po použití všetkých zvyšných kartičiek je \(R\). Potom výsledok (koľko granadíru
zostane) po použití kartičiek v poradí g%
bude \((R - m) \cdot k = R \cdot k - m \cdot k\)
zatiaľčo v poradí %g
bude \(R
\cdot k - m\), kde \(0 \leq b \leq
1\). Vidíme teda, že použitím kartičiek v poradí g%
iba zbytočne odčítavame menej. Výsledné kartičky teda obsahujú najprv
postupnosť %
-kariet a potom už iba
g
-kariet.
Spojením týchto dvoch uvedomení zistíme, že našou úlohou je iba pre každú kartu rozhodnúť o jej type, čo už potom jednoznačne určuje výsledok. Naskytá sa nám teda priamočiare riešenie vyskúšať všetkých \(2^N\) možností, každú vyhodnotiť a vypísať najmenšiu.
Najťažšou časťou takéhoto programu je iterovanie cez všetky kombinácie. To sa štandardne robí prostredníctvom iterovania cez čísla od 0 po \(2^N-1\). Binárny zápis každého tohoto čísla reprezentuje jednu podmnožinu \(N\)-prvkovej množiny.
for binarna_mnozina in range(1 << N):
mnozina = set(i for i in range(N) if binarna_mnozina & (1 << i))
Pamäťová zložitosť je \(O(N)\) a časová zložitosť je \(O(N\times 2^N)\). Efektívnou implementáciou tohoto prístupu sa dali prejsť až dve sady.
Stredová stretávka
Pri riešení úloh vieme použiť obmedzenia vstupov ako pomôcku na nájdenie riešenia. V tomto prípade sme si mohli všimnúť, že \(N\) je podozrivo malé, a teda by sa úloha mohla dať riešiť Meet-In-The-Middle prístupom.
Princíp MITM riešení je využiť symetriu problému a rozdeliť ho na dve časti, ktoré sa dajú riešiť nezávisle. Snažíme sa teda nájsť také rozdelenie, aby každá časť bola dostatočne malá na to, aby sme ju vedeli vyriešiť nejakým iným prístupom (napríklad bruteforce) a výsledky z oboch častí dakázali spojiť do výsledného riešenia.
Ako by to vyzeralo? Rozdelíme si množinu kartičiek na dve rovnako veľké disjunktné časti. Pre každú z nich zbehneme bruteforce a zapamätáme si všetky podvýsledky – podvýsledok je optimálne riešenie pre zvolené určenie typov pre danú polovicu kartičiek. Pre každú časť ich bude \(2^{N/2}\).
My už vieme, že určením typov kartičiek je jednoznačne určený
výsledok čo nimi vieme dosiahnuť a efekt ich uplatnenia vieme
zjednodušene reprezentovať ako dve čísla – súčet všetkých
g
-kartičiek a súčin všetkých %
-kartičiek, teda
\((M, K)\).
Skombinovanie podvýsledkov z týchto dvoch podmnožín je potom jednoduché. Ak chceme skombinovať podvýsledok \((M_{1,i}, K_{1,i})\) s podvýsledkom \((M_{2,j}, K_{2,j})\), kombinácia bude \((M_{1,i} + M_{2,j}, K_{1,i} \cdot K_{2,j})\), čo po konzumácii spôsobí zostatok granadíru \((H \cdot K_{1,i} \cdot K_{2,j}) - (M_{1,i} + M_{2,j})\).
Nás by teraz zaujímalo, aký je najlepší možný výsledok. To zistíme tak, že pre každý podvýsledok prvej časti nájdeme preňho najlepší podvýsledok v druhej časti – teda taký, ktorý minimalizuje daný výraz.
Naivným skúšaním všetkých možností by sme znova získali bruteforce (\(O(2^{N/2}\times 2^{N/2})\)). Naším cieľom je pre fixné \((M_{1,i}, K_{1,i})\) minimalizovať \((H \cdot K_{1,i} \cdot K_{2,j}) - (M_{1,i} + M_{2,j})\) cez všetky \((M_{2,j}, K_{2,j})\). Všimnime si, že to je to isté ako minimalizovať \(H_i \cdot K_{2,j} - M_{2,j}\), pre \(H_i := H \cdot K_{1,i}\), keďže \(M_{1,i}\) a \(K_{1,i}\) sú v tomto prípade konštanty. Problém je, že \(H_i\) je konštanta iba pre jedno konkrétne \(K_{1,i}\), pričom rôznych \(K_{1,i}\) je až \(2^{N/2}\).
Konvexný obal
Sťažme si úlohu. Ak by sme vedeli nájsť optimálne \((M_{2,j}, K_{2,j})\) pre každé reálne \(H'\), tak by sme ho predsa vedeli nájsť aj pre ľubovoľné konkrétne \(H_i\). Z \(H_i\) sa teda stáva reálna premenná \(x\) a \(x \cdot K_{2,j} - M_{2,j}\) nám určuje lineárnu funkciu – priamku. Každé jedno \((M_{2,j}, K_{2,j})\) určuje jednu priamku a nás pre každé \(x\) zaujíma najnižší bod ležiaci na niektorej z týchto priamok. Inak povedané, hľadáme konvexný obal týchto priamok.
Hľadanie konvexného obalu priamok je podobné hľadaniu konvexného obalu bodov. Priamky si utriedime podľa ich smernice a potom ich prechádzame od najväčšej po najmenšiu (teda budeme tvoriť KO zľava doprava), pričom si udržiavame doteraz nájdený KO. Každú priamku sa pokúsime pridať do KO. Môžu nastať dve situácie – buď nová priamka nepatrí do KO alebo patrí.
V prípade, že nová priamka \(f_{\mathrm{nová}}\) patrí do KO tak existuje nejaký najľavejší bod, ktorý patrí aj tejto priamke aj KO – teda to bude priesečník \(f_{\mathrm{nová}}\) a niektorej doterajšej priamky \(f_{\mathrm{hľadaná}}\) z KO. Otestujme, či posledná priamka KO \(f_{\mathrm{posledná}}\) je \(f_{\mathrm{hľadaná}}\). Ak je priesečník priamok \(f_{\mathrm{nová}}\) a \(f_{\mathrm{posledná}}\) ľavší než priesečník priamok \(f_{\mathrm{posledná}}\) a \(f_{\mathrm{predposledná}}\), tak \(f_{\mathrm{posledná}}\) nie je \(f_{\mathrm{hľadaná}}\) a dokonca \(f_{\mathrm{posledná}}\) nie je ani súčasťou KO. V takom prípade ju odstránime a pokračujeme v hľadaní najľavejšieho bodu.
Inak povedané: Tým, že sa na priamky pozeráme v poradí s klesajúcou smernicou platí, že najnovšia priamka je vždy lepšia ako nejaký (potenciálne nulový) počet priamok na konci KO. Teda porovnávame novú priamku s poslednou priamkou KO a odstraňujeme túto poslednú priamku pokým je horšia ako nová. Ošetrenie rovnobežných priamok ponechávame na čitateľa.
Časová zložitosť je \(O(N\log(N))\) a pamäťová zložitosť je \(O(N)\), kde \(N\) je počet priamok. Viac si o konvexnom obale môžete prečítať v kuchárke.
Dôsledok
S nájdeným konvexným obalom potom pre ľubovoľné \(H_i\) vieme nájsť najlepšie \((M_{2,j}, M_{2,j})\) binárnym vyhľadávaním. V prípade, že sa na jednotlivé \(H_i\) budeme pýtať v utriedenom poradí ani nemusíme binárne vyhľadávať, ale len prechádzať postupne priamky KO. Tento prístup sa volá Convex Hull Optimization/Trick.
Pamäťová zložitosť je \(O(2^{N/2})\) a časová zložitosť je \(O(2^{N/2}\times\log(2^{N/2})) = O(N\times 2^{N/2})\) (logaritmus pochádza z triedenia v hľadaní KO a triedenia \(H_i\) alebo binárneho vyhľadávania). Oproti bruteforce teda úspešne zvládame približne dvakrát väčšie vstupy. Pre aktuálne obmedzenia toto však nie je dostatočne rýchle riešenie. Na iných vstupoch (ktoré by mali napríklad väčšie hodnoty gramov) by toto bol dobrý prístup. Tento prístup zvláda prejsť až tri sady, ale v hodnotení popisov vie takéto riešenie získať plný počet.
Vzorové riešenie
Čo ďalšie by sme si mohli všimnúť zo zadania? Gramáže kartičiek sú nanajvýš \(10^4\) a spolu s malým \(N\) teda aj súčet gramáží bude malé číslo.
Ako sme si už povedali, pre zvolené určenie typov kartičiek je
výsledok závislý iba od súčinu %
-kartičiek (\(=k\)) a súčtu g
-kartičiek
(\(=m\)). Preto ak by sme mali pevne
určený nejaký súčin \(k\), našou snahou
je maximalizovať súčet \(m\). Naopak,
ak by sme mali pevne určený nejaký súčet \(m\), našou snahou je dosiahnuť minimálny
súčin \(k\).
A my vieme, že rôznych súčtov \(m\) je málo. Ak pre každé možné \(m\) nájdeme minimálne \(k\), tak sme našli riešenie. Naskytá sa nám celkom štandardné riešenie dynamickým programovaním – stav je určený počtom kartičiek ktorým sme už určili typ a súčtom \(m\) týchto kartičiek. Pre každý stav si pamätáme minimálny súčin \(k\) pre zvyšné kartičky. V každom stave sa do ďalšieho stavu dostaneme určením typu ďalšej kartičky. Teda:
dp[i+1][m] = min(dp[i+1][m], dp[i][m] * k_i) # ak použijeme % kartičku
dp[i+1][m+m_i] = min(dp[i+1][m+m_i], dp[i][m]) # ak použijeme g kartičku
Poznámky k implementácii
Nakoniec, aby sme vedeli vypísať riešenie, musíme vedieť z tabuľky nejako vyčítať ako sme určovali kartičky. Toto si vieme v tabuľke buď priamo pamätať, alebo si to vieme v prípade tejto úlohy jednoducho spätne zistiť (keďže existujú iba dve možnosti), čo nám ušetrí pamäť a kúsok urýchli program (nie asymptoticky, ale iba konštantne).
Vieme ešte riešenie urýchliť? Mohli by sme veľkosť tabuľky ďalej zmenšiť tým, že jednotlivé riadky budú mať veľkosť iba doterajšieho súčtu gramáží kartičiek. Tomuto ďalej pomôžeme ak si kartičky na začiatku utriedime podľa gramáže, keďže v tomto prípade bude veľkosť tabuľky minimálna. Znova, nejde o asymptotické zlepšenie, ale vieme takto reálne program zrýchliť dvojnásobne.
Dynamiku neodporúčame kódiť v Pythone, keďže priamy prepis C++ do
Pythonu je často krát 100x pomalší. Dodatočnými optimalizáciami vieme
získať násobne zrýchlenia, ale môžeme byť šťastný keď sa dostaneme na
30x spomalenie. Ako malý tip povieme, že je oveľa rýchlejšie napísať
if x < y: y = x
než y = min(y, x)
.
V úlohách kde násobíme veľa desatinných čísel a záleží nám na presnosti sa väčšinou oplatí počítať si súčet logaritmov namiesto priameho súčinu. V tomto prípade to však nie je nutné, keďže násobíme maximálne \(40\) čísel, čo zvládneme presne uložiť do dostatočne veľkého dátového typu.
Zložitosť
Časová a pamäťová zložitosť je \(O(N \times \sum A_i) = O(N^2 \times MaxA)\). Vzorové riešenie v C++ zvláda vstupy aj pre \(N=100\).
Často upozorňujeme, že pamäťová zložitosť sa pri úlohách s dynamickým programovaním dá znížiť na veľkosť menšiu ako celkový počet stavov. Väčšinou to dosiahneme tak, že si pamätáme iba posledné dva riadky tabuľky. V tomto prípade si však v tabuľke okrem najlepšieho výsledku implicitne pamätáme aj cestu a teda ich nemôžeme zabudnúť! Alebo? V skutočnosti to je možné a dokonca bez toho aby sa nám zhoršila časová zložitosť. Viac informácií nájdete v tomto codeforces tutoriáli v poslednom odseku sekcie Store results only for two layers of DP state domain.
Uvedomme si, že všetky tri uvedené riešenie prehľadajú všetkých \(2^N\) možností. Prvý prístup naivne, druhý šikovne a tretí iba tak, že nevykonáva žiadnu robotu dva krát – dynamické programovanie pracuje iba na stavoch, ktoré sú relevantné a pre každý takýto stav si pamätá iba jeden výsledok. Toto je dôvod, prečo tieto riešenia fungujú, zatiaľ čo heuristiky a greedy riešenia nie.
= 1e18
INF = lambda x: 1 - x / 100
div
def solve():
= map(int, input().split())
N, X = [tuple(map(lambda s: int(s[:-1]), input().split())) for _ in range(N)]
C
= [[1.0]]
dp for ni in range(N):
= C[ni]
xm, xd * (len(dp[ni]) + xm))
dp.append([INF] = div(xd)
d for mi in range(len(dp[ni])):
if dp[ni][mi] == INF:
continue
+ 1][mi] = min(dp[ni + 1][mi], dp[ni][mi] * d)
dp[ni + 1][mi + xm] = min(dp[ni + 1][mi + xm], dp[ni][mi])
dp[ni
= (X, -1)
finish for mi, d in enumerate(dp[-1]):
= min(finish, (X * d - mi, mi))
finish
= finish[1]
mi = []
ans for ni in range(N - 1, -1, -1):
= C[ni][0]
xm = mi >= xm and dp[ni + 1][mi] == dp[ni][mi - xm]
card
ans.append((card, ni))-= card * xm
mi
ans.sort()for card, ni in ans:
print(ni + 1, "%g"[card])
= int(input())
TC for _ in range(TC):
solve()
#include <bits/stdc++.h>
using namespace std;
using ld = double;
const ld INF = 1e18;
template<typename T> void setmin(T &a, T b) { a = min(a, b); }
void solve() {
int N, X;
>> N >> X;
cin
<pair<int, int>> C(N);
vectorchar trash;
for (int i = 0; i < N; i++)
>> C[i].first >> trash >> C[i].second >> trash;
cin
<vector<ld>> dp(N + 1);
vector[0] = {1};
dpfor (int ni = 0; ni < N; ni++) {
auto [xm, xd] = C[ni];
[ni + 1].assign(dp[ni].size() + xm, INF);
dpauto d = 1 - (ld)xd / 100;
for (int mi = 0; mi < (int)dp[ni].size(); mi++) {
if (dp[ni][mi] == INF) continue;
(dp[ni + 1][mi], dp[ni][mi] * d);
setmin(dp[ni + 1][mi + xm], dp[ni][mi]);
setmin}
}
<ld, int> finish = {X, -1};
pairfor (int mi = 0; mi < (int)dp.back().size(); mi++)
(finish, {X * dp.back()[mi] - mi, mi});
setmin
<pair<bool, int>> ans;
vectorint mi = finish.second;
for (int ni = N - 1; ni >= 0; ni--) {
int xm = C[ni].first;
bool card = mi >= xm && dp[ni + 1][mi] == dp[ni][mi - xm];
.push_back({card, ni});
ans-= card ? xm : 0;
mi }
(ans.begin(), ans.end());
sort
for (auto [card, ni] : ans)
<< (ni + 1) << " " << "%g"[card] << '\n';
cout }
int main() {
.tie(0)->sync_with_stdio(0);
cinint TC; for (cin >> TC; TC--;) solve();
}
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ť.