Matematická olympiáda – kategorie P

Zadání úloh ústředního kola (2. soutěžní den) 57. ročníku

P-III-4 Sbírka čísel

Program:	sbirka.pas / sbirka.c / sbirka.cpp
Vstup:	sbirka.in
Výstup:	sbirka.out

Pan Pterodaktylos je sběratelem. Vášnivým a takříkajíc univerzálním. Sbírá úplně všechno: známky, motýly, známky s obrázky motýlů, ba dokonce i všechna přirozená čísla. Těch má několik zvláště vydařených sbírek.

Každá sbírka čísel je určena parametry B a D a obsahuje všechna nezáporná celá čísla, která se dají zapsat v soustavě o základu B pomocí nejvýše D číslic.^*Připomeňme, že zápis x_k-1...x₀, x_i∈{0,...,B-1}, v soustavě o základu B představuje číslo ∑_i=0^k-1 x_i Bⁱ. Tato čísla jsou ve sbírce seřazena důmyslným způsobem: nejprve vzestupně podle svého ciferného součtu a uvnitř každé skupiny se stejným ciferným součtem pak vzestupně podle hodnoty čísel. Například sbírka označená parametry B=3, D=2 obsahuje nejvýše dvouciferná čísla v trojkové soustavě, a to v následujícím pořadí: 0; 1, 10; 2, 11, 20; 12, 21; 22 (středníkem jsou odděleny bloky čísel se stejným ciferným součtem).

Pro větší hodnoty B a D je taková sbírka dosti rozsáhlá. Pokud pan Pterodaktylos chce ze sbírky vytáhnout k-té číslo v pořadí, čeká ho obvykle dlouhá cesta mezi kilometry regálů, než se k němu dostane. Vás napadlo, že to vůbec není potřeba – když víte, že sbírka obsahuje opravdu všechna čísla, lze k-té číslo v pořadí snadno spočítat.

Úloha

Napište program, který dostane parametry B a D sbírky čísel a číslo k a odpoví k-tým číslem ve sbírce.

Vstup

Vstupní soubor sbirka.in obsahuje jediný řádek, na němž jsou zapsána tři čísla oddělená mezerami: základ soustavy B (2≤B≤10), délka čísla D (1≤D≤30) a pořadí hledaného čísla (1≤k≤10¹⁸). Můžete se spolehnout na to, že všechna čísla ve sbírce jsou menší než 10¹⁸.

Výstup

Výstupní soubor sbirka.out obsahuje jediný řádek a na něm k-té číslo sbírky zapsané v soustavě o základu B. Nevýznamné nuly na začátku čísla nevypisujte.

Příklad 1

sbirka.in
3 2 5
sbirka.out
11 (viz příklad sbírky výše)

Příklad 2

sbirka.in
10 15 999999999999998
sbirka.out
999999999999989

P-III-5 Strouhání mrkve

Program:	mrkev.pas / mrkev.c / mrkev.cpp
Vstup:	mrkev.in
Výstup:	mrkev.out

Jak zajíček Hopsálek stárnul, začaly mu padat zuby. Dostal sice pěknou zubní protézu, ale už si nemohl pochutnávat na své oblíbené mrkvi. Rozhodl se tedy, že začne provozovat továrnu na strouhání mrkve. Do továrny pak může přijít zaječí důchodce a mrkev mu tam nastrouhají, aby si na ní mohl pochutnat i v pokročilém věku.

Hopsálek plánuje, že továrna bude fungovat na směny. Každá směna bude trvat přesně M minut a směny budou následovat bezprostředně jedna za druhou. První směna musí začít v jedné z prvních M minut provozu.

Továrna pracuje jenom tehdy, když do ní přijde nějaký (za)ječící důchodce. Pokud víme, že v průběhu celé směny nepřijde ani jeden, můžeme směnu zrušit a tím ušetřit.

Úloha

Zjistili jste přesně, v jakých minutách budou do továrny chodit mrkvechtiví důchodci. Mrkev stihnou zaměstnanci továrny nastrouhat ještě v té minutě, kdy ji zákazník přinesl. Vaším úkolem je zjistit, kterou z prvních M minut má začít první směna, aby bylo směn, ve kterých se v továrně pracuje, co nejméně.

Vstup

Na prvním řádku vstupního souboru mrkev.in jsou dvě mezerou oddělená přirozená čísla M a N (1≤M,N≤1000000). M je délka trvání každé směny v minutách, N je počet zaječích seniorů, kteří si přijdou nechat nastrouhat mrkev. Na druhém řádku je mezerou oddělených N přirozených čísel z₁ < z₂ < ...< z_N – čísla minut příchodů zaječích zákazníků. Všechna z_i splňují M < z_i < 2000000000 a minuty jsou číslovány od jedné.

Výstup

Na první řádek výstupního souboru mrkev.out vypište jedno přirozené číslo S – nejmenší počet směn, ve kterých se musí v továrně pracovat, tj. těch, které nebudou zrušeny. Na druhý řádek vypište, kterou minutou musí začínat první směna, aby bylo třeba pracovat jenom S směn. Pokud je možností více, vypište všechny v rostoucím pořadí oddělené právě jednou mezerou.

Příklad 1

Vstup
5 4
7 8 14 16

Výstup
2
2 4

Šedivou barvou jsou označeny příchody zaječích stařešinů. Spodní dva řádky znázorňují dvě optimální řešení, černé jsou směny, ve kterých se v továrně pracuje.

Příklad 2

Vstup
5 4
7 9 14 17

Výstup
3
1 2 3 4 5

V této situaci jsou všechny možné začátky stejně dobré. Nezapomeňte na to, že je musíte vypsat setříděné.