Школьная олимпиада по информатике, 2013 год

Знаковые события в научной и общественной жизни вуза.

Модератор: xdsl

Школьная олимпиада по информатике, 2013 год

Сообщение xdsl 08 дек 2013, 11:18

7 декабря 2013 года в ШГПИ состоялась школьная олимпиада по информатике.
------------------------------------------------------------------------------------------------------------
9.12.2013: Опубликованы результаты олимпиады
9.12.2013: Опубликованы условия задач олимпиады
9.12.2013: Опубликованы проверочные тесты олимпиады
12.12.2013: Опубликовано решение задачи №1 (шашки)
14.12.2013: Опубликовано решение задачи №2 (боулинг)
14.12.2013: Опубликована теоретическая часть решения задачи №3 (числа)
15.12.2013: Опубликована практическая часть решения задачи №3 (числа)
20.12.2013: Опубликовано альтернативное решение задачи №3 (числа)
20.12.2013: Опубликовано решение задачи №4 (повороты)
------------------------------------------------------------------------------------------------------------
4 задачи были предоставлены Главным управлением образования Курганской области в день проведения олимпиады. Каждая задача предусматривала разработку программы на одном из известных школьникам языков программирования.

Состав жюри: Пирогов Владислав Юрьевич (к.ф-м.н, профессор, зав. кафедрой Прикладной Информатики и Экономики, ник в форуме - Vladislav_133) и Слинкин Дмитрий Анатольевич (к.п.н, доцент, преподаватель программирования кафедры Программирования и Сетевых Технологий, зав. Вычислительным Центром ШГПИ, ник в форуме - xdsl).

Присутствовало более 20 школьников из города Шадринска и Шадринского района. Решения предоставили 15 человек. По окончании олимпиады решения были архивированы в файл olimp2013_shools.7z с md5-суммой 2dc44543edf9ca5d5b28c8eb3feba5f2 и переданы на хранение специалисту отдела образования администрации г. Шадринска.

Критерии оценки, в соответствии с рекомендациями по проведению муниципального этапа всероссийской олимпиады школьников по информатике в 2013/2014 учебном году, предоставленными Центральной предметно-методической комиссией всероссийской олимпиады школьников по информатике, были разработаны следующими:
1. За решение каждой задачи начисляется максимум 100 баллов.
2. Если решение дает неверный результат на примерах, приведенных в условии задачи, задача считается нерешенной.
3. Каждое решение проверяется на наборе тестов, за корректное прохождение каждого теста начисляется одинаковое количество баллов.

К сожалению, в отличии от предыдущих школьных олимпиад, с предоставленными задачами не передавалось ни решений, ни контрольных тестов. Таким образом, для обеспечения корректной проверки, жюри вынуждено было самостоятельно прорешать все представленные задачи и составить набор адекватных тестов, затянув тем самым проверку решений олимпиады до 9 декабря.

По окончании проверки результаты олимпиады будут опубликованы здесь (на форуме) и переданы специалисту отдела образования администрации г. Шадринска.

Также, здесь будут опубликованы условия и решения задач, наборы проверочных тестов, комментарии жюри о процессе проведения олимпиады и проверке решения задач.

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

Re: Школьная олимпиада по информатике, 2013 год

Сообщение xdsl 09 дек 2013, 15:16

Результаты олимпиады:
result1.png
result1.png (72.79 Кб) Просмотров: 14895
Результаты представлены в количестве пройденных тестов и процентах от максимального количества тестов. Для пересчета в баллы количество тестов следует умножить на 10.
Не представленные в списке школьники набрали 0 баллов.

Победителем олимпиады объявляется Белов Евгений, лицей №1. Поздравляем!
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Школьная олимпиада по информатике, 2013 год

Сообщение xdsl 09 дек 2013, 20:26

Условия задач олимпиады.
Вложения
tasks-9-11.pdf
(95.68 Кб) Скачиваний: 1165
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Школьная олимпиада по информатике, 2013 год

Сообщение xdsl 09 дек 2013, 20:52

Набор проверочных тестов. В тестах, где требовалось по условию задач включать в ответ слово "ДА", считался верным вариант со словом "ДА" в различных регистрах, кодировках и на английском языке ("YES").
Вложения
tests.7z
(1.72 Кб) Скачиваний: 596
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Школьная олимпиада по информатике, 2013 год: ввод-вывод данных

Сообщение xdsl 11 дек 2013, 09:15

