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

Adott N négyzet a koordinátarendszerben, melyeknek oldalai párhuzamosak a koordinátarendszer tengelyeivel. Minden négyzet sarokpontjainak koordinátái egész számok. A négyzetek nem fedik és nem is érintik egymást, azaz oldalaiknak sincs közös pontja.
Ki kell számitani, hogy hány négyzet látható az  O origóból. Az  origó koordinátái (0,0).
Egy négyzet látható az origóból, ha van két olyan különböző A és B pont  a négyzet valamelyik oldalán, hogy az OAB háromszögnek nincs közös pontja a többi négyzettel.

Bemenet:

A SQUARES.IN szöveges állomány első sora a négyzetek  N (1<= N<=1000) számát tartalmazza. A következő N sor mindegyike egy négyzetet ir le a sorban található X, Y és L számokkal, (1<= X,Y,L<=10000), ahol X és Y a négyzet bal alsó sarkának koordinátái (azaz a legkisebb X és Y koordinátájú sarok), L pedig a négyzet oldalhossza.

Kimenet:

A SQUARES.OUT szöveges állomány első és egyetlen sora az origóból látható négyzetek számát tartalmazza.

Példa:
 

SQUARES.IN	SQUARES.OUT
3 2 6 3 1 4 1 3 4 1	3
4 1 2 1 3 1 1 2 4 2 3 7 1	2

Alice és Bob olyan kártyával játszik, amelynek N lapja van és minden kártya az 1..N számok valamelyikét tartalmazza cimkeként. Tehát nincs két kártya azonosan cimkézve. Feltételezzük, hogy N páratlan szám.
Van egy kártyakeverő gépük, amely átrendezi a sorban egymás után lerakott kártyák sorrendjét. A keverőgép úgynevezett duplakeverést végez, ami a következőt jelenti: minden i (1<= i<=N) pozicióra ha ott a j cimkéjű kártya van, akkor megnézi, hogy a j pozicióban milyen kártya van, legyen ez k. Ekkor az átrendezést úgy végzi el, hogy az  i  pozicióba a  k cimkéjű kártya kerül.
Alice és Bob a következőképpen játszik. Először Alice véletlenszerűen lerakja a kártyákat, legyen ekkor a kártyák cimkéjének sorrendje a₁, a₂, ..., a_N Ezután átrendezi a kártyák sorrendjét úgy, hogy az a_i  pozicióba az a_i+1 cimkéjű kártya kerül minden i-re (1<= i<=N-1), és az a_N pozicióba az a₁ kerül.
Az igy kapott cimkesorrendet jelölje x₁, x₂, ..., x_N, ami azt jelenti, hogy  az i-edik pozicióban az x_i cimkéjű kártya van.
Ezután Alice végrehajt S számú duplakeverés műveletet a keverőgéppel. Az igy kapott kártyasorozat cimkéinek sorrendjét jelölje p₁, p₂, ..., p_N. Ezt a kártyaállást kapja Bob, és megkapja az S számot is. Bob feladata, hogy kideritse azt az x₁, x₂, ..., x_N  kártyaállást , amelyet Alice előállitott a keverés megkezdése előtt.

Bemenet:

A CARDS.IN szöveges állomány első sora két egész számot tartalmaz egy szóközzel elválasztva, az N (1<=N<=1000) páratlan számot, amely a kártyák száma, és a duplakeverések S (1<=S<=1000) számát.
A következő N sor mindegyike egy egész számot tartalmaz. Ez az N szám az összes duplakeverés végrehajtása után kapott kártyaállást irja le. Az állomány (i+1) – edik sorában álló p_i szám azt jelenti, hogy a kártyaállásban az i -edik pozicióban a p_i cimkéjű kártya áll.

Kimenet:

A CARDS.OUT szöveges állomány N sort tartalmazzon, ami azt az x₁, x₂, ..., x_N  kártyaállást irja le, amely a keverések elvégzése előtt volt. Az  állomány i –edik sorában az x_i szám álljon, azaz az i –edik pozicióban álló kártya cimkéje.

Példa:
 

CARDS.IN	CARDS.OUT
5 2 4 1 5 3 2	2 5 4 1 3
7 4 6 3 1 2 4 7 5	4 7 5 6 1 2 3

Adott N darab pozitiv egész számoknak egy a = [a₁, a₂, ..., a_N] sorozata. Egy ilyen sorozaton úgynevezett kontrakció műveletet végezhetünk.
Egy kontrakció művelet azt jelenti, hogy valamely i indexre az a_i és az a_i+1 számokat helyettesitjük az a_i-a_i+1.értékkel. Pontosabban, con(a,i) jelölje azt az (N-1) elemű sorozatot, amelyet az [a₁, a₂, ..., a_N] sorozatból kapunk az a_i és a_i+1 elemeket helyettesitve az a_i-a_i+1 értékkel.

con(a,i) = [a₁, ..., a_i-1, a_i-a_i+1, a_i+2, ..., a_N]

Látható, hogy egy N elemű sorozaton pontosan  N-1 különböző kontrakció műveletet hajthatunk végre, és mindegyik egy N-1 elemű sorozatot eredményez.
Nyilvánvaló, hogy N-1 kontrakciót vágrehajtva egy N elemű sorozatra, az eredmény egy egész szám lesz.
Például a [12,10,4,3,5] sorozatra a 2, 3, 2 és 1 indexekkel végrehajtott kontrakciók a 4 értéket eredményezik.

con([12,10,4,3,5],2) = [12,6,3,5]
con([12,6,3,5]   ,3) = [12,6,-2]
con([12,6,-2]    ,2) = [12,8]
con([12,8]       ,1) = [4]

Adott az a₁, a₂, ..., a_N sorozat és a T cél érték. A feladat az, hogy keressünk olyan N-1 kontrakciót, amelyeket az adott sorrendben végrehajtva az eredmény a T szám lesz.
 

Bemenet:

A SUBTRACT.IN szöveges állomány első sora két egész számot tartalmaz egy szóközzel elválasztva, a számsorozat N (1<= N<=100) számát és a T (-10000<=T<=10000) cél értéket.
A következő N sor mindegyike egy egész számot tartalmaz, az állomány (i+1)-edik sorában a szémsorozat ai (1<=a_i<=100) eleme áll.

Kimenet:

A SUBTRACT.OUT szöveges állomány N-1 sort tartalmazzon, ami egy olyan kontrakció sorozatot ad, amelyet ebben a sorrendben végrehajtva a bemeneti sorozatra, a kivánt T cél értéket kapjuk.
Feltételezhetjük, hogy minden bemenő adatra van legalább egy megfelelő kontrakció sorozat.

Példa:
 

SUBTRACT.IN	SUBTRACT.OUT
4 5 10 2 5 2	1 2 1
5 4 12 10 4 3 5	2 3 2 1