Közép-európai Informatikai Olimpia 1994

A grafikus képernyőt a következőképpen kódoljuk: A képernyő egy részét négy részre osztjuk és a részeket a bal felső negyedtől az óramutató járásával egyező irányban az 1, 2, 3, 4 számokkal jelöljük. Nevezzük az így kódolt négyzeteket normalizált négyzeteknek!

Egyszerű kép:

---

Összetett kép:

Ha az összetett ábrán a X betűvel jelzett téglalapot a +-szal jelölt helyére akarjuk mozgatni, akkor négyszer kell lefelé és kétszer jobbra eltolni.

Feladat:

Írj programot, amely adott négyzeten képes elvégezni az eltolásokat.

Bemenet:

A SQUARE.DAT állomány kétsoronként egy-egy tesztesetet tartalmaz. Az első sor a normalizált négyzet kódját foglalja magába (a sor csak az 1, 2, 3, 4 számjegyeket tartalmazza. (Az egyes adatsorozatokban a számjegyek száma legfeljebb 35.) A második sor egy eltolássorozat leírását tartalmazza (L=left, R=right, D=down, U=up). Az állományt egy üres sor zárja.

Kimenet:

A SQUARE.RES fájlba az eltolások eredményeként kapott négyzet kódját kell beírni. Amennyiben az eltolások eredményeként a szabott területen kívülre kerülünk, az OUT OF THE BORDER sort kell írni. Az eredménysorokat egy-egy üres sor válassza el!

Példa:
 

SQUARE.DAT	SQUARE.RES
133 DDDDRR 1 DD	343 OUT OF THE BORDER

Legyen n egy pozitív egész. Az {1, 2, ..., n}halmaz összes részhalmazán definiáljunk egy < rendezést, melyet lexikografikus rendezésnek hívunk. Legyen S₁={x₁, x₂, ..., x_i} és S₂={y₁, y₂, ..., y_j} két különböző részhalmaza az {1, 2, ..., n} halmaznak, melyekben x₁<x₂<...<x_i és y₁<y₂<...<y_j. Azt mondjuk, hogy S₁<S₂, ha létezik k, (0<=k<=min(i,j)) és x₁=y₁, ..., x_k=y_k és k=i vagy x_k+1<y_k+1.

Például az {1, 2, 3} részhalmazai lexikografikus sorrendben a következők:
 

{}	1
{1}	2
{1, 2}	3
{1, 2, 3}	4
{1, 3}	5
{2}	6
{2, 3}	7
{3}	8

A lexikografikus rendezés minden részhalmazhoz egy természetes számot, az ő sorszámát rendeli.

Bemenet:

Az INPUT.TXT állományban a következő formátumú sorok lehetnek:
1 n k
2 n k₁, k₂, ..., k_i

Kimenet:

Az OUTPUT.TXT-be az első formátumú sorok esetén a k-adik részhalmazt kell beírni, ha a második formának felel meg, akkor a {k₁, k₂, ..., k_i} részhalmazhoz milyen sorszámot rendelünk {feltesszük, hogy 0<k₁<k₂<...<k_i<=n}

Példa:

 

HALMAZ.BE	HALMAZ.KI
1 3 5 2 3 2 3	1 3 7

A következő szabályok alapján alakzatokat hozunk létre:

1. A kezdő alakzat egy egységnyi oldalú négyzet.
2. Egy előállított alakzatból később tetszőleges számút előállíthatunk.
3. Egy új alakzatot úgy kapunk, hogy két létező alakzatot egyenlő hosszúságú oldaluk mentén összeragasztunk.

Feladat:

A program olvasson be egy N pozitív egész számot, majd határozza meg azon alakzatok számát, melyeknek területe legfeljebb N!
Ezt kétféleképpen végezze el:

Az első esetben két alakzatot csak akkor ragaszthatunk össze, ha egybevágóak.

A második esetben ilyen megszorítás nincs.

Bemenet:

A billentyűzetről kell beolvasni i és N értékét. (N<=10000). Az i azt adja meg, hogy első vagy második esetet vesszük figyelembe.

Kimenet:

Az eredményt az OBJECTS.DAT állományba kell beírni.

Példa:
 

Bemenet	OBJECTS.DAT
i=1, N=20	(1,1), (2,1), (4,2), (8,2), (16,3)
i=2, N=10	(1,1), (2,1), (3,1), (4,2), (5,1), (6,2), (7,1), (8,2), (9,2), (10,2)

Magyarázat: A kimenetben az egyes számpárok első eleme az előállított alakzat területe. A második szám pedig azt adja meg, hogy hány ilyen területű, de különböző alakú alakzat állítható elő az 1-3 szabályok segítségével.