Олимпиады. Олимпиадные задания

Интересные алгоритмы, олимпиадные задачи, эффектные и эффективные решения. freepascal, delphi, c, c++, c#, java, javascript, perl, ruby, python, php, bash, wsh и т.д. Компиляторы, интерпретаторы, линкеры, отладчики, системы контроля версий и многое другое.

Модератор: xdsl

Олимпиады. Олимпиадные задания

Сообщение Gemini 21 фев 2009, 13:28

В прошедшую пятницу господин Слинкин высказался весьма негодующе по поводу столь малого участия студентов информатики в олимпиадах (2е студентов ШГПИ из 11 участников заочной олимпиады по программированию)...и пообщещал принять меры, раз уж сейчас информатики настолько "слабые" и неинициативные студенты...

Но собственно эта тема, для того чтобы господа преподователи выкладывали олимпиадные задания для показа уровня заданий.
Не относитесь к этой жизни слишком серьезно,господа.Все равно вам из неё живым не выбраться.
Gemini
 
Сообщения: 90
Зарегистрирован: 13 янв 2009, 12:42
Откуда: Сейчас в Ша
Полное имя: Плешков Сергей Александрович

Re: Олимпиады. Олимпиадные задания

Сообщение Vladislav_133 21 фев 2009, 15:56

Замечательно. Задачи будут, в том числе и из прошлых лет. Будем обсуждать.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1325
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 21 фев 2009, 16:12

Эк он меня пропесочил ;). Ладно, будет задачек, будет решений, однако и от вас, господа студенты, ждем реального участия.
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиады. Олимпиадные задания

Сообщение LMP 21 фев 2009, 18:32

Gemini писал(а):... В прошедшую пятницу господин Слинкин высказался весьма негодующе по поводу столь малого участия студентов информатики в олимпиадах (2е студентов ШГПИ из 11 участников заочной олимпиады по программированию) ...

Всего двое студентов, но почему так мало?

PS: Архив задач - acm.timus.ru.
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 22 фев 2009, 02:16

Собираюсь на виртуалке поднять сервер автоматической проверки олимпиадных решений. Сделать это самому катастрофически не хватает времени. Приглашаю помочь мне в этом компетентных студентов (требуется понимание специфики проверки ол.задач + навыки админства linux). При качественном и быстром решении данной задачи будут положительные бонусы. Предупреждаю заранее - технологию надо внедрить быстро, чтобы успеть до очной олимпиады (18-19 марта). Если не успеть, то смысла нет затевать привлечение студентов - разверну все сам, как будет свободное время.

LMP писал(а):... но почему так мало?
Сие есть тайна великая. Могу только предполагать. Навскидку варианты:
1. Мозгов мало
2. Нафиг надо
3. Порешал-запутался-нерешил, плюнул, сделал вид что просто мимо проходил.
4. А? Что? Какая олимпиада? Где? Когда? Почему мне персонально не сообщили?
5. Грипп
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиады. Олимпиадные задания

Сообщение Rei 23 фев 2009, 12:31

Интересно. Будем ждать задачек. Но по их появлению боюсь окажется что их сложность такая будет, что мозгов и правда мало станет :lol:

LMP писал(а):PS: Архив задач - http://acm.timus.ru/.

пока ушел сюда.
Демократия есть одурачивание народа при помощи народа ради блага народа. (Оскар Уайльд)
Аватара пользователя
Rei
Elite
 
Сообщения: 52
Зарегистрирован: 21 дек 2008, 20:45
Откуда: Шадринск
Полное имя: Кононцев Павел Викторович

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 25 фев 2009, 12:01

По результатам проверки заочной олимпиады выложу сюда некоторые технические соображения. Проверка закончится только 1 марта, но соображения уже накопились.
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 25 фев 2009, 14:32

Вот, например, задачка, которая (с небольшими модификациями) идет у меня лабораторной работой для 4курса по СРВ.

Дан набор задач с заранее известным временем исполнения (сколько едениц времени задача проработает) и временем готовности к исполнению (начиная с какого момента времени задача может быть запущена). Найти такую последовательность запуска задач, чтобы среднее время исполнения задачи было минимальным. Простой системы недопустим и считается ошибкой.
В исходном файле первая строка - кол-во задач, последующие строки - через пробел 1)буква-идентификатор задачи, 2)время исполнения, 3)время готовности к исполнению.

