Задача 5 - Сортировка Урфина Джюса (100 баллов)
Задача 1 - Прямоугольники из кубиков (100 баллов)
| Полный балл: | 100 |
| Ограничение времени: | 500 мс |
| Ограничение памяти: | 128M |
Сколько различных прямоугольников можно сложить из N кубиков. Прямоугольники считаются одинаковыми, если один из них можно получить из другого поворотом на 90o. Например, из 3-х кубиков можно сложить только один прямоугольник размером 1 х 3. Из 6-и кубиков можно сложить 2 различных прямоугольника: 1 х 6, 2 х 3 (прямоугольники 3 х 2 и 2 х 3 считаются одинаковыми).
Формат входных данных
Входные данные содержат единственное целое число N (1 ≤ N ≤ 109).
Формат результата
Выведите единственное число - количество различных прямоугольников, которое можно сложить из N кубиков.
Примеры
Входные данные
3
Результат работы
1
Входные данные
6
Результат работы
2
Задача 2 - Сложение в Зазеркалье (100 баллов)
| Полный балл: | 100 |
| Ограничение времени: | 1 с |
| Ограничение памяти: | 128M |
В Зазеркалье все арифметические операции выполняются очень странно. Например, когда Алиса хочет найти сумму двух чисел A+B, происходит следующее. Числа A и B записываются зеркально, полученные зеркальные отображение чисел A и B складываются, полученный результат опять записывается зеркально. Это и есть ответ. Если при зеркальном отображении у чисел получаются лидирующие нули, то их необходимо отбросить.
|
|
|
Например, при сложении Алисой числа 3257 и 748 произойдет следующее. Число 3257 запишется зеркально как 7523. Число 748 запишется зеркально как 847. Выполнится суммирование 7523 + 847 = 8370. Полученная сумма 8370 записывается зеркально как 0738, лидирующий ноль отбрасывается, и получается ответ 738.
Формат входных данных
Входные данные содержат два натуральных числа A и B, разделенные пробелом. Это слагаемые, сумму которых хочет вычислить Алиса (1 ≤ A, B < 109).
Формат результата
Выведите единственное число - результат сложения чисел A и B по описанному в условии правилу.
Примеры
Входные данные
3257 748
Результат работы
738
Задача 3 - Делимость на 11 (100 баллов)
| Полный балл: | 100 |
| Ограничение времени: | 500 мс |
| Ограничение памяти: | 128M |
Для того, чтобы выяснить, делится ли некоторое число на 11, нужно выполнить следующие шаги.
1. Найти сумму цифр числа, стоящих не нечетных местах.
2. Найти сумму цифр числа, стоящих на четных местах.
3. Вычесть из первой суммы вторую.
4. Если получившаяся разность делится на 11, то и все число делится на 11.
В этой задаче вам достаточно найти разность из третьего пункта, то есть разность суммы цифр, стоящих на нечетных местах, и суммы цифр, стоящих на четных местах, для некоторого очень большого целого положительного числа.
|
|
|
Формат входных данных
Входные данные содержат единственное число N (1 ≤ N ≤ 10100);
Формат результата
Выведите разность суммы цифр, стоящих на нечетных местах и суммы цифр, стоящих на четных местах в числе N. Цифры нумеруются слева направо, начиная с самого старшего разряда числа. Цифры нумеруются, начиная с 1, то есть самый старший разряд числа имеет номер 1.
Примеры
Входные данные
1323456
Результат работы
2
Задача 4 - Программа для марсохода (100 баллов)
| Полный балл: | 100 |
| Ограничение времени: | 1 с |
| Ограничение памяти: | 128M |
Разработка программного обеспечения для марсохода приближается к завершению. Вам, как главному программисту, поручено завершить самую важную часть проекта - написать программу для навигатора, которая позволит марсоходу передвигаться из одной заданной точки координатной плоскости в другую.
Марсоход умеет выполнять следующие команды:
· команда U увеличивает текущую координату y на 1, то есть, выполняя эту команду, марсоход переместится из точки с координатами (x,y) в точку с координатами (x, y+1)
|
|
|
· команда D уменьшает текущую координату y на 1, то есть, выполняя эту команду, марсоход переместится из точки с координатами (x,y) в точку с координатами (x, y-1)
· команда R увеличивает текущую координату x на 1, то есть, выполняя эту команду, марсоход переместится из точки с координатами (x,y) в точку с координатами (x+1, y)
· команда L уменьшает текущую координату x на 1, то есть, выполняя эту команду, марсоход переместится из точки с координатами (x,y) в точку с координатами (x-1, y)
Программа для марсохода представляет собой строку, состоящую только из символов U,D,L,R. Например, если в начальный момент времени марсоход находился в точке с координатами (1,2), то, выполняя программу RURUU, он переместится в точку с координатами (3,5). А выполняя программу LULL, он переместиться из точки (1,2) в точку (-2,3).
Вам необходимо написать программу, которая по заданному начальному и конечному положению марсохода выведет строку указанных выше команд, выполняя которые марсоход переместится из заданной начальной точки в заданную конечную.
Формат входных данных
Входные данные содержат две строки. В первой строке записаны два целых числа X1 и Y1, разделенные пробелом - координаты начального положения марсохода (-50 ≤ X1, Y1 ≤ 50). Во второй строке записаны два целых числа X2 и Y2, разделенные пробелом - координаты конечного положения марсохода (-50 ≤ X2, Y2 ≤ 50). Гарантируется, что начальное и конечное положение марсохода не совпадают.
|
|
|
Формат результата
Выведите единственную строку, состоящую только из букв U,D,L,R - последовательность команд, выполняя которые марсоход переместиться из точки (X1,Y1) в точку (X2,Y2). Если таких последовательностей команд существует несколько - выведите любую. Длина выводимой последовательности команд не должна превышать 1000 символов.
Примеры
Входные данные
1 2
3 5
Результат работы
RURUU
Входные данные
1 2
-2 3
Результат работы
LULL
Задача 5 - Сортировка Урфина Джюса (100 баллов)
| Полный балл: | 100 |
| Ограничение времени: | 1 с |
| Ограничение памяти: | 128M |
Урфин Джюс все еще мечтает расставить своих деревянных солдат по росту. Для этого он придумывает все новые и новые алгоритмы, и каждый раз неудачно. И вот опять он принес мудрому филину Гуамоку очередной алгоритм, который состоит в следующем.
Перед Урфином стоит шеренга из N деревянных солдат-дуболомов. Урфин разбивает дуболомов на группы по K дуболомов. Первую группу образую дуболомы, стоящие в позициях с номерам от 1 до K, вторая группа - в позициях с номерами от K+1 до 2*K, третья - от 2*K+1 до 3*K и так далее. Урфин идет вдоль шеренги слева направо, выбирает самого высокого дуболома в первой группе, сдвигает всех, кто стоит левее его, на одну позицию вправо, после чего ставит выбранного дуболома на первое место в шеренге. Затем он переходит ко второй группе, выбирает там самого высокого дуболома, сдвигает всех, кто стоит левее его, начиная со второй позиции, на одну позицию вправо, и ставит выбранного дуболома на второе место. Далее он выбирает самого высокого в третьей группе и ставит его на третье место, сдвинув дуболомов, начиная с третьего места до выбранного, и так далее, пока не кончится шеренга.
Конечно же, мудрый филин Гуамоку сразу понял, что в результате применения этого алгоритма дуболомы не будут отсортированы по росту. Но чтобы наглядно продемонстрировать это Урфину, Гуамоку просит вас написать программу, которая реализует описанный выше алгоритм.
Формат входных данных
В первой строке входных данных записаны два натуральных числа N и K - количество дуболомов в строю и число дуболомов, из которого Урфин выбирает самого высокого на каждом шаге алгоритма (1 ≤ N ≤ 100, 1 ≤ K ≤ N, N делится на K без остатка).
В следующей строке записаны через пробел N натуральных чисел Ai. Каждое число - рост дуболома (1 ≤ Ai ≤ 100). Все числа Ai различны.
Формат результата
Выведите одну строку, содержащую N чисел, разделенных одним пробелом - исходные значения, переставленные в соответствии с алгоритмом Урфина Джюса.
Примеры
Входные данные
9 3
2 3 1 4 5 6 7 8 9
Результат работы
3 6 9 2 1 4 5 7 8
Примечания
Пояснение к примеру
Первоначально дуболомы были расставлены так:
2 3 1 4 5 6 7 8 9
Сначала Урфин выберет самого высокого дуболома среди первых трех (это дуболом ростом 3) и поставит его на первое место, сдвинув первого вправо на одну позицию. Строка чисел примет вид
3 2 1 4 5 6 7 8 9
Затем Урфин выберет самого высокого дуболома среди следующих трех (это дуболом ростом 6) и поставит его на второе место, сдвинув всех со второго места по пятое вправо на одну позицию. Строка чисел примет вид
3 6 2 1 4 5 7 8 9
Наконец, Урфин выберет самого высокого дуболома среди последних трех (это дуболом ростом 9) и поставит его на третье место, сдвинув всех дуболомов с третьего по восьмое место на одну позицию вправо. Строка чисел примет вид
3 6 9 2 1 4 5 7 8
Дата добавления: 2018-11-24; просмотров: 268; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!