олимпиада 2013-2014
Регламент проведения олимпиады.
Время выполнения: 5 часов.
Языки программирования:
· Turbo Pascal,
· Visual Basic,
· C++,
· Object Pascal,
· QBasic,
· Free Pascal,
· ABC Pascal.
Максимальное количество баллов:
· 7-9 классы 100;
· 9-10 классы 130.
Список задач для олимпиады по информатике 10-11 классов.
1. Постулат Бертрана
(Время: 1 сек. Память: 16 Мб Сложность: 30 баллов)
Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого n > 1 найдется простое число p в интервале n < p < 2n. Такая гипотеза была выдвинута в 1845 году французским математиком Джозефем Бертраном (проверившим ее до n=3000000) и доказана в 1850 году Пафнутием Чебышевым. Раманужан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.
Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала n < p < 2n.
Напомним, что число называется простым, если оно делится только само на себя и на единицу.
Входные данные
Входной файл INPUT.TXT содержит целое число n (2 ≤ n ≤ 50000).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – ответ на задачу.
Примеры
№
INPUT1.TXT
OUTPUT1.TXT
1
2
1
2
239
39
3
3000
353
2. Игра
(Время: 1 сек. Память: 16 Мб Сложность: 60 баллов)
Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали даже. Что ж, расскажем о новой игре. На доске написана последовательность n целых чисел. Играют двое. На очередном ходе игрок выбирает число с правого или с левого края последовательности, затем это число стирается и последовательность становится на одно число меньше, а ход переходит к противнику. Выигрывает тот, кто наберет в сумме больше. Написать программу, определяющую победителя в конкретной игре, при условии, что игроки будут играть оптимально.
Входные данные
В первой строке входного файла INPUT.TXT записано целое число n (0 < n < 100). Во второй строке через пробел заданы n натуральных чисел, не превосходящих 1000.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести 1, если победит первый игрок, 2 – если победит второй игрок и 0 – в случае ничьей.
Пример
№
INPUT2.TXT
OUTPUT2.TXT
1
4
3 2 5 4
1
2
6
5 5 5 5 5 5
0
3
9
2 1 3 2 9 1 2 3 1
2
4
10
2 5 3 12 4 6 13 7 1 3
1
3. Нули
(Время: 1 сек. Память: 16 Мб Сложность: 10 баллов)
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц.
Входные данные
В единственной строке входного файла INPUT.TXT записана последовательность нулей и единиц (без пробелов). Суммарное количество цифр не превышает 100.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести искомую длину цепочки нулей.
Пример
№
INPUT3.TXT
OUTPUT3.TXT
1
00101110000110
4
Тесты
№
INPUT3.TXT
OUTPUT3.TXT
Балл
1
1111111
0
1
2
00000011100000101
6
3
3
1100000011110000000
7
3
4
00111000111000
3
3
Решение
Решение представляет собой цикл, включающий посимвольное чтение из файла и накопление счетчика (k), если прочитанный символ равен "0”. Как только цепочка нулей обрывается, производится сравнение накопленного счетчика с текущим максммальным значением (max), и если счетчик превышает это значение, то оно заменяется на значение счетчика
{ Самая длинная цепочка нулей }
program maxZeros;
var
f_In, f_out: text;
i,k: byte;
j:char;
max: byte;
begin
assign(f_In,'inMaxZeros.txt');
assign(f_Out,'outMaxZeros.txt');
reset(f_In);
max:=0;
while not eof(f_In) do {пока не конец файла}
begin
k:=0; {обнуляем счетчик цепочки}
read(f_In, j); {читаем первый символ цепочки}
while (j='0') and not eof(f_In) do
begin
inc(k);
read(f_In,j)
end;
if k>max then max:=k
end;
{ коррекция результата, если искомая цепочка в конце файла}
if (j='0') and (k=max) then inc(max);
writeln(max);
rewrite(f_Out);
writeln(f_Out,max);
close(f_Out);
readln
end.
5 Домашнее задание
(Время: 1 сек. Память: 16 Мб Сложность: 30 баллов)
Петя успевает по математике лучше всех в классе, поэтому учитель задал ему сложное домашнее задание, в котором нужно в заданном наборе целых чисел найти сумму всех положительных элементов, затем найти где в заданной последовательности находятся максимальный и минимальный элемент и вычислить произведение чисел, расположенных между ними. Так же известно, что минимальный и максимальный элемент встречаются в заданном множестве чисел только один раз. Поскольку задач такого рода учитель дал Пете около ста, то Петя как сильный программист смог написать программу, которая по заданному набору чисел самостоятельно находит решение. А Вам слабо?
Входные данные
В первой строке входного файла INPUT.TXT записано единственное число N – количество элементов массива. Вторая строка содержит N целых чисел, представляющих заданный массив. Все элементы массива разделены пробелом. Каждое из чисел во входном файле не превышает 102 по абсолютной величине.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести два числа, разделенных пробелом: сумму положительных элементов и произведение чисел, расположенных между минимальным и максимальным элементами. Значения суммы и произведения не превышают по модулю 3*104.
Примеры
№
INPUT4.TXT
OUTPUT4.TXT
1
5
-7 5 -1 3 9
17 -15
2
8
3 14 -9 4 -5 1 -12 4
26 180
3
10
-5 1 2 3 4 5 6 7 8 -3
36 5040
Тесты
№
INPUT4.TXT
OUTPUT4.TXT
Балл
1
10
12 -35 6 22 65 -10 3 5 12 34
159 -471900
10
2
6
12 -6 22 65 -10 34
133 -650
5
3
13
32 -12 2 11 -14 4 22 12 -6 82 65 -10 34
264 7273728
10
4
5
1 2 3 4 5
0 120
5
Список задач для олимпиады по информатике 7-9 классов.
1. Наихудший делитель
(Время: 1 сек. Память: 16 Мб Сложность: 30 баллов)
Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго — шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.
Дано число n. Найдите такой его делитель d (само число n и единица считаются делителями числа n), что любой другой делитель c числа n лучше, чем d.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 105).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
№
INPUT1.TXT
OUTPUT1.TXT
1
10
10
2
239
1
2. 2^N
(Время: 1 сек. Память: 16 Мб Сложность: 40 баллов)
Необходимо вычислить значение 2n.
Входные данные
В единственной строке входного файла INPUT.TXT записано натуральное число n (0 < n < 1000).
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести значение 2n.
Примеры
№
INPUT2.TXT
OUTPUT2.TXT
1
3
8
2
10
1024
3
72
4722366482869645213696
Тесты
№
INPUT2.TXT
OUTPUT2.TXT
Балл
5
0
1
2
6
10
1024
3
7
72
4722366482869645213696
15
8
128
340282366920938463463374607431768211456
20
Решение
Идея решения может состоять в том, что результат получается в цифровом массиве, длина которого достаточна для хранения всех цифр результата (примерно 302 для n=1000).
Алгоритм срстоит из двух циклов, вложенных друг в друга. Внешний цикл обеспечивает умножение на 2 n раз. Внутренний цикл реализует каждое такое умножение поразрядно с учетом переноса в следующий разряд, т.е обычное умножение столбиком.
{ Вычислить значение 2^N, где 0
Время выполнения: 5 часов.
Языки программирования:
· Turbo Pascal,
· Visual Basic,
· C++,
· Object Pascal,
· QBasic,
· Free Pascal,
· ABC Pascal.
Максимальное количество баллов:
· 7-9 классы 100;
· 9-10 классы 130.
Список задач для олимпиады по информатике 10-11 классов.
1. Постулат Бертрана
(Время: 1 сек. Память: 16 Мб Сложность: 30 баллов)
Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого n > 1 найдется простое число p в интервале n < p < 2n. Такая гипотеза была выдвинута в 1845 году французским математиком Джозефем Бертраном (проверившим ее до n=3000000) и доказана в 1850 году Пафнутием Чебышевым. Раманужан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.
Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала n < p < 2n.
Напомним, что число называется простым, если оно делится только само на себя и на единицу.
Входные данные
Входной файл INPUT.TXT содержит целое число n (2 ≤ n ≤ 50000).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – ответ на задачу.
Примеры
№
INPUT1.TXT
OUTPUT1.TXT
1
2
1
2
239
39
3
3000
353
2. Игра
(Время: 1 сек. Память: 16 Мб Сложность: 60 баллов)
Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали даже. Что ж, расскажем о новой игре. На доске написана последовательность n целых чисел. Играют двое. На очередном ходе игрок выбирает число с правого или с левого края последовательности, затем это число стирается и последовательность становится на одно число меньше, а ход переходит к противнику. Выигрывает тот, кто наберет в сумме больше. Написать программу, определяющую победителя в конкретной игре, при условии, что игроки будут играть оптимально.
Входные данные
В первой строке входного файла INPUT.TXT записано целое число n (0 < n < 100). Во второй строке через пробел заданы n натуральных чисел, не превосходящих 1000.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести 1, если победит первый игрок, 2 – если победит второй игрок и 0 – в случае ничьей.
Пример
№
INPUT2.TXT
OUTPUT2.TXT
1
4
3 2 5 4
1
2
6
5 5 5 5 5 5
0
3
9
2 1 3 2 9 1 2 3 1
2
4
10
2 5 3 12 4 6 13 7 1 3
1
3. Нули
(Время: 1 сек. Память: 16 Мб Сложность: 10 баллов)
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц.
Входные данные
В единственной строке входного файла INPUT.TXT записана последовательность нулей и единиц (без пробелов). Суммарное количество цифр не превышает 100.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести искомую длину цепочки нулей.
Пример
№
INPUT3.TXT
OUTPUT3.TXT
1
00101110000110
4
Тесты
№
INPUT3.TXT
OUTPUT3.TXT
Балл
1
1111111
0
1
2
00000011100000101
6
3
3
1100000011110000000
7
3
4
00111000111000
3
3
Решение
Решение представляет собой цикл, включающий посимвольное чтение из файла и накопление счетчика (k), если прочитанный символ равен "0”. Как только цепочка нулей обрывается, производится сравнение накопленного счетчика с текущим максммальным значением (max), и если счетчик превышает это значение, то оно заменяется на значение счетчика
{ Самая длинная цепочка нулей }
program maxZeros;
var
f_In, f_out: text;
i,k: byte;
j:char;
max: byte;
begin
assign(f_In,'inMaxZeros.txt');
assign(f_Out,'outMaxZeros.txt');
reset(f_In);
max:=0;
while not eof(f_In) do {пока не конец файла}
begin
k:=0; {обнуляем счетчик цепочки}
read(f_In, j); {читаем первый символ цепочки}
while (j='0') and not eof(f_In) do
begin
inc(k);
read(f_In,j)
end;
if k>max then max:=k
end;
{ коррекция результата, если искомая цепочка в конце файла}
if (j='0') and (k=max) then inc(max);
writeln(max);
rewrite(f_Out);
writeln(f_Out,max);
close(f_Out);
readln
end.
5 Домашнее задание
(Время: 1 сек. Память: 16 Мб Сложность: 30 баллов)
Петя успевает по математике лучше всех в классе, поэтому учитель задал ему сложное домашнее задание, в котором нужно в заданном наборе целых чисел найти сумму всех положительных элементов, затем найти где в заданной последовательности находятся максимальный и минимальный элемент и вычислить произведение чисел, расположенных между ними. Так же известно, что минимальный и максимальный элемент встречаются в заданном множестве чисел только один раз. Поскольку задач такого рода учитель дал Пете около ста, то Петя как сильный программист смог написать программу, которая по заданному набору чисел самостоятельно находит решение. А Вам слабо?
Входные данные
В первой строке входного файла INPUT.TXT записано единственное число N – количество элементов массива. Вторая строка содержит N целых чисел, представляющих заданный массив. Все элементы массива разделены пробелом. Каждое из чисел во входном файле не превышает 102 по абсолютной величине.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести два числа, разделенных пробелом: сумму положительных элементов и произведение чисел, расположенных между минимальным и максимальным элементами. Значения суммы и произведения не превышают по модулю 3*104.
Примеры
№
INPUT4.TXT
OUTPUT4.TXT
1
5
-7 5 -1 3 9
17 -15
2
8
3 14 -9 4 -5 1 -12 4
26 180
3
10
-5 1 2 3 4 5 6 7 8 -3
36 5040
Тесты
№
INPUT4.TXT
OUTPUT4.TXT
Балл
1
10
12 -35 6 22 65 -10 3 5 12 34
159 -471900
10
2
6
12 -6 22 65 -10 34
133 -650
5
3
13
32 -12 2 11 -14 4 22 12 -6 82 65 -10 34
264 7273728
10
4
5
1 2 3 4 5
0 120
5
Список задач для олимпиады по информатике 7-9 классов.
1. Наихудший делитель
(Время: 1 сек. Память: 16 Мб Сложность: 30 баллов)
Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго — шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.
Дано число n. Найдите такой его делитель d (само число n и единица считаются делителями числа n), что любой другой делитель c числа n лучше, чем d.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 105).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
№
INPUT1.TXT
OUTPUT1.TXT
1
10
10
2
239
1
2. 2^N
(Время: 1 сек. Память: 16 Мб Сложность: 40 баллов)
Необходимо вычислить значение 2n.
Входные данные
В единственной строке входного файла INPUT.TXT записано натуральное число n (0 < n < 1000).
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести значение 2n.
Примеры
№
INPUT2.TXT
OUTPUT2.TXT
1
3
8
2
10
1024
3
72
4722366482869645213696
Тесты
№
INPUT2.TXT
OUTPUT2.TXT
Балл
5
0
1
2
6
10
1024
3
7
72
4722366482869645213696
15
8
128
340282366920938463463374607431768211456
20
Решение
Идея решения может состоять в том, что результат получается в цифровом массиве, длина которого достаточна для хранения всех цифр результата (примерно 302 для n=1000).
Алгоритм срстоит из двух циклов, вложенных друг в друга. Внешний цикл обеспечивает умножение на 2 n раз. Внутренний цикл реализует каждое такое умножение поразрядно с учетом переноса в следующий разряд, т.е обычное умножение столбиком.
{ Вычислить значение 2^N, где 0