Начинаем разбор задач. В качестве языка программирования я буду использовать freepascal в режиме совместимости objfpc.
Часть 1. Ввод-вывод данных.
Во всех представленных задачах исходные данные находятся в текстовом файле input.txt, результат должен быть помещен в текстовый файл output.txt.
Структура входного и выходного файла жестко определена для каждой задачи и не может быть изменена. Дело в том, что все задачи проверяются на наборах тестовых пар input.txt-output.txt. Программа запускается в каталоге, где находится тестовый input.txt. По окончании работы программы полученный output.txt сравнивается с тестовым output.txt. Если их содержимое эквивалентно (в более строгих случаях - побайтово равно), то считается, что программа успешно прошла тест. Иначе тест считается не пройденным. Также тест считается не пройденным, если программа за определенный промежуток времени не завершила свою работу (зависла или заблокирована). Значит, если участник олимпиады ошибся в названии исходного или результирующего файла, считывает данные не из входного файла или не в том формате, который задан, генерирует данные в некорректном виде или выводит данные не в результирующий файл, решение задачи считается неверным.

Данный набор правил является общеизвестным, применяется на всех олимпиадах по информатике. Существуют вариации данных правил, которые в обязательном порядке оговариваются. Например, в некоторых случаях требуют вместо input.txt-output.txt использовать стандартные потоки ввода-вывода. Однако в этой олимпиаде никаких отступлений от стандартных правил предусмотрено не было.

1. Рассмотрим пример посимвольного чтения входных данных и генерации выходных на базе задачи №1(шашки). Напомним описание входных данных:
В единственной строке входного файла input.txt записаны в шахматной нотации: клетка, где стоит шашка, затем через пробел клетка, куда шашка должна попасть. Начальная и конечная клетки не совпадают.
Описание выходных данных:
В единственную строку выходного файла output.txt нужно вывести слово YES (заглавными буквами), если шашка может попасть из начальной клетки в конечную, и слово NO – в противном случае.
Таким образом, из файла input.txt программа должна считать ровно 5 символов. Первые два - координаты начальной позиции, третий - пробел, последние два - координаты конечной позиции. Либо считать из файла ровно одну строку и разобрать ее содержимое. По окончании обработки в результирующий файл output.txt должна быть помещена ровно одна строка, со значением YES или NO.
Подсветка синтаксиса: (1tmpl.pp) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
  1. {$mode objfpc}
  2. var fin,fout:text;
  3.     firstV,firstH,lastV,lastH,space:char;
  4. begin
  5.  assign(fin,'input.txt');
  6.  reset(fin);
  7.  read(fin,firstV,firstH); // начальные координаты
  8.  read(fin,space); // символ-разделитель
  9.  read(fin,lastV,lastH); // конечные координаты
  10.  close(fin);
  11.  
  12.  assign(fout,'output.txt');
  13.  rewrite(fout);
  14.  
  15.  {
  16.  
  17.   здесь - обработка полученных данных
  18.   и вывод в результирующий файл,
  19.   например так:
  20.  
  21.    writeln(fout,'YES');
  22.  
  23.   или так:
  24.  
  25.    writeln(fout,'NO');
  26.  
  27.  }
  28.  
  29.  close(fout);
  30. end.

2.Рассмотрим пример форматированного чтения исходных данных на базе задачи №2 (боулинг). Напомним описание входных данных:
Входной файл input.txt содержит в первой строке одно натуральное число, определяющее количество совершенных бросков. Вторая строка содержит разделенные пробелом натуральные числа, обозначающие количество сбитых кеглей за соответствующий бросок.
В первой строке файла содержится натуральное число, следовательно его можно загрузить в переменную целочисленного типа. Вторую строку можно обработать, последовательно считывая числовые значения в количестве, определенном в первой строке. Это становится возможно благодаря заявленному разделителю-пробелу, который используется в большинстве реализаций языка Pascal в качестве разделителя по умолчанию при чтении числовых данных. Если-бы в качестве разделителя предполагался другой символ (например - запятая или точка с запятой), вторую строку пришлось-бы полностью считывать в программу и последовательно обрабатывать, вычленяя из нее числовые значения.
Подсветка синтаксиса: (2tmpl.pp) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
  1. {$mode objfpc}
  2. var fin,fout:text;
  3.     bc:integer; // кол-во бросков
  4.     i:integer;
  5.     kc:array[1..20] of integer; // кол-во сбитых кеглей за каждый бросок
  6. begin
  7.  assign(fin,'input.txt');
  8.  reset(fin);
  9.  readln(fin,bc);
  10.  for i:=1 to bc do read(fin,kc[i]);
  11.  close(fin);
  12.  // далее - обработка и вывод
  13. end.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Школьная олимпиада по информатике, 2013 год: Решение задачи №1 (шашки)

