Всероссийская олимпиада школьников
школьный этап
информатика и ИКТ
9 – 11 класс
«Знаменатель – 100 баллов».Для сложения трех обыкновенных дробей со знаменателями a, b и c (1<a, b,c≤1200) Даше необходимо найти наименьший общий знаменатель, который может быть большим, но не больше 231–1 = 2147483647. Помогите ей, составьте программу, которая будет находить его.
Ваша программа должна
- Запросить три натуральных числа – знаменатели трех дробей (1<a, b,c≤1200); Вычислит и выведет на экран наименьший общий знаменатель.
Пример:
Знаменатели 4, 6, 18
Наименьший общий знаменатель 36
«Сдвиг – 100 баллов».
К цифрам натурального числа a (a > 9) применяется операция циклический сдвиг влево. Пример применения этой операции к числу 1730382 показана на рисунке.
1 | 7 | 3 | 0 | 3 | 8 | 2 |
7 | 3 | 0 | 3 | 8 | 2 | 1 |
Из числа 1730382 получено число 7303821. К этому числу опять можно применить сдвиг. К полученному тоже. Получается последовательность чисел 1730382, 7303821, 3038217, 0382173, 3821730, 8217303, 2173038, 1730382, ….
Составьте программу, которая
- Читает натуральное число a, которое может содержать до 100 цифр; Находит и выводит на экран наибольшее число, получаемой сдвигами.
Примеры:
Исходное число 1730382
Наибольшее число 8217303
«Кенгуру – 100 баллов».
Суперкенгуру может прыгать по прямой вправо и влево и совершать гигантские прыжки. Длина его первого прыжка составляет 1 м, второго — 2 м, третьего — 4 м и так далее (длина каждого прыжка всегда в два раза больше, чем предыдущего). Через какое минимальное количество прыжков суперкенгуру окажется на расстоянии d метров от исходной точки O?
Программа должна
- Запросить расстояние d (натуральное число, 0 < d < 2147483647 = 231–1; Найти и вывести на экран минимальное количество прыжков для попадания в точку на расстоянии d или сообщить, что это невозможно.
Примеры:
Расстояние 16 Невозможно
Расстояние 17 Минимальное число шагов 5
Примечание. Имеется в виду последовательность прыжков –1–2–4+8+16, дающая расстояние 17.
Примечание. Время прохождения одного теста во всех задачах – 1 секунда.
Тесты и рекомендации по оценке
Задание 1. «Знаменатель – 100 баллов».
Тест | Исходные данные | Результат |
1 | 6, 12, 36 | 36 |
2 | 3, 5, 7 | 105 |
3 | 1000, 800, 600 | 12000 |
4 | 1100, 1050, 1000 | 231000 |
5 | 1119, 1117, 1115 | 1393664145 |
Оценка: 20 баллов за тест
Задание 2. «Сдвиг – 100 баллов».
Тест | Исходные данные | Результат |
1 | 76 | 76 |
2 | 555 | 555 |
3 | 2012 | 2201 |
4 | 243143 | 432431 |
5 | 570470370270170070170270370670 | 706705704703702701700701702703 |
Оценка: 20 баллов за тест.
Задание 3. «Кенгуру – 100 баллов».
Тест | Исходные данные | Результат | Примечание (как образован и почему не меньше) |
1 | 18 | Невозможно | |
2 | 19 | 5 | 1–2–4+8+16 = 19 1+2+4+8 = 15 < 19 |
3 | 255 | 8 | 1+2+4+8+16+32+64+128 = 255 |
4 | 111111 | 17 | 1+2–4–8–16–32–64–128+256–512–1024+2048+4096– –8192+16384+32768+65536 = 111111 1+2+4+8+16+32+64+128+256+512+1024+2048+4096+ +8192+16384+32768 = 65535 < 111111 |
5 | 2147483645 | 31 | –1+2+4+8+16+32+64+128+256+512+1024+2048 +4096+8192+16384+32768+65536+131072+262144+ +524288+1048576+2097152+4194304+8388608+ +16777216+33664432+67108864+134217728+ +268435456+536870912+1073741824 = 2147483645 +1+2+4+8+16+32+64+128+256+512+1024+2048 +4096+8192+16384+32768+65536+131072+262144+ +524288+1048576+2097152+4194304+8388608+ +16777216+33664432+67108864+134217728+ +268435456+536870912 = 1073741823 < 2147483645 |
Оценка: 20 баллов за тест.
