Презентация на тему «Муниципальный этап Всероссийской олимпиады школьников по информатике»

Муниципальный этап Всероссийской олимпиады школьников по информатике

2011-2012 учебный год

7-8 классы Задача 1

Числа. Дано трехзначное целое положительное число. После удаления первой цифры это число уменьшилось в N раз. Вывести в порядке убывания все такие числа. Формат входных данных Файл содержит число N. Формат выходных данных Выходной файл содержит такие числа.

Решение

Организуем перебор всех трехзначных чисел от 999 до 100. В каждом числе отбрасываем первую цифру и умножаем результат на N. Если получившееся число равно исходному числу, то выводим его.

Решение

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.

9 класс Задача 1

Числа. Дано четырехзначное целое положительное число. После удаления первой цифры это число уменьшилось в N раз. Вывести в порядке убывания все такие числа. Формат входных данных Файл содержит число N. Формат выходных данных Выходной файл содержит такие числа.

Решение

Организуем перебор всех четырехзначных чисел от 9999 до 1000. В каждом числе отбрасываем первую цифру и умножаем результат на N. Если получившееся число равно исходному числу, то выводим его.

Решение

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.

10-11 классы Задача 1

Числа. Дано не более чем семизначное целое положительное число A (10?А?9999999). После удаления первой цифры это число уменьшилось в N раз. Вывести количество таких чисел. Формат входных данных Файл содержит число N. Формат выходных данных Выходной файл содержит количество таких чисел.

Решение

Организуем перебор всех чисел от 10 до 9999999. Заметим, что на этом диапазоне 90 двузначных чисел, 900 – трехзначных, 9000 – четырехзначных и т.д. Поэтому в первых девяносто числах отбрасываем вторую справа цифру. Затем в 900 числах отбрасываем третью справ цифру и т.д. Получившееся число умножаем на N. Если результат равен исходному числу, то считаем его.

Решение

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.

7-8-9 классы Задача 2

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

Решение

Динамическое программирование (прежде чем найти кол-во маршрутов до позиции N, найдем кол-во маршрутов до позиций 1, 2, 3, …, N-1).

Кол-во маршрутов будем хранить в массиве S.

0

1

2

3

…

N-1

N

Решение

Сначала найдем позиции, в которые можно дойти за 1 шаг. Очевидно, что это позиции 1, 2, 3, …, K. Занесем в S[1], S[2], …, S[K] значения 1.

0

1

2

3

…

K

N

…

S:

1

1

1

…

1

0

…

Решение

В 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

…

Решение

Таким образом, вычисляя последовательно значения величин S[2], S[3],..., S[N] получаем значение S[N], которое и указывает общее количество различных путей, по которым фишка может пройти поле от начала до позиции с номером N.

Решение

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.

Шеренга

Сколько вариантов имеется у учеников для того, чтобы стать в шеренгу из N человек? Формат входных данных Файл содержит число N (1?N?150). Формат выходных данных Выходной файл содержит количество вариантов расстановки.

10-11 классы Задача 2

Решение

Количество вариантов - это число перестановок из 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 Надо использовать «длинную арифметику».

Решение

Факториал вычисляется последовательно с 1! до N!. Для размещения цифр факториала используем массив f, в который в первую ячейку заносим 1 (т.к. 0!=1). Затем в цикле по переменной k от 1 до N производим поразрядное умножение занятых ячеек массива f на число k. Этапы умножения проследим по схеме.

Решение

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

Решение

Назначение переменных: z – количество позиций массива f хранящих цифры факториала; ab – результат умножения очередной позиции массива f на число k; a – количество десятков в результате умножения.

Решение

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.

7-8-9 классы Задача 3

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

7-8-9 классы Задача 3

0

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

Решение

Напишем логическую функцию, которая будет проверять, есть ли в прямоугольнике с координатами левой верхней вершины (x1,y1) и координатами правой нижней вершины (x2,y2) заштрихованные клетки (т.е. элементы, равные 1). Если такие элементы есть, то функция будет возвращать FALSE, если нет - TRUE

Решение

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;

Решение

В основной программе организуем два попарно вложенных цикла: в первом цикле будем изменять координаты верхнего левого угла прямоугольника, во втором - координаты нижнего правого угла. Если в прямоугольнике нет заштрихованных клеток, то вычислим его площадь, и если она является максимальной, запомним её и координаты противоположных вершин этого прямоугольника.

Решение

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

Решение

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.

10-11 классы Задача 3

Выкройка. На квадратном клетчатом листе бумаги N?N клеток нарисованы фигуры, каждая из которых состоит только из целых соприкасающихся клеток. Фигуры не соприкасаются и не пересекаются. Написать программу, которая определяет фигуру максимальной площади. Предполагается, что такая фигура единственная. В качестве ответа вывести площадь фигуры. Формат входных данных Первая строка файла содержит число N. Следующие N строк содержат по N значений элементов таблицы, разделенных пробелами (1- заштрихованная клетка, 0 – нет). Формат выходных данных Первая строка выходного файла содержит значение максимальной площади.

7-8-9 классы Задача 3

0

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

Решение

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

Решение

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;

Решение

В основной программе перебираем все клетки таблицы и, если текущая равна 1, то, обнулив площадь, вызываем рекурсивную процедуру. При выходе из рекурсии, проверяем площадь на максимальность.

Решение

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.