Matematická olympiáda – kategorie P

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

Druhý soutěžní den - 25.4.1997

P-III-4

 Program: HRA.PAS/HRA.CPP

Hracím plánem je pás políček očíslovaných zleva doprava čísly 0, 1, 2, ... Na některých políčkách hracího plánu leží kamínek, celkový počet kamínků k je mezi 1 a 4. Pořadovým číslem kamínku rozumíme počet kamínků, které leží na hracím plánu vlevo od něho. První kamínek zleva má tedy pořadové číslo 0 a poslední k-1. Každou situaci hry můžeme popsat počtem kamínků a čísly políček, na nich jsou jednotlivé kamínky umístěny. Můžete předpokládat, že žádný kamínek neleží na políčku s číslem větším než 231-1. Koncovou situací hry je situace, v níž kamínky leží na políčkách 0, 1, ..., k-1.

Hru hrají dva hráči, kteří střídavě posouvají kamínky. V jednom tahu je povoleno posunout jeden z kamínků o libovolný počet políček při dodržení následujících pravidel:

V koncové situaci tedy není možné udělat žádný tah a hra končí. Vyhrává ten hráč, který provedl poslední tah. Můžete předpokládat, že hra nezačíná v koncové situaci.

Napište program (dále označovaný jako "hráč"), který bude hrát tuto hru, a to vždy jako začínající (tj. první na tahu). Druhého hráče bude zastupovat knihovna popsaná níže (dále označovaná jako "protivník"), kterou použijete ve vašem programu. Vaším úkolem je napsat program, který hraje co nejúspěšněji proti libovolnému protivníkovi (tj. proti každé knihovně splňující uvedený popis).

Knihovny jsou uloženy v souborech HRA_C.LIBT (pro C/C++), resp. HRA_P.TPU (pro Pascal). Knihovna obsahuje následující prostředky:

/* C/C++ */ #ifdef __cplusplus extern "C" { #endif #define MAXKAM 4 typedef long THraciPlan[MAXKAM]; void inicializuj (int* pocetKamienkov, THraciPlan hraciPlan); void mojKrok (int kamienok, long dlzkaKroku); void tvojKrok (int* kamienok, long* dlzkaKroku); #ifdef __cplusplus } #endif {Pascal} interface const MAXKAM = 4; type THraciPlan = array[0..MAXKAM-1] of longint; procedure inicializuj (var pocetKamienkov: integer; var hraciPlan: THraciPlan); procedure mojKrok (kamienok: integer; dlzkaKroku: longint); procedure tvojKrok (var kamienok: integer; var dlzkaKroku: longint); Funkce inicializuj inicializuje hru a vrátí počáteční situaci hry. V parametru pocetKamienkov vrátí počet kamínků na hracím plánu a v poli hraciPlan vrátí pozice jednotlivých kamínků, přičemž hraciPlan[i] je pozice kamínku s pořadovým číslem i, pro i=0,1,...,pocetKamienkov-1 (hodnoty ostatních prvků pole nejsou definovány).

Pomocí funkce mojKrok oznamujete protivníkovi svůj tah. V parametru kamienok odevzdáte pořadové číslo posouvaného kamínku a v parametru dlzkaKroku počet políček, o který posouváte zvolený kamínek. Pomocí funkce tvojKrok získáte naopak soupeřův tah, přičemž význam parametrů je stejný jako u funkce mojKrok.

Váš program na začátku výpočtu zavolá funkci inicializuj a potom střídavě volá funkce mojKrok a tvojKrok, přičemž začíná voláním funkce mojKrok. Můžete předpokládat, že protivník hraje korektně. Jestliže hráč provede vítězný tah, tzn. tah po němž nastane koncová situace, funkce mojKrok ukončí program. Jestliže naopak protivník svým tahem zvítězí, funkce tvojKrok ukončí program.

Pokud váš program nedodrží popsané pořadí volání procedur nebo pokud zadá nepovolený tah jako parametr funkce mojKrok, váš program prohrává. Ukončení programu před koncem hry je zakázáno.

Poznámky

  1. Pro potřeby ladění máte k dispozici jednoho protivníka. Tento protihráč načítá počáteční pozici ze souboru HRA.IN. Soubor obsahuje počet kamínků a jejich pozice.
  2. Váš program může být testován i s jinými protivníky.

P-III-5

 Program: KURU.PAS/KURU.CPP
Vstup: KURU.IN
Výstup: KURU.OUT

Ve starověkém městě Kuru objevili archeologové zvláštní trezor. Měl čtvery dveře. Dveře se musely otevřít ve správném pořadí, neboť jinak celou místnost zalila voda. Na každých dveřích bylo vytesáno nějaké zvíře. Na stěně archeologové rozluštili text tohoto znění:
Jako první otevři dveře, na kterých je buď lev nebo orel.
Jako druhé otevři dveře, na kterých je buď had nebo škorpión.
Jako třetí otevři dveře, na kterých je buď orel nebo had.
Jako druhé otevři dveře, na kterých je buď lev nebo had.
Budeme-li předpokládat, že všechna tato tvrzení jsou pravdivá, můžeme určit správné pořadí otvírání dveří. Z druhého a čtvrtého tvrzení vyplývá, že jako druhé je třeba otevřít dveře s hadem. Z třetího tvrzení a z faktu, že had je na druhých dveřích, plyne, že orel je na třetích dveřích. Z prvního tvrzení a z faktu, že orel je na třetích dveřích, vyplývá, že lev je na prvních dveřích. Pro škorpióna zůstaly čtvrté dveře.

Napište co nejefektivnější program, který bude řešit takovýto typ hlavolamů. Je dán počet dveří n (1 <= n <= 1000). Na každých dveřích je vytesané jiné zvíře, přičemž tato zvířata označíme čísly od 1 do n. Dále je dáno číslo m (1 <= m <= 1000) a m tvrzení, z nichž každé může mít jeden z dvou možných tvarů:

  1. Jako i-té je třeba otevřít dveře, na nichž je zvíře j, kde 1<=i,j<=n. Toto tvrzení budeme kódovat trojicí čísel 1 i j.
  2. Jako i-té je třeba otevřít dveře, na nichž je buď zvíře j nebo zvíře k, kde 1<=i,j,k<=n, j<>k. Toto tvrzení budeme kódovat čtveřicí čísel 2 i j k.
Řešením hlavolamu je takové pořadí otvírání dveří, ve kterém se každé dveře vyskytnou právě jednou a které vyhovuje všem zadaným tvrzením.

Vstupní soubor

Vstupní soubor KURU.IN obsahuje několik hlavolamů. První řádek souboru je tvořen jediným číslem určujícím počet hlavolamů v souboru. Pro každý hlavolam obsahuje vstupní soubor blok údajů. Na prvním řádku bloku jsou uvedena čísla n a m. Každý z dalších m řádků obsahuje kód jednoho tvrzení. Jednotlivé bloky údajů jsou odděleny vždy jedním prázdným řádkem.

Výstupní soubor

Program vypíše do výstupního souboru KURU.OUT pro každý hlavolam jeden řádek, který bude obsahovat:
Řešením je posloupnost čísel zvířat vytesaných na dveřích v takovém pořadí, v jakém je třeba dveře otvírat. Čísla jsou na řádku oddělena vždy jednou mezerou.

Příklad

Soubor KURU.IN

2 4 4 2 1 1 2 2 2 4 3 2 3 2 4 2 2 1 4 3 1 1 1 2

Soubor KURU.OUT

1 4 2 3 Vice reseni