НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА

ПЛОВДИВ, 27–28 МАЙ 2006

Задача B1. Игра с топки

            Дадени са n топки, които са наредени в редица по права линия в един физкултурен салон, успоредно на една от стените. На тази стена са поставени m празни коша в редица, успоредна на редицата на топките. Всяка топка и всеки кош са оцветени с един от следните цветове:  r – червен, b – син, g – зелен, w – бял, p – розов, y – жълт.

Играем следната игра. Вземаме последователно топки, в реда в който са подредени, отляво-надясно. Можем да върнем взета топка на същото място в редицата й, но не можем да вземем топка, която вече веднъж сме върнали, както и не можем да се връщаме назад по редицата от топки. Топка, която не връщаме, поставяме в кош от същия цвят, който е разположен по надясно от последния до момента пълен кош в редицата от кошове (ако сме в самото начало на играта, взета топка може да поставим в произволен кош от същия цвят).

Във всеки кош може да влезе най-много една топка. Целта на играта е да се вкарат максимален брой топки.

Напишете програма BALLS, която въвежда от стандартния вход два низа, съдържащи някои от буквите r, b, g, w, p, y. Всеки от низовете не е по-дълъг от 999 знака. Първият низ задава разположението на топките, а втория – на кошовете.

На стандартния изход програмата трябва да изведе едно цяло число, равно на максималния брой топки, които могат да се поставят в кошовете, съгласно описаните правила.

ПРИМЕР 1	ПРИМЕР 2
Вход rrbgwgbpp yppgwbpbp	Вход ygbgygbgyby ybygygygybyby
Изход 5	Изход 9

НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА

ПЛОВДИВ, 27–28 МАЙ 2006

Задача B2. Преговори с фропейците

            Като главен преговарящ за Земляните, днес Вие имате среща с фропейците – съюз на няколко свръх-цивилизации. Знаете, че от тази среща зависи цялото бъдеще на Земята, защото само приемането ни в техния съюз означава върховно благоденствие. Иначе ни чакат още доста хилядолетия на орбита в този забутан ъгъл на Млечния път...

            Изненадващо за Вас, Върховният преговарящ фропеец Óлене Дей Ви предлага “просто” решение: тъй като не е ясно дали и  доколко е напреднал разумът на Земята, ще играете една игра (двадесет пъти) по следните правила:

· Фропеецът избира “случайно” две галактики и (след консултация с базата си данни) Ви съобщава по колко значими обекти (разбирайте, по-големи от човешки юмрук) има във всяка от тях. Означаваме данните съответно с A и B – това може наистина да са “космически” естествени числа, но не са с повече от 50 десетични цифри.

· Вие пък имате право да изберете кой ще играе първия ход – Вие или фропеецът. Демократично, нали?

· Ходовете следват алтернативно до края на играта.

· Играчът, който е на ход, трябва да избере една от двете галактики и да “завладее” поне един свободен обект от нея. Нека е завладял X обекта. Преди да предостави ход на опонента си, той е длъжен за завладее и два пъти повече (2X) свободни обекти от другата галактика. Естествено, след тези действия броят на свободните обекти в първата от избраните галактики намалява с X, а в другата – с 2X.

· Ако играчът, който е на ход, не може да го направи, като спазва горното правило, играта приключва с негова загуба.

            Тъй като няма ограничения за използването на компютърна техника (даже напротив – това е съществена част от изпита за интелигентност на всяка цивилизация), Вие решавате да напишете една програма PHROPE, с помощта на която да вземете двете първи решения: дали да искате първи ход и ако да – какъв да бъде той, с цел да спечелите играта. Не разчитайте на грешка на фропееца – той също има помощна (че и по-мощна) техника. И не забравяйте, че от Вашата игра зависи приемането ни във Фропейския съюз!

            От стандартния вход се въвежда един ред с естествените числа A и B, разделени с интервал. Това са същите онези (евентуално “космически”) числа от базата данни на фропейците. Запишете на стандартния изход един ред, който съдържа две неотрицателни цели числа, разделени с интервал. Ако предоставяте първия ход на фропееца, двете числа са нули. Иначе първото от тях (X) показва колко обекта да завладеете от галактиката, в която има A обекта, а второто (Y) – колко да завладеете от галактиката с B обекта. Съгласно правилата, трябва да е изпълнено или X=2Y, или Y=2X.

            Двадесетте тестови примера се оценяват по двойки – нула точки даже ако само единият от отговорите в двойката не е верен.

Пример 1. Вход 20 17 Изход 20 10

Пример 2. Вход 3 3 Изход 0 0

НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА

ПЛОВДИВ, 27–28 МАЙ 2006

Задача B3. Пътешествие.

            Като награда за първото място в поредния Пролетен турнир младият програмист Пешо получил награда – безплатно пътешестви в екзотична страна. Той трябвало да си избере два от N-те града на страната, номерирани с числата от 1 до N, а фирмата-спонсор да заплати пътуването от единия до другия град по най-късия път, свързващ тези два града. Пътната мрежа на страната се състои от M пътни отсечки, всяка от които свързва два различни града и дължините на тези отсечки са такива, че можем да ги считаме еднакво дълги. Това обаче не било първото пътуване на Пешо в тази страна и K от градовете той вече познавал добре. Затова много би искал така да избере маршрута, че да посети колкото може повече градове, които още не е посещавал. Напишете програма TRIP, която намира максмалния брой нови за Пешо градове, които той би могъл да посети при подходящ избор на началния и крайния град на пътешествието.

            Вход

            На първия ред на стандартния вход са зададени числата N, M  и K (5 £ N £ 1001, 2 £ K £ N/2), разделени с по един интервал. Всеки от следващите редове съдържа номерата на два града – краища на една пътна отсечка, разделени с интервал. На последния ред са зададени номерата на градовете, които Пешо вече е посещавал.

            Изход

            На единствения ред на стандартния изход пограмата трябва да изведе само едно число – максималния брой нови градове, които Пешо би могъл да посети при условията, поставени от фирмата спонсор.

ПРИМЕР  

Вход                                                   Изход

6 7 3                2

1 2

2 3

1 4

4 5

5 3

1 6

6 3

1 3 6