Задача A

Нов български университет

Институт по математика и информатика, БАН

Школа „Състезателно програмиране”

СЪСТЕЗАНИЕ, 11 декември 2010 г.

Задача A. ФАКИР

Факир има във вълшебна шапка a сиви, b бели, c черни и d пъстри мишки. Ако е със затворени очи, колко най-малко мишки трябва да извади от шапката, за да е сигурен, че измежду извадените мишки ще има от всеки цвят?

Вход

Програмата прочита от първия ред на входа броя на тестовите примери. Следват данните за тестовите примери, всеки на отделен ред съдържащ стойностите на целите числа a, b, c и d.

Изход

Програмата трябва да изведе на отделни редове отговорите за съответните от входа тестове.

Оганичения

0 < a < 500

0 < b < 500

0 < c < 500

0 < d < 500

Пример

Вход:

14 9 4 7

2 2 2 4

Изход:

Задача B. СТЕПЕНИ

Дадена е таблица, съставена от n + 1 реда и n стълба. В първия ред на таблицата са записани цели положителни числа, а на следващите n реда са пресметнати и записани съответно вторите, третите и т. н. степени на числата от първия ред.

Например, в следващата таблица n = 4 и тя съдържа степените на числата 3, 5, 2 и 1 до петата им степен:

125

625

243

3125

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

За примера, ако m = 3, тогава резултатът ще бъде 1, защото остатъкът при делене с 3 на сумата 9+125+16+1 е равен на 1.

Вход

От първия ред на стандартния вход програмата въвежда броя на тестовите примери. Следват данните за тестовите примери. За всеки тест програмата трябва да въведе два реда. В първия от тях са записани целите положителни числа n и m, а във втория – числата от първия ред на таблицата, разделени с интервали.

Изход

Програмата трябва да изведе на стандартния изход съответната пресметната сума като едно цяло число за всеки от тестовите примери на отделен ред.

Ограничения: n ≤ 1000000, m ≤ 10000000. Числата в първи ред на таблицата са цели, положителни и са по-малки от 100 000.

Пример

Вход:

4 3

3 5 2 1

1 10

Изход:

1
5

Задача C. ПРЕСКАЧАНЕ

Разглеждаме n последователни точки с целочислени координати x_i = i, i = 1, 2, ..., n, върху правата линия (2 < n < 1000). За всяка от точките, са дадени по две стойности a_i и b_i, i = 1, 2, ..., n. Започвайте от точка 1, нашата цел е да отидем до точка n чрез скокове с дължина 1 или 2. Скачайки от i-тата точка, трябва да платим a_i лева за скок с дължина 1 или b_i лева за скок с дължина 2.

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

Програмата трябва да прочете от първия ред на входа броя на тестовите примери. За всеки тестов пример данните са следните: стойност на n, следвана от n – 2 двойки стойности a_i и b_i, i = 1, 2, ..., n – 2 и стойността на a_n– 1. Стойностите на a_i и b_i са неотрицателни цели числа, по-малки от 1000.

Програмата трябва да изведе на отделни редове съответните отговори на тестовете.

Пример.

Вход:

3 1 1 1

5 1 3 2 1 1 1 3

Изход:

Задача D. Отдалеченост

В равнината е даден квадрат с дължина на страната a и с център началото на координатната система. Отдалеченост на една точка наричаме сумата от абсолютните стойности на нейните координати. Например, отдалечеността на точката с координати (2, –3) е 5. Дадена е редица от n точки с координатите им. Напишете програма, която намира стойността на най-малката отдалеченост на точка от дадената редица, която е извън дадения квадрат. Една точка е извън квадрата, ако нито е вътрешна за него, нито принадлежи на контура му. Ако няма точки извън квадрата, да се изведе 0.

Вход

От първия ред на стандартния вход програмата прочита броя на тестовите примери. За всеки тест се въвеждат стойностите на n и a – цели положителни числа, разделени с един интервал и следват n реда, съдържащи двойките координати на точките от дадената редица – цели числа, разделении с един интервал.

Изход

