№ | Слайд | Текст |
1 |
 |
Муниципальный этап Всероссийской олимпиады школьников по информатике2011-2012 учебный год |
2 |
 |
7-8 классы Задача 1Числа. Дано трехзначное целое положительное число. После удаления первой цифры это число уменьшилось в N раз. Вывести в порядке убывания все такие числа. Формат входных данных Файл содержит число N. Формат выходных данных Выходной файл содержит такие числа. |
3 |
 |
РешениеОрганизуем перебор всех трехзначных чисел от 999 до 100. В каждом числе отбрасываем первую цифру и умножаем результат на N. Если получившееся число равно исходному числу, то выводим его. |
4 |
 |
Решениеprogram O11_78_1; var n,i:integer; begin assign(input,'task1.in'); reset(input); read(n); close(input); assign(output,'task1.out'); rewrite(output); for i:=999 downto 100 do if i=i mod 100 * n then writeln(i); close(output) end. |
5 |
 |
9 класс Задача 1Числа. Дано четырехзначное целое положительное число. После удаления первой цифры это число уменьшилось в N раз. Вывести в порядке убывания все такие числа. Формат входных данных Файл содержит число N. Формат выходных данных Выходной файл содержит такие числа. |
6 |
 |
РешениеОрганизуем перебор всех четырехзначных чисел от 9999 до 1000. В каждом числе отбрасываем первую цифру и умножаем результат на N. Если получившееся число равно исходному числу, то выводим его. |
7 |
 |
Решениеprogram O11_9_1; var n,i:integer; begin assign(input,'task1.in'); reset(input); readln(n); close(input); assign(output,'task1.out'); rewrite(output); for i:=9999 downto 1000 do if i=i mod 1000 * n then writeln(i); close(output) end. |
8 |
 |
10-11 классы Задача 1Числа. Дано не более чем семизначное целое положительное число A (10?А?9999999). После удаления первой цифры это число уменьшилось в N раз. Вывести количество таких чисел. Формат входных данных Файл содержит число N. Формат выходных данных Выходной файл содержит количество таких чисел. |
9 |
 |
РешениеОрганизуем перебор всех чисел от 10 до 9999999. Заметим, что на этом диапазоне 90 двузначных чисел, 900 – трехзначных, 9000 – четырехзначных и т.д. Поэтому в первых девяносто числах отбрасываем вторую справа цифру. Затем в 900 числах отбрасываем третью справ цифру и т.д. Получившееся число умножаем на N. Если результат равен исходному числу, то считаем его. |
10 |
 |
Решениеprogram O11_10_1; var k,n:integer; i,t,r:longint; begin assign(input,'task1.in'); reset(input); read(n); close(input); k:=0; t:=10; r:=0; for i:=10 to 9999999 do begin if i=i mod t*n then k:=k+1; r:=r+1; if r=t*9 then begin t:=t*10; r:=0 end; end; assign(output,'task1.out'); rewrite(output); write(k); close(output) end. |
11 |
 |
7-8-9 классы Задача 2Фишка. Фишка может двигаться только вперед по полю длины N. Длина хода фишки не может быть более K. Найти число различных вариантов ходов, при которых фишка может пройти поле от начала до конца. Например, при N=3, K=2 – возможные пути: (1,1,1), (1,2), (2,1), т.е. возможны 3 варианта. Формат входных данных Файл содержит числа N и K. Формат выходных данных Выходной файл содержит число вариантов. |
12 |
 |
РешениеДинамическое программирование (прежде чем найти кол-во маршрутов до позиции N, найдем кол-во маршрутов до позиций 1, 2, 3, …, N-1). Кол-во маршрутов будем хранить в массиве S. 0 1 2 3 … N-1 N |
13 |
 |
РешениеСначала найдем позиции, в которые можно дойти за 1 шаг. Очевидно, что это позиции 1, 2, 3, …, K. Занесем в S[1], S[2], …, S[K] значения 1. 0 1 2 3 … K N … S: 1 1 1 … 1 0 … |
14 |
 |
