Nemzetközi Informatikai Olimpia 1998

Dr. Astro Insky egy rádiócsillagász-központban dolgozik. A napokban rendkívül furcsa mikrohullámú impulzusokat észlelt. Lehet, hogy valamilyen földönkívüli intelligencia küldte

Feladat:

Segíts Dr. Inskynek, hogy eldönthesse, mi az igazság. Dr. Insky az észlelt impulzussorozatban meg akarja keresni a legtöbbször előforduló összes olyan részsorozatot (sablont), amelynek a hossza legalább A és legfeljebb B.
Az N darab legnagyobb előfordulási számot keressük.
A sablonok átfedhetik egymást. Csak azokat a sablonokat kell figyelembe venni, amelyek legalább 1-szer előfordulnak az észlelt sorozatban.

Bemenet:

A CONTACT.IN állomány az alábbi formában tartalmazza az adatokat:
Az első sorban van az A egész szám, a minimális sablonhossz.
A második sorban van a B egész szám, a maximális sablonhossz.
A harmadik sorban van az N egész szám, a különböző előfordulási számok darabszáma.
A negyedik sor a 0 és 1 karakterekből álló sorozat, amelyet egy 2 karakter zár.

Kimenet:

A CONTACT.OUT állományba legfeljebb N sort kell írni, az N legnagyobb előfordulási számot a hozzájuk tartozó sablonokkal.
A sorok az előfordulási szám szerint csökkenő sorrendben, az alábbi formában legyenek:

előfordulásiSzám  sablon sablon … sablon

ahol előfordulásiSzám az utána felsorolt sablonok előfordulásának számát jelenti.
A sablonok minden sorban a hosszuk szerint csökkenő sorrendben, az azonos hosszúak pedig numerikus értékük szerint csökkenő sorrendben szerepeljenek.
Ha N-nél kevesebb különböző előfordulási szám van, akkor az output értelemszerűen N-nél kevesebb sort tartalmaz.
 

Korlátok:

Az input állomány 2 Mbyte is lehet.
Az A, B és N paraméterekre az alábbi feltételek teljesülnek:
0 < N<= 20
0 < A <= B <= 12

Példa:
 

INPUT	OUTPUT
2 4 10 010100100100010001111011 000010100110011110000100 100111100100000002	23 00 15 10 01 12 100 11 001 000 11 10 010 8 0100 7 1001 0010 6 0000 111 5 1000 110 011 4 1100 0011 0001

Az IOI'98 díszvacsoráján N darab színes lámpát használnak, 1-től N-ig sorszámozva. A lámpasor 4 kapcsolóval működtethető.

1. kapcsoló – lenyomására az összes lámpa ellenkezőjére váltja állapotát: amelyik égett (ON), az kialszik (OFF), amelyik pedig nem égett (OFF), az kigyullad (ON).
2. kapcsoló – lenyomására az összes páratlan sorszámú lámpa ellenkezőjére váltja állapotát.
3. kapcsoló – lenyomására az összes páros sorszámú lámpa ellenkezőjére váltja állapotát.
4. kapcsoló – lenyomására az összes 3K+1 (K>=0), vagyis az 1,4,7,... sorszámú lámpa ellenkezőjére váltja állapotát.

A C számláló tartja nyilván a kapcsolások számát.
A vacsora kezdetén minden lámpa ég (ON) és a C számláló értéke 0.

Feladat:

Adott a C számláló értéke és a végállapotra előírt követelmény. A követelmény bizonyos kitüntetett lámpák állapota C számú kapcsolás elvégzése után.
Írj programot, amely meghatározza a lámpasor összes lehetséges különböző végállapotát, amelyekben a kezdeti állapotból indulva, C lehetséges kapcsolás után a végállapotra előírt követelmény teljesül.

Bemenet:

A PARTY.IN állományban 4 sor van.
Az első sorban a lámpák N száma, a második sorban a C számláló értéke van.
A harmadik sorban azoknak a kitüntetett lámpáknak a sorszáma van, amelyeknek a végállapotban égni kell, egy-egy szóközzel elválasztva, a felsorolás után –1 áll.
A negyedik sorban azoknak a kitüntetett lámpáknak a sorszáma van, amelyeknek a végállapotban nem szabad égni, egy-egy szóközzel elválasztva, a felsorolás után –1 áll.

Kimenet:

A PARTY.OUT állomány a követelményt teljesítő összes különböző végállapotot tartalmazza, soronként egyet. A kiírás sorrendje tetszőleges.

