ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА и информационни технологии “джон атанасов” -ШУМЕН’03

22 ноември 2003

ТЕМА ЗА 7-8 КЛАС (ГРУПА C)

Задача С1. ОСВЕТЛЕНИЕ

Залата за закриването на есенен турнир по информатика има N (2 < N < 102) лампи разположени в кръг, които се контролират от N ключа. В момента някои от тях са запалени, а другите изгасени. Предвид предстоящата церемония по награждаването организаторите искат да запалят всички лампи и това да стане възможно най-бързо. Обаче това не е толкова лесно, колкото изглежда. При конструирането на залата, техниците монтирали осветлението (вероятно останали недоволни от заплащането) си направили една малка шега – всеки от ключовете при натискане променя състоянието на различна двойка съседни лампи, т.е. ключ 1 променя лампи 1 и 2, ключ 2 променя лампи 2 и 3, ..., ключ N – 1 променя лампи N – 1 и N, и ключ N променя лампи N и 1.

Например, ако лампи 1 и 2 са запалени и натиснем ключ 1, то и двете ще изгаснат. Ако едната от тях е била запалена, а другата изгасена, то след натискането на ключа тази която е била изгасена ще се запали, а другата ще изгасне.

Напишете програма BULB.EXE, която намира с какъв минимален брой натискания на ключове могат да се запалят всички лампи, ако това изобщо е възможно.

Входните данни ще бъдат зададени в текстов файл, който вашата програма ще прочете от стандартния си вход. В първия ред на входния файл ще бъде зададено цялото число N. Вторият ред съдържа N числа, съответстващи на текущите състояния лампите: 1, ако лампата е запалена или 0, ако лампата е изгасена.

Резултатът трябва да бъде изведен на стандартния изход. Той трябва да съдържа един ред с числото, даващо с колко минимални натискания можем да запалим всички лампи. Ако не е възможно всички лампи да се запалят, трябва да се изведе –1.

Пример 1 – виж фиг.1

Вход:

6

0 0 1 0 1 0

Изход:

3

Пример 2 – виж фиг.2

Вход:

3

1 0 1

Изход:

-1

Забележка: Отговорът за пример 1 може да се постигне чрез натискане на ключове 1, 4, 5 или 2, 3, 6.

ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА и информационни технологии “джон атанасов” -ШУМЕН’03

22 ноември 2003

ТЕМА ЗА 7-8 КЛАС (ГРУПА C)

Задача C2. ДВИЖЕНИЕ

Робот се движи в равнината изпълнявайки последователност от команди. Възможните команди са следните:

	Команда	Действие:  роботът се премества
1.	x+	от точка (x,y) в точка (x+1,y)
2.	x-	от точка (x,y) в точка (x-1,y)
3.	y+	от точка (x,y) в точка (x,y+1)
4.	y-	от точка (x,y) в точка (x,y-1)

Например, ако роботът започне движението си от точката (0,0), след изпълнението на последователността от команди x+ x+ y+ x+ y- y- ще се окаже в точката с координати (3,-1).

Напишете програма MOVE.EXE,  която по зададена начална точка (x0,y0) и последователност от команди, намира крайната точка (x1,y1), в която ще се окаже роботът, след изпълнението на тази последователност от команди.

Входните данни се въвеждат от стандартния вход. Първият ред съдържа координатите   x0 y0  на началната точка, а вторият – последователността от команди.

Ограничения: броят на командите е не по-голям от 10 000, между отделните команди може да има произволен брой интервали, между буквите   x/y и  знаците  +/-   няма интервали.

Координатите на крайната точка трябва да се изведат на стандартния изход. Единственият ред на стандартния изход трябва да съдържа двете числа x1 y1, разделени с интервал.

Примери:

Вход                                                                                       Вход

0 0               100 200  

x+ x+ y+ x+ y- y-                     y+x–x+y-

Изход Изход

3 –1                                  100 200

ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА и информационни технологии “джон атанасов” -ШУМЕН’03

22 ноември 2003

ТЕМА ЗА 7-8 КЛАС (ГРУПА C)

Задача C3. ОСТРОВИ

За картографирането на голям воден басейн (море) е използван модел (карта) във вид на квадратна таблица, попълнена със знаците “*” и “=”. Знакът “*” означава, че съответният елемент от таблицата е част от остров, а знакът “=” означава, че това е част от морето. Реалното използване на картата е доста трудно и се налага да се направи програма за различни видове справки. Вашата задача е да напишете програма ISLANDS.EXE, която след като прочете данните за таблицата от стандартния вход извежда на стандартния изход броя на островите във водния басейн. За остров се приема непрекъсната последователност от съседни клетки от таблицата, съдържащи “*”. Клетките са съседни, ако имат обща страна.

На първият ред от стандартния вход се изписва едно цяло число 0 < N <= 1000, което задава броя на редовете и колоните на картата, а на всеки един от останалите N реда се въвеждат комбинации от N знака “*” и “=”. Между знаците не се оставят интервали. Възможно е картата да обхваща и част от сушата, т.е. по крайните клетки също да има “*”. В този случай и тези части се преброяват като острови.

На стандартния изход програмата извежда едно единствено цяло число – броя на островите на картата.

Примери:

Вход                                                                                       Вход

5 10

 =====                                ====***===

 =*=*=                                *==**==*=*

 **===                                ===***=*==

 ==**=                                *=***=***=

 ===*=                                **=====*==

                                      ***=======

                                      *====*==**

Изход *==******* **********

3 **********

Изход

                                                                                          5