РешениеВ S[i] будем хранить количество маршрутов по которым фишка может пройти поле от начала до позиции с номером i. В позицию i можно попасть из позиций i-1, i-2, …, i-K. Каждый этот шаг это продолжение уже существующего маршрута. Значит кол-во маршрутов S[i] равно сумме S[i-1]+S[i-2]+…+S[i-K]. 0 i-K ... i-2 i-1 i N … |
15 |
 |
РешениеТаким образом, вычисляя последовательно значения величин S[2], S[3],..., S[N] получаем значение S[N], которое и указывает общее количество различных путей, по которым фишка может пройти поле от начала до позиции с номером N. |
16 |
 |
Решениеprogram O11_789_2; var n,k,i,j:integer; s:array[1..10] of integer; begin assign(input,'task2.txt'); reset(input); readln(n,k); close(input); assign(output,'task2.out'); rewrite(output); for i:=1 to n do if i<=k then s[i]:=1 else s[i]:=0; for i:=2 to n do begin j:=i-1; while (j>0) and (j>=i-k) do begin s[i]:=s[i]+s[j]; j:=j-1 end end; write(s[n]); close(output) end. |
17 |
 |
ШеренгаСколько вариантов имеется у учеников для того, чтобы стать в шеренгу из N человек? Формат входных данных Файл содержит число N (1?N?150). Формат выходных данных Выходной файл содержит количество вариантов расстановки. 10-11 классы Задача 2 |
18 |
 |
РешениеКоличество вариантов - это число перестановок из N элементов. P(N)=N! Но при N типа integer (-32 768?+32 767) максимальное значение факториала, которое можно разместить в памяти, 7!=5 040, т.к. 8!=40 320. При N типа longint (-2 147 483 648? 2 147 483 647) максимальное значение 12!=479 001 600, т.к. 13!=6 227 020 800 Надо использовать «длинную арифметику». |
19 |
 |
РешениеФакториал вычисляется последовательно с 1! до N!. Для размещения цифр факториала используем массив f, в который в первую ячейку заносим 1 (т.к. 0!=1). Затем в цикле по переменной k от 1 до N производим поразрядное умножение занятых ячеек массива f на число k. Этапы умножения проследим по схеме. |
20 |
 |
Решение1 2 3 4 5 6 7 1 Начальное 1 i=1 2 i=2 6 i=3 4 2 i=4 0 2 1 i=5 |
21 |
 |
РешениеНазначение переменных: z – количество позиций массива f хранящих цифры факториала; ab – результат умножения очередной позиции массива f на число k; a – количество десятков в результате умножения. |
22 |
 |
Решениеprogram O11_1011_2; var f:array[1..300] of 0..9; n,i,z,k,a,ab:integer; begin assign(input,'task2.in'); reset(input); readln(n); close(input); assign(output,'task2.out'); rewrite(output); f[1]:=1; z:=1; for k:=2 to n do begin a:=0; for i:=1 to z do begin ab:=f[i]*k+a; f[i]:=ab mod 10; a:=ab div 10 end; i:=z+1; while a<>0 do begin f[i]:=a mod 10; z:=z+1; a:=a div 10; i:=i+1 end; for i:=z downto 1 do write(f[i]); writeln end; close(output) end. |
23 |
 |
7-8-9 классы Задача 3Выкройка. На квадратном клетчатом листе бумаги N?N клеток заштрихована часть клеток. написать программу, которая определяет прямоугольник максимальной площади, не содержащий заштрихованных клеток. Предполагается, что такой прямоугольник единственный. В качестве ответа вывести площадь прямоугольника и координаты его двух противоположных вершин (левой верхней и правой нижней). Формат входных данных Первая строка файла содержит число N. Следующие N строк содержат по N значений элементов таблицы, разделенных пробелами (1- заштрихованная клетка, 0 – нет). Формат выходных данных Первая строка выходного файла содержит значение максимальной площади. Две следующие строки – координаты левой верхней и правой нижней клеток такого прямоугольника. |
24 |
 |
7-8-9 классы Задача 30 1 0 0 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 7 12 3 2 6 4 |
25 |
 |
РешениеНапишем логическую функцию, которая будет проверять, есть ли в прямоугольнике с координатами левой верхней вершины (x1,y1) и координатами правой нижней вершины (x2,y2) заштрихованные клетки (т.е. элементы, равные 1). Если такие элементы есть, то функция будет возвращать FALSE, если нет - TRUE |
26 |
 |