Сообщение xdsl 12 дек 2013, 14:03

Условие задачи №1 (шашки).
Задача достаточно проста и к ее решению можно подойти несколькими путями. Рассмотрим один из них. Фактически, клетка принципиально достижима при одновременном выполнении трех условий: 1) конечное местоположение выше начального; 2) начальная и конечная клетки одного цвета; 3) конечная клетка находится внутри фигуры, образованной направленными вверх диагоналями, исходящими из начальной клетки. Аналогично, клетка принципиально недостижима, если не выполняется хотя-бы одно из вышеперечисленных условий.
board.jpg
board.jpg (16.25 Кб) Просмотров: 14719
Проведем формализацию данных условий. Координаты клеток пометим с помощью двух целочисленных значений от 1 до 8. Пусть firstV - вертикальная координата начальной клетки, firstH - горизонтальная координата начальной клетки, lastV - вертикальная координата конечной клетки, lastH - горизонтальная координата конечной клетки (на рисунке шашка находится в начальной клетке с координатами firstV=firstH=3)

Первое условие будет выполнено при lastH>firstH.
Второе условие будет выполнено, если модуль разности между горизонтальными (deltaV:=abs(lastH-firstH)) и вертикальными (deltaH:=abs(lastV-firstV)) координатами начальной и конечной точек разной четности, т.е если deltaV нечетен, то deltaH также должен быть нечетен. И наоборот. Для проверки данного факта находим четность суммы полученных величин. Если результат четен, то deltaV и deltaH одинаковой четности.
Третье условие будет выполнено, если выполняется первое и второе условие, а также если deltaV<=deltaH.

Следующая программа демонстрирует решение задачи. Для удобства и уменьшения объема кода был выбран вариант проверки на невыполнение условий.
Подсветка синтаксиса: (1shashki.pp) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
  1. {$mode objfpc}
  2. // функция анализирует исходную строку в соответствии с условием задачи и возвращает YES или NO
  3. function calculate(s:string):string;
  4. var
  5.     firstV,firstH:integer; // начальные координаты (V-вертикаль, H-горизонталь)
  6.     lastV,lastH:integer; // конечные координаты (V-вертикаль, H-горизонталь)
  7.     deltaV,deltaH:integer; // модуль разности конечных и начальных координат (V-вертикаль, H-горизонталь)
  8.  begin
  9.     result:='NO'; // предполагаем, что достижение конечной точки невозможно
  10.     // переводим символьные координаты '1'..'8' и 'a'..'h' в числовые координаты 1..8
  11.     firstV:=ord(s[1])-ord('a')+1; firstH:=ord(s[2])-ord('1')+1;
  12.     lastV:=ord(s[4])-ord('a')+1;  lastH:=ord(s[5])-ord('1')+1;
  13.     if firstH>=lastH then exit; // назад ходить запрещено
  14.     deltaV:=abs(firstV-lastV); deltaH:=abs(firstH-lastH);
  15.     if ((deltaV+deltaH) mod 2) <> 0 then exit; // начальная и конечная точки - на разноцветных полях
  16.     if deltaV>deltaH then exit; // конечная точка - за пределами справа или слева
  17.     result:='YES'; // в остальных случаях конечная точка достижима
  18.  end;
  19.  
  20. var
  21.     s:string; // строка исходных данных
  22.     fin,fout:text; // исходный и результирующий файлы
  23. begin
  24.     // считываем строку из input.txt
  25.     assign(fin,'input.txt');
  26.     reset(fin);
  27.     readln(fin,s);
  28.     close(fin);
  29.     // сохраняем в output.txt результат рассчетов
  30.     assign(fout,'output.txt');
  31.     rewrite(fout);
  32.     writeln(fout,calculate(s));
  33.     close(fout);
  34. end.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Школьная олимпиада по информатике, 2013 год: Решение задачи №2 (боулинг)

Сообщение xdsl 14 дек 2013, 09:17