Minden sor pontosan N karaktert tartalmaz, a sorok első karaktere az első, utolsó karaktere pedig az N. lámpa állapotát írja le. A 0 (nulla) jelenti, hogy a lámpa nem ég (OFF), az 1 (egy) pedig azt, hogy ég (ON).

Korlátok:

Az N és C paraméterekre az alábbiak teljesülnek: (10<=N<=100, 1<=C<=10000)
A végállapotra vonatkozó követelményben (tehát az input állomány harmadik és negyedik sorában) legfeljebb 2-2 lámpa sorszáma szerepelhet.

Minden tesztre biztosan van legalább egy, a követelményeket kielégítő végállapot.

Példa:

 

PARTY.IN	PARTY.OUT
10 1 -1 7 -1	0000000000 0110110110 0101010101

Az éjszakai égbolton különböző csillagalakzatok láthatók. Egy alakzat szomszédos csillagok nem üres csoportja. A csillagok szomszédjai a körülöttük levő 8 helyen lehetnek (balra, jobbra, lent, fent, valamint átlósan 4 irányban). Egy alakzat sem lehet egy másik nagyobb alakzat része.

Az alakzatok hasonlíthatnak egymásra. Két alakzat hasonló, ha ugyanannyi csillagból állnak és forgatással vagy tükrözéssel egymásba alakíthatók.
Így minden alakzat 8 másikba transzformálható át. Ezt mutatja az 1. ábra.
 

***   ***     *   *  *  *    *  *  *  *  *       *   ***  *         *         ***  ***  ***  *      *  *  *  *    *  *    *    *  *    ***     *        *         ***

Az éjszakai égboltot egy csillagtérkép, egy 0 és 1 értékeket tartalmazó mátrix írja le. Ott van csillag, ahol a mátrixban 1-es található. A 0-val jelölt helyeken nincs csillag.

Feladat:

Adott egy csillagtérkép, amelyen a csillagokat az angol ábécé kisbetűivel kell megjelölni. A hasonló alakzathoz tartozó csillagokat azonos betűvel, a nem hasonlókhoz tartozókat pedig  különböző betűvel kell helyettesíteni.
Tehát minden alakzatot az 1-esek helyére írt kisbetűvel kell azonosítani.

Bemenet:

A STARRY.IN állomány első két sorában a csillagtérkép mérete van, az elsőben a W szélesség, a másodikban pedig a H magasság.
Az ezt követő H sorban, soronként pontosan W darab karakter írja le a csillagtérképet. (Közöttük nincs szóköz.)

Kimenet:

A STARRY.OUT állományba az átalakított csillagtérképet kell írni, amelyben az alakzatokban levő 1-esek helyére az alakzatot azonosító kisbetű kerül.

Korlátok:

0 <= W (a csillagtérkép szélessége) <= 100
0 <= H (a csillagtérkép magassága) <= 100
0 <= alakzatok maximális száma <= 500
0 <= a nem hasonló alakzatok maximális száma <= 26 (a..z)
1 <= az egy alakzatba tartozó csillagok  maximális száma <= 160

Példa:
 

POLYGON.IN	POLYGON.OUT
23 15 10001000000000010000000 01111100011111000101101 01000000010001000111111 00000000010101000101111 00000111010001000000000 00001001011111000000000 10000001000000000000000 00101000000111110010000 00001000000100010011111 00000001110101010100010 00000100110100010000000 00010001110111110000000 00100001110000000100000 00001000100001000100101 00000001110001000111000	a000a0000000000b0000000 0aaaaa000ccccc000d0dd0d 0a0000000c000c000dddddd 000000000c0b0c000d0dddd 00000eee0c000c000000000 0000e00e0ccccc000000000 b000000e000000000000000 00b0f000000ccccc00a0000 0000f000000c000c00aaaaa 0000000ddd0c0b0c0a000a0 00000b00dd0c000c0000000 000g000ddd0ccccc0000000 00g0000ddd0000000e00000 0000b000d0000f000e00e0b 0000000ddd000f000eee000
*   *          *   *****   *****   * ** *  *       *   *   ******          * * *   * ****      *** *   *      *  * *****  *      *    * *      *****  *      *      *   *  *****        *** * * * *   *       *  ** *   *     *   *** *****    *    ***       *      *   *    *   *  * *        ***   *   ***	a   a          b   aaaaa   ccccc   d dd d  a       c   c   dddddd          c b c   d dddd      eee c   c      e  e ccccc  b      e    b f      ccccc  a      f      c   c  aaaaa        ddd c b c a   a       b  dd c   c     g   ddd ccccc    g    ddd       e      b   d    f   e  e b        ddd   f   eee