1. Мотель (100 балів)
Рiвнину перетинають прямолінійні швидкiснi автостради.
Завдання
Створiть програму motel.*, яка вибере найвигiднiше мiсце для мотелю, вiд якого сума вiдстаней до всiх автострад найменша.
Вхідні дані
Перший рядок вхiдного файлу motel.in мiстить натуральне число n — кiлькiсть
автострад, якi надалi вважаємо рiзними прямими лiнiями.
Для j в межах вiд 1 до n включно (j + 1)-ий рядок цього файлу мiстить 4 натуральних числа — декартовi координати двох рiзних точок на j-iй прямiй, вiдстань мiж якими виражається натуральним числом. Ці 4 числа подано у такому порядку: спочатку абсциса й ордината однієї точки, потім — абсциса й ордината іншої точки.
Кiлькiсть прямих n лежить в межах вiд 2 до 10, а всi iншi числа вхiдного файлу motel.in не перевищують 123.
Вихідні дані
Перший рядок вихiдного файлу motel.out має мiстити найменшу можливу суму вiдстаней вiд автострад до мотелю. Наступні рядки мають такий вигляд.
Занумеруємо дані прямі, координати точок яких подано вхідним файлом, у тому порядку, в якому їх подано вхідним файлом. У випадках 2–3 дані про вершини, що є точками перетину пари з даних прямих, потрібно розташувати у порядку неспадання меншого номера пари прямих, а при однакових менших номерах — у порядку зростання більшого номера. У випадку 5 коефіцієнти рівнянь прямих потрібно розташувати у порядку зростання номера прямої.
У випадках 1–3 координати точки потрібно записати у такому порядку:
У випадках 4–5 коефіцієнти рівняння прямої потрібно записати у такому порядку:
Усі ці коефіцієнти мають бути цілими і найменшими за абсолютною величиною. Інакше кажучи, найбільший спільний дільник коефіцієнтів рівняння однієї прямої має дорівнювати 1. При цьому коефіцієнт при абсцисі має бути невід'ємним. Якщо він дорівнює нулю, то коефіцієнт при ординаті має бути додатним.
Будь-яке число у вiдповiдi треба подати нескоротним дробом з цiлим чисельником i натуральним знаменником, роздiленими знаком дiлення /. Якщо знаменник дорiвнює 1, то знак дiлення i знаменник не записувати.
Приклад
| motel.in | motel.out |
|---|---|
|
2 0 0 4 3 1 1 0 1 |
0 1 4/3 1 |
2. Тест (100 балів)
У дитячому садку проводиться тестування. Дiтям показують бiлi аркушi паперу прямокутної форми, якi подiлено на рiвнi квадрати горизонтальними та вертикальними лiнiями. Частину квадратiв зафарбовано чорною фарбою, а частину нi.
Фiґурою на такому малюнку називають сукупнiсть чорних квадратiв, для довiльної пари яких центри квадратiв можна з'єднати ламаною, що повнiстю мiститься у чорних квадратах i не мiстить жодної вершини квадрата.
Рiзними фiґурами називають фiґури, якi неможливо сумiстити послiдовним застосуванням паралельних перенесень, поворотiв на 90° i симетрiї вiдносно вертикальної чи горизонтальної прямої.
Дiтям пропонують встановити, скiльки всього фiґур зображено на малюнку, i скiльки рiзних фiґур зображено на цьому малюнку.
Завдання
Створiть програму test.*, яка дає правильну вiдповiдь на поставлене питання.
Вхідні дані
Перший рядок вхiдного файлу test.in мiстить натуральне число n — кiлькість квадратiв, якi розташованi на малюнку по вертикалi та горизонталi.
Наступнi n рядкiв по n символiв цього файлу мiстять подання малюнку, в якому символ « » (пропуск) означає бiлий квадрат, а будь-який інший — чорний.
У 20% тестів n ≤ 30, у 40% тестів n ≤ 90, у 60% тестів n ≤ 180, у 80% тестів n ≤ 360, у всіх тестах n ≤ 528.
Кількість клітин однієї фіґури не перевищує:
50 у 20% тестів, 500 у 36% тестів, 2000 у 52% тестів, 8000 у 68% тестів, 15000 у 84% тестів, 125000 у 100% тестів.
Вихідні дані
Єдиний рядок вихiдного файлу test.out має мiстити у вказаному порядку два натуральних числа: кiлькiсть всiх фiґур та кiлькiсть рiзних фiґур. Вiдомо, що обидва шуканих числа не перевищують 248.
Приклад
| test.in | test.out |
|---|---|
9
*** **
* **
* *
* *
** ***
** *
* *
* * | 4 2 |
Зауваження щодо програмної реалізації мовою Pascal
При використанні рекурсивної процедури визначення клітин однієї фіґури у програмі Turbo Pascal за рахунок керування стеком можна отримати до 76% балів за завдання. Використання того самого коду з іншими параметрами керуванням стеком при компіляції Free Pascal'ем забезпечує 100% балів.
3. Cудоку (100 балів)
Прообраз сучасного судоку, так звані «магічні квадрати» знали ще у стародавньому Китаї. В Європі щось схоже згадують з XVIII століття. Тоді швейцарський математик Леонард Ейлер (Leonhard Euler) з'ясував, що в матриці розміром 9×9 кожен рядок і кожен стовпчик можна заповнити цифрами від 1 до 9 без повторення. Судоку в сучасному вигляді з'явилася в одному з американських журналів пазлів в 1979 році. Автором ломиголовки був громадянин США, 74 річний архітектор на пенсії Говард Ґарнс (Howard Garns). Видавець — журнал «Math Puzzles and Logic Problems» дав пазлу ім'я «Number Place», яке досі використовують у США. Справжню популярність головоломка здобула у 2005 році, коли японський журнал Nikoli став регулярно друкувати її на своїх сторінках.
Правила судоку такі.
Ігрове поле складається з квадрата розміру 9×9 клітин, розділеного на менші квадрати-регіони розміру 3×3 клітини. Таким чином, все поле налічує 81 клітинку. У деяких з них вже на початку гри розташовані числа від 1 до 9 включно.
Мета головоломки — потрібно заповнити вільні клітинки цифрами від 1 до 9 так, щоб в кожному рядку, в кожному стовпчику й у кожному малому квадраті-регіоні розміру 3×3 кожна цифра, відмінна від нуля, зустрічалася лише один раз.
Завдання
Створiть програму sudoku.*, яка розв'язує ломиголовку судоку.
Вхідні дані
Кожний з 9-ти рядів вхiдного файлу sudoku.in містить 9 символів, кожен з яких є прогалиною або цифрою від 1 до 9 включно. Прогалина відповідає незаповненому полю. Вхідні дані ґарантують єдиність розв'язку та можливість його отримання без перебору гіпотез щодо вмісту незаповнених полів.
Вихідні дані
Вихiдний файл sudoku.out має мiстити результат повного заповнення поля судоку, поданого вхідним файлом.
Приклад
| sudoku.dat | sudoku.res |
|---|---|
6 5 4 83 4 7 92 761 1 85 6 82 61 2 79 3 629 81 8 4 59 4 7 2 | 675139824 831624975 924857613 719385246 358246197 246791538 562973481 187462359 493518762 |
Програма мовою Turbo Pascal 7.0
для тестування коректності взаємодії з системою тестування Kgrader
{$I-}
uses dos,windos;
const
drive=4; {Номер логiчного пристрою: 1-A, 2-B,
3-C, 4-D, 5-E, 6-F, 7-G, 8-H, 9-I, 10-J,
11-K, 12-L, 13-M, 14-N, 15-O, 16-P, 17-Q, 18-R,
19-S, 20-T, 21-U, 22-V, 23-W, 24-X, 25-Y, 26-Z}
np=3; {Кiлькiсть: програм}
nc=6; {компiляторiв}
p: array[1..np] of pchar = {Назви програм}
('motel.*','test.*' ,'sudoku.*');
c: array[1..nc] of string[16] {Компiлятори}
= ('{ Turbo Pascal }',
'{ Free Pascal }','{ Turbo Delphi }',
'/* TCC */','/* GCC */','/* VC */');
ex=' виявлено';
no=' вiдсутнiй';
yes=' має такий перший рядок: ';
var ip,ic,j: byte; dir: pchar; s: string;
nofile: boolean; i,o: text;
dirInfo: tsearchrec; BEGIN
assign (o,'readme.txt');
rewrite(o);
GetMem (dir,800);
GetCurDir(dir,drive);
writeln(o,dir); close(o); reset(o);
readln(o,s); close(o); rewrite(o);
write(o,'Поточна тека: ',s);
j:=length(s);
repeat dec(j)
until not (s[j] in ['A'..'Z','a'..'z']);
if (s[j] <> '\') or (j+9 < length(s))
then writeln(o,' має некоректну назву')
else writeln(o);
assign(i,'contest.txt'); reset(i);
if ioresult <> 0 then writeln(o,'contest.txt ',no)
else begin
readln(i,s); close(i);
writeln(o,'contest.txt ',yes,s) end;
for ip:=1 to np do begin
nofile:=true;
findfirst(p[ip],faarchive,dirinfo);
while doserror = 0 do begin
write(o,dirinfo.Name+ex+' з ');
nofile:=false;
assign(i,dirinfo.Name);
reset (i);
readln(i,s);
close (i);
if not ((s=c[1])or(s=c[2])or(s=c[3])
or (s=c[4])or(s=c[5])or(s=c[6]))
then write(o,'не');
writeln(o,'коректним замовленням комiлятора ',s);
findnext(dirInfo) end;
if nofile then writeln(o,p[ip],no) end;
close(o) END.