Решениеfunction check(x1,y1,x2,y2:integer):boolean; var i,j:integer; b:boolean; begin b:=true; i:=x1; while b and (i<=x2) do begin j:=y1; while b and (j<=y2) do begin if a[i,j]=1 then b:=false; j:=j+1 end; i:=i+1 end; check:=b end; |
27 |
 |
РешениеВ основной программе организуем два попарно вложенных цикла: в первом цикле будем изменять координаты верхнего левого угла прямоугольника, во втором - координаты нижнего правого угла. Если в прямоугольнике нет заштрихованных клеток, то вычислим его площадь, и если она является максимальной, запомним её и координаты противоположных вершин этого прямоугольника. |
28 |
 |
Решениеvar a:array[1..10,1..10] of 0..1; n,i1,j1,i2,j2,s,smax,i1max,j1max,i2max,j2max:integer; function check(x1,y1,x2,y2:integer):boolean; … begin assign(input,'task3.in'); reset(input); readln(n); for i1:=1 to n do for j1:=1 to n do read(a[i1,j1]); close(input); smax:=0; for i1:=1 to n do for j1:=1 to n do for i2:=i1 to n do for j2:=j1 to n do |
29 |
 |
Решениеif check(i1,j1,i2,j2) then begin s:=(i2-i1+1)*(j2-j1+1); if s>smax then begin smax:=s; i1max:=i1; j1max:=j1; i2max:=i2; j2max:=j2 end end; assign(output,'task3.out'); rewrite(output); writeln(smax); writeln(i1max,' ',j1max); writeln(i2max,' ',j2max); close(output) end. |
30 |
 |
10-11 классы Задача 3Выкройка. На квадратном клетчатом листе бумаги N?N клеток нарисованы фигуры, каждая из которых состоит только из целых соприкасающихся клеток. Фигуры не соприкасаются и не пересекаются. Написать программу, которая определяет фигуру максимальной площади. Предполагается, что такая фигура единственная. В качестве ответа вывести площадь фигуры. Формат входных данных Первая строка файла содержит число N. Следующие N строк содержат по N значений элементов таблицы, разделенных пробелами (1- заштрихованная клетка, 0 – нет). Формат выходных данных Первая строка выходного файла содержит значение максимальной площади. |
31 |
 |
7-8-9 классы Задача 30 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 7 7 |
32 |
 |
РешениеСоздадим рекурсивную функцию, вызов которой происходит, если очередная клетка таблицы равна 1. Заменяем эту клетку на 2 (признак, что она посчитана), увеличиваем площадь на 1 и, если клетка справа, снизу , слева или сверху равна 1, то снова вызываем эту функцию. |
33 |
 |
Решениеprocedure poisk(x,y:integer;var s:integer); begin a[x,y]:=2; s:=s+1; if (x+1<=n) and (a[x+1,y]=1) then poisk(x+1,y,s); if (y+1<=n) and (a[x,y+1]=1) then poisk(x,y+1,s); if (x-1>=1) and (a[x-1,y]=1) then poisk(x-1,y,s); if (y-1>=1) and (a[x,y-1]=1) then poisk(x,y-1,s); end; |
34 |
 |
РешениеВ основной программе перебираем все клетки таблицы и, если текущая равна 1, то, обнулив площадь, вызываем рекурсивную процедуру. При выходе из рекурсии, проверяем площадь на максимальность. |
35 |
 |
Решениеvar a:array[1..10,1..10] of 0..2; n,i,j,s,smax:integer; procedure poisk(x,y:integer;var s:integer); … begin assign(input,'task3.in'); reset(input); readln(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); close(input); smax:=0; for i:=1 to n do for j:=1 to n do if a[i,j]=1 then begin s:=0; poisk(i,j,s); if s>smax then smax:=s; end; assign(output,'task3.out'); rewrite(output); writeln(smax); close(output) end. |
«Муниципальный этап Всероссийской олимпиады школьников по информатике» |
http://900igr.net/prezentacija/fizkultura/munitsipalnyj-etap-vserossijskoj-olimpiady-shkolnikov-po-informatike-69113.html