ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН'02

16 ноември 2002

ТЕМА ЗА 9 – 10 КЛАС (ГРУПА B)

 

Задача 1.  КАНДИДАТИ

 

На избори за кмет се явили 5 кандидата P, Q, R, S и Т – по един представител на всяка от партиите A, B, C, D и E. Редът, по който са написани кандидатите не е задължително да указва принадлежност към съответна партия в дадената по-горе редица от партии. Определете какви могат да бъдат резултатите от изборите (кой кандидат кое поредно място е заел) и кой кандидат от коя партия е, ако е известно следното:

 

Представителите на партия B и на партия C са се класирали на първо и на пето място (но без да уточняваме кой кое от тези две места e заел) и никой от тях не носи име Q или R. Кандидатът T е заел по-предно място от S. P не е представител на C. Представителят на партия D е заел по-предно място от R, но е след Q.

 

Създайте текстов файл с име CANDID.TXT, който да съдържа толкова редове,  колкото са намерените от вас възможности за удовлетворяване на условията на задачата. Всеки ред трябва да съдържа по 5 двойки главни латински букви, определящи партията и името на представителя й (първо буквата за партията, после буквата на кандидата). Във всеки от тези редове двойките букви трябва да са подредени по реда на класирането на изборите – първата двойка да представя партията и представителя й, заели първото място на изборите и т.н. Буквите в двойките, както и самите двойки трябва да бъдат отделени с точно един интервал. Така всеки ред трябва да съдържа по 19 знака, включително интервалите.

 

Правила за оценяване:

 

Ако сте намерили правилно всички възможности, получавате максималния брой точки за задачата. При намерени по-малко възможности, но удовлетворяващи условията, получавате съответна пропорционална част от максималния брой точки. За всяка посочена от вас грешна възможност, от вашата оценка се отнемат по 20 точки, като ще се спази изискването оценка ви да не стане отрицателна.

 

 


ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН’02

16 ноември 2002

ТЕМА ЗА 9-10 КЛАС (ГРУПА B)

 

Задача 2. ЛАБИРИНТ

 

"- Червени Котако - започна Алиса доста боязливо - би ли ми казал кой път да хвана оттук?
- Зависи накъде отиваш - отвърна Котака.
- Все едно накъде... - каза Алиса.
- Тогава е все едно кой път ще хванеш - рече Котака "

 

При своите приключения в Страната на чудесата Алиса се оказала затворена в лабиринт. Понеже това било Страната на чудесата няма нищо чудно в това, че лабиринтът има форма на правоъгълна мрежа от квадратчета с M стълба и N реда. Всяко квадратче на лабиринта е или запълнено - стена - и през него не може да се преминава, или празно и през него може да се преминава. Също така, в лабиринта няма цикли т.е. между всеки две празни квадратчета има единствен път. Път е последователност от празни, съседни квадратчета – включително квадратчета между които е пътят – като всеки две квадратчета от пътя са различни. Две квадратчета са съседни, ако имат обща страна.

 

За да излезе от лабиринта, Алиса трябва да изрече числото, което е дължината на пътя между двете най-отдалечени празни квадратчетата. Дължината на път между две квадратчета е равна на броя на квадратчета от пътя минус 1.

 

Напишете програма LAB.EXE, която по зададен лабиринт намира най-голямата дължина на път между две празни квадратчета.

 

Входният файл се чете от стандартния вход и съдържа числата М (3 <= М <= 1000) и N (3 <= N <= 1000) на първия си ред. Всеки от останалите N реда съдържа по М символа – всеки символ е или “#” – запълнена клетка, или “.” – празна клетка.

 

Изходният файл се записва на стандартния изход и има само един ред с едно число на него: най-голямата дължина на път между две празни квадратчета.

 

 

Пример:

 

Вход                                                   Изход

 

7 6                     8

#######

#.#.###

#.#.###

#.#.#.#

#.....#

#######

 


ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН'02

16 ноември 2002

ТЕМА ЗА 9 – 10 КЛАС (ГРУПА B)

 

Задача 3.  ЧИСЛОРЕД

 

Напишете програма GRADE.EXE, която по зададена редица от цели положителни числа намира такива, колкото може по-малко на брой измежду тях, които, ако бъдат отстранени от редицата, тя ще се окаже не намаляваща (всяко число в нея ще се предхожда само от по-малки или равни на него).

 

Входните данни съдържат единствен ред, в който са записани числата от редицата, разделени с интервали.  Те са не повече от 1 000 000 на брой, като всяко от тях е не по-голямо от 30 000.

 

Резултатът съдържа един ред с поредните номера на намерените числа, разделени с интервали (броенето започва от 1). Входните данни са такива, че в изхода винаги ще има поне едно число.

 

Входните данни се четат от стандартния вход, а изходните данни се записват на стандартния изход.

 

Пример.

 

Вход

3 1 2 0 5 4

 

Изход

1 4 5

 

(Възможен отговор е и 1 4 6)

 

 

ОБРАТНО