Условие задачи №2 (боулинг).
Задача несложная, требует только внимательного прочтения условия и скурпулезного следования заявленным требованиям. В условии присутствует излишняя информация, которая может сбить с толку, а именно - правила игры, в то время как для решения задачи нужны только правила подсчета очков. Правила игры могли быть полезными, если бы требовалось найти число сделанных бросков. Но, т.к. число бросков задано в исходном файле, достаточно загрузить количество сбытых кеглей для каждого и обработать по правилам подсчета очков:
Подсветка синтаксиса: (2bouling.pp) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
  1. {$mode objfpc}
  2. var
  3.     bc:integer; // кол-во бросков
  4.     i:integer;
  5.     kc:array[1..21] of integer; // кол-во сбитых кеглей за каждый бросок
  6.     tsum:array[1..10] of integer; // суммы очков в каждом туре
  7.     sum:integer=0; // общая сумма очков
  8.     tour:integer=0; // текущий тур
  9.     bctour:integer=1; // текущий бросок
  10.     fin,fout:text;
  11. begin
  12. // загрузка исходных данных
  13. assign(fin,'input.txt');
  14. reset(fin);
  15. readln(fin,bc); for i:=1 to bc do read(fin,kc[i]);
  16. close(fin);
  17. // проход по турам
  18. while (tour<=10) do begin
  19.  inc(tour); // переход на следующий тур
  20.  if (kc[bctour]=10) then begin // strike
  21.     tsum[tour]:=kc[bctour]+kc[bctour+1]+kc[bctour+2]; // подсчет очков для тура по правилам strike
  22.     inc(bctour); // на следующий тур без второго броска
  23.  end
  24.  else
  25.  if (kc[bctour]+kc[bctour+1]=10) then begin // spire
  26.     tsum[tour]:=kc[bctour]+kc[bctour+1]+kc[bctour+2]; // подсчет очков для тура по правилам spire
  27.     inc(bctour,2); // на следующий тур с учетом двух бросков
  28.  end
  29.  else begin // обычный тур
  30.     tsum[tour]:=kc[bctour]+kc[bctour+1]; // подсчет очков для тура по по обычным правилам
  31.     inc(bctour,2); // на следующий тур с учетом двух бросков
  32.  end;
  33. end;
  34. //суммирование очков, набранных в каждом туре
  35. for i:=1 to 10 do sum+=tsum[i];
  36. //вывод результата
  37. assign(fout,'output.txt');
  38. rewrite(fout);
  39. writeln(fout,sum);
  40. close(fout);
  41. end.
Решение можно немного оптимизировать, находя общую сумму очков внутри цикла. Однако предложенный вариант гораздо эффективней в отладке. Если подсчеты завершаются неверным результатом, всегда можно проанализировать количество набранных в каждом туре очков и найти ошибку. Например, в своем первом решении на одном из тестов я обнаружил ошибку.
Тест:
21
1 9 2 8 3 7 4 6 5 5 6 4 7 3 8 2 9 1 10 0 10

Требуемый результат: 164
Полученный результат: 166

Добавив в конце программы цикл for i:=1 to 10 do write(tsum[i]:4);
я обнаружил, что количество очков в последнем туре действительности не соответствует:
12 13 14 15 16 17 18 19 20 22
По исходным данным это количество должно вычисляться как 10+0+10 = 20

Предположив, что проблемы в некорректном чтении исходных данных, я вывел их на экран циклом for i:=1 to bc do write(kc[i]:3); и получил удивительную картину:
1 9 2 8 3 7 4 6 5 5 6 4 7 3 8 2 9 1 10 0 12
Было совершенно непонятно, каким образом последнее загруженное из файла значение оказалось вместо 10 равно 12! Однако было достаточно взглянуть на мое определение массива kc: var kc:array[1..20] of integer; и все стало на свои места.

Получается, что при количестве бросков = 21 (strike - только последним броском или spire - последним броском) несуществующая ячейка kc[21] с определенной вероятностью, которая зависит от способов выравнивания массивов в оперативной памяти, может разделять память с ячейкой tsum[1], которая во время подсчета заполняется значением 12 (первый бросок strike = 1+9+2). Таким образом, при подсчете последнего значения tsum[10] получаем вместо 20=10+0+10, значение 22 = 10 + 0 + 12.

Для решения проблемы оказалось достаточно переопределить массив: var kc:array[1..21] of integer;

