НАЦИОНАЛЕН ПРОЛЕТЕН
ТУРНИР ПО ИНФОРМАТИКА
ПЛОВДИВ, 27–28 МАЙ 2006
Задача А1. Атомна сигурност
Страната X трябва да построи бомбоубежища в случай на евентуална
ядрена война. Тъй като е добре тези убежища да са максимално отдалечени от
местата на бомбардировката, военните стратези са събрали информация за
плановете на вражеските страни и са съставили списък A, съдържащ N места, които биха били
бомбардирани при евентуални военни действия. За удобство можем да си представим
тези места като точки в равнината. Известни са координатите на тези точки.
Самата държава има форма на изпъкнал многоъгълник – това е най-малкият изпъкнал
многоъгълник, съдържащ всички точки от A.
Задачата ви е, при зададени
координати на точките от А, да
намерите къде да бъде построен VIP-бункера, който ще бъде
бомбоубежище за най-важните личности на страната Х. Този букнер трябва да е
максимално отдалечен от местата на бомбардировка: т.е разстоянието до
най-близката точка от A трябва да е колкото може
по-голямо. Разстоянията са евклидови. Интересуват ни само точки, които са в
границите на страната (евентуално може и да са на самата границата). За целта трябва да напишете програма ATOM.
На първия ред в стандартния вход се
намира числото N (3 ≤ N ≤ 100). Следват N реда с координатите на местата, които са застрашени от
бомбардировка (координатите са цели числа в интервала [–10000, 10000]). Страната
е с ненулево лице. Във входа няма повтарящи се точки.
Отпечатайте два реда на стандарния
изход. На първия ред да се намира числото R – намереното от вас максимално
разстояние до най-близкото място от бомбардираните. Числото се иска с точност
до втория знак след десетичната точка. На втория ред запишете координатите на
точката, изпълваща исканото условие. Координатите се изискват също с 2 знака точност
след десетичната точка.
|
Вход |
Изход |
|
4 |
7.07 |
НАЦИОНАЛЕН ПРОЛЕТЕН
ТУРНИР ПО ИНФОРМАТИКА
ПЛОВДИВ, 27–28 МАЙ 2006
Задача А2. Улици
В един
град било решено, че е крайно време да пооправят улиците. Ето защо решили да
премахнат всички досегашни улици и да направят съвсем нови. Градът се състои от
кръстовища, които са свързани чрез улици. Кръстовищата са номерирани с числата
от 1 до N. След премахването на всички стари улици нито едно кръстовище не е
свързано с друго. Кмета обявил конкурс да се измисли такава схема от нови
улици, че от всяко кръстовище да може да се стига до всяко друго поне по един
път образуван от улици. Между всеки две кръстовища може да се построи улица, но
не повече от една. Новите улици в града са двупосочни.
За всеки
нов, непредложен до момента план, кмета е обещал да плати 1 лев. Той се
интересува колко най-много пари може да му се наложи да даде. Главният архитект
на града имал за задача да пресметне тази стойност и да я каже на кмета. На път
за кметството архитекта забравил числото, тъй като то било прекалено голямо.
Все пак то може да се намери като се знае броят на всички кръстовища в града.
Напишете програма STREETS, която по зададен брой на кръстовищата в града извежда
най-голямата възможна сума, която кмета трябва да плати. Отговора трябва да
бъде изведен по модул от 4999999, тъй като кмета не обичал големите числа и нямало да му се хареса да го
занимават с огромни стойности.
Входните
данни се четат от стандартния вход. На първия и единствен ред има едно число N (1 ≤ N ≤ 1000), което показва броят на
кръстовищата. Изходните данни се извеждат на стандартния изход. Те се състоят
от един ред с едно число на него – максималната сума, която може да се наложи
кмета да плати по модул от 4999999.
|
Примерен вход 1: |
Примерен изход 1: |
|
3 |
4 |
|
|
|
|
Примерен вход 2: |
Примерен изход 2: |
|
4 |
38 |
|
|
|
|
Примерен вход 3: |
Примерен изход 3: |
|
30 |
3439964 |
НАЦИОНАЛЕН ПРОЛЕТЕН
ТУРНИР ПО ИНФОРМАТИКА
ПЛОВДИВ, 27–28 МАЙ 2006
Задача А3. WAC – Word Auto Completion
Пешо Хакера
завърши следването си и както често се случва в днешни дни единствената работа,
която си намери бе в новоизлюпена фирма, пишеща софтуер за мобилни телефони.
Телефоните, за които фирмата прави софтуер са доста слаби като процесор и
памет, но имат изключително бърза връзка към централния сървър и затова на Пешо
беше дадена задачата да напише програма, която да върви на сървъра и да
обработва милионите заявки за автоматично завършване на думи, които се генерират
всеки ден от различни мобилни телефони. Пешо не разбира много от алгоритми
затова Вие ще трябва да напишете
програмата WAC вместо него.
Програмата на Пешо трябва да
изпълнява команди получени от библиотека и пак чрез нея да връща отговорите на
командите. Командите са следните видове :
ADD <нова_дума>
FIRST <номер_на_мобилен_телефон>
<представка>
NEXT <номер_на_мобилен_телефон>
При команда
'ADD' думата <нова_дума> трябва да се прибави в
речника на програмата.
На команда
'FIRST' трябва да
се отговори с първата добавена в речника
дума, която има <представка> като своя
представка.
На команда
'NEXT' трябва да
се отговори с поредната дума от речника(по реда на добавянето им), която има за
представка <представка> от
последната подадена от <номер_на_мобилен_телефон> команда 'FIRST'(такава задължително ще има). В
случай, че думите се изчерпят на тази команда трябва да бъде отговорено отново
с първата добавена дума отговаряща на <представка>. След това с втората и т.н.
Работа с библиотеката
Преди викането на която и да е
друга процедура на библиотеката, трябва
да се извика процедурата init(). След това поредната команда се
получава с помощта на процедурата getQuery() единствения параметър, на която е низ, в който
библиотеката записва поредната команда в същия формат както е описано
по-горе(отделните полета са разделени с точно един интервал). Този низ трябва да е достатъчно дълъг
за да побере всяка заявка според условието на задачата. След вземане на команда
от вид 'FIRST' или 'NEXT' на нея трябва да бъде отговорено с answerQuery() преди вземане на друга заявка. Низът, който се предава
на answerQuery() е думата отговор на заявката или
само една точка ако такава дума не съществува. След отговора на последната
заявка библиотеката ще прекрати изпълнението на програмата Ви. При неспазване
на горните правила получавате 0 точки за
съответния тест. При опит за четене от стандартния вход или от файл или писане на стандартния изход или на
файл получавате 0 точки за съответния тест.
ЗА ПИШЕЩИТЕ НА FreePascal
Библиотека:
(module.ppu, module.o)
procedure
init;
procedure
getQuery(var input_line : string);
procedure
answerQuery(const answer : string);
Програмата example.pas е пример за използване на тази
библиотека.
Инструкции: За да компилирате вашия файл wac.pas, включете оператора uses module; в изходния текст и компилирайте с
fpc –So –O2 –XS wac.pas
Библиотека
(module.h, module.o)
void
init();
void
getQuery(char *input_line);
void
answerQuery(char *answer);
Програмата
example.c е пример за използване на тази библиотека.
Инструкции:
За да компилирате вашия файл wac.c или wac.cpp, използвайте #include “module.h” в изходния текст и
компилирайте с:
gcc –O2
-static wac.c module.o -lm -o wac.exe
gxx –O2
-static wac.cpp module.o -lm -o wac.exe
За пишещите на C/C++ в RHIDE: Задайте
на Options->Linker configuration стойност module.o.
Вход
Модулът чете
заявките от файл с име “wac.in”. На първия ред е записан броя на
командите, а на всеки следващ по една команда във формата описан по-горе.
Изход
Модулът записва отговорите на заявките в изходен файл с
име “wac.out” в
текущата директория.
Ограничения
Нека с N бележим броя команди ADD. С M сумата от дължините на думите
добавени с ADD. С W дължината на най-дългата
дума от речника или представка. С Q броя команди от тип FIRST и тип NEXT сумарно.
1 ≤ N ≤ 105
1 ≤ M, Q ≤ 106
1 ≤ W ≤ 30
1 ≤length(<номер_на_мобилен_телефон>) ≤ 16
Броят различни номера на мобилни телефони за едно стартиране
на програмата не надвишава 100000.
Номерата на мобилни телефони се състоят от цифрите от 0 до 9. Всички
думи и представки се състоят от малки латински букви.
Пример
|
wac.in 11 FIRST
002 ala ADD
alakazala NEXT
002 ADD
alamazala ADD
alabala ADD
ala FIRST
003 alak NEXT
002 NEXT
003 FIRST
001 bala NEXT
002 |
wac.out . alakazala alakazala alamazala alakazala . alabala |