Ускова О.Ф., Горбенко О.Д. Олимпиадные задачи по программированию. Лучшие решения. Часть 3

Подождите немного. Документ загружается.

Перед уходом ставим флаг. Он означает что

город уже БЫЛ у нас на пути.

Идём по выбранной дороге в следующий

город. (Переходим к пункту 2.)

4. По своим следам возвращаемся в предыдущий

город.

Если мы вернулись НЕ к началу пути то:

Убираем флаг. (Переходим к пункту 3.)

Если мы вернулись к началу пути то:

Открываем дорогу по которой вернулись.

(Переходим к пункту 1.)

5. Все нужные города найдены...

Program Plz2;

{Автор Колбешкин Д.М.}

Const MaxN = 50;

Var i,j,N,t : byte;

fin,fout : text;

a : array [1..MaxN,1..MaxN] of byte;

{Матрица дорог}

b : array [1..MaxN] of byte;

{Запоминаем путь}

c : array [1..MaxN] of byte;

{Формируем ответ}

Procedure Rekurs(k:byte);

{k - город, в котором мы сейчас}

var l:byte;

{l - город, в который думаем сходить}

begin

{i - начало пути}

if k=i then

{Мы вернулись к началу?}

begin

c[i]:=1;

for t:=1 to N do

if b[t]=1 then c[t]:=1

end

else

for l:=1 to N do

{Есть ли дорога к новому городу?}

if (a[k,l]<>0) and (b[l]=0) and

(c[i]=0) then

begin

b[k]:=1;

{Ставим влаг перед уходом}

Rekurs(l);

{Идём в следующий город}

b[k]:=0;

{Убираем флаг при обратном пути}

end;

Begin

writeln (' Задача о дорогах ');

assign(fin,'input.txt');

assign(fout,'output.txt');

reset(fin);

rewrite(fout);

read(fin,n);

for i:=1 to N do

for j:=1 to N do

a[i,j]:=0;

for i:=1 to N do

b[i]:=0;

for i:=1 to N do

c[i]:=0;

while not Eof(fin) do

{Составляем карту дорог}

begin

readln(fin,i,j);

a[i,j] := 1;

a[j,i] := 1;

end;

for i:=1 to N do

for j:=1 to N do

if (c[i]=0)and(a[i,j]=1) then

begin

a[i,j]:=0;

{Закрываем дорогу}

a[j,i]:=0;

{Закрываем дорогу}

Rekurs(j);

{Идём в следующий город}

a[i,j]:=1;

{Открываем дорогу}

a[j,i]:=1;

{Открываем дорогу}

end;

for i:=1 to N do

if c[i]=1 then write(fout,i,' ');

close(fin);

close(fout);

End.

МАТЕРИАЛЫ ПЕРВОЙ ОТКРЫТОЙ РЕГИОНАЛЬНОЙ

СТУДЕНЧЕСКОЙ ШКОЛЫ -ОЛИМПИАДЫ 2001 ГОДА

Результаты 1 тура первой открытой региональной

студенческой школы -олимпиады по программированию и

компьютерному моделированию 2001 года

Список прошедших во 2 тур в ОСНОВНОЙ номинации

1 Абросимов Александр Иванович ВГУ ПММ

2 Белобродский Андрей Андреевич ВГУ Эконом .

3 Белоусова Юлия Владимировна ВИ МВД РТФ

4 Вахтин Сергей Александрович ВГУ Геол.

5 Воронина Татьяна ВГУ ПММ

6 Выростков Дмитрий Андреевич ВГУ ПММ

7 Гашков Максим Александрович ВГПУ ФИЗМАТ

8 Гладышев Олег Викторович ВГУ ПММ

9 Громов Станислав Андреевич ВГУ ПММ

10 Десятов Алексей Дмитриевич ВИ МВД РТФ

11 Домбровская Ольга Валерьевна ВГУ Геол.

12 Затворницкий Александр Петрович ВГТА АТП

13 Иванников Максим Игоревич ВГТУ ФАЭМ

14 Иванов Андрей Васильевич ВГПУ ФИЗМАТ

15 Кадимов Олег Нариманович ВГУ ПММ

16 Карпюк Дмитрий Александрович ВВАИ

17 Катов Михаил Викторович ВГУ Физ.

18 Клинских Антон Александрович ВГУ ПММ

19 Козлов Юрий Станиславович ВИ МВД РТФ

