Тема
"Структуры данных: очереди, стеки, списки"

1. Вокруг считающего стоят N человек, из которых выделен первый, а остальные занумерованы по часовой стрелке числами от 2 до N. Считающий, начиная с кого-то, ведет счет до M. Человек, на котором остановился счет, выходит из круга. Счет продолжается со следующего человека и так до тех пор, пока не останется один человек.
   Определить:
   1. номер оставшегося человека, если известно M и то, что счет начинался с первого человека;
   2. номер человека c которого начинался счет, если известно M и номер оставшегося человека L.
2. Задана полоска длиной 2^k клеток и шириной в одну клетку. Полоску сгибают пополам так, чтобы правая половинка оказалась под левой. Сгибание продолжают до тех пор, пока сверху находится больше одной клетки. Необходимо пронумеровать клетки таким образом, чтобы после окончания сгибания полосы номера клеток в получившейся колонке были расположены в порядке 1, 2, 3, 4, ..., 2^k.
3. Квадрат разбит на 4^k равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной (правая половина подкладывается под левую) и горизонтальной (нижняя половина подкладывается под верхнюю) оси симметрии до тех пор, пока все клетки не будут расположены друг под другом.
   Требуется занумеровать клетки исходного квадрата таким образом, чтобы в результате выполнения операций перегиба номера клеток, расположенных друг под другом, образовали числовую последовательность 1, 2, 3, ..., 4^k, начиная с верхней клетки.
4. Даны обозначения двух полей шахматной доски (например, A5 и C2). Найти минимальное число ходов, которое нужно шахматному коню для перехода с первого поля на второе.
5. В таблице А размера N за один просмотр необходимо каждый элемент заменить на ближайший следующий за ним элемент, который больше его. Если такого элемента нет, то необходимо заменить его на ноль. Можно использовать дополнительную память.
   
   Пример А=1 3 2 5 3 4
   Ответ А=3 5 5 0 4 0
6. В городе имеется n автобусных остановок, обозначенных числами из N={1,2,....,n}. Имеется R автобусных маршрутов, заданных последовательностями соседних остановок при движении автобуса в одном направлении:
   
   М₁={I₁₁,I₁₂,...,I_1m1},
   М₂={I₂₁,I₂₂,...,I_2m2},
   .....
   M_r={I_r1,I_r2,...,I_rmr},
   где I_jk натуральное.
   Написать программу, которая по заданным номерам остановок I и J определяет наиболее быстрый путь перемещения пассажира из остановки I в остановку J с использованием имеющихся маршрутов автобусов при условий, что время движения между соседними остановками у всех маршрутов одинаково и в 3 раза меньше времени изменения маршрута. Кроме того, автобусы могут двигаться в обоих направлениях.
7. Одинокий король долго ходил по бесконечной шахматной доске. Известна последовательность из N его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.). Написать программу, определяющую побывал ли король дважды на одном и том же поле за минимально возможное при заданном N число вычислений.
8. По кругу расположено N монет гербами вверх и M монет гербами вниз. Обходя круг по ходу часовой стрелки, переворачивает каждую S-тую монету. В первый раз счет начинается с герба. В каком порядке надо расставить монеты, чтобы после K ходов стало L монет, лежащих гербами вверх.
9. N серых и M белых мышей сидят по кругу. Кошка ходит по кругу по часовой стрелке и съедает каждую S-тую мышку. В первый раз счет начинается с серой мышки. Составить алгоритм, определяющий порядок, в котором сидели мышки, если через некоторое время осталось K серых и L белых мышей.
10. Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На какое количество кусков распадется оставшаяся часть листа, если перед удалением клеток лист склеили в цилиндр высотой N?
    Пример.
    Если из шахматной доски удалить все клетки одного цвета, то оставшаяся часть распадется на 32 куска.
11. Имеется n черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая под низ стопки, третья - на стол, четвертая - под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.
12. Фоpма тела задана матpицей А pазмеpности MxN. Элементы матpицы есть натуpальные числа. Элемент А[i,j] соответствует высоте гоpизонтальной квадpатной площадки pазмеpа 1x1 относительно нижнего основания. Нижнее основание фоpмы горизонтально.
    Необходимо опpеделить объем невытекшей воды, если
    Тело опускается полностью в воду, затем поднимается;
    Пример:
    

    А =	5	3	1
    	5	2	5
    	2	5	5

    После подъема вода останется только во внутреннем углублении, над элементом А[2,2]=1. Объем воды равен 1.
    В позицию A[i₀, j₀] выливается объем воды V.
13. Матрица размера N*M определяет некоторый лабиринт. B матрице элемент 1 обозначает стену, а 0 определяет свободное место. В первой строке матрицы определяются входы x(i), а в последней выходы y(i), i=1, ..., k, которые должны быть нулевыми элементами.
    Необходимо определить, можно ли:
    1. провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..., k таким образом, чтобы каждое свободное место посещалось не более одного раза.
    2. то же, но человека можно выводить через любой из выходов.
    Примечание:
    Движение в лабиринте осуществляется только по вертикали или горизонтали.
