Заочна олімпіада з інформатики. Хмельницька область 2003 - 2004 Тур 4 5.01.2004 - 15.01.2004 Правила оформлення розв'зків: КОМУ : popyk@ief.tup.km.ua КОПІЯ: tur4@oiuv.infocom.khmelnitskiy.ua ТЕМА : ZOI_2003 Листи з розв'язками приймаються до 24.00 15.01.2004р Питання щодо умов задач можна надсилати на popyk@ief.tup.km.ua На перевірку задач буде відведено час в 2 рази більший за час роботи авторських розв'язків. Козакам, що спочивають на полі пилявецької битви (с.Пилявці, Старосинявського району) присвячується… T4Z1 (25 балів) Бібліотека кошового писаря. В бібліотеці кошового писаря є зібрання з N книжок. (N<=1000). Він вирішив упорядкувати їх у книжкову шафу. Шафа має ширину W<=2000000000 і писар може обирати висоти книжкових полиць такі, які лише захоче. Але йому необхідно підібрати їх так, щоб загальна висота шафи була найменш можливою. Порядок книжок змінювати не можна! (Товщини та висоти книжок - цілі додатні числа, що не перевищують 2000000. Ширина шафи гарантовано не менша за товщину найтовстішої книги) Вхідні дані: У першому рядку числа N та W. Другий рядок містить N цілих чисел - висоти книжок. Третій містить також N цілих чисел - товщини книжок. Приклад: 3 5 2 4 4 2 2 2 Вихідні дані: Ціле число - мінімально можлива висота шафи. Вихідні дані до прикладу: 6 T4Z2 (25 балів) Гетьманська реформа. Біля Чигирину, у степу широкім, Там могила скіфа, воля козака, Вони пам'ятають червоні жупани, Чують голос Гонти і Залізняка… Щойно обраний гетьман вирішив здійснити адміністративну реформу на Україні. Оскільки війни у ті часи точилися майже без перестану, головним завданням було обрати столицю так, щоб вона була на максимально можливій віддалі від небезпечних територій. На території гетьманської України того часу знаходилось N<=100, великих вузлових пунктів(міст,селищ). (Назва пункту - послідовність великих латинських літер і символа "-" дефіс, мінус. Кількість символів в назві не більше 30). Вхідні дані: У першому рядку два числа N, K та M . Далі K рядків - назви небезпечних пунктів. Далі M рядків, кожен з яких містить назву першого пункту, назву другого пункту, відстань між ними. Вихідні дані: У перший рядок вивести назву столиці, у другий відстань до найближчого небезпечного пункту. Приклад вхідних даних: 7 2 7 KONOTOP GUSIATYN GUSIATYN KAMIANETS-PODILSKY 1 KAMIANETS-PODILSKY KANIV 3 KONOTOP KYIV 8 KANIV KYIV 2 KANIV BATURYN 1 KANIV CHYGYRYN 3 BATURYN CHYGYRYN 2 Відповідь до прикладу вхідних даних: CHYGYRYN 7 T4Z3 (50 балів) У Таврію за волею… Зібралися одного разу козаки в похід до кримського ханства, дівчат українських з полону визволяти, прийшли оточили ханський палац, та й кажуть: "А ну бусурмани, віддавайте дівчат наших, бо скучили вже сади вишневі за ними, а як не віддасте, то будемо битися з вами, аж поки останній з нас не поляже чи не посічемо вас усіх на капусту…". Злякався хан шабель козацьких, але й полонянок віддавати не хотів. Надіслав він листа отаману кошовому: "Навіщо нам кров проливати, от як виграєш ти в мене в хрестики-нулики віддам дівчат ваших без бою". І став кошовий думу думати, як хана-бусурмана обіграти, і винайшли козаки шлях до виграшу, а чи ви знайдете? Хрестики-нулики граються на полі розміром 3х3. Усі 9 клітинок на початку гри порожні. Перший хід має гравець, що ставить хрестики. Гравці по черзі ставлять у порожні клітинки свої знаки (перший - хрестики, друтий - нулики). Гра закінчується коли: А) на певній горизонталі, вертикалі чи діагоналі є три однакових знаки. Хто зміг виставити свої знаки відповідним чином 3 в ряд, той і виграв. Б) Коли пункт "А" не здійснився, і не залишилось вільних клітинок. Результат у цьому випадку - нічия. Ваша програма повинна: На початку викликати функцію BeginGame, яка поверне значення 0 чи 1. 0 - ви граєте нуликами, 1 - хрестиками. Для того, щоб зробити свій хід, викликати процедуру MakeMove(r,c) де параметри r та с - номер рядка та стовпчика в який ви робите хід. Для того, щоб взнати хід суперника викликати процедуру TakeMove(r,c), яка поверне у змінні r та с номер рядка та стовпчика в який робить хід суперник. Якщо гра закінчується - викликати процедуру EndGame(res). В параметр res - передати 0 - якщо ви програли, 1 - у випадку нічиєї, 2 - якщо ви виграли. Програма буде перевірятися на декількох модулях, різного рівня складності. Усі вищенаведені процедури знаходяться у модулі zeros.tpu для мови Pascal (не використовуйте інших модулей! CRT,DOS і т.д.) і у файлі zeros.h для мови C++. Ваша програма мовою Pascal може мати наступний вигляд: USES zeros; ….. BEGIN … K:=BeginGame; … MakeMove(r,c); … TakeMove(r,c); … EndGame(res); END. Ваша програма мовою C++ може мати наступний вигляд: #include "zeros.h" … int main() { k=BeginGame(); … MakeMove(r,c); … TakeMove(r,c); … EndGame(res); return 0; } Вам надаються зразки модулей (але грають вони не найкращим чином) {Zeros.pas} UNIT zeros; INTERFACE FUNCTION BeginGame:integer; PROCEDURE EndGame(res:integer); PROCEDURE MakeMove(r,c:integer); PROCEDURE TakeMove(var r,c:integer); IMPLEMENTATION VAR F:Array[1..3,1..3] of integer; FUNCTION BeginGame:integer; var r,c:integer; begin for r:=1 to 3 do for c:=1 to 3 do F[r,c]:=0; randomize; BeginGame:=random(2); end; PROCEDURE MakeMove(r,c:integer); begin F[r,c]:=1; end; PROCEDURE TakeMove(var r,c:integer); var rr,cc:integer; begin for rr:=1 to 3 do for cc:=1 to 3 do if F[rr,cc]=0 then begin F[rr,cc]:=1; r:=rr; c:=cc; Exit end; end; PROCEDURE EndGame(res:integer); begin end; BEGIN END. //zeros.h #include int BeginGame(); void EndGame(int res); void MakeMove(int r,int c); void TakeMove(int &r, int &c); int _F[3][3]; int BeginGame() { int r,c; for(r=0;r<3;r++) for(c=0;c<3;c++) _F[r][c]=0; randomize(); return random(2); } void EndGame(int res) { } void MakeMove(int r,int c) { _F[r-1][c-1]=1; } void TakeMove(int &r, int &c) { for(r=0;r<3;r++) for(c=0;c<3;c++) if (_F[r][c]==0) { _F[r][c]=1; r++; c++; return; } }