Выход за пределы массива является одной из самых опасных и трудно уловимых ошибок в программировании, создавая легко эксплуатируемые уязвимости, точки проникновения в систему вирусов и шпионских программ. Большинство языков программирования предлагают механизм автоматического слежения за переполнением массива, который, тем не менее, не помогает в некоторых ситуациях, а также понижает скорость работы программы. Для freepascal - это директива компилятора {$R+}, которая аварийно остановит программу при возникновении такой ошибки. Однако наилучшим способом избежать подобных ошибок являлся и является профессионализм программиста.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Школьная олимпиада по информатике, 2013 год: Решение задачи №3 (числа). Часть 1, теоретическая.

Сообщение xdsl 14 дек 2013, 11:56

Условие задачи №3 (числа).
Задача сложнее предыдущих, попытки решения решения ее "в лоб", а именно - загрузкой числового значения и нахождением остатка от деления арифметической операцией, обречены на неудачу. Дело в том, что величина числа ограничивается 1000 знаков, в то время как самый большой встроенный неотрицательный тип данных в большинстве языков программирования имеет размер 8 байт (во freepascal - qword), что ограничивает его 64 знаками в двоичном представлении и 18 знаками в десятичном. Использование вещественных типов также не даст положительного результата из-за ограничений точности максимум в 19-20 знаков.

Таким образом приходит понимание, что с числом надо работать как с массивом символов или числовых значений (каждое значение - один знак). В то-же время создание собственных операций для получения остатка от деления с помощью прямых манипуляций с массивом (например - реализация вычитания числа из массива) слишком затратно по времени с учетом малых значений вычитаемых (3, 4 и 11). Понимание данного факта заставляет завершить поиск инженерных подходов к решению задачи и привлечь к делу математику. Из математики нам потребуются признаки делимости для чисел 3, 4, 11 и признаки равноостаточности для этих-же чисел. Будем считать, что 0 делится на любое число (кроме 0) без остатка, т.к. именно такой результат обеспечивает операция нахождения остатка в большинстве языков программирования.

Признак делимости на 3: Если сумма цифр числа делится на 3 без остатка, то и само число делится на 3 без остатка
Признак равноостаточности для 3: Такой-же, как признак делимости.

Признак делимости на 4: Если две последние цифры числа (единицы и десятки) составляют число, которое делится на 4 без остатка, то исходное число также делится на 4 без остатка.
Признак равноостаточности для 4: Такой-же как признак делимости.

С признаком делимости и равноостаточности на 11 имеются некоторые проблемы. Дело в том, что самый известный признак делимости на 11 (если знакопеременная сумма цифр числа делится на 11 без остатка, то и само число делится на 11 без остатка), НЕ ЯВЛЯЕТСЯ ПРИЗНАКОМ РАВНООСТАТОЧНОСТИ. Например, остаток деления чисел 10 или 120 на 11 равен 10, в то время как абсолютное значение знакопеременной суммы этих чисел равно 1 (abs(1-0)=1, abs(1-2+0)=1). К сожалению, некоторые доступные в сети Интернет источники говорят обратное, например - http://www.school.mipt.ru/FileDown.asp?ItemId=1103(страница 12). Поэтому воспользуемся другим, менее известным признаком делимости:
Признак делимости на 11: Если на 11 без остатка делится сумма чисел, образующих группы по две цифры (начиная с единиц), то исходное число также делится на 11 без остатка.
Признак равноостаточности для 11: Такой-же как признак делимости.

