Сайт підготовки до олімпіади з інформатики

Задача 1. (Властивості Ейлера) Є N поселень. Деякі поселення попарно  з'єднані  стежками. За ними ніякі дві  стежки  загальних  точок  не  мають.  В цілочисельній таблиці СТЕЖКИ [1..N,1..N] задана  інформація  про стежки; кількість стежок між і-m і j-m рівна  значенню  елемента таблиці СТЕЖКИ [і,j]=СТЕЖКИ[j,і]>0 (в тому числі і=j);  Написати алгоритм, який визначає, чи можливо зобразити карту стежок,  не відриваючи олівця від паперу і не малюючи жодної стежки двічі.

Задача 2. (Пошук в глибину)

Турбаза мала для ночівлі N місць, з’єднаних стежками. Туристів можна вести в одну сторону. Довжина стежки – одноденний перехід. Пройти і перевірити всі M-денні маршрути, які починаються на базі K.

Задача 3. Міжнародна конференція

Вас найняли для того, щоб визначити мiсця дипломатiв за столом обговорень мiжнародної конференцiї. На конференцiю запрошенi по одному дипломату з N рiзних країн свiту. Кожен дипломат знає вiд однiєї до М мов. Дипломати, якi не знають спiльної мови, не можуть розмовляти один з одним. До того ж, деякi країни проголосили, що не будуть пiдтримувати дипломатичних стосункiв  з деякими iншими, тобто представники  цих країн не будуть розмовляти один з одним. Ваше  завдання  полягає в розробцi програми  DIPLOMAT.*, що визначає мiсця за столом для дипломатiв таким чином, щоб кожен мiг розмовляти з обома своїми сусiдами, якi сидять лiворуч та праворуч вiд нього.

Стiл, що використовується, круглий i розрахований на N персон. Дипломат може спiлкуватись з дипломатом, який сидить лiворуч однiєю мовою, а з дипломатом, що сидить праворуч, – iншою.

Вхiднi данi:

В першому рядку текстового          файлу DIPLOMAT.DAT – число N. Далi – N рядкiв, по одному рядку на дипломата. Кожен рядок – послiдовнiсть слiв. Сусiднi слова вiдокремленi пропуском. Кожне слово – це послiдовнiсть великих латинських лiтер. Перше слово – код країни – складається з 3 лiтер. Друге слово           має довжину вiд      1 до 5 лiтер i представляє перелiк мов, на яких може спiлкуватись дипломат. Кожна мова позначена однiєю лiтерою. Далi iде список з не бiльш як N              трилiтерних слiв – кодiв  країн, з якими уряд дипломата  пiдтримує стосунки.

Вихiднi данi:

До файлу DIPLOMAT.SOL треба  вивести список  дипломатiв в порядку розмiщення за  столом  (по одному дипломату в рядку). Кожен рядок складається з 3 слiв: перше – код           мови, якою  дипломат може спiлкуватись з  сусiдом  лiворуч, друге – код країни дипломата, третє – код мови для спiлкування з сусiдом праворуч. Можливе iснування  декiлькох   розв'язкiв. Вам  потрiбно  знайти  один. Якщо розв'язку не iснує, Ваша програма повинна видати таке повiдомлення: NO SOLUTION EXISTS.

procedure p(ni,v:integer);

var s,ii:integer;

begin

c[ni]:=v;

if(ni=n)then begin

{***** 1}

for ii:=1 to ni do write(c[ii]);

end

else

for ii:=1 to n do

if (a[v,ii]>0)and (f(ni,ii)) then p(ni+1,ii);

end;

Практична робота «Пошук у ширину та глибину, ейлерів та гамільтонів графи»