Олимпиады по информатике в Ханты-Мансийском автономном округе – Югре (2008 – 2013 гг.) PDF

Департамент образования и молодежной политики Ханты-Мансийского автономного округа – Югры Автономное учреждение дополнительного профессионального образования Ханты-Мансийского автономного округа – Югры «Институт развития образования»...

Департамент образования и молодежной политики Ханты-Мансийского автономного округа – Югры Автономное учреждение дополнительного профессионального образования Ханты-Мансийского автономного округа – Югры «Институт развития образования» А.В. Алексеев Олимпиады по информатике в Ханты-Мансийском автономном округе – Югре (2008 – 2013 гг.) Сборник олимпиадных заданий муниципального этапа всероссийской олимпиады школьников Ханты-Мансийск 2013 ББК 74.263.2 Издается в рамках государственного задания А 47 Департамента образования и молодежной политики Ханты-Мансийского автономного округа – Югры. Приказ от 14.12.2012 г. № 1479 Рекомендовано решением Научно-методического совета АУ ДПО ХМАО – Югры «Институт развития образования» Протокол № 4 от 28 мая 2013 г. Рецензенты: Семёнов С.П., к.ф.-м.н., доцент, заведующий кафедрой компьютерного моделирования и ин- формационных технологий Югорского государственного университета Царегородцев А.Л., к.т.н., доцент, заместитель директора Югорского НИИ ИТ Авторы-составители: Алексеев А.В., к.п.н., доцент, главный научный сотрудник Югорского НИИ ИТ Карелин В.А., аспирант Югорского государственного университета Короткова Е.М. ведущий программист Югорского НИИ ИТ Алексеев А.В. и др. Олимпиады по информатике в Ханты-Мансийском автоном- ном округе – Югре (2008 – 2013 гг.): сборник олимпиадных заданий муниципального этапа всероссийской олимпиады школьников для учащихся 7-11 классов /Вступ. статья А.В. Алексеева /А.В. Алексеев, В.А. Карелин, Е.М. Короткова /Общая редакция Е.Г. Мазуровой. / – Ханты-Мансийск: Редакционно-издательский отдел АУ ДПО ХМАО – Югры «Институт развития образования», 2013.- 108 с. ISBN 978-5-94611-165-2 В сборнике представлены задания муниципального этапа всероссийской олимпиады школьников по информатике c 2007-2008 по 2012-2013 учебные годы. Для каждой из задач предусмотрены её разбор и программа, используемые знания и примерная сложность. Посо- бие ориентировано на школьников 7-11 классов, студентов сузов и вузов, учителей информа- тики общеобразовательных учреждений и преподавателей программирования различных учебных заведений дополнительного и профессионального образования. ISBN 978-5-94611-165-2 ББК 74.263.2 © Департамент образования и молодежной политики Ханты-Мансийского автономного округа – Югры © АУ «Институт развития образования», 2013 © Алексеев А.В., Карелин В.А., Короткова Е.М., 2013 2  Введение В сборнике представлены задания муниципального этапа Все- российской олимпиады школьников по информатике в 2007-2008 – 2012-2013 учебных годах. Такой выбор обусловлен тем, что в 2007- 2008 учебном году было принято Министерством образования и нау- ки РФ новое Положение о проведении всероссийской олимпиады школьников. Также с этого учебного года, впервые в практике прове- дения такого уровня олимпиад школьников по информатике, была использована автоматизированная проверяющая система сайта в сети интернет «Олимпиады по информатике, ХМАО-Югра» (адрес – http://acmu.ru). Это позволило всем школьникам автономного округа выполнять единые задания в одно и то же время, что, несо- мненно, способствовало повышению объективности оценки работы учащихся, сравнению степени их подготовленности к олимпиадам в разных муниципалитетах и учебных заведениях. Для каждой из 64-х задач проведённых олимпиад приведены её условие, описания входных и выходных данных, примеры, разбор ме- тода или методов её решения, программа на алгоритмическом языке Паскаль. Программы на языке программирования Си, которые подго- товлены Е.М. Коротковой, не вошли в печатную версию и могут быть взяты на сайте «Подготовка к олимпиадам в ХМАО-Югре» (адрес – http://zvn.uriit.ru) в разделе, посвященном этому задачнику. Также ма- териалы, вошедшие в задачник, можно взять в разделе «Муниципаль- ные этапы ВсОШ» на сайте Методической службы издательства «БИНОМ. Лаборатория знаний» по адресу http://metodist.lbz.ru/lections/6/. На основе анализа задач, использовавшихся на олимпиадах, ма- териалов других авторов в сборнике предлагается примерная про- грамма подготовки учащихся к школьному и муниципальному этапу олимпиады школьников по информатике. Сопоставление заданий сборника с аналогичными материалами других регионов России по- казало, что разработка заданий выполнена очень качественно и эти материалы имеют достаточный для такого уровня соревнований уро- вень сложности. Сопоставление проводилось на материалах муници- пального этапа в г. Москве, Новосибирской области, Республики Ка- релия, Красноярского и Ставропольского краёв и нескольких других регионов России, где олимпиады также проводятся централизованно 3 с использованием интернет-сайтов с автоматизированными прове- ряющими системами. На сайте «Интернет-олимпиады для школьников ХМАО-Югры» (адрес – http://olymp.uriit.ru) реализована возможность проведения тренировок школьников при подготовке к олимпиадам с использова- нием всех задач предлагаемого сборника. Интерфейсы участника и преподавателя разработаны В.А. Карелиным и их описание приведе- но в соответствующем параграфе. Это позволяет преподавателю ор- ганизовать подготовку своих школьников к олимпиадам в удобное время с выбором набора задач по определённой тематике или слож- ности. В тестировании подготовленных материалов и сайта приняли участие учащиеся БУОО Ханты-Мансийского автономного округа – Югры «Югорский физико-математический лицей», МБОУ г. Ханты- Мансийска «Средняя общеобразовательная школа № 1 им. Ю.Г. Со- зонова», студенты Ханты-Мансийского технолого-педагогического колледжа. Активнее всех работали Николай Павлушин, Александр Субач, Иван Жуков, Никита Сычёв, Евгений Косьмин, Алеся Курба- нова. Большое содействие в становлении представленного подхода к проведению олимпиад оказали консультант Департамента образова- ния и молодёжной политики автономного округа Н.В. Гусева, спе- циалисты научно-методического центра Института развития образо- вания по главе с Е.Г. Мазуровой. Авторы пособия всем им выража- ют искреннюю благодарность. Муниципальный этап 2007-2008 уч. года, 1-й тур 1. Сумма факториалов (Время: 1 сек. Память: 16 Мб) Факториалом натурального числа K называется произведение K!=1×2×3×…×K. Требуется написать программу, которая по заданному числу N вычислит сумму 1!+2!+…+N!. Входные данные Входной файл input.txt содержит одно натуральное число N (N ≤ 200). Выходные данные Выходной файл output.txt должен содержать все десятичные знаки искомой суммы. 4  Примеры № input.txt output.txt 1 1 1 2 2 3 3 3 9 Разбор Так как факториал быстро растущая целочисленная функция, то для получения суммы факториалов необходимо использовать длин- ную арифметику. Если вычислять сумму по формуле слева направо, то потребуется реализовать две операции длинной арифметики: сло- жение многозначных чисел и умножение многозначного числа на ко- роткое. Для упрощения набора используемых операций преобразуем формулу 1!+2!+…+N!=1+2*(1+3*(…(1+N)…)). А это позволяет ис- пользовать вместо сложения более просто программируемую опера- цию добавления единицы. Программа var n, p, i, k, l : integer; a : array [1..1000] of integer; begin assign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output); read(n); k:=1; a[k]:=1; for i:=n downto 2 do begin p:=0; for l:=1 to k do begin p:=p+a[l]*i; a[l]:=p mod 10; p:=p div 10 end; while p>0 do begin k:=k+1; a[k]:=p mod 10; p:=p div 10 end; l:=1; while a[l]=9 do begin a[l]:=0; l:=l+1 end; a[l]:=a[l]+1; if l>k then k:=l end; for i:=k downto 1 do write(a[i]) end. 5  2. К-удивительные числа (Время: 3 сек. Память: 16 Мб) Переворотом числа X назовем число, в котором все цифры числа X стоят в обратном порядке. Например, переворотом числа 6372 яв- ляется число 2736, а числа 7800 - 87. Назовем K-удивительным такое число, которое в сумме со своим переворотом дает число K. Например, у числа 222 имеется всего два K-удивительных числа: 111 и 210, а у числа 1050 имеется девять K-удивительных числа: 129, 228, 527, 426, 525, 624, 723, 822, 921. Требуется написать программу, которая по заданному числу K определит количество K-удивительных чисел. Входные данные Входной файл input.txt содержит одно натуральное число K (1 ≤ K ≤ 106). Выходные данные Выходной файл output.txt должен содержать одно число – коли- чество K-удивительных чисел. Примеры № input.txt output.txt 1 222 2 2 1050 9 Разбор Организуем перебор всех чисел от 1 до заданного числа. Для ка- ждого из этих чисел проверяем его K-удивительность, используя оп- ределение из условия задачи. Программа на Паскале var k, i, j, m, s : longint; begin assign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output); read(k); s:=0; for i:=1 to k do begin j:=i; m:=0; while j>0 do begin m:=m*10+j mod 10; j:=j div 10 end; if i+m=k then s:=s+1 6  end; write(s) end. 3. Рамка из клеток (Время: 1 сек. Память: 16 Мб) Прямоугольник состоит из X×Y квадратных клеток одинакового размера. Из него вырезан прямоугольник размером (X-2)×(Y-2) так, что осталась рамка шириной в одну клетку. Определить, можно ли покрыть всю рамку плитками размером A×1. Запас плиток неограни- чен, плитки не накладываются одна на другую и за пределы рамки не выходят. Требуется написать программу, которая решает эту задачу. Входные данные Входной текстовый файл input.txt содержит в первой строке на- туральное число K – количество тестов (1 ≤ K ≤ 10). В следующих K строках записаны по три натуральных числа: X, Y – размеры рамки, А – размер плитки (3 ≤ X, Y ≤ 2×109, 1 ≤ A ≤ 2×109). Числа разделены пробелами. Выходные данные Выходной текстовый файл output.txt должен содержать одну строку из K символов 0 или 1 (1 – если покрытие существует, 0 – иначе). Примеры № input.txt output.txt 1 1 1 3 3 1 2 10 2 3 3 2 3 3 3 Разбор Рамку можно покрыть плитками А×1, если А=1 или А=2 или одна из сторон кратна А, а вторая при делении на А дает остаток 2, или каждая при делении на А дает остаток 1. Программа на Паскале var k : integer; x, y, a : longint; begin assign(input,'input.txt'); reset(input); 7  assign(output,'output.txt'); rewrite(output); read(k); while k>0 do begin k:=k-1; readln(x,y,a); if (a=0) and (v mod z=0) then k:=k+1 end; write(k) end. 5. Следующее число (Время - 1 сек., память - 16 Мб) Задано натуральное число N. Требуется написать программу, которая найдет следующее за ним число, в двоичном разложении которого столько же единиц, сколько в двоичном разложении числа N. Входные данные В единственной строке входного файла input.txt записано одно натуральное число N (1 ≤ N ≤ 230). Выходные данные В единственную строку выходного файла output.txt нужно вывес- ти одно число – следующее за заданным, в двоичном разложении ко- торого столько же единиц. Примеры № input.txt output.txt 1 1 2 2 2 4 3 3 5 Разбор Найдем двоичное разложение заданного числа. Просматривая его слева направо, пропускаем нули, первую единицу заменяем нулем, также далее следующую группу единиц заменяем нулями, подсчиты- 9 вая количество таких замен, первый встретившийся ноль заменяем на единицу, справа дописываем подсчитанное количество единиц. Программа на Паскале var n : longint; i, k, j : integer; a : array [1..32] of integer; begin assign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output); read(n); k:=0; while n>0 do begin k:=k+1; a[k]:=n mod 2; n:=n div 2 end; i:=1; while a[i]=0 do i:=i+1; a[i]:=0; i:=i+1; j:=0; while a[i]=1 do begin a[i]:=0; i:=i+1; j:=j+1 end; a[i]:=1; if i>k then k:=i; for i:=1 to j do a[i]:=1; if k=32 then write('2147483648') else begin for i:=k downto 1 do n:=n*2+a[i]; write(n) end end. 6. Точки отрезка (Время - 1 сек., память - 16 Мб) Концы отрезка на плоскости имеют целочисленные координаты. Требуется написать программу, которая вычислит, сколько всего точек с целочисленными координатами принадлежат этому отрезку. Входные данные В единственной строке входного файла input.txt записаны четыре числа – координаты концов отрезка (x1, y1) и (x2, y2). Каждая из коор- динат не превышает по абсолютной величине значения 109. Выходные данные В единственную строку выходного файла output.txt нужно вывес- ти одно число – количество точек на заданном отрезке, имеющих це- лочисленные координаты. 10  Примеры № input.txt output.txt 1 1 1 2 2 2 2 0 0 -2 -2 3 3 1 1 1 10 10 Разбор Пусть (x1, y1), (x2, y2) – координаты концов отрезка. Переместим отрезок и, если нужно, отразим его относительно вертикали и гори- зонтали так, чтобы его левый нижний конец находился в точке (0, 0), а второй имел координаты (x, y)=(|x1-x2|, |y1-y2|). Очевидно, что коли- чество «целочисленных» точек на отрезке при этих перемещениях не изменяется. Найдем наибольший общий делитель координат отрезка, d=НОД(x, y). Тогда x=k∙d, y=l∙d, то точки (k, l), (2k, 2l), …,((d-1)∙k, (d- 1)∙l) принадлежат отрезку, поэтому всего «целочисленных» точек (d-1)+2=d+1. Программа на Паскале var x1, y1, x2, y2, a, b, c : longint; begin assign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output); read(x1,y1,x2,y2); a:=abs(x1-x2); b:=abs(y1-y2); if a=0 then write(b+1) else if b=0 then write(a+1) else begin while b>0 do begin c:=a mod b; a:=b; b:=c end; write(a+1) end end. Муниципальный этап 2007-2008 уч. года, 3-й тур 7. Коридор (Время - 1 сек., память - 16 Мб) Прямоугольный коридор длиной N метров и шириной M метров решили застелить N прямоугольными плитками шириной 1 метр и длиной M метров, таким образом, чтобы не было не застеленной по- верхности. Требуется написать программу, которая найдет количество спо- собов это сделать. Например, для коридора с размерами 6 на 4 суще- ствует четыре способа застелить плитками 1 на 4. 11  Входные данные В единственной строке входного файла input.txt записаны два це- лых числа – M (длина плитки и ширина коридора) и N (длина кори- дора). Для этих чисел верны неравенства 2 ≤ M ≤ N ≤ 50. Выходные данные В единственную строку выходного файла output.txt нужно вывес- ти одно число – количество способов. Примеры № input.txt output.txt 1 4 6 4 2 2 2 2 Разбор Задача решается методом динамического программирования. Для этого обозначим через A(n) – количество способов замостить коридор длиной n. Так как для коридора длиной k0 do begin m:=i mod k; c[m]:=c[m]+1; i:=i div k end; t:=true; for j:=0 to k-1 do t:=t and (c[j]