Любопытствующим в указанных вопросах могу порекомендовать первоисточник, известную книгу Воробьева Н.Н. "Признаки делимости" (напр. http://mat.net.ua/mat/biblioteka/Vorobev-Delimost.djvu или http://ilib.mccme.ru/plm/ann/a39.htm) 1988 года выпуска (математика не стареет ;)!), а также обширные выводы из нее на Википедии: http://ru.wikipedia.org/wiki/Признаки_делимости
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Школьная олимпиада по информатике, 2013 год: Решение задачи №3 (числа). Часть 2, практическая.

Сообщение xdsl 15 дек 2013, 17:43

Условие задачи №3 (числа).
В предыдущем посте я разобрал математический подход к решению задачи, сейчас представляю код.
В программе определим 3 функции, каждая из которых будет возвращать либо слово YES, либо остаток от деления переданного числа, представленного в виде длинной строки, на 3 (функция test3), 4 (функция test4), или 11 (функция test11). Алгоритм работы программы следующий: 1) загружаем строку из input.txt 2) последовательно вызываем функции test3, test4 и test11 с исходной строкой в качестве параметра, результат их работы также последовательно сохраняем в output.txt.
Подсветка синтаксиса: (3chisla.pp) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
  1. {$mode objfpc}
  2. // из модуля sysutils будем использовать функции inttostr (аналог str) и strtoint (аналог val)
  3. uses sysutils;
  4.  
  5. // делимость на 3 - сумма цифр делится на 3
  6. // равноостаточность - аналогично
  7. function test3(var s:ansistring):string;
  8.   var i:integer; sum:integer;
  9.  begin
  10.   sum:=0;
  11.   for i:=1 to length(s) do sum+=strtoint(s[i]);
  12.   if sum mod 3=0 then result:='YES' else result:=inttostr(sum mod 3);
  13.  end;
  14.  
  15. // делимость на 4 - две последние цифры делятся на 4
  16. // равноостаточность - аналогично
  17. function test4(var s:ansistring):string;
  18.   var last2c:integer;
  19.  begin
  20.   if length(s)=1 then last2c:=strtoint(s[length(s)])
  21.   else last2c:=strtoint(copy(s,length(s)-1,2));
  22.   if last2c mod 4 = 0 then result:='YES' else result:=inttostr(last2c mod 4);
  23.  end;
  24.  
  25. // делимость на 11 - сумма чисел, составленных из пар по две цифры, начиная с единиц, делится на 11.
  26. // равноостаточность - аналогично
  27. function test11(var s:ansistring):string;
  28.   var sum,i:integer;
  29.  begin
  30.   i:=length(s)-1;
  31.   sum:=0;
  32.   while i>0 do begin
  33.    sum+=strtoint(copy(s,i,2));
  34.    dec(i,2);
  35.   end;
  36.   if i=0 then sum+=strtoint(s[1]);
  37.   if sum mod 11=0 then result:='YES' else result:=inttostr(sum mod 11);
  38.  end;
  39.  
  40. var fin,fout:text;// исходный и результирующий файлы
  41.         s:ansistring;// строка исходных данных, тип ansistring - размер строки до 2GB
  42. begin
  43.  // считываем строку из input.txt
  44.  assign(fin,'input.txt');
  45.  reset(fin);
  46.  readln(fin,s);
  47.  s:=trim(s);// удалим начальные и конечные пробелы
  48.  close(fin);
  49.  // сохраняем в output.txt результаты рассчетов
  50.  assign(fout,'output.txt');
  51.  rewrite(fout);
  52.  write(fout,test3(s),' ');
  53.  write(fout,test4(s),' ');
  54.  writeln(fout,test11(s));
  55.  close(fout);
  56. end.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Школьная олимпиада по информатике, 2013 год: Решение задачи №3 (числа). Часть 3, альтернативная.

Сообщение xdsl 20 дек 2013, 12:46

Условие задачи №3 (числа).
Полностью математическое решение иногда не может быть получено по различным причинам: нехватка времени, незнание тех или иных математических формул и т.п. Например, в данной задаче используются принципы делимости и равноостаточности. И если признаки делимости достаточно хорошо известны, то информации о признаках равноостаточности - гораздо меньше. Попробуем решить данную задачу, используя только признаки делимости. При этом следует понять, как искать остаток от деления, если он не равен нулю. Очевидно, что если N-K делится без остатка на X при 0<K<X (в нашем случае N - исходное большое число, а X - 3, 4 или 11), то K - остаток от деления N на X. Значение K можно найти, циклически вычитая из N единицу и проверяя полученный результат с использованием соответствующего признака делимости до тех пор пока он не сработает. Количество вычитаний и будет равно K.