Пример исходного файла 1:
Код: Выделить всё
4
A 30 50
B 50 0
C 70 0
D 10 20

Пример результата 1:
Код: Выделить всё
B D A C


Пример исходного файла 2:
Код: Выделить всё
3
A 30 50
B 10 0
C 15 0

Пример результата 2:
Код: Выделить всё
Error
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиады. Олимпиадные задания

Сообщение LMP 01 мар 2009, 17:22

xdsl писал(а):... Найти такую последовательность запуска задач, чтобы среднее время исполнения задачи было минимальным. ...

Что значит "среднее время исполнения задачи было минимальным". Насколько я понимаю среднее время всегда будет одинаковым и равно сумме всего "времени исполнения" делить на количество задач(кроме случаев простоя системы, но эта ситуация считается ошибкой).
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 01 мар 2009, 21:04

LMP писал(а):Что значит "среднее время исполнения задачи было минимальным". Насколько я понимаю среднее время всегда будет одинаковым и равно сумме всего "времени исполнения" делить на количество задач(кроме случаев простоя системы, но эта ситуация считается ошибкой).

А на лекции кто ходить будет? Ко всему прочему еще и экзаменационный вопрос будет, куда этот алгоритм включен.

Пример на двух задачах: A (10 секунд на работу) и B (20 секунд на работу)
Случай 1: AB - задача A выполняется 10 секунд, задача B - 30 секунд (из них 10 ждет, пока завершится задача А)
Случай 2: BA - задача B выполняется 20 секунд, задача A - 30 секунд (из них 20 ждет, пока завершится задача B)

P.S. Вас пока можно поздравить с 1 местом на заочной олимпиаде (до завершения периода аппеляций)
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиады. Олимпиадные задания

Сообщение LMP 01 мар 2009, 22:03

xdsl писал(а):... А на лекции кто ходить будет? Ко всему прочему еще и экзаменационный вопрос будет, куда этот алгоритм включен. ...

Про лекции да, виноват. Но данная задача выложена на общее обсуждение, и её может порешать любой человек, и большинство из них так же не были на лекциях по данному предмету. Лично мне было бы понятней если бы в условии было написано "среднее время ожидания задач". Остались ещё вопросы, ну да ладно, в лекциях всё узнаю.
xdsl писал(а):... P.S. Вас пока можно поздравить с 1 местом на заочной олимпиаде (до завершения периода аппеляций) ...

Спасибо.
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 07 мар 2009, 09:37

Заочная олимпиада закончилась, выкладываю решение четвертой задачи. Делал я его специально под Solver, поэтому написано на php. Если появятся заинтересованные лица, перепишу на freepascal, с комментариями - что получилось сложнее, а что проще.
Вложения
gtree.php.gz
Решение "пиратской" задачки
(2.29 Кб) Скачиваний: 315
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиада по программированию в рамках студенческого форума

Сообщение Vladislav_133 20 мар 2009, 20:06

Перенесено из ветки https://shgpi.edu.ru/forum/viewtopic.php?f=41&t=85

Думаю, что можно начинать обсуждение олимпиадных задач. Начну с задачи 5. За нее давали всего 2 очка. В последствии я понял, что цена ее должна быть несколько выше. Ну, перейдем к самой задаче.
Суть задачи в следующем. Дано множество пар чисел (файл input.txt). Например, такое

2 3
7 8
8 9
12 11

Необхожимо выделить такое подмножество (поместить его в output.txt), в котором
1. Все числа были различны.
2. Количество пар чисел было бы максимально.
В нашем примере таких множеств два

2 3
7 8
12 11

и

2 3
8 9
12 11

Но по условию задачи требуется найти только одно множество, указав в первой строке файла количество пар в множестве.
Замечу сразу, что по условию задачи пары типа 2 2 или 4 4 не могут входить ни в какой из искомых подмножеств, ведь в них уже два одинаковых числа. Но эти пары лучше всего отбрасывать еще на стадии чтения из исходного файла.

Задача 5. Продолжение следует...
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1325
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Олимпиада по программированию в рамках студенческого форума

Сообщение Vladislav_133 20 мар 2009, 20:12