20 Колбешкин Дмитрий Михайлович ВГУ ПММ

21 Комова Анна Анатольевна ВГУ Геол.

22 Курин Михаил Сергеевич ВГТА АТП

23 Куропаткин Андрей Сергеевич ВГПУ физ.-мат.

24 Лесников Дмитрий Вячеславович ВГАСУ ДорСТР

25 Минаков Сергей ВГУ ПММ

26 Мухоедов Дмитрий Сергеевич ВГУ ПММ

27 Некрасов Станислав Юрьевич ВГУ ПММ

28 Новиков Александр Васильевич ВГУ ПММ

29 Окунев Александр Иванович ВГУ ЮРФАК

30 Перов Сергей Николаевич ВГТА ТехнМяса

31 Плешкова Оксана Игоревна ВГУ Гео.

32 Просин Сергей Александрович ВГУ ПММ

33 Рышков Евгений Валериевич ВГАСУ МехАвтоДор

34 Савельев Константин Эдуардович ВГПУ ФИЗ

35 Хаустов Дмитрий Васильевич ВИРЭ ВБСС

36 Чулюков Алексей Владимирович ВГУ ПММ

37 Ширяев Михаил Михайлович ВГУ ПММ

38 Якунин Максим Сергеевич ВГПУ физ.-мат.

Список прошедших во 2 тур в номинации

"ПЕРВОКУРСНИКИ"

1. Андрейчиков Василий Андреевич, ВГУ , ПММ

2 Архипова Ирина Николаевна ВГУ Хим.

3 Безродный Алексей Николаевич ВИРЭ РЭБС

4 Вощинская Елена Сергеевна ВГУ РГФ

5 Глухов Артем Леонидович ВГУ ПММ

6 Родионов Дмитрий Александрович ВГУ ЭКОНОМ

7 Десятов Андрей Дмитриевич ВГУ ФКН

8 Дураков Роман Александрович ВГПУ ФИЗМАТ

9 Колесник Артем Валерьевич ВГТА ФАТП

10 Коржов Николай Евгеньевич ВГУ ПММ

11 Ларин Игорь Александрович ВГУ ПММ

12 Логунов Сергей Иванович ВГУ мат.

13 Лучкин Алексей Юрьевич ВГУ мат.

14 Писаревский Сергей Юрьевич ВГТУ ВМ

15 Сидоренко Станислав Владленович ВГУ ПММ

16 Хлопков Андрей ВГУ ПММ

Список прошедших во 2 тур в номинации

"ИНОГОРОДНИЕ УЧАСТНИКИ"

1 Бабенко Антон Петрович Лискинсий ф-л ВГУ

2 Бурнаев Константин Евгеньевич БелгородскийГТАСМ

АПиИТ

3 Вознюк Дмитрий Леонидович Лискинсий ф-л ВГУ

4 Гриднев Александр Николаевич Ст. Оскольский ф-л ВГУ

ПММ

2 Заколодяжный Юрий Викторович Ст. Оскольский ф-л ВГУ

ПММ

3 Иванов Олег Олегович Липецкий ГТУ ФАИИ

4 Исаева Татьяна Михайловна БелгородскийГТАСМ АПиИТ

5 Козлова Ольга Викторовна Ст.Оскольский ф-л МИСиС

6 Колесников Максим Александрович Ст.Оскольский ф-л

МИСиС ИТ

7 Корниенко Станислав Альбертович Липецкий ГТУ ФАИ

8 Мавлеткулов Андрей Леонидович Липецкий ГТУ ФАИИ

9 Малашенко А.П. Ст.Оскольский ф-л МИСиС

10 Михалин Роман Валерьевич Лискинсий ф-л ВГУ

11 Неумывакин Сергей Сергеевич Лискинсий ф-л ВГУ

12 Семерин Сергей Павлович БелгородскийГТАСМ АПиИТ

13 Сувейкэ Евгений Георгиевич Ст.Оскольский ф-л МИСиС

14 Тищенко Иван Ст.Оскольский ф-л МИСиС

Результаты 2 тура открытой региональной студенческой

школы -олимпиады по программированию и

компьютерному моделированию

Ф .И .О . участников Баллы

Колбешкин Дмитрий Михайлович 11

Просин Сергей Александрович 10

Гайдай Виктор 8

Некрасов Станислав Юрьевич 8

Мухоедов Дмитрий Сергеевич 7

Гладышев Олег Викторович 6,5