Подсветка синтаксиса: (3chislaAlto.pp) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
  1. {$mode objfpc}
  2. uses sysutils;
  3.  
  4. // уменьшение большого числа на 1
  5. procedure decStr(var s:ansistring);
  6.     var i:integer;
  7.  begin
  8.   for i:=length(s) downto 1 do begin
  9.    if s[i]='0' then s[i]:='9'
  10.    else begin
  11.     dec(s[i]); exit;
  12.    end;
  13.   end;
  14.  end;
  15.  
  16.  // делимость на 3 - сумма цифр делится на 3
  17. function test3(var s:ansistring):boolean;
  18.   var i:integer;
  19.       sum:integer;
  20.  begin
  21.   sum:=0;
  22.   for i:=1 to length(s) do sum+=ord(s[i])-ord('0');
  23.   result:=sum mod 3=0;
  24.  end;
  25.  
  26. // делимость на 4 - две последние цифры делятся на 4
  27. function test4(var s:ansistring):boolean;
  28.   var last2c:integer;
  29.  begin
  30.   if length(s)=1 then last2c:=strtoint(s[length(s)])
  31.   else last2c:=strtoint(copy(s,length(s)-1,2));
  32.   result:=last2c mod 4 = 0;
  33.  end;
  34.  
  35. // делимость на 11 - накопеременная сумма цифр числа делится на 11 без остатка
  36. function test11(var s:ansistring):boolean;
  37.   var sum,sign,i:integer;
  38.  begin
  39.   i:=1;
  40.   sum:=0; sign:=1;
  41.   for i:=1 to length(s) do begin
  42.    sum+=sign*strtoint(s[i]);
  43.    sign:=-sign;
  44.   end;
  45.   result:=sum mod 11=0;
  46.  end;
  47.  
  48. // -------- основная программа -----------
  49. var k:integer;  s,stest:ansistring;
  50.     fin,fout:text;
  51. begin
  52.  // считываем строку из input.txt
  53.  assign(fin,'input.txt');
  54.  reset(fin);
  55.  readln(fin,s);
  56.  s:=trim(s);// удалим начальные и конечные пробелы
  57.  close(fin);
  58.  
  59.  assign(fout,'output.txt');
  60.  rewrite(fout);
  61.  
  62.  stest:=s; k:=0;
  63.  while not test3(stest) do begin
  64.    decStr(stest);
  65.    inc(k)
  66.  end;
  67.  if k=0 then write(fout,'YES ') else write(fout,k,' ');
  68.  
  69.  stest:=s; k:=0;
  70.  while not test4(stest) do begin
  71.    decStr(stest);
  72.    inc(k)
  73.  end;
  74.  if k=0 then write(fout,'YES ') else write(fout,k,' ');
  75.  
  76.  stest:=s; k:=0;
  77.  while not test11(stest) do begin
  78.    decStr(stest);
  79.    inc(k)
  80.  end;
  81.  if k=0 then writeln(fout,'YES') else writeln(fout,k);
  82.  
  83.  close(fout);
  84.  
  85. end.

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

Школьная олимпиада по информатике, 2013 год: Решение задачи №4 (повороты).

Сообщение xdsl 20 дек 2013, 14:03

Условие задачи №4 (повороты).
Очень известная, можно сказать "заезженная" геометрическая задача, имеющая к программированию достаточно слабое отношение. Решается через векторное произведение векторов на плоскости XY, образованными каждыми двумя последовательными участками пути. Если поворот левый, то векторное произведение положительно, правый - отрицательно. Если разворот или дальнейшее движение по прямой - равно нулю. Разворот определяется как левый поворот (рассмотрено в одном из примеров), движение по прямой невозможно по условию задачи (камеры фиксируют только повороты). Задача подробно разобрана, например, здесь: http://www.tverobr.ru/data/fizmat/kompmod.doc. Поэтому привожу ее решение без каких-либо дополнительных комментариев:
Подсветка синтаксиса: (4poworoty.pp) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
  1. {$mode objfpc}
  2. type tpoint=record x,y:integer; end;
  3. var a:array of tpoint;
  4.     cnt,i:integer;
  5.     sum:integer=0;
  6.     fin,fout:text;
  7. begin
  8.  assign(fin,'input.txt');
  9.  reset(fin);
  10.  readln(fin,cnt);
  11.  setlength(a,cnt);
  12.  for i:=0 to length(a)-1 do begin
  13.   read(fin,a[i].x);
  14.   read(fin,a[i].y);
  15.  end;
  16.  close(fin);
  17.  
  18.  for i:=1 to length(a)-2 do begin
  19.   if ((a[i].x-a[i-1].x)*(a[i+1].y-a[i].y)-(a[i].y-a[i-1].y)*(a[i+1].x-a[i].x))>=0 then inc(sum);
  20.  end;
  21.  
  22.  assign(fout,'output.txt');
  23.  rewrite(fout);
  24.  writeln(fout,sum,'M');
  25.  close(fout);
  26. end.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.


Вернуться в Конференции и семинары, олимпиады и форумы, выставки и конкурсы в ШГПУ

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

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

cron