И так, продолжим с задачей 5.
Первое решение, которое я предлагаю, рекурсивно. Да, все решения буду публиковать на языке С. Как то сложилось, что олимпиадные задачи я прорешиваю именно на С.
И так в основе решения лежит рекурсивная функция. Вот она

Код: Выделить всё
int rec(int h)
{
    int i,k,g;
    a1[max1]=a[h]; b1[max1]=b[h]; max1++;
    if(max1>max)
    {
        max=max1;
        for(g=0; g<max1; g++)
        {
            a2[g]=a1[g]; b2[g]=b1[g];
        }
    }
    for(i=h+1; i<m; i++)
    {
        for(k=0; k<max1; k++)
        {
            if(a[i]==a1[k]||a[i]==b1[k]||b[i]==a1[k]||b[i]==b1[k])break;
        }
        if(k==max1)  rec(i);
    }
    max1--;
}


Вызов функции rec осуществляется из следующего цикла

Код: Выделить всё
max=0;
for(j=0; j<m; j++)
{
  max1=0; rec(j);
}


Здача 5. Продолжение следует...
Последний раз редактировалось Vladislav_133 21 мар 2009, 08:14, всего редактировалось 1 раз.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1325
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Олимпиада по программированию в рамках студенческого форума

Сообщение Vladislav_133 20 мар 2009, 20:32

Продолжаем с задачей 5.
Вообще при использовании рекурсии важно правильно определить глобальные и локальные переменные. Можно воспользоваться следующим правилом: все, что по сути задачи должно быть быть глобальным, нужно сделать глобальным. Все остальное должно быть локальным. Попробуйте в нашем примере переменную i сделать глобальной переменной и наша программа будет работать не верно.
Какие же глобальные переменные мы используем?
max - длина подмножества. В конце работы программы переменная будет содержать длину искомого множества. Замечу, что значение переменной может только увеличиваться или оставаться постоянным. Переменную можно назвать также временным максимум.
max1 - текущая длина искомого подмножества. Значение может уменьшаться и увеличиваться. Как только max1>max, так сразу выполняется действие max=max1.
a[], b[] - исходное множество пар чисел.
a1[], b1[] - переменное подмножетсво длины max1.
a2[],b2[] - подмножество длины max. В конце работы программы это будет искомое подмножество. Замечу, что как только выполниться условие max1>max, так сразу a1->a2 и b1->b2.

Комментарий к решению пока закончился. Хотелось бы услышать:
1. Вопросы по решению.
2. Предложения, как улушить алгоритм (наверняка они есть).
3. Предложения новых решений.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1325
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 21 мар 2009, 10:25

Внесу и свою лепту.
3. В поисках пиратского клада, второй сезон (4 балла) (полное условие см. http://shgpi.edu.ru/f11/info/conf_olimp_2009/rule.html)
Если отбросить в сторону весь "пиратский" антураж, то суть задачи проста. Есть "зашумленный" двумерный шаблон, нужно найти все совпадения этого шаблона со столь-же "зашумленным" содержимым некоторой большой двумерной области. Этакий finereader в миниатюре ;) . К счастью, нужно найти все точные совпадения, что упрощает задачу на порядок. Еще более задачу упрощает то, что совершенно достоверно известно, что является "шумом", а что - нет. Значащей точкой является цифра 1, все остальные цифры - шум
Пример исходного файла input.txt:
Код: Выделить всё
912
101
111
141
121

210800
131008
111410
101101
101111
000101
310181
131417
111110
121910
121715

Пример результирующего файла output.txt:
Код: Выделить всё
1 1
3 4
7 1
7 3
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 21 мар 2009, 11:12