Выростков Дмитрий Андреевич 6

Затворницкий Александр Петрович 6

Клинских Антон Александрович 6

Громов Станислав Андреевич 5

Корниенко Станислав Альбертович 5

Ширяев Михаил Михаилович 5

Бурнаев Константин Евгениевич 4

Новиков Александр Васильевич 4

Минаков Сергей 4

Хауи Мария 3

Абросимов Александр 2

Исаева Татьяна Михайловна 2

Катов Михаил Викторович 2

Мавлеткулов Андрей Леонидович 2

Тищенко Иван Иванович 2

Белобродский Андрей Андреевич 1

Вахтин Сергей Александрович 1

Воронина Татьяна Ивановна 1

Гашков Максим Александрович 1

Гриднев Александр Николаевич 1

Десятов Алексей Дмитриевич 1

Докучав Михаил Юрьевич 1

Заколодяжный Юрий Викторович 1

Иванов Олег Олегович 1

Козлов Юрий Станиславович 1

Козлова Ольга Викторовна 1

Колесников Максим Александрович 1

Лесников Дмитрий Вячеславович 1

Малашенко Олег П 1

Плешкова Оксана Игоревна 1

Пронин Сергей Сергеевич 1

Рышков Евгений Валерьевич 1

Семернин Сергей Павлович 1

Сувейкэ Евгений Георгиевич 1

Тузов Сергей 1

Чулюков Алексей Владимирович 1

Якунин Максим Сергеевич 1

Белоусова Юлия Владимировна 0,5

Вознюк Дмитрий Леонидович 0,5

Домбровская Ольга Валерьевна 0,5

Иванников Максим Игоревич 0,2

Иванов Андрей Васильевич 0,2

Кадимов Олег Нариманович 0,2

Карпюк Дмитрий Александрович 0,5

Комова Анна Анатольевна 0,2

Курин Михаил Сергеевич 0,5

Куропаткин Андрей Сергеевич 0,5

Логунов Сергей Иванович 0,2

Михалин Роман Валерьевич 0,2

Неумывакин Сергей Сергеевич 0,2

Окунев Александр Иванович 0,5

Перов Сергей Николаевич 0,2

Савельев Константин Эдуардович 0,2

Хаустов Дмитрий Васильевич 0,2

Номинация "ПЕРВОКУРСНИКИ"

ФИО ВУЗ Баллы

Коржов Николай Евгеньевич ВГУ 13

Десятов Андрей Дмитриевич ВГУ 12

Сидоренко Станислав Владленович ВГУ 10

Глухов Артем Леонидович ВГУ 8

Логунов Сергей Иванович ВГУ 7

Писаревский Сергей Юрьевич ВГТУ 6

Андрейчиков Василий Андреевич ВГУ 5

Колесник Артем Валерьевич ВГТА 5

Ларин Игорь Александрович ВГУ 5

Хлопков Андрей ВГУ 5

Дураков Роман Александрович ВГПУ 3

Архипова Ирина Николаевна ВГУ 1

Безродный Алексей Николаевич ВИРЭ 0,2

Вощинская Елена Сергеевна ВГУ 0,2

Лучкин Алексей Юрьевич ВГУ 0,2

Родионов Дмитрий Александрович ВГУ 0,2

ВАРИАНТЫ ЗАДАНИЙ, ПРЕДЛАГАВШИХСЯ НА

ПЕРВОЙ ОТКРЫТОЙ РЕГИОНАЛЬНОЙ

СТУДЕНЧЕСКОЙ ШКОЛЕ -ОЛИМПИАДЕ 2001 ГОДА

З А Д А Н И Я 1 Т У Р А

З а д а ч а

(общая для всех номинаций)

На острове BORLAND каждый из его жителей организовал

партию, которую сам и возглавил. В каждой партии – не менее

двух человек. По Конституции острова в парламент должны

войти главы всех партий, но финансовые трудности не

позволяют это сделать. На референдуме граждане острова

решили , что каждую партию в парламенте достаточно

представлять одним членом партии.

Требуется сформировать парламент как можно меньшей

численности , в котором были бы представлены все партии.

Технические требования.

Все главы партий (и партии) перенумерованы от 1 до N

(4<=N<=150).

Входные данные.

Первая строка входного текстового файла input.txt

содержит N - число партий, в каждой из последующих строк

перечисляются через пробел порядковые номера граждан –

членов соответствующей партии.

Выходные данные.