Олимпиадные задания по информатике (Ломоносов 2011-2012)

SHIISH — Sat, 07 Jan 2012 07:29:27 GMT

Задание 1. Сколько пятниц в календаре в период с 1 января 2001 года по 31 декабря 2020
года включительно? Сколько пятниц попадает на 13-е число? Ответ запишите в виде двух
чисел, разделяя их дефисом. Обоснуйте свой ответ и приложите исходные тексты (например,
тексты программ или электронные таблицы), использованные для получения ответа.
Задание 2. Даны переменные A, B, C, D (заглавные латинские буквы), принимающие
значения 0 или 1. С использованием символов этих переменных, символа 1 для записи
константы 1, скобок ( и ) и символа операции + запишите самую короткую по числу символов
формулу, реализующую следующий вектор значений:
0111001011101010
При подсчете числа символов учитываются все вхождения переменных, константы 1, скобок
и операции +.
Вектор значений содержит 16 значений функции, которые она принимает при всех 16
возможных значениях переменных A, B, C, D. Нулевой элемент вектора соответствует
значениям переменных A=0, B=0, C=0, D=0, первый — A=0,B=0,C=0,D=1, второй –
A=0,B=0,C=1,D=0, третий A=0,B=0,C=1,D=1, то есть в порядке лексикографического
возрастания четверок значений переменных A, B, C, D.
Знак операции + обозначает сложение по модулю 2, то есть функцию от двух переменных,
принимающую вектор значений 0110.
Обоснуйте свой ответ и приложите исходные тексты (например, тексты программ или
электронные таблицы), использованные для получения ответа.
Задание 3. Последовательность цифр: 1223242434... образована выписыванием подряд чисел,
равных количеству делителей числа n (n=1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...). Укажите в ответе 10
цифр последовательности, начиная с 2012-й цифры. Нумерация цифр начинается с единицы.
Обоснуйте свой ответ (обоснованием может быть текст программы или математический ра счѐт).
Задание 4. Рассмотрим девятеричную позиционную систему счисления с цифрами { B, A, 0,
1, 2, 3, 4, 5, 6 }, где цифра A имеет значение -1, а цифра B – значение -2. Выполните
следующие операции и представьте результат в этой же самой системе счисления:
24+5A
B5+61
52*A6
312+41B
A1A*B2B
Обоснуйте свой ответ и приложите исходные тексты (например, тексты программ или
электронные таблицы), использованные для получения ответа.
Задание 5. Рассмотрим текст романа Л. Н. Толстого «Анна Каренина» (следует использовать
электронную версию романа, находящуюся по адресу http://ejudge.ru/study/anna.txt ).
Словоформой назовем последовательность латинских или русских букв. Словоформы
ограничиваются символами, не являющимися латинскими или русскими буквами. В
словоформах не различаются заглавные и строчные буквы и буквы е и ѐ. Например, Осел и
осѐл — это одна словоформа. Выпишите 10 наиболее часто встречающихся словоформ
длиной 4 буквы в порядке уменьшения частоты их появления и для каждой словоформы
укажите частоту ее появления. Словоформы должны быть выписаны строчными буквами, с
буквой ѐ, преобразованной к букве е. Если несколько словоформ имеют равную частоту
появления, они должны быть упорядочены по алфавиту (причем русские буквы идут раньше
Олимпиада школьников «Ломоносов», отборочный этап, информатика, 2011-2012 учебный год
латинских). Обоснуйте свой ответ и приложите исходные тексты (например, тексты
программ или электронные таблицы), использованные для получения ответа.
Задание 6. Рассмотрим последовательность чисел от 1000000000 и до 1999999999
(включительно). В этой последовательности чисел вычеркнем все числа, сумма цифр
которых меньше 30. Из оставшихся чисел вычеркнем все числа, сумма цифр которых больше
или равна 40. Из оставшихся чисел вычеркнем все числа, в которых цифра 5 содержится
более одного раза. Найдите остаток от деления произведения оставшихся чисел на число 29.
Обоснуйте свой ответ и приложите исходные тексты (например, тексты программ или
электронные таблицы), использованные для получения ответа.
Задание 7. Пусть дана строка s длины n. Суффиксом sn строки s является строка,
образованная из последних n символов строки s. Таким образом, sn совпадает с s, а s0 – это
пустая строка. Все n + 1 суффиксов строки s можно поместить в массив и отсортировать
массив в порядке лексикографического возрастания. Такой массив называется суффиксным
массивом.
Рассмотрим строку длиной 2012, полученную как запись 2012 знаков числа pi после
десятичной точки (начинающуюся с "1415..."). Какая строка будет находиться в элементе
массива с индексом 64? Элементы массива нумеруются от 0.
Обоснуйте свой ответ и приложите исходные тексты (например, тексты программ или
электронные таблицы), использованные для получения ответа.
Задание 8. Напишите программу, которая решает следующую задачу. Программа может быть
написана на языках программирования Pascal, Basic, C, C++, Java, C#, PHP, Python. В качестве
решения должен быть приложен исходный текст программы в виде текстового файла.
Напишите программу, находящую корни уравнения ax2 + bx + c = 0.
На стандартном потоке ввода задаются три знаковых целых 32-битных числа a, b, c, по
абсолютной величине не превышающие 100000000.
На стандартный поток вывода напечатайте:
 -1, если данное уравнение имеет бесконечное количество вещественных корней;
 0, если данное уравнение не имеет вещественных корней;
 1, если данное уравнение имеет один (различный) корень;
 2, если данное уравнение имеет два различных вещественных корня.
В случае 1 или 2 на стандартный поток вывода выведите значения корней, округленные до целых
чисел в порядке возрастания. Значения должны быть напечатаны как целые числа, то есть не
должны содержать дробную или экспоненциальную часть. Случай, когда два различных
вещественных корня после округления стали равными целыми числами, рассматривается как
случай двух различных вещественных корней.
В программе запрещается использовать вещественную арифметику.
Программа должна работать как консольное приложение, при этом на стандартный поток вывода
не должна выводиться никакая посторонняя информация. Пример реализации ввода и вывода на
языке Pascal.
program q;
var a, b, c, x1, x2 : integer;
begin
read(a, b, c);
{ вычисление ответа }
writeln(2);
writeln(x1);
writeln(x2);
end.

Персональный сайт

Олимпиадные задания по информатике (Ломоносов 2011-2012)