На стандартния изход да се изведе по едно цяло число на ред, съответстващо на тестовите примери – търсената отдалеченост или 0, ако няма точки извън квадрата.

Ограничения:

1 ≤ n ≤ 10000

1 ≤ a ≤ 1000

Координатите на точките не са по-малки от –100000 и не са по-големи от 100000.

Пример:

Вход:

1 2

0 0

5 4

1 2

4 6

-3 2

-2 2

4 -1

Изход:

Задача Е. НАУЧЕН КАЛКУЛАТОР

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

Входът съдържа повече от един пример и започва с цяло число, което оказва броя на примерите.

Пример.

Вход:

1+2*5

4-7*2+10.5

Изход:

0.5

Задача F. ПРЕСЕЧНИ ТОЧКИ

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

Програмата прочита от първия ред на входа броя на тестовите примери. За всеки тестов пример програмата въвежда броя на отсечките n, следван от данните за отсечките (1 < n < 1000. За всяка отсечка се въвеждат по 2 двойки цели числа (в диапазона от 0 до 1000), които задават двойките координати на краищата на отсечката.

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

Пример.

Вход:

2 0 0 0 1 0 0 0 1

4 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0

5 1 2 1 0 2 2 2 0 0 1 2 1 0 1 3 1 0 0 1 0

Изход:

Задача G. Най-малко и най-голямо число

Дадено е едно естествено число. Чрез разместване на различни цифри на числото се получава ново число, което е по-голямо или по-малко от даденото. Да се намерят най-малкото и най-голямото число, които могат да се получат чрез разместване на цифрите на даденото число.

Вход

От първия ред на стандартния вход програмата прочита броя на тестовите примери. Следват числата, които са по-малки от 10¹⁰⁰⁰.

Изход

За всеки пример програмата извежда на отделен ред най-малкото число и най-голямото число, разделени с един интервал.

Примерен вход:

202

132

Примерен изход:

22 220

123 321

Задача H. имоти

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

Входът може да съдържа повече от един пример, като всеки е зададен на един ред с редица от реални числа x и y - координатите на върховете. Редът за обхождане на върховете на заградените площи е обратен на часовниковата стрелка. Разделител между числата е интервал.

Примерен вход:

0 0 1 0 0 3

Изход за примерния вход:

1.5

Задача I.

Даден е текст на български език, в който има добавени команди за LaTeX за маркиране на думи и изрази. Всяка такава команда започва с “\” (обратна наклонена черта), след това е името на командата – стринг, съставен само от латински букви, следва “{“ (отваряща голяма скоба), стринг на български и “}” (затваряща голяма скоба). Не се допускат вложени команди. Да се напише програма за премахване на LaTeX командите от текста.

Пример.

Вход

\name{Райна} в лозята отива, \underline{мари,}

\name{Райна} в лозята отива,

в лозята за бяло грозде, \underline{мари,}

в лозята за бяло грозде.

\name{Иван} подиря й вървеше, /2

\name{Иван} на \name{Райна} думаше:

- Чакай ма, \name{Райне}, чакай ма, /2

двама в лозята да идем, /2

да вървим, да хортуваме, /2

верничко да са питаме, /2

ше ли ма земеш, \name{Райни} мо. /2

Изход

Райна в лозята отива, мари,

Райна в лозята отива,

в лозята за бяло грозде, мари,

в лозята за бяло грозде.

Иван подиря й вървеше, /2

Иван на Райна думаше:

- Чакай ма, Райне, чакай ма, /2

двама в лозята да идем, /2

да вървим, да хортуваме, /2

верничко да са питаме, /2

ше ли ма земеш, Райни мо. /2

Задача J. тетраедър

Зададен е тетраедър с координатите на своите върхове. Координатите са цели неотрицателни числа като за всеки пример на нов ред последователно са зададени x, y и z координатата на съответния връх, разделени с интервал. Числата са зададени в двоична бройна система.

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

За всеки пример отпечатайте обема на тетраедъра в десетична бройна система.

Пример.

Вход:

1 1 10 1 101 10 101 1 1 11 11 100

Изход:

6.6667