Инструменты пользователя

Инструменты сайта


подготовка_к_олимпиаде._тур_11

Это старая версия документа.


1. Шестеренки

Даны две сцепленные шестеренки. У одной шестеренки N зубцов, у другой – K. Требуется найти, какое минимальное число поворотов на один зубчик требуется сделать, чтобы шестеренки вернулись в исходное состояние.

Формат входных данных. В единственной строке - два натуральных числа N и K, не превосходящих 10 миллионов.

Формат выходных данных. Выведите искомое количество зубчиков. Гарантируется, что оно не более миллиарда.

Пример вводаПример вывода
5 55

2. Круглые числа

Будем называть числа круглыми, если они содержат в своей записи только цифры 0 и 5. Составим последовательность круглых чисел в порядке возрастания: 0, 5, 50, 55, 500, 505 и так далее.

Написать программу, которая находит K-ое по порядку в этой последовательности круглое число.

Входные данные. Со стандартного потока ввода вводится натуральное число K — номер круглого числа в последовательности (0 < K ≤ 109).

Выходные данные. Выведите на экран требуемое круглое число.

Пример вводаПример вывода
25
6505

3. Палиндром (Муниципальный этап, 2012)

Палиндромом называется строка, которая читается одинаково слева направо и справа налево. Например, 1001 – палиндром, 1010 – нет. Напишите программу, которая превращает любую строку из 0 и 1 в палиндром, добавляя в нее минимальное количество новых символов. Добавлять новые символы можно слева, справа и внутрь строки. Вводится строка длиной не более 100 символов, состоящая только из 0 и 1.

Вывести в первой строке количество добавленных символов, во второй строке – получившийся палиндром. Если существует несколько вариантов, вывести вариант, который идет раньше в лексикографическом порядке.

Пример вводаПример вывода
1010 1
01010

4. Подмножества (Муниципальный этап, 2010)

Возьмем все непустые различные подмножества из некоторого набора букв и упорядочим их в алфавитном порядке: сначала буквы внутри подмножеств, а затем сами подмножества. Например, из набора букв AABC получаются следующие подмножества после записи их в алфавитном порядке A, AA, AAB, AABC, AAC, AB, ABC, AC, B, BC, C.

Ввести последовательность букв (до 30 прописных латинских букв) и номер подмножества в упорядоченном списке подмножеств.

Вывести подмножество с соответствующим номером.

Пример вводаПример вывода
AABC
5
AAC

5. Разложение на простые слагаемые (Муниципальный этап, 2010)

Любое целое число большее 1 можно единственным способом представить в виде произведения простых множителей (если перечислять множители в неубывающем порядке). Но если попытаться представлять целые числа в виде суммы простых слагаемых (также в неубывающем порядке), то таких разложений окажется несколько. Например, для числа 11 есть 6 таких разложений: 11=11, 11=2+2+7, 11=3+3+5, 11=2+2+2+5, 11=2+3+3+3, 11=2+2+2+2+3. Напишите программу, которая вводит натуральное число N (1<N≤5000) и выводит количество разложений данного числа на простые слагаемые.

Пример вводаПример вывода
116
/home/m/mvgoru/wiki.gumnasion.ru/public_html/data/attic/подготовка_к_олимпиаде._тур_11.1384630977.txt.gz · Последние изменения: 2013/11/16 23:42 — Пронин Роман