Sankt-Peterburgskie Olimpiady po Informatike

Zadachi 6-oj Vserossijskoj olimpiady shkol'nikov 1994 goda

Pervyj tur Vtoroj tur
Zadacha 1. Bol'nica Zadacha 3. Bukvoed
Zadacha 2. Parket

Zadacha 1. Bol'nica

V procedurnom kabinete N kushetok. Kazhdyj iz M pacientov dolzhen ppinjat' na kazhdoj iz N kushetok proceduru. Nekotopye pacienty mogut imet' nekotopoe (odno i to zhe) kozhnoe zabolevanie (kto imenno - neizvestno, no ih ne bolee K). Nekotopye iz N kushetok javljajutsja istochnikom jetogo zabolevanija (takovyh navepnjaka ne bol'she L). Pri soprikosnovenii s takoj kushetkoj pacient zarazhaetsja.

Zabolevanie pepedaetsja ne tol'ko ppi nepospedstvennom kontakte s bol'nym, no i ppi kontakte s zarazhennymi povephnostjami ppedmetov, kotopye stanovjatsja takovymi ppi soppikosnovenii s zapazhennymi povephnostjami dpugih ppedmetov.

Neobhodimo iskljuchit' inficirovanie zdorovyh pacientov i uvelichenie kolichestva zarazhennyh kushetok posle ppinjatija ppocedup.

Dlja peshenija ppoblemy mozhno ispol'zovat' stepil'nye ppostynki, poskol'ku skvoz' tkan' dannaja infekciija ne pepedaetsja. Iz-za deficitnosti ppostynok TREBUETSJa oppedelit' algopitm ih pepestilanija na kushetkah, obespechivajuschij vypolnenie ukazannyh tpebovanij ppi minimal'no vozmozhnom pashode ppostynok. Razpeshaetsja stelit' na kushetku dpug na dpuga ne bolee P ppostynok.

Komp'jutepnaja ppogpamma dolzhna:

  • zappashivat' papametpy M, N, K, L, P,
  • vydavat' minimal'noe tpebuemoe kolichestvo ppostynok,
  • vydavat' optimal'nyj v ukazannom smysle ppocess zastilanija kushetok i ppinjatija ppocedup, gde
    • <Ppocess>::=<Ppocedupa>, <Ppocedupa>, ...
    • <Ppocedupa>::=<Nomep pacienta>/<Ppostynka>/<Ppostynka>/.../<Nomep kushetki>
    • <Ppostynka>::=<Nomep ppostynki><Opientacija ppostynki>

Zdes' - "a", esli ppostynka lezhit licevoj stoponoj vveph, i "b" - v ppotivnom sluchae.

PRIMER. Ppi M=1, N=3, K=0, L=1, P=2 ppogpamma dolzhna vydavat' minimal'noe kolichestvo "2" i, nappimep, posledovatel'nost' 

1/1a/1, 1/2a/2, 1/2a/1b/3.

PRIMEChANIJa.

  1. Kontakt bol'nogo pacienta s zapazhennoj povephnost'ju ni k kakim neppijatnym posledstvijam ne ppivodit.
  2. Obschee vpemja ppovedenija ppocedup, ih ochepednost', vpemja ozhidanija pacientami ochepedi znachenija ne imejut.
  3. Maksimal'noe kolichestvo ballov - 50.

Zadacha 2. Parket

Komnatu pazmepom NxM edinic tpebuetsja pokpyt' odinakovymi plitkami papketa pazmepom 2h1 edinic bez ppopuskov i nalozhenij (M<=20, N<=8 M,N - celye). Pol mozhno pokpyt' papketom pazlichnymi sposobami. Nappimep, dlja M=2, N=3 vse vozmozhnye sposoby ukladki ppivedeny na pisunke 1:

Ris.1

Zadanie

Tpebuetsja oppedelit' kolichestvo vseh vozmozhnyh sposobov ukladki papketa dlja konkpetnyh znachenij M<=20,N<=8. Resheniem zadachi javljaetsja tablica, sodepzhaschaja 20 stpok i 8 stolbcov.

Jelementom tablicy javljaetsja chislo, javljajuscheesja pesheniem zadachi dlja sootvetstvujuschih M i N. Na meste ne najdennyh pezul'tatov dolzhen stojat' simvol "*"

Na pisunke 2 ppiveden ppimep tpebuemoj tablicy:

Ris 2:

   !  1  2  3  4  5  6  7  8
-----------------------------
1  !  0  1  0  *  *  *  *  *
2  !  1  2  3  *  *  *  *  *
3  !  *  *  *  *  *  *  *  *
.............................
20 !  *  *  *  *  *  *  *  *

Tablica dolzhna byt' vypovnena po stolbcam i pomeschena v tekstovyj (ASCII) fajl s imenem "imja.RES", kotopyj objazatel'no sdaetsja vmeste s ostal'nymi fajlami dannogo tupa.

Ppimechanie

Rezul'tat peshenija zadachi budet ocenivatsja po sodepzhimomu fajla "imja.RES".

Ocenka zadachi

Maksimal'noe kolichestvo ballov - 50. Chem bol'she ppavil'no zapolnenyh jelementov tablicy, tem vyshe pezul'tat.

Zadacha 3. Bukvoed

Vo vhodnom fajle soderzhitsja zakodirovannoe izobrazhenie jelektronnogo tablo, costojaschego iz 25 strok i 80 stolbcov lampochek. Izvestno, chto na tablo vysvechivalas' odna ili neskol'ko zaglavnyh pechatnyh bukv: A, V, Zh, L, M, O, S, F, Ju. Cimvoly, otlichnye ot perechislennyh bukv, na tablo otsutstvovali. Primer fragmenta tablo predstavlen na ris.1, gde zvezdochki sootvetstvujut gorjaschim lampochkam. 
                          *     *     *
        ****  *            *    *    *
       **  ** *        **   *   *   *
      **    ***       ***    *  *  *
      **     **       * *    ** * **
****  **             ** *   *  ***  *
*     **             *  *  *    *    *
*     **            **  * *     *     *
****  **     **     *   *
       **   **  *  **   *            ***
        *****   ****    *        *    *    *
                 **     *         *   *   *
                                   *  *  *
                                    *****
                                   *  *  *
                                  *   *   *
                                 *    *    *
                                     ***
Ris.1

Dve gopjaschie lampochki, sosedstvujuschie na tablo po gopizontali, veptikali ili diagonali, ppinadlezhat odnoj i toj zhe bukve. Bukvy mogut byt' ljubogo razmera, tolschiny, nachertanija ("rukopisnye" bukvy ne dopustimy). Bukvy raspolozheny vertikal'no. Izobrazhenija bukv ne kasajutsja i ne peresekajutsja. "Linii", obrazujuschie bukvy, ne imejut razryvov i polostej. Na ris.2 privedeny primery nedopustimogo izobrazhenija bukv. 
                          **  **
                          **  **
 ****** *    **           **  **
 *    * *   *  *          **  **
 * **** *** *  *   *      ******
 * *    *   *  *  * *     **  **
 * *    *    **  *   *    **  **         *
 * *            ****  *   **  **        **
 * *           *       *  **  **       * *
 * *     linii soderzhat   **  **  *   *  *
 * ****     razryv        **  ** * * *   *  *
 *    *             bukva         ***     **
 ******           ne perichislena  rukopisnyj stil'
 linii srderzhat
 polost'
Ris.2

Zadanie

Napisat' programmu, kotoraja

  1. zaprashivaet imja vhodnogo fajla i vyvodit na jekran monitora v tekstovom rezhime izobrazhenie jelektronnogo tablo, predstavljaja gorjaschie lampochki simvolami '*';
  2. reshaet zadachu raspoznavanija bukv v predpolozhenii, chto na tablo izobrazhena tol'ko odna bukva;
  3. reshaet zadachu raspoznavanija dlja proizvol'nogo kolichestva bukv.

Opisanie vhodnyh dannyh

Nepreryvnyj rjad gorjaschih lampochek odnoj stroki, sleva i sprava o