Zadání úloh ústředního kola (2. soutěžní den) 52. ročníku
P-III-4 Poklad kapitána Flinta
Program: poklad.pas /
poklad.c /
poklad.cpp
Vstup: poklad.in
Výstup: poklad.out
Kapitán Flint si při svých pirátských výpravách přišel k docela pěkné hromádce
zlaťáků. Pirátské výpravy jsou však dosti nejisté a štěstěna vrtkavá, a proto
kapitán zakopal část svého jmění na pustém ostrově a cestu k pokladu zakreslil
na ovčí kůži ve tvaru konvexního N-úhelníka. Celou mapu pak rozřezal na mnoho
částí, přičemž každý řez vedl přímo mezi dvěma vrcholy mnohoúhelníka a žádné
dva řezy se neprotínaly. Aby si pojistil věrnost posádky svého škuneru, rozhodl
se Flint některé části darovat nejzdatnějším pirátům. Protože by se ale
námořníci mohli snadno dohodnout, mapu sestavit a poklad vykopat, chce mezi ně
kapitán rozdělit části mapy tak, aby žádní dva námořníci neměli sousední díly.
Přitom chce mezi námořníky rozdělit co nejvíce částí mapy. Dokázali byste
napsat program, který pomůže kapitánovi vyřešit jeho problém?
Formát vstupu
Na prvním řádku vstupního souboru
poklad.in dostane program dvě celá
čísla N a M oddělená mezerou, 3<=N<=30 000, 0<=M<=30 000
- počet vrcholů mapy a počet řezů. Následuje M řádků popisujících
jednotlivé řezy. Každý z těchto řádků obsahuje dvě čísla A a B oddělená
mezerou - čísla vrcholů, mezi kterými vede řez (vrcholy číslujeme od jedné
do N).
Formát výstupu
Výstupní textový soubor
poklad.out bude obsahovat jediné číslo udávající
maximální počet částí mapy, které lze mezi námořníky rozdělit tak, aby žádní
dva námořníci neměli sousední díly mapy.
Příklad
poklad.in
5 2
1 3
3 5
poklad.out
2
P-III-5 Vážení
Program: vahy.pas /
vahy.c /
vahy.cpp
Vstup: vahy.in
Výstup: vahy.out
Mudrc Tlučhuba se přihlásil do konkurzu na královského rádce v jednom
nejmenovaném království. Vzápětí však byl zaskočen podmínkami
tohoto konkurzu: Jako test svých schopností obdrží N mincí,
z nichž některé mají různou a některé stejnou hmotnost. Jeho úkolem
bude tyto mince rozdělit do skupin tvořených mincemi stejné hmotnosti a
tyto skupiny pak seřadit vzestupně podle hmotností mincí tak,
aby v první skupině byly nejlehčí mince a
v poslední skupině byly nejtěžší mince.
Bude mít k dispozici dvouramenné váhy, na jejichž misky smí
v jednom okamžiku položit po jedné minci.
Mudrc Tlučhuba vás požádal o pomoc při plnění tohoto úkolu.
Chtěl by, abyste vytvořili
program, jenž mu pomůže při rozhodování, které mince zvážit,
jak mince rozdělit do skupin a jak vytvořené skupiny uspořádat.
Pro účely programu si mince očíslujeme od 1 do N.
Samotné vážení bude ve vašem
programu zastoupeno funkcí porovnej.
Mudrc Tlučhuba musí úkol splnit v časovém limitu, který mu byl
stanoven (tedy v něm musí úkol splnit i váš program).
Kromě toho musí provést všechna nezbytná vážení, tj. nesmí
existovat dvě či více možných řešení konzistentních s odpověďmi
funkce porovnej, jinak by byl mudrc upálen jako čarodějník (jak
jinak by mohl vědět, které uspořádání je správné?).
Na druhou stranu nesmí být provedeno žádné zbytečné vážení,
tj. takové, jehož výsledek by již (přímo či nepřímo) vyplýval
z předchozích odpovědí funkce porovnej.
Popis funkce porovnej
Funkce
porovnej je definována v knihovně
vahy_lib. Váš program
musí obsahovat následující řádek, aby mohl používat funkci
porovnej:
Pascal:
uses vahy_lib;
C/C++:
#include "vahy_lib.h"
Funkce
porovnej je deklarována takto:
Pascal:
function porovnej(a,b: longint): integer;
C/C++:
int porovnej(int, int);
Tato funkce očekává jako vstupní parametry čísla dvou mincí.
Vrátí hodnotu -1, pokud mince odpovídající prvnímu parametru je
lehčí než mince odpovídající druhému parametru, +1, pokud je tomu
naopak, a 0, pokud obě mince mají stejnou hmotnost.
Nezapomeňte, že váš program nesmí funkci porovnej volat zbytečně,
tj. výsledek žádného volání funkce porovnej nesmí
vyplývat (tedy být jednoznačně určen) z předchozích volání této funkce.
Např. pokud jsme voláním funkce porovnej zjistili, že mince
s číslem 1 je lehčí než mince s číslem 2 a že mince s číslem 2 je lehčí
než mince s číslem 3, nelze již funkci porovnej zavolat
s parametry 1 a 3. Kromě toho,
váš program může funkci porovnej zavolat nejvýše 250 000-krát.
Formát vstupu
Vstupní soubor
vahy.in obsahuje jediný řádek s jediným číslem
N, 1<=N<=10 000, které udává počet mincí.
Formát výstupu
Výstupní soubor vahy.out
musí obsahovat K řádků, kde K je počet různých
hmotností mincí. Na každém řádku budou uvedena čísla mincí téže
hmotnosti v rostoucím pořadí. Hmotnosti mincí jednotlivých řádků
tvoří rovněž rostoucí posloupnost, tzn. první řádek obsahuje
všechny nejlehčí mince a poslední řádek všechny nejtěžší mince.
Příklad
vahy.in
4
Průběh komunikace:
Volání porovnej(2,4) vrací -1.
Volání porovnej(1,2) vrací 1.
Volání porovnej(3,4) vrací -1.
Volání porovnej(1,3) vrací 0.
vahy.out
2
1 3
4