Олимпиадные задания по информатике для 9, 10, 11 классов
Школьный уровень
1. “Число” (30 баллов)
Натуральное число вводится своим двоичным представлением (длина числа не превышает 10000 двоичных разрядов). Необходимо определить делится ли число на 15.
Ваша программа должна
· принять исходное число с клавиатуры;
· вывести на экран ответ.
Пример: 1111, ответ – “да”
2. «Матрица – 100 баллов ».
Линейный массив в n (n£10) элементов, заполнен целыми числами (|ai|<100). Составить квадратную матрицу n´n такую, что первая ее строка совпала с элементами заданного линейного массива, а каждая последующая строка получалась циклическим сдвигом элементов предыдущей строки влево, с переносом первого элемента в конец строки.
Например:
Размер таблицы 3
Элементы таблицы 1, 2, 3
Результат
Ваша программа должна
· запросить n (n£10), размер линейной таблицы;
· запросить по одному элементы линейной таблицы (целые числа);
· заполнить требуемым образом квадратную таблицу;
· вывести ее на экран в удобном для просмотра виде.
3. «Обработка – 100 баллов ».
Каждый из участников ЕГЭ по информатике и ИКТ получил свой индивидуальный порядковый номер от 1 до n (n<1000). Файл input.dat содержит в первой строке количество участников n, а в последующих n строках – результаты участников (от 0 до 100 баллов) в порядке увеличения их индивидуальных номеров. Необходимо вывести в файл output.dat индивидуальные порядковые номера участников ЕГЭ (по одному в строке) в порядке убывания количества набранных ими баллов. Если два участника набрали равное количество баллов, то раньше указывается меньший номер.
Пример:
| input.dat | output.dat |
Программа должна
· прочитать исходные данные из файла input.dat;
· найти и записать в выходной файл output.dat номера участников ЕГЭ в порядке убывания набранных баллов (если два участника набрали равное количество баллов, то раньше указывается меньший номер);
· программа не должна требовать ввода с клавиатуры и/или выводить результат на экран.
Примечание. Если исходные данные вводятся с клавиатуры, а результат выводится на экран, то решение оценивается из 80 баллов.
4. «Сумма – 100 баллов ».
Натуральное число (длинное целое) можно представить в виде в виде произведения нескольких натуральных чисел (не менее двух) разными способами. Необходимо найти такое представление исходного числа в виде произведения, чтобы сумма сомножителей была наименьшей возможной.
Примеры:
Исходное число 12, наименьшая возможная сумма 7 (имеется в виду представление 3´4 или 2´2´3)
Программа должна
· запросить исходное число;
· найти и сообщить наименьшую возможную сумму натуральных сомножителей, произведение которых дает исходное число.
Примечание. Время прохождения одного теста во всех задачах – 1 секунда.
Ключи. Тесты и рекомендации по оценке
(олимпиада по информатике для 9-11 классов школьный этап)
Задание 1. «Число – 30 баллов ».
| Тест | Исходное число | Результат |
| да | ||
| нет | ||
| да |
Оценка: 1 тест – 10 баллов, 2 теста – 20 баллов, все – 30 баллов.
Задание 2. «Матрица – 100 баллов ».
| Тест | Исходные данные | Результат | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 11, 2010 |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 99, –22, 3 |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| -1, 2, -3, -4 |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 1, 2, 3, 4, 5, 9, 8, 7, 6 |
|
Оценка: 25 баллов за каждый тест
Задание 3. «Обработка – 100 баллов ».
| Тест | Исходные данные (input.dat) | Результат (output.dat) |
| … | … |
Оценка: 25 баллов за каждый тест. При вводе информации с клавиатуры и выводе на экран общая оценка уменьшается на 20 баллов. Файлы для проверки input.dat, правильные ответы answer.dat и программа proverka.dat сравнения файлов input.dat и answer.exe прилагаются.
Скопируйте файлы input.dat, answer.dat для первого теста и proverka.exe в папку ученика с программой. Запустите программу ученика, а потом – программу proverka.exe, которая выдаст сообщение Ok! или Error!. Впрочем, тесты 1-3 могут проверяться визуально.
Задание 4. «Сумма – 100 баллов »
| Тест | Исходные данные | Результат |
| 2 (1´1) | ||
| 6 (2´2´2 или 2´4) | ||
| 77 (2´3´5´67) | ||
| 379761 (3´3´17´17´379721) |
Оценка: 25 баллов за каждый тест.
Задание 1. «Число – 30 баллов ».
Если вспомнить, что признаком деления на 9 в десятичной системе счисления является делимость на 9 суммы цифр числа действительно, пусть есть число
S = a[n]*10n + a[n-1]*10(n-1) +... + a[1]*10 + a[0].
S mod 9 = (a[n]*(10n-1)+a[n] + a[n-1]*(10(n-1)-1)+a[n-1] +... + a[1]*(10-1)+a[1] + a[0]) mod 9
А так как 10k - 1 делится на 9 нацело, то и S mod 9 = (a[n] +... +a[1] +a[0]) mod 9,
и т.д.), то аналогично получаем, что признаком деления на 15 в системе счисления с базисом 16 будет делимость на 15 суммы всех шестнадцатеричных цифр числа.
Мы разбиваем двоичное число справа налево на тетрады, которые однозначно можно преобразовать в шестнадцатеричные цифры, находим их сумму и делим ее на 15. Если остаток 0, то введенное число делится на 15, иначе - нет.
Решение задачи 2. «Матрица – 100 баллов ».
program massiv;
uses crt;
const
m=10;
var
i,j,n:integer;
a:array[1..m] of integer;
b:array[1..m,1..m] of integer;
begin
clrscr;
writeln('Длина массива ');
readln(n);
writeln('Введите ',n,' элементов массива ');
for i:=1 to n do
read(a[i]);
writeln('Искомый квадратный массив ');
for i:=1 to n do
b[1,i]:=a[i];
for i:=2 to n do
begin
for j:=1 to n-1 do
b[i,j]:=b[i-1,j+1];
b[i,n]:=b[i-1,1];
end;
for i:=1 to n do
begin
for j:=1 to n do
write(b[i,j]:6);
writeln;
end;
readkey;
end.
Задача 3 «Обработка – 100 баллов »
program obrabotka;
uses crt;
const m=1000;
var ball,nomer:array [1..m] of integer;
i,n,r:integer;
fi,fo:text;
begin
clrscr;
assign(fi,'input.dat');
reset(fi);
assign(fo,'output.dat');
rewrite(fo);
read(fi,n);
for i:=1 to n do
begin
read(fi,ball[i]);
nomer[i]:=i
end;
i:=1;
while i<n do
if (ball[i]<ball[i+1]) then
begin
r:=ball[i];
ball[i]:=ball[i+1];
ball[i+1]:=r;
r:=nomer[i];
nomer[i]:=nomer[i+1];
nomer[i+1]:=r;
if (i>1) then i:=i-1 else i:=2;
end
else
i:=i+1;
for i:=1 to n do
writeln(fo,nomer[i]);
close(fi);
close(fo);
end.
Программа для проверки
program proverka;
uses crt;
const m=1000;
var ball,nomer:array [1..m] of integer;
a,b,n,i:integer;
s:string;
fi,fe,fo:text;
begin
clrscr;
assign(fi,'input.dat');
reset(fi);
assign(fe,'answer.dat');
reset(fe);
assign(fo,'output.dat');
reset(fo);
read(fi,n);
s:='Ok!';
for i:=1 to n do
begin
read(fo,a);
read(fe,b);
if (a<>b) then s:='Error!';
end;
writeln(s);
close(fi);
close(fo);
close(fe);
readkey;
end.
Задача 4. «Сумма – 100 баллов »
program summin;
uses crt;
var
k,n,nn,s,d:longint;
begin
clrscr;
writeln('Исходное натуральное число ');
readln(n);
nn:=n;
k:=0;
s:=0;
d:=2;
while (nn>1) do
begin
if (nn mod d=0) then
while (nn mod d=0) do
begin
write(d,' ');
s:=s+d;
k:=k+1;
nn:=nn div d
end;
d:=d+1;
end;
writeln;
writeln('Сумма');
if (k<2) then
writeln(1+n)
else
writeln(s);
readkey
end.