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

Kolozsvár, Románia


Fekete vagy fehér - 2. Nap, 1. feladat (100 pont, időlimit: 60 mp)
Írj programot, amely beolvas három pozitív egészet (N, P, Q). Döntsd el, létezik-e olyan N darab egész számból álló számsorozat, amelyben bármely P egymást követő elem összege pozitív és bármely Q egymást követő elem összege pedig negatív!

Ha a válasz IGEN, akkor programodnak meg kell határoznia egy ilyen sorozatot.

Bemenet:

A BW.IN állomány 3 számot tartalmaz, az N, P, Q értékét, egymástól szóközzel elválasztva. (N<=50)
Kimenet:
A BW.OUT állomány első sorában a YES áll, ha létezik megoldás, egyébként tartalma NO. YES válasz esetén a második sorban az N elemű, egészekből álló sorozat található.
Példa:
 
BW.IN BW.OUT
4 2 3 NO
6 5 3 YES
-3 5 -3 -3 5 -3

Páros és páratlan - 2. Nap, 2. feladat (100 pont, időlimit: 10 mp)
Egy országban N város van. Adottak a városokat közvetlenül összekötő utak. Minden egyes közvetlen út hossza 1. Az úthálózatot páros-páratlannak nevezzük, ha van két olyan város, melyek között van páros és páratlan hosszúságú útvonal is.
  1. Állapítsd meg egy úthálózatról, hogy páros-páratlan-e vagy sem!
  2. Ha az A kérdésre a válasz NEM, akkor keresd meg a városok olyan, maximális elemszámú X részhalmazát, melyben bármely két várost összekötő összes út hossza páros! (Ez az út az X részhalmazban kezdődik és végződik, de érinthet X-en kívüli városokat is.)


Bemenet:

Az INPUT.TXT állomány első sora az N értéket, azaz a városok számát (N<=300) tartalmazza. A következő sorok I, J párokat tartalmaznak, amelyek azt jelentik, hogy I és J között közvetlen út van.
Kimenet:
Az OUTPUT.TXT első sora az IGEN vagy a NEM szót tartalmazza. Ha az első sor NEM, akkor a második sor a keresett X részhalmaz elemszámát tartalmazza, a harmadik sorba pedig a részhalmaz elemeinek felsorolását tartalmazza.
Példa:
 
INPUT.TXT OUTPUT.TXT
5
1 2
2 3
3 4
4 5
5 1		 IGEN
3
1 2		 NEM
2
2 3

Kifejezések - 2. Nap, 3. feladat (100 pont, időlimit: 10 mp)
Egy kifejezés összeadásokat és szorzásokat tartalmaz. Az összeadás (+) elvégzéséhez P, a szorzáséhoz Q idő szükséges. Az AoB kifejezés kiértékeléséhez szükséges idő egyenlő a művelet (o) ideje plusz az A és a B részkifejezések kiértékeléséhez szükséges idő maximuma. (Az A és a B részeket párhuzamosan értékeljük ki.) A műveletek operandusai egyetlen karakterből álló változónevek. Ezek kiértékelésének ideje 0.
A kifejezésekben a zárójeleket a megszokott módon, a máveletek elvégzési sorrendjének meghatározására használjuk.
 
  1. Írj programot, amely minden kifejezésre meghatározza a kiértékeléshez szükséges időt!
  2. Keresd meg azt, az eredetivel ekvivalens kifejezést, melynek kiértékelési ideje minimális, és add meg ennek az idejét is!


Az átalakítási szabályok a következők:

 
x+y=y+x x*y=y*x kommutativitás
x+(y+z)=(x+y)+z x*(y*z)=(x*y)*z asszociativitás
Az egyes kifejezések teljesen zárójelezettek (a zárójelek nem hagyhatók el).

Bemenet:

Az INPUT.TXT állomány első sora a P és a Q értékét tartalmazza, a következő sorok pedig egy-egy kifejezést.
Kimenet:
Az OUTPUT.TXT tesztesetenként 3 sort tartalmaz. Az első sor az A eset megoldását adó szám, a második a B feladatban szereplő kifejezés, a harmadik sorban pedig az ennek kiértékeléséhez szükséges idő szerepel.
Példa:
 
INPUT.TXT OUTPUT.TXT
1 1
((a+(b+(c+d)))*e)*f
((((a*b)*c)*d)+e)+(f*g)		 5
((a+b)+(c+d))*(e*f)
3
5
(((a*b)*(c*d))+e+(f*g)
4