International Olympiad in Informatics 2011 22–29 July 2011, Pattaya City, Thailand Soutěžní úlohy – Den 2
PARROTS Czech 1.3
Papoušnet Není většího ptačího nadšence, než Yanee. Není tedy divu, že poté, co si přečetla článek IP over Avian Crarriers (IPoAC), se bezhlavě vrhla do výcviku hejna papoušků, kteří by efektivně nahradili její stávající pomalé internetové připojení. Aby toho mohla dosáhnout, potřebuje pomocí papoušků umět přenést zprávu M, která se skládá z posloupnosti N (ne nutně různých) celých čísel v intervalu 0 až 255 včetně. Dosud se jí podařilo vycvičit K papoušků, kteří se umí naučit papouškovat libovolné číslo v intervalu 0 až R včetně. Nejdříve vyzkoušela brát jednotlivé papoušky, každého naučit papouškovat odpovídající číslo ze zprávy, a vyslat je do cíle v pořadí, které odpovídá pořadí čísel ve zprávě. Bohužel se ukázalo, že tento postup nefunguje. Papoušci sice do cíle dorazili, ale ne v tom pořadí, v jakém je Yanee vypustila. Takže ačkoliv bylo možné zrekonstruovat všechna čísla původní zprávy, nebylo možné zrekonstruovat jejich pořadí. Nezbývá jí tedy nic jiného, než vymyslet lepší postup. Resp. nechat si od vás lepší postup poradit. Nerada by ale papoušky přeučovala to, co už umí, takže by potřebovala program, který provádí dvě samostatné operace: •
První operace by měla umět přečíst zprávu M a transformovat ji do posloupnosti nejvýše K celých čísel v intervalu 0 až R včetně, která pak naučí jednotlivé papoušky papouškovat.
•
Druhá operace by měla umět přečíst seznam celých čísel v intervalu 0 až R včetně tak, jak byla nadiktována papoušky v místě jejich příletu, a převést tento seznam zpět na původní zprávu M.
Můžete předpokládat, že každý vypuštěný papoušek vždy dorazí do cíle a že přenese právě to číslo, které se naučil. Papoušci ale mohou do cíle přilétat v jakémkoliv pořadí. Připomeňme, že Yanee má pouze K papoušků, takže sekvence celých čísel v intervalu 0 až R včetně, kterou odešlete, musí být dlouhá nejvýše K.
Váš úkol Naimplementujte dvě samostatné procedury. Jedna z nich bude použita pro odesílání zpráv jako enkodér a druhá pro jejich příjem jako dekodér. Celý proces je zachycen na následujícím obrázku:
Vaším úkolem je naimplemetovat následující procedury: • encode(N, M) s následujícími parametry: Strana 1 z 5
International Olympiad in Informatics 2011 22–29 July 2011, Pattaya City, Thailand Soutěžní úlohy – Den 2
PARROTS Czech 1.3
• N – délka zprávy. • M – jednorozměrné pole celých čísel reprezentující zprávu. Můžete předpokládat, že pro všechna i (0 ≤ i < N) platí, že 0 ≤ M[i] ≤ 255. Tato procedura musí zakódovat zprávu M do posloupnosti celých čísel v intervalu 0 až R včetně, která bude přenesena pomocí papoušků. Pro odeslání této sekvence musí procedura encode volat proceduru send(a) pro každé číslo, které si přejete poslat po některém z papoušků. • decode(N, L, X) s následujícími parametry: • N – délka původní zprávy. • L – počet čísel, která byla přijata (resp. počet papoušků, které Yanee vypustila). • X – jednorozměrné pole L celých čísel, reprezentující přijatá čísla. Čísla X[i] (0 ≤ i < L) jsou stejná čísla, která odeslala vaše procedura encode, ale mohou být ve zcela odlišném pořadí. Tato procedura musí zrekonstruovat původní zprávu. Pro výpis této zprávy musí vaše procedura volat proceduru output(b), pro každé celé číslo b v původní zprávě, tato volání musí být samozřejmě ve správném pořadí. Všimněte si, že čísla R ani K nejsou předána jako parametry, viz popis jednotlivých podúloh. Pro korektní vyřešení daných podúloh, musí vaše procedury splňovat následující podmínky: • Všechna čísla odeslaná procedurou encode musí být v rozsahu, který je specifikovaný v podúloze. • Počet volání funkce send nesmí překročit limit K specifikovaný v podúloze. Připomeňme, že K závisí na délce zprávy. • Procedura decode musí správně zrekonstruovat původní zprávu M a počet volání procedury output(b) musí být přesně N s tím, že b je postupně rovné číslům M[0], M[1], ..., M[N-1]. V poslední podúloze závisí přidělený počet bodů na poměru mezi počtem papoušků potřebných na přenos zprávy a délkami těchto zpráv.
Příklad Uvažute případ, kdy N = 3, 10 M= 30 20 Procedura encode(N,M), za pomocí černé magie a několika kouzelných krabiček, může enkódovat zprávu do posloupnosti čísel (7, 3, 2, 70, 15, 20, 3). Pro odeslání této posloupnosti by tedy měla zavolat proceduru send následovně: send(7) send(3) Strana 2 z 5
International Olympiad in Informatics 2011 22–29 July 2011, Pattaya City, Thailand Soutěžní úlohy – Den 2
PARROTS Czech 1.3
send(2) send(70) send(15) send(20) send(3) Jakmile všichni papoušci dosáhnou cíle, dostaneme např. následující seznam přijatých čísel: (3, 20, 70, 15, 2, 3, 7). Procedura decode poté bude zavolána s parametry N=3, L=7, 3 20 70 X= 15 2 3 7 Procedura, tentokrát pomocí bílé magie a několika křišťálových koulí, zrekonstruuje původní zprávu (10, 30, 20) a odešle ji na výstup pomocí následujících volání procedury output: output(10) output(30) output(20)
Podúlohy Podúloha 1 (17 bodů) • N = 8 a každé číslo v poli M je 0 nebo 1. • Každé odeslané číslo musí být v intervalu 0 až R=65535 včetně. • Počet volání procedury send musí být nejvýše K=10×N.
Podúloha 2 (17 bodů) • 1 ≤ N ≤ 16 • Každé odeslané číslo musí být v intervalu 0 až R=65535 včetně. • Počet volání procedury send musí být nejvýše K=10×N.
Podúloha 3 (18 bodů) • 1 ≤ N ≤ 16 • Každé odeslané číslo musí být v intervalu 0 až R=255 včetně. • Počet volání procedury send musí být nejvýše K=10×N.
Strana 3 z 5
International Olympiad in Informatics 2011 22–29 July 2011, Pattaya City, Thailand Soutěžní úlohy – Den 2
PARROTS Czech 1.3
Podúloha 4 (29 bodů) • 1 ≤ N ≤ 32 • Každé odeslané číslo musí být v intervalu 0 až R=255 včetně. • Počet volání procedury send musí být nejvýše K=10×N.
Podúloha 5 (až 19 bodů) • 16 ≤ N ≤ 64 • Každé odeslané číslo musí být v intervalu 0 až R=255 včetně. • Počet volání procedury send musí být nejvýše K=15×N. • Důležité: Přidělený počet bodů za tuto podúlohu závisí na poměru mezi počty volání procedury send a délkami odpovídajících zpráv. • Pro každý testovací vstup t v této podúloze označme jako Pt=Lt/Nt poměr mezi počtem volání procedury send Lt a délkou původní zprávy Nt. Dále označme jako P maximum ze všech Pt. Celkový bodový zisk bude určen následujícími pravidly: Pokud P ≤ 5, dostanete plný počet bodů, tj. 19 bodů. Pokud 5 < P ≤ 6, dostanete 18 bodů. Pokud 6 < P ≤ 7, dostanete 17 bodů. Pokud 7 < P ≤ 15, dostanete 1+2×(15-P) bodů. Počet bodů bude zaokrouhlen dolů k nejbližšímu celému číslu. • Pokud P > 15 nebo jakýkoliv z výstupů bude nesprávný, dostanete 0 bodů. • Důležité: Jakékoliv korektní řešení pro podúlohy 1 až 4 vyřeší správně i všechny předchozí podúlohy. To ale, kvůli vyšší hranici pro K, neplatí pro podúlohu 5, neboť korektní řešení pro tuto podúlohu nemusí být schopné vyřešit podúlohy 1 až 4. Je ale možné vyřešit všechny podúlohy jedním programem. • • • •
Implementační detaily Limity • Vyhodnocovací prostředí: Ve skutečném vyhodnocovacím prostředí bude vaše řešení přeloženo do dvou programů e a d a ty budou spuštěny odděleně. Moduly encoder i decoder budou slinkovány dohromady, ale pouze e zavolá metodu encode a pouze d zavolá decode. • Časový limit: Program e zavolá 50krát proceduru encode a měl by skončit do 2 sekund. Program d zavolá 50krát proceduru decode a měl by skončit do 2 sekund. • Paměťový limit: 256 MB Poznámka: Není žádný explicitní limit pro velikost zásobníku programu. Jeho velikost se počítá do celkově spotřebované paměti.
Rozhraní (API) • Složka s implementací: parrots/ Strana 4 z 5
International Olympiad in Informatics 2011 22–29 July 2011, Pattaya City, Thailand Soutěžní úlohy – Den 2
PARROTS Czech 1.3
• Účastníci mají implementovat: • encoder.c nebo encoder.cpp nebo encoder.pas • decoder.c nebo decoder.cpp nebo decoder.pas Poznámka pro programátory v C/C++: v ukázkovém i ve finálním vyhodnocovači jsou encoder.c[pp] i decoder.c[pp] slinkovány dohromady s vyhodnocovačem. Proto byste měli všechny globální proměnné v každém zdrojovém souboru deklarovat jako statické, abyste předešli pomíchání proměnných z různých souborů. • Rozhraní pro účastníky: encoder.h nebo encoder.pas decoder.h nebo decoder.pas • Rozhraní vyhodnocovače: encoderlib.h nebo encoderlib.pas decoderlib.h nebo decoderlib.pas • Ukázkový vyhodnocovač: grader.c nebo grader.cpp nebo grader.pas Ukázkový vyhodnocovač provádí dva kroky. V každém kroku zavolá encode se vstupními daty a následně zavolá decode s daty, která encode odeslala. V prvním kroku pořadí odeslaných čísel nemění, zatímco ve druhé navzájem prohodí odeslaná čísla na sudý a lichých pozicích. Skutečný vyhodocovač provádí různé druhy permutací nad odeslanými čísly. Samozřejmě můžete libovolně měnit způsob, kterým se permutace dat v ukázkovém vyhodnocovači provádí editací procedury shuffle (v C/C++) resp. Shuffle (v Pascalu). Ukázkový vyhodnocovač rovněž kontroluje rozsah i délku odeslaných dat. Implicitně kontroluje, zda jsou všechna odeslaná čísla v rozsahu 0 až 65535 a zda je jejich počet nejvýše 10×N. Toto chování může změnit editací konstant channel_range (např. z 65535 na 255) a max_expansion (např. z 10 na 15 nebo 7). • Ukázkové vstupy pro vyhodnocovač: grader.in.1, grader.in.2, ... Poznámka: Ukázkový vyhodnovač čte vstupy v následujícím formátu: • Řádek 1: N • Řádek 2: Seznam N čísel M[0], M[1], ..., M[N-1] • Očekávaný výstup pro vzorové vstupy je v souborech: grader.expect.1, grader.expect.2, … V této úloze každý z těchto souborů obsahuje text „Correct.“.
Strana 5 z 5
