Книга "Алгоритмы и программы"

Задачи из главы 1 "Разминка"

содержание задачника

1. Стрелки часов движутся с постоянными угловыми скоростями и показывают $h$ часов $m$ минут. Найдите число полных минут до ближайшего момента, в который стрелки совпадут. Решение
   Вход. Два целых числа $h$ и $m$ (на клавиатуре). Выход. Целое число минут (на экране).
   Пример. Вход: 0 0;  выход: 0. Вход: 1 1; выход: 4.
2. Разбить последовательность чисел от 1 до $N^2$ на $N$ подпоследовательностей так, чтобы все они состояли из $N$ чисел и имели равные суммы. Если решений несколько, то вывести любое из них. Решение
   Вход. Целое число от 1 до 200 (на клавиатуре).
   Выход. $N$ строк, содержащих по $N$ возрастающих чисел, разделенных пробелами (на экране). Порядок, в котором выводятся подпоследовательности, роли не играет.
   Примеры.
   Вход: 1; выход: 1.
   Вход: 3; выход:
   1 5 9
   2 6 7
   3 4 8
3. Составить программу поиска всех решений ребуса VOLVO + FIAT = MOTOR. Разным буквам соответствуют разные цифры, одинаковым - одинаковые. Старшая цифра каждого числа отличается от нуля. Решение
4. Определите, является ли натуральное число простым.  Таблица простых чисел  Что такое простое число   Решение
5. Как известно, каждое натуральное число $n, n>1$, однозначно раскладывается в произведение простых сомножителей, например, $13=13$, $105=3\cdot 5\cdot 7$, $72=2\cdot 2\cdot 2\cdot 3\cdot 3$. Разложите натуральное число на простые множители (факторизация числа). Решение
6. По целому $n$ и $n$ положительным целым числам определите, можно ли из них образовать подмножество, сумма элементов которого делится на $n$ без остатка. Если можно, то найти любое из таких подмножеств. Решение
7. Найти все делители данного натурального числа. Решение
8. Дан действительный радиус $r$ круга на плоскости. Известно, что центр круга - точка с целочисленными координатами. Найдите количество узлов целочисленной координатной сетки внутри круга. Предложите одно решение с оценкой сложности $\Theta(r^2)$, другое - $\Theta(r)$.
9. Числа от 1 до $n$, ($2\le n\le 10^6)$ нужно разбить на максимально возможное количество пар так, чтобы суммы чисел в парах были простыми числами. Найдите количество пар. Например, при $n=3$ получается одна пара (1;2), при $n=7$ получается три пары (1;2), (3;4), (6;7).
10. От прямоугольника с целочисленными размерами $n x m$ отрезают квадраты максимального размера, пока не останется квадрат. Найдите количество отсечений.
11. По двум натуральным числам $a$ и $b$ найдите наименьшее положительное число $d$ и какие-нибудь целые $u$ и $v$, при которых $a\cdot u+b\cdot v=d$.
12. По заданным натуральным числам $a_1, a_2, ..., a_n$, где $n\le 2\cdot 10^9$, найдите наибольшее натуральное число $d$, при котором остатки от деления заданных чисел на $d$ равны.
13. В одном ящике находится $a$ морковок, в другом - $b$ морковок, всего не больше $2\cdot 10^9$. Каждый ящик может вместить всю морковь. За один раз из одного ящика можно переложить в другой столько морковок, сколько лежит в другом ящике. Определите, можно ли в результате таких перекладываний освободить один из ящиков. Например, при $a=9, b=3$ это возможно, при $a=6, b=3$ - нет.
14. Концы отрезка на плоскости имеют целочисленные координаты. Вычислите, сколько всего точек с целочисленными координатами принадлежат отрезку.
15. У Аси есть неограниченный запас монеток достоинством $a$ копеек, у Васи - $b$ копеек. Нужно найти максимальную сумму, которую Ася и Вася не смогут набрать своими монетками. Если такие суммы не ограничены, выдать ответ 0. Например, при $a=2, b=5$ ответ 3, а при $a=2, b=4$ нельзя набрать ни одной нечетной суммы, поэтому ответ 0.
16. Прямоугольник состоит из $X$x$Y$ клеток единичного размера. Из него вырезан прямоугольник размером $(X-2)$x$(Y-2)$ так, что осталась рамка шириной в одну клетку. Определите, можно ли покрыть всю рамку плитками размером $A$x$1$. Запас плиток не ограничен, плитки не накладываются одна на другую и за предел рамки не выходят.
    Вход. В первой строке теста записаны $X$ и $Y$, во второй - последовательность размеров $A$, для которых нужно проверить возможность покрытия (через пробел).
    Выход. Последовательность строк. Каждая строка состоит из 0 и 1, соответствующих проверяемым размерам плиток (1 - покрыть можно, 0 - покрыть нельзя). Например, при $X=5$ и $Y=3$ размерам 2, 3, 4 соответствует строка 110.
17. Найти минимальное натуральное число, которого нет в данной последовательности.
18. Напечатать в порядке возрастания первые $N$ чисел ($1\le N\le 10^4$), имеющие из простых делителей только числа 2, 3 и 5 (последовательность Хэмминга). Например, первые 10 чисел таковы: 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.

содержание задачника