1. Вуличнi перегони (100 балів)
Орґанiзацiйний комiтет велосипедних перегонiв Лазуровий Берег-99 звернувся до жандармерiї Сан-Тропе з проханням дозволити провести велосипеднi перегони вулицями цього курортного мiстечка таким чином, щоб кожен учасник мав би певну свободу у виборi шляху до фiнiшу. Жандармерiя у вiдповiдь надiслала в органiзацiйний комiтет план проведення таких перегонiв. На плані пункти-перехрестя було позначено кругами i занумеровано натуральними числами в межах вiд 1 до певного натурального числа n, а окрем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дмiннi вiд старту й фiнiшу цього плану;

• новоутворенi плани не мають спiльних стрiлок, але мають єдиний спiльний пункт, що є фiнiшом для одного плану i стартом для iншого. Цей спільний пункт неможливо досягнути рухом вздовж стрілок, почавши рух з нього самого.

Завдання
Створiть програму race.*, яка допоможе членам органiзацiйного комiтету провести аналiз поданого плану.

Вхідні дані
Кiлькiсть рядкiв вхiдного файлу race.in дорiвнює n — кiлькостi всiх пунктiв перегонiв, що не перевищує 222. Для j в межах вiд 1 до n включно j-ий рядок цього ж файлу мiстить номери кiнцевих пунктiв тих стрiлок, якi виходять з j-го пункту.

Вихідні дані
Перший рядок вихiдного файлу race.out має мiстити у вказаному порядку номери пунктiв, що є стартом i фiнiшом.
Другий рядок цього самого файлу має мiстити кiлькiсть пунктiв, якi неможливо уникнути на шляху вiд старту до фiнiшу та номери цих пунктiв у порядку зростання.
Третiй рядок цього самого файлу має мiстити кiлькiсть пунктiв, якими можна розбити поданий план перегонiв на окремi плани, та номери цих пунктiв у порядку зростання.

Приклад

race.in	race.out	план
3 3 4 5 6 6 7 8 9 5 9 1 2	10 9 2 3 6 1 3

2. Криптограма (100 балів)
Завдання
Створiть програму cripto.*, яка дешифрує запису д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в не перевищує 9, запис кожного з них мiстить не бiльше 9 цифр, але й не менше 2 цифр.

Вхідні дані
Перший рядок вхiдного файлу cripto.in мiстить натуральне число, яке є основою системи числення i лежить в межах вiд 5 до 10 включно.
Другий рядок цього самого файлу мiстить запис дії додавання. Роздiлення доданкiв, суми, знакiв + i = додатковими прогалинами не передбачається.

Вихідні дані
Файл cripto.out має містити всi способи дешифрацiї поданого запису дiї додавання по одному у кожному рядку без повторення (порядок довільний).

Приклад

3. Спіраль чисел (100 балів)
Прямі x = 1/2 + j та y = 1/2 + k при усіх цілих j та k розбивають координатну площину на квадрати. Координати центрів (симетрії) цих квадратів — усі можливі пари цілих чисел. Такі квадрати можна перелічити, тобто занумерувати натуральними числами, різними способами. Наприклад, рухаючись «спіраллю», що складається з відрізків.

Якщо рух розпочати з квадрата з центром (0; 0), то кожній парі цілих чисел, що є центром квадрата, можна поставити у взаємно однозначну відповідність одне натуральне число — див. індекс праворуч знизу на такому рисунку.

• додатний напрям осі абсцис x — це напрям праворуч;
• додатний напрям осі ординат у — це напрям догори;
• індекс праворуч знизу координат (x; у) — натуральне число, що відповідає цій парі.

Завдання
Створiть програму spiral.*, яка для описаного способу нумерації квадратів рухом «спіраллю»:

• при наявності одного натурального числа n у вхідному файлi spiral.in запише у вихідний файл spiral.out пару цілих чисел x та y, що є координатами центра симетрії квадрата з номером n;

• при наявності пари цілих чисел x та y у вхідному файлi spiral.in запише у вихідний файл spiral.out натуральне число n, що є номером квадрата з центром симетрії (x; y).

Для усіх завдань n < 10¹⁷.

Приклади

Програма мовою 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 =         {Назви програм}
  ('race.*','cripto.*' ,'spiral.*');
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.