14. Есть министерство из N чиновников, где N натуральное число. У каждого из чиновников могут быть как подчиненные, так и начальники, причем справедливы правила: подчиненные моего подчиненного - мои подчиненные, начальники моего начальника - мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника. Для того чтобы получить лицензию на вывоз меди необходимо получить подпись 1-ого чиновника - начальника всех чиновников. Проблема осложняется тем, что каждый чиновник, вообще говоря, может потребовать "визы", т.е. подписи некоторых своих непосредственных подчиненных и взятку - известное количество долларов. Для каждого чиновника известен непустой список возможных наборов "виз" и соответствующая каждому набору взятка. Пустой набор означает, что данный чиновник не требует виз в данном случае. Чиновник ставит свою подпись лишь после того, как ему представлены все подписи одного из наборов "виз" и уплачена соответствующая взятка. Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость. N < 100. Количество наборов для каждого чиновника не превосходит 1.
15. Имеется план местности, разбитой на квадраты, заданный матрицей размера NxN. Каждый квадрат имеет высоту относительно уровня моря, значение которой определяется натуральным числом. Необходимо определить маршрут каравана из позиции (Х₁,У₁) в позицию (Х₂,У₂). Караван может двигаться только по местности параллельно осям Ох и Оу между центрами квадратов и только в соседний квадрат с меньшей высотой.
16. Имеется план местности, разбитой на квадраты, заданный матрицей размера NxN. Каждый квадрат имеет высоту относительно уровня моря, значение которой определяется натуральным числом. Необходимо определить маршрут каравана из позиции (Х₁,У₁) в позицию (Х₂,У₂), при котором крутизна его подъемов и спусков не превышает величины K. Караван может двигаться только по местности и только параллельно осям Оx и Оy между центрами квадратов. При переходе в соседний квадрат крутизна подъема (спуска) равна модулю разности высот квадратов.
17. Имеется план местности, разбитой на квадраты, заданный матрицей размера NxN. Каждый квадрат имеет высоту относительно уровня моря, значение которой определяется натуральным числом. Необходимо определить маршрут робота из позиции (Х₁,У₁) в позицию ((Х₂,У₂), при котором суммарная длина его маршрута минимальна. Длина маршрута определяется как суммарная длина подъемов и спусков плюс суммарная длина перемещений из квадрата в квадрат. Робот может двигаться только по местности и только параллельно осям Оx и Оy между центрами квадратов. При переходе в соседний квадрат длина подъема (спуска) равна модулю разности высот квадратов, а длина перемещения из квадрата в квадрат равна величине K.
18. Имеется шахматная доска. Некоторые поля не ней заняты белыми фигурами и пешками. Каждая занятое поле определяется числом -1.
    Необходимо определить:
    1. минимальное количество ходов белого коня, которое требуется для его перемещения с поля (Х₁,У₁) на поле (Х₂,У₂),
    2. маршрут белого коня с поля (Х₁,У₁) на поле (Х₂,У₂), при котором количество его ходов минимально.
19. Имеется шахматная доска. Некоторые поля не ней заняты белыми и черными фигурами и пешками. Каждая занятое поле белыми фигурами и пешками определяется числом -1, а черными - числом 1.
    Необходимо определить маршрут белого коня с поля (Х₁,У₁) на поле (Х₂,У₂), при котором количество его ходов минимально. Сбитие черной фигуры считается дополнительным ходом (т.е. ход на поле, занятое черной фигурой или пешкой, "стоит" 2 хода).
20. Имеется шахматная доска. Некоторые поля не ней заняты белыми фигурами и пешками (не конями). Каждая занятое поле определяется числом -1.
    Необходимо определить минимальное количество белых коней, которое необходимо расставить на доске, чтобы при постановке черной фигуры в любое оставшееся свободное поле она может быть сбита одним из коней за некоторое количество ходов.
21. Имеется шахматная доска. Некоторые поля не ней заняты белыми фигурами и пешками (не ладьями). Каждая занятое поле определяется числом -1.
    Необходимо определить минимальное количество:
    1. белых ладей, которое необходимо расставить на доске, чтобы при постановке черной фигуры в любое оставшееся свободное поле она может быть сбита одной из ладей за некоторое количество ходов;
    2. белых слонов.
22. Имеется шахматная доска. Некоторые поля не ней запрещены для белых ладей (на это поле ладья не может сделать ход). Каждая такое поле определяется числом -1.
    Необходимо определить минимальное количество белых ладей, которое необходимо расставить на доске, чтобы при постановке черной фигуры в любое оставшееся свободное поле она может быть сбита одной из ладей за некоторое количество ходов.
23. Имеется шахматная доска. Некоторые поля не ней заняты белыми фигурами и пешками. Каждая занятое поле определяется числом -1.
    Используя стек, необходимо определить маршрут белого коня с поля (Х₁,У₁) на поле (Х₂,У₂).