3. В поисках пиратского клада, второй сезон (4 балла). Продолжение первое.
Первая проблема, которую требовалось решить, единообразна для всех задач и собственно с алгоритмами решения самих задач несвязанна, а именно - анализ исходного файла. Проблема имеет место быть, т.к. формат исходного файла может быть разнообразен, в нем могут присутствовать незначащие строки, лишние разделители и т.п. (см. "Правила формирования исходных файлов данных" здесь: http://shgpi.edu.ru/f11/info/conf_olimp_2009/rule.html). Таким образом внагрузку всегда шла маленькая подзадача, за некорректное решение которой лично я снимал 1 балл (один из тестов всегда формировался с учетом "Правил"). Рассмотрим ее решение для задачи номер 3 (язык программирования - freepascal).
Подсветка синтаксиса: (first.pas) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
  1. uses sysutils;
  2.  
  3. var obraz:array[1..10] of string;  obri,obrj:integer; // матрица для хранения образа (шаблона) и его размеры
  4. var data:array[1..100] of string; datai,dataj:integer; // матрица для хранения области и ее размеры
  5.  
  6. procedure correct(var s:string); var i:integer; begin  for i:= 1 to length(s) do if s[i]<>'1' then s[i]:='0'; end;
  7.  // процедура для очистки переданной строки от шума
  8.  
  9. procedure reada;
  10.   var s:string;
  11.  begin
  12.   repeat readln(s); s:=trim(s); until s<>''; // считали и отбросили все пустые строки из файла
  13.   obri:=0;
  14.   repeat
  15.    inc(obri);  correct(s);  obraz[obri]:=s;  readln(s);  s:=trim(s);
  16.   until s=''; // считали образ, по выходу из цикла в переменной obri - кол-во строк образа
  17.                 // на пустые строки внутри образа не проверяли, т.к. по условию задачи их там быть не может
  18.   obrj:=length(obraz[1]); // определили кол-во столбцов образа
  19.  
  20.   repeat readln(s); s:=trim(s); until s<>''; // считали и отбросили все пустые строки между образом и областью
  21.   datai:=1;  correct(s);  data[datai]:=s;
  22.   while not eof do begin
  23.    readln(s);   s:=trim(s);   if s='' then continue;  
  24.    inc(datai);  correct(s);  data[datai]:=s
  25.   end;
  26.   dataj:=length(data[1]);
  27.   // аналогично образу считали содержимое области. Отличия - считывали до конца файла и с учетом возможных пустых строк в теле области
  28.  end;
  29.  
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 21 мар 2009, 13:29

3. В поисках пиратского клада, второй сезон (4 балла). Окончание.
Код: Выделить всё
function test(i,j:integer):boolean; // возращает истину, если по координатам i,j области находится левый верхний угол образа
  var k: integer;
begin
  result:=false; // предполагаем, что образа в области нет
  for k:=1 to obri do begin
   if obraz[k]<>copy(data[i+k-1],j,obrj) then exit;  // если действительно есть несовпадения в очередной строке образа и области - выходим
  end;
  result:=true; // вышли из цикла запланировано, значит образ полностью соответствует рассматриваемому участку области
end;

// начинаем основную программу
var found:boolean;  i,j:integer;
begin
assign(input,'input.txt'); reset(input); // сопоставили стандартный поток ввода с файлом 'input.txt'
assign(output,'output.txt'); rewrite(output); // сопоставили стандартный поток вывода с файлом 'output.txt'
// две предыдущих операции проделали, чтобы перенаправить ввод и вывод на требуемые файлы
reada; // считали образ и область
found:=false; // считаем, что образ нигде с областью не совпадает
for i:=1 to datai-obri+1 do
  for j:=1 to dataj-obrj+1 do // перебираем все точки области
   if test(i,j) then begin
    writeln(i,' ',j); // образ совпал с участком области, выводим координаты левого верхнего угла совпадения
    found:=true;
   end;
if not found then writeln('empty'); // совпадений не было, сигнализируем об этом
end.
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 23 мар 2009, 22:20

1. В поисках пиратского клада, четвертый сезон (8 баллов) (полное условие см. http://shgpi.edu.ru/f11/info/conf_olimp_2009/rule.html)

Снова отбросив "пиратский" антураж, можем видеть, что суть задачи - нахождение всех кратчайших путей в лабиринте. Каждый шаг в лабиринте имеет свой вес, равный либо 1 (свободный проход), либо заранее заданному значению >1 (стена). Решение может быть рекурсивным, однако в таком случае мы найдем все пути в лабиринте от исходной точки до конечной, из которых затем выберем кратчайшие. К сожалению, такой подход в нашем случае совершенно нереален, несмотря на все возможности оптимизации (напр., отбрасывание путей, длина которых к определенному моменту становится больше уже найденного пути). Математики могут на досуге подсчитать кол-во всех путей из одной точки в другую хотя-бы в матрице 10 на 10. В нашем-же случае матрица может быть 100 на 100.

Решение проблемы было в свое время предложено Дейкстрой. Суть его не слишком сложна, поэтому предлагаю заглянуть в википедию, на страницу Алгоритм Дейкстры. С помощью модификации данного алгоритма мы найдем минимальные расстояния от исходной точки лабиринта до всех остальных (чуть оптимизировав, можно искать только до конечной точки). Затем рекурсивно пройдемся от конечной точки до начальной, перемещаясь по найденным путям и готовя для вывода строку, в которой закодирован очередной найденный путь.

Итак, решение разбиваем на 3 части:
1. Загрузка данных из файла
2. Нахождение всех кратчайших путей от исходной точки до всех остальных в матрице
3. Формирование закодированных строк, описывающих кратчайший путь от исходной точки к конечной
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 24 мар 2009, 11:21

1. В поисках пиратского клада, четвертый сезон (8 баллов), продолжение первое (полное условие см. http://shgpi.edu.ru/f11/info/conf_olimp_2009/rule.html)
Рассмотрим механизм загрузки и принципы хранения данных. Исходный файл может выглядеть так:
Код: Выделить всё
7
001000000100
001000000101
000101000101
013101001100
010001010101
011111110101
001000010101
100010001111
000011011011
001000210011

Нужно решить, где и как хранить лабиринт и сопутствующие данные (сложность "пробоя" стены, размеры лабиринта, координаты начальной и конечной точек и т.д.). Вот что у меня получилось:
Код: Выделить всё
uses  Classes, SysUtils
var a:array[1..1000,1..1000,1..2] of integer;
// каждая ячейка матрицы содержит массив из двух элементов. В первом - сложность прохода по данной точке лабиринта, во втором в дальнейшем будем хранить
// минимальное кол-во шагов от данной точки до начальной.
ci:integer; cj:integer; // размеры матрицы
endi,endj:integer; // координаты конечной точки
begi,begj:integer; // координаты начальной точки (для данной задачи - необязательно, но на всякий случай)
difficulty:integer; // сложность прохода
current,i,j:integer; filled:boolean; // используются позднее
var ts:TStringList; // используется позднее для хранения списка найденных путей и выполнения их сортировки.

Теперь - процедура загрузки исходных данных.
Код: Выделить всё
procedure reada;
  var s:string;
begin
  readln(difficulty);
  ci:=0;
  while not eof do begin
   readln(s);  s:=trim(s);  if s='' then continue;
   inc(ci);
   for cj:=1 to length(s) do begin
     case s[cj] of
      '0': begin a[ci,cj,1]:=1;  a[ci,cj,2]:=0; end;
      '1': begin a[ci,cj,1]:=difficulty; a[ci,cj,2]:=0; end;
      '2': begin a[ci,cj,1]:=1; a[ci,cj,2]:=1; begi:=ci; begj:=cj; end;
      '3': begin a[ci,cj,1]:=1; a[ci,cj,2]:=0; endi:=ci; endj:=cj; end;
     end;
   end;
  end;
end;

Считывание данных производится со стандартного потока ввода, однако в основной программе поток ввода будет сопоставлен с файлом input.txt.
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 24 мар 2009, 12:59

1. В поисках пиратского клада, четвертый сезон (8 баллов), продолжение второе (полное условие см. http://shgpi.edu.ru/f11/info/conf_olimp_2009/rule.html)
Процедура spf заполняет каждую точку матрицы кратчайшим расстоянием до исходной точки.
Код: Выделить всё
procedure spf;
begin
current:=0; // отвечает за текущую длину кратчайшего пути
filled:=false;
while not filled do begin // выходим из цикла, если не осталось необработанных точек матрицы
  inc(current); // увеличиваем текущую длину кратчайшего пути
  filled:=true; // предположим, что не осталось необработанных точек матрицы
  for i:=1 to ci do begin
   for j:=1 to cj do begin
    if a[i,j,2]=0 then filled:=false; // предположение неверно, необработанные точки остались
    if a[i,j,2]=current then begin
       // если точка содержит текущий кратчайший путь, обрабатываем все ранее необработанное вокруг нее,
       // с учетом сложности прохождения
       if (i>1) and (a[i-1,j,2]=0) then inc(a[i-1,j,2],a[i-1,j,1]+current);
       if (i<ci)and (a[i+1,j,2]=0) then inc(a[i+1,j,2],a[i+1,j,1]+current);
       if (j>1) and (a[i,j-1,2]=0) then inc(a[i,j-1,2],a[i,j-1,1]+current);
       if (j<cj)and (a[i,j+1,2]=0) then inc(a[i,j+1,2],a[i,j+1,1]+current);
    end;
   end;
  end;
end;
end;

Если сейчас создать проверочную процедуру, типа:
Код: Выделить всё
procedure outa;
   var s:string;
begin
  for i:=1 to ci do begin
   for j:=1 to cj do begin
     s:=format('%2d',[a[i,j,1]])+'('+format('%2d',[a[i,j,2]])+')';  write(s:7);
   end;
   writeln;
  end;
  writeln;
end;

то на исходном файле
Код: Выделить всё
7
001000000100
001000000101
000101000101
013101001100
010001010101
011111110101
001000010101
100010001111
000011011011
001000210011

Получим вызовом outa:
Код: Выделить всё
1(16)  1(17)  7(24)  1(19)  1(18)  1(17)  1(16)  1(17)  1(18)  7(25)  1(26)  1(27)
1(15)  1(16)  7(23)  1(18)  1(17)  1(16)  1(15)  1(16)  1(17)  7(24)  1(25)  7(32)
1(14)  1(15)  1(16)  7(23)  1(16)  7(21)  1(14)  1(15)  1(16)  7(23)  1(24)  7(31)
1(13)  7(20)  1(17)  7(22)  1(15)  7(20)  1(13)  1(14)  7(21)  7(28)  1(23)  1(24)
1(12)  7(19)  1(16)  1(15)  1(14)  7(19)  1(12)  7(19)  1(14)  7(21)  1(22)  7(29)
1(11)  7(16)  7(21)  7(14)  7(13)  7(12)  7(11)  7(18)  1(13)  7(20)  1(21)  7(28)
1(10)  1( 9)  7(14)  1( 7)  1( 6)  1( 5)  1( 4)  7(11)  1(12)  7(19)  1(20)  7(27)
7(15)  1( 8)  1( 7)  1( 6)  7(11)  1( 4)  1( 3)  1( 4)  7(11)  7(18)  7(25)  7(32)
1( 8)  1( 7)  1( 6)  1( 5)  7(10)  7( 9)  1( 2)  7( 9)  7(16)  1(11)  7(18)  7(25)
1( 9)  1( 8)  7(11)  1( 4)  1( 3)  1( 2)  1( 1)  7( 8)  1( 9)  1(10)  7(17)  7(24)
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиады. Олимпиадные задания

Сообщение xdsl 25 мар 2009, 13:59

1. В поисках пиратского клада, четвертый сезон (8 баллов), окончание (полное условие см. http://shgpi.edu.ru/f11/info/conf_olimp_2009/rule.html)
Теперь задача заключается в переборе всех найденных кратчайших путей, кодировании и выводе их в результирующий файл. В данном случае вполне безболезненнено воспользуемся рекурсией, т.к. количество найденных кратчайших путей на порядки меньше, чем общее кол-во путей.
Код: Выделить всё
procedure findpath(path:string; curi,curj:integer);
// path - закодированный текущий путь
// curi,curj - текущая позиция в матрице
begin
if a[curi,curj,2]=1 then begin
  ts.add(path); // добрались до исходной точки, добавляем полученный путь в список путей
  exit; // и выходим
end;
// следующими операторами ищем вокруг текущей позиции такие точки, из которых произошел переход в текущую
// и рекурсивно продолжаем поиск пути, переходя в эти точки
if (curi>1) and (a[curi-1,curj,2]=a[curi,curj,2]-a[curi,curj,1]) then findpath('D'+path,curi-1,curj);
if (curi<ci) and (a[curi+1,curj,2]=a[curi,curj,2]-a[curi,curj,1]) then findpath('U'+path,curi+1,curj);
if (curj>1) and (a[curi,curj-1,2]=a[curi,curj,2]-a[curi,curj,1]) then  findpath('R'+path,curi,curj-1);
if (curj<cj) and (a[curi,curj+1,2]=a[curi,curj,2]-a[curi,curj,1]) then findpath('L'+path,curi,curj+1);
end;

Осталось только создать основную программу:
Код: Выделить всё
begin
ts:=tstringlist.create;
assign(input,'input.txt'); reset(input); // сопоставили стандартный поток ввода с файлом 'input.txt'
assign(output,'output.txt'); rewrite(output); // сопоставили стандартный поток вывода с файлом 'output.txt'
   // две предыдущих операции проделали, чтобы перенаправить ввод и вывод на требуемые файлы
reada; // загрузили исходные данные
spf; // нашли все кратчайшие пути
findpath('',endi,endj); // сформировали набор закодированных кратчайших путей от исходной точки к конечной
ts.sort; // отсортировали
for i:=0 to ts.count-1 do writeln(ts.strings[i]); // и вывели в результирующий файл
ts.free;
end.
xdsl
 
Сообщения: 1233
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиады. Олимпиадные задания

Сообщение Vladislav_133 11 апр 2009, 17:15

Возвращаюсь к задаче 5 (см. viewtopic.php?f=15&t=71&st=0&sk=t&sd=a&start=10).
Привожу решение LMP полностью. Программа написана на Паскале. Признаться я хотел переписать решение на Си, но из-за нехватки времени и некоторого непонимания кода (увы, проще всегда самому написать) я не стал тратить на это время. Вот это решение и пустьт LMP за него отдувается сам.
program prog;

Код: Выделить всё
program prog;

{$APPTYPE CONSOLE}

uses
  SysUtils;

function DelX(es: String): String; // удаляет из строки все символы кроме цифр
  var
   i: Integer;
  begin
    Result:= '';
    for i:= 1 to Length(es) do
      if (es[i] >= '0') and (es[i] <= '9') then
        Result:= Result+es[i];
  end;

var
  a: array [1..1000] of record
    c1, c2: integer;
  end;
  c: Integer;
  lSave, gSave: array [0..1000] of Integer;

procedure ReadD;
  var
    lc1, lc2: Integer;
    s: String;
  begin
    while true do begin
      Read(lc1);
      Readln(s);
      s:= DelX(s);
      if (s = '') then
        Break;
      lc2:= StrToInt(s);
      if (lc1 = lc2) then
        Continue;
      c:= c+1;
      a[c].c1:= lc1;
      a[c].c2:= lc2;
    end;
  end;

procedure ShowR;
  var
    i: Integer;
  begin
    Writeln(gSave[0]);
    for i:= 1 to gSave[0] do
`      Writeln(a[gSave[i]].c1, ' ', a[gSave[i]].c2);
  end;

function Check(n: Integer): Boolean;
  var
    i, l1, l2, t1, t2: Integer;
  begin
    Result:= false;
    t1:= a[n].c1;
    t2:= a[n].c2;
    for i:= 1 to lSave[0] do begin
      l1:= a[lSave[i]].c1;
      l2:= a[lSave[i]].c2;
      if (t1 = l1) or (t1 = l2) or (t2 = l1) or (t2 = l2) then
        Exit;
    end;
    Result:= true;
  end;

procedure Find(n: Integer);
  var
    i, j: Integer;
  begin
    for i:= n+1 to c do begin
      if Check(i) then begin
        lSave[0]:= lSave[0]+1;
        lSave[lSave[0]]:= i;

        Find(i);

        if (lSave[0] > gSave[0]) then
          for j:= 0 to lSave[0] do begin
            gSave[j]:= lSave[j];
          end;

        lSave[0]:= lSave[0]-1;
      end;
    end;
  end;

begin
  Assign(Input, 'input.txt'); // перенаправляем потоки ввода/вывода
  Reset(Input);
  Assign(Output, 'output.txt');
  Rewrite(Output);{}

  lSave[0]:= 0; // инициализируем переменные
  c:= 0;

  ReadD; // считываем входные данные

  Find(0); // находим максимальную цепочку пар чисел

  ShowR; // выводим результат
end.


Уважаемый vovan, теперь все ждут ваше решение и с задачей 5 будет покончено
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1325
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.


Вернуться в Алгоритмизация и программирование

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron