Олимпиада по информатике

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

Задачи школьной олимпиады Костромской области.

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

9-11 класс

Задача 1. Как известно, натуральное число N > 1 называется простым, если оно делится нацело только на себя и на единицу. В противном случае число N называется составным и может быть представлено как произведение простых чисел. В этом случае говорят, что N разложено на простые сомножители. Напишите программу, которая по заданному натуральному N  > 1 определяет количество простых сомножителей в его разложении.

Входные данные.

С клавиатуры вводится натуральное число N, находящееся в диапазоне от 2 до 2000000000.

Выходные данные.

На экран выводится одно число — количество простых сомножителей в его разложении. В случае, если N окажется простым, на экране печатается число 1

Задача 2. Петя придумал способ кодирования натуральных десятичных чисел латинскими буквами a, b и c. Чтобы закодировать число его способом, надо каждую цифру этого числа заменить буквосочетанием в соответствии со следующей таблицей:

Напишите программу, восстанавливающую по кодирующему слову закодированное число. Если восстановить число невозможно, следует вывести сообщение «No».

Входные данные.

Имя входного файла вводится с клавиатуры.

Во входном файле записана единственная строка, содержащая только маленькие латинские буквы a, b, c и имеющая длину не более 250 символов.

Выходные данные.

На экран выводится восстановленное число или слово «No».

Задача 3. В Костроме, как известно, проезд на городском общественном транспорте составляет 12 рублей на всех маршрутах. Однако, далеко не всегда можно проехать с одной остановки на другую за эти деньги: иногда приходится ехать с пересадками.

В городе имеется некоторое количество маршрутов, пронумерованных натуральными числами от 1 до N. Каждый маршрут включает в себя несколько остановок. Если через одну и ту же остановку проходит сразу несколько маршрутов, то на ней можно сделать пересадку с любого, проходящего через нее маршрута, на любой другой (опять же проходящий через нее). Напишите программу, которая определяет минимальную стоимость проезда с остановки A на остановку B.

Входные данные.

Имя входного файла вводится с клавиатуры.

Во входном файле в первой строке записаны два числа, разделенных пробелом: сначала число N – количество остановок в городе (2 ≤ N ≤ 100), затем число M – количество маршрутов (1 ≤ M ≤ 20). Во второй строке файла также записаны два числа, разделенных пробелом: номера остановок A и B. Далее идет описание M маршрутов. Описание каждого маршрута занимает одну строку файла; оно состоит из числа P_i — количество остановок на i-ом маршруте (2 ≤ P_i ≤ 30) и затем P_i чисел, задающих номера остановок, через которые проходит i-й маршрут.

Выходные данные.

На экран выводится минимальная стоимость переезда. Если добраться с остановки A на остановку B невозможно, на экране печатается число –1 (минус один).

Задача 4. Для заданного натурального числа N подсчитать количество натуральных чисел K £ N, имеющих в своей двоичной записи ровно три значащих нуля.

Примечание. Первая слева ненулевая цифра в записи числа и все цифры правее ее называются значащими. Таким образом, незначащими оказываются только лидирующие нули.

Входные данные.

С клавиатуры вводится натуральное число N, находящееся в диапазоне от 8 до 2000000000.

Выходные данные.

На экран выводится единственное число – искомое количество чисел.

Пример работы программы:

Пояснение к примеру. Числа 8, 17, 18 и 20 в двоичной записи имеют три нуля – 1000, 10001, 10010 и 10100 соответственно.-

Другие олимпиадные задачи

Первый уровень сложности

1. Положительная сумма 

По трем заданным числам выяснить, является ли сумма каких-нибудь двух из них положительной.

2. Делители 

Найти все делители натурального числа n.

3.Простые делители  

Найти все простые делители натурального числа n.

4. Треугольник 

Вычислите, в какой координатной четверти расположен треугольник, образованный прямой, заданной уравнением y=ax+b, и осями координат.

5. Курьеры 

Хлестакова приглашали управлять департаментом. В первый день ему прислали 1000 курьеров, а в каждый следующий — в 2 раза больше, чем в предыдущий. Хлестаков согласился, когда прислали 30000 курьеров. На какой день это произошло?

6. Счастливые билеты 

Написать программу определения количества билетов с 6-значными номерами, у которых сумма первых 3 десятичных цифр равна сумме 3 последних десятичных цифр.

7. Произведение 

Дано натуральное число N. Вычислить произведение первых N сомножителей: (2/1)*(2/3)*(4/3)*(4/5)*…

8. Число

По заданным n (n<7) и k определить сколько существует n-значных чисел, заканчивающихся цифрой k и делящихся на 3.

9. Число в последовательности

Последовательность целых чисел строится следующим образом:

- первое задается (обозначим его через a),

- каждое следующее число является суммой цифр квадрата предыдущего.

Например, если a=4, то получится последовательность 4, 7, 13, 16, ….

По заданным a и n определить n-е число в этой последовательности. Известно, что a<10000 и n<1000000.

10. Среднее арифметическое

По заданному n (1<n<7) определить все n-значные числа, обладающие свойством:

среднее арифметическое всех чисел, получающихся из исходного числа различными перестановками его цифр, равно самому числу.

11. Вычеркивание

Заданы натуральные числа k и n (k<100). Из числа 12345123445… 123455 (цифры 12345 записываются k раз) вычеркнуть n цифр так, чтобы оставшееся число было максимально возможным.

Например, если из числа 12345 вычеркнуть 3 цифры, то должно получиться 45.

12. Роман

В романе n глав (n<100). В i-й главе ai страниц. Требуется издать роман в k томах так, чтобы количество страниц в самом толстом томе было минимально. Делить главы нельзя.

Написать программу определения количества страниц самого толстого тома.

Например, роман из 3 глав (1, 2, 2 страницы, соответственно) издать в 2 томах можно двумя способами:

1-й том — 1 и 2 главы, 2-й том — 3 глава;

1-й том — 1 глава, 2-й том — 2 и 3 главы.

Тогда в первом способе самый толстый том имеет 3 страницы, а во втором — 4 страницы. Таким образом ответом будет — 3 страницы.

Второй уровень сложности

1. Самое длинное слово

Найти самое длинное слово в тексте. Если таких слов несколько, то взять первое.

2. Простые числа

Определите, какая из цифр в десятичной записи всех простых чисел из заданного диапазона встречается чаще всего.

3. Слияние чисел  

Из цифр двух натуральных чисел составить наибольшее возможное число, сохраняя первоначальную последовательность цифр.

4. Поиск палиндромов 

Найти в тексте все слова-перевёртыши, то есть те, которые читаются одинаково слева-направо и справа-налево.

5. Поиск различных цифр 

 Дано натуральное число N. Сколько различных чисел встречается в его десятичной записи?

6. Пересечение отрезков 

 Даны координаты начала и конца двух отрезков в декартовой системе координат. Надо вычислить пересекаются эти отрезки или нет.

 7.  Самая длинная цепочка 

Дана вещественная таблица a[1], a[2],…,a[1000]. Определить максимальное количество подряд идущих положительных элементов последовательности, не прерываемых ни нулями, ни отрицательными элементами. Напечатать найденный фрагмент.

8. Стрелки часов 

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

Третий уровень сложности

1. Следующее слово 

Написать программу, которая по заданному слову строит непосредственно следующее за ним по алфавиту слово.

2. Перестановки 

Даны n чисел в произвольном порядке. Вывести на экран всевозможные их перестановки.

3. Сумма 

Рассмотрим некоторую сумму S (см. подробное условие). Требуется написать программу, которая по заданным n и k определяет k-ю цифру десятичного разложения дробной части числа Sn.

4. Простые гири 

 Имеются гири с массами: 1 г, 2 г, …, N г (N<500000). Требуется написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.

5. Пропущенное число

    Ученик Ваня Петров записал n чисел (n >=3), образующих арифметическую прогрессию. Затем Ваня одно число вычеркнул, а оставшиеся числа перемешал.

    Опишите алгоритм, который проверяет, можно ли определить пропущенное число, и восстанавливает его, если это возможно.

Материалы взяты на сайте: http://iqmena.wordpress.com/2008/10/29/zadaniya-dlya-olimpiady-po-informatike/