XVI обласна олімпіада з інформатики (Хмельницька обл.) 2001-2002 навчальний рік 1 тур (теоретичний) 1. За допомогою програми БЛОКНОТ створіть текстовий файл Theorist.txt, в який запишіть відповідь на запитання "Роль українських вчених у створенні і розвитку засобів комп'ютерної техніки" (5 балів). 2. За допомогою програми БЛОКНОТ створіть Web-сторінку Mypage.htm, з якої б викликався файл Anketa.txt. При відкритті файла Mypage.htm браузером на екрані має бути гарно оформлена така інформація: Мене звати ім'я. Мені число років. Я хочу перемогти на обласній олімпіаді з інформатики. Це моя Web-сторінка, яку я створюю під час теоретичного туру, де маю показати знання мови розмітки гіпертексту HTML. Чим більше тег я знаю, тим красивішою буде моя сторінка. ... Для отримання анкетних даних натисніть на посилання ПРО МЕНЕ. Файл Anketa.txt має містити таку інформацію: 1. Прізвище, ім'я, по батькові 2. Рік, число і місяць народження 3. Клас, школа 4. Район (місто) 5. Домашня адреса, поштовий індекс 6. Телефон 7. Прізвище, ім'я, по батькові місце роботи і робочий телефон батьків: мати батько 8. Відомості про тих, хто підготував до олімпіади (15 балів) 3.Складіть програми мовою програмування. (80 балів). 3.1. Прямокутники На площині задано N прямокутників. Сторони кожного прямокутника паралельні осям координат. Визначити площу тієї частини площини, яка належить усім прямокутникам. Вхідні дані: У першому рядку число N, у наступних N рядках містяться по 4 числа X1 Y1 X2 Y2 - координати лівого верхнього та правого нижнього кутів прямокутника відповідно. Координати - цілі числа, що лежать у межах від -10000 до 10000 (1<=N<=1000). Вихідні дані: єдине число - значення площі. Приклад: 2 10 40 30 20 20 30 40 10 Відповідь: 100 3.2. Числа (+ -) У рядок виписано N чисел (1<=N<=40). Потрібно перед кожним числом поставити знак "+" або "-" так, щоб значення отриманого виразу було рівне K. Вхідні дані: у першому рядку числа N і K. у другому N цілих чисел, у межах [0..20]. Вихідні дані: результуючий вираз, в якому знаки та числа відокремлені одним пропуском. Приклад: 3 7 10 14 3 Відповідь: - 10 + 14 + 3 = 7 3.3. Перекладачі В складних умовах ринкової економіки директор фірми "POLYGLOT", що спеціалізується на перекладі літератури з інформатики з N різних мов, вирішив зменшити витрати своєї фірми. Для цього він вирішив звільнити з роботи деяких перекладачів. Напишіть програму, яка визначить працівників, яких потрібно залишити на роботі за таких умов: 1) Кожен перекладач знає дві мови (M1 M2), та отримує заробітну платню C. 2) Бюро повинно перекладати тексти з будь-якої мови на будь-яку іншу. 3) Сумарна заробітна платня повинна бути мінімальною Вхідні дані: у першому рядку два числа, N та K. (2<=N<=100, K<=30000) у наступних K рядках міститься по три числа: M1i M2i Ci - мови які знає i-й перекладач, та його заробітна платня. (1<=Ci<=100). Вихідні дані: у перший рядок вивести число P - кількість працівників, яких потрібно залишити на роботі. у другий рядок вивести P чисел - номери перекладачів, яких потрібно залишити на роботі. Приклад: 6 7 1 2 4 1 6 3 2 3 5 2 5 4 2 6 2 3 4 4 4 5 1 Відповідь: 5 2 5 4 7 6 Примітка. Ваша програма може заробити певні бали навіть у випадку, якщо вона видасть не мінімальну платню. Увага! Створіть папку (каталог) із перших восьми (або менше, якщо прізвище коротке) латинських літер вашого прізвища 2 тур (практичний) 1. Футбольна таблиця. У першому рядку файлу FOOTBALL.DAT містяться два числа, N - кількість команд та M - кількість зіграних матчів. У наступних N рядках - назви команд. Кожен матч описаний у файлі *.DAT, де * - порядковий номер матчу. (1.DAT, 2.DAT, ...). Файл що описує кожен матч має таку структуру: Склад команд описується двома послідовними блоками. У першому рядку блоку записана назва команди, а у другому - число P - кількість гравців, що були заявлені на матч цією командою. У наступних P рядках - прізвища гравців. Далі записано число K - кількість забитих у матчі голів. Наступні K рядків містять прізвища гравців, що забили голи. Побудувати турнірну таблицю за правилами: Команда, що набрала більше очок, повинна йти раніше у таблиці. При рівності очок, першою буде йти команда яка має більше перемог, а якщо цей параметр теж буде рівний, то впорядкування повинно бути за алфавітним порядком. Записати у файл TABLE.REP кожний рядок таблиці таким чином: Спочатку друкується назва команди, далі йде N блоків такого формату "A:B", " - " або " X ". Нехай номер поточної команди Num1, а номер поточного блоку Num2. " X " - ставиться, якщо Num1 = Num2. "A:B" - результат гри між командами Num1 та Num2. (A, B - кількість голів забитих командою Num1 та Num2 відповідно). " - " - якщо Num1 та Num2 ще не грали між собою. В кінці рядка - загальна кількість очок, які набрала команда. Перший блок повинен починатися в рядку з позиції під номером 25. За перемогу нараховується 3 очка, за нічию 1, за програш 0. Обмеження: 2<=N,P<=20; 0<=K<=10. Назви команд та прізвища гравців складаються не більше 20 латинських літер та цифр. Команди грають між собою не більше одного матчу. FOOTBALL.DAT 3 2 BALLERS FOOTERS PROGRAMMERS 1.DAT FOOTERS 4 Player1 Player2 Player3 Player4 BALLERS 5 Gamer1 Gamer2 Gamer3 Gamer4 Gamer5 3 Player1 GAMER3 PLAYER3 2.DAT PROGRAMMERS 4 Olymp1 Olymp2 Olymp3 Olymp4 FOOTERS 3 Player1 Cook Lamberto 2 Olymp3 Olymp2 TABLE.REP FOOTERS X 0:2 2:1 3 PROGRAMMERS 2:0 X - 3 BALLERS 1:2 - X 0 2. Стиснення зображень. Чорно-біле зображення, що складається лише з білих та чорних точок, стискається таким чином. Якщо зображення складається лише з чорних точок, то в вихідний потік виводиться два біта - 0 та 0. Якщо зображення складається лише з білих точок, то в вихідний потік виводиться два біта - 0 та 1. Якщо ж зображення містить чорні та білі точки, то в вихідний потік виводиться біт 1, зображення розбивається на 4 частини, та кожна частина стискується цим самим алгоритмом окремо, спочатку перша, потім друга, третя та четверта: 1 2 4 3 Вихідний потік представляє собою стиснене зображення. Наприклад, зображення 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 буде стиснене як 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 Вхідні дані: Файл test.img містить стиснене зображення розміром 256 на 256 точок. Першими йдуть молодші біти байту. Напишіть програму, що виводить зображення на екран в графічному режимі. 3. Шифр. Вам дано програму CODE, яка шифрує рядки, що складаються з великих латинських літер. Необхідно написати DECODE.* (де * - розширення в залежності від мови програмування, CPP, PAS або BAS), яка буде розшифровувати рядки, що були отримані програмою CODE. Довжина рядків, не перевищує 250 символів. DECODE.* повинна читати рядок з стандартного потоку вводу, і розшифровний рядок виводити у стандартний потік виводу. CODE.PAS Program Code; Function Add(a,b:char):char; Begin a:=chr(ord(a)-ord('A')); b:=chr(ord(b)-ord('A')); Add:=chr((ord(a)+ord(b)) mod 26 + ord('A')) End; var S:string; i:integer; begin readln(S); for i:=2 to length(S) do S[i]:=Add(S[i-1],S[i]); S[1]:=Add(S[length(S)],S[1]); Writeln(S) End. CODE.CPP #include #include char Add(char a, char b) { a-='A'; b-='A'; return (a+b)%26+'A'; } int main() { char S[256]; cin>>S; int n=strlen(S); for(int i=1; i