Учебная задача A "Стек неограниченного размера"
Операции работы со стеком описаны в разделе 2 лекции 2. Для того, чтобы сделать все это неограниченным, нужно было воспользоваться динамически расширяемым массивом или списком. Или прикинуть, что во всех задачах стандартное ограничение 1-2 секунды, значит 10 мегабайт теоретически верхний предел размера входных данный. А значит, "неограниченный" размер равен максимум 2-м миллионам.
Учебная задача B "Очередь неограниченного размера"
Решение задачи полностью аналогично предыдущей. Только стек следует заменить очередью.
Учебная задача C "2^n + 2^m"
Сдвиг на k бит влево эквивалентен умножению числа на 2^k. Следовательно, можно было написать следующие команды:
j = 1;
ans = j << n + j << m;
На паскале:
j := 1;
ans := j shl n + j shl m;
Олимпиадная задача A "Забавная игра"
Нам необходимо перебрать все числа, длиной k бит, получаемых из заданного циклическим сдвигом и выбрать среди них максимальное. Сначала необходимо определить длину числа в битах, вернее, найдем минимальную степень двойки, превосходящую наше число (число с единственной 1 в записи с k нулями после нее). Сделать это очень просто: будем сдвигать 1 на 1 бит влево до тех пор, пока число меньше заданного N.
Несложно заметить, что в результате k применений циклического сдвига влево мы получим те же числа, что и при k сдвигах вправо. Циклический сдвиг влево реализуется так: сдвигаем число N на один бит влево. Если она стало больше или равно 2^k, то это означает, что оно "вылезло" из своих k бит. Тогда отнимаем от N 2^k и прибавляем 1 (переносим вылезшую единицу в конец числа). Операцию нужно повторить k раз и просто выбрать из всех чисел максимальное.
Олимпиадная задача B "Сортировка вагонов"
Несложно понять, что тупик представляет собой стек. Каждый шаг будет состоять из двух действий:
1) загнать один вагон в стек
2) выгонять вагоны из стека, если на вершине стека стоит вагон, который должен быть загнан.
Удобнее всего завести переменную, которая обозначает количество загнанных вагонов (K = 0 в начале работы программы). Пока стек не пуст и на вершине стека стоит вагон с номером K+1 выгоняем его на путь 2 (убираем из стека) и K прибавляем 1. Если в конце работы программы стек не пуст, то осуществить сортировку вагонов невозможно.
Для вывода ответа необходимо было создать массив, в котором при каждом действии сохранять команду, которая была осуществлена. В качестве второго параметра всегда можно было указывать 1 (т.е. каждое действие совершать над одним вагоном) - это облегчает программирование.
Подробный разбор можно прочитать по ссылке: http://olympiads.ru/moscow/2008/team/problems/wagons_razbor.pdf
Олимпиадная задача C "Тупики"
Нам необходимо упорядочить события (приезды и отъезды электричек). Поскольку формально сортировать мы не умеем, то воспользуемся кучей. Куча минимумов будет состоять из структур, содержащих три поля: время события (ключ, по которому строится куча); номер электрички, с которой произошло событие; и признак события (приезд или отъезд).
Кроме того, заведем кучу (минимумов) свободных тупиков. Сначала добавим туда все тупики.
Затем пойдем по событиям. Если событие - приезд электрички, то необходимо взять из кучи свободных тупиков минимальный тупик и сохранить для этой электрички номер тупика, в который она встанет (это удобно делать в массиве, где индекс равен номеру электрички). Если же куча свободных тупиков пуста, то сразу выводим, что расставить электрички нельзя.
Если событие - объезд электрички, то смотрим, какой тупик она занимала и добавляем этот тупик в кучу свободных тупиков.
Для вывода ответа необходимо просто вывести содержимое массива, в котором сохранялись номера тупиков при приезде электрички.
Дополнительная олимпиадная задача A "Strategy tetris"
Упорядочим фигуры по левой координате (с помощью кучи минимумов). Также заведем кучу уровней (которая в начале пуста), в которой для каждого уровня будет хранится номер последней занятой клетки (заполнятся уровни будут слева направо).
При обработке очередной фигуры будем брать из кучи уровней минимум и если он оказался меньше, чем левая граница фигуры, то добавляем фигуру в этот уровень (т.е. удаляем уровень из кучи и добавляем в кучу уровень, с правой границей, равной правой границе добавленной фигуры. Если же условие оказалось не выполненным, то просто создаем новый уровень с правой границей, равной правой границе фигуры.
Для восстановления ответа необходимо для каждого уровня выделять уникальный номер (т.е. в куче уровней хранить не только правую границу, но и номер уровня, а при создании нового уровня выделять ему очередное число). Для каждой фигуры необходимо сохранять номер уровня, в который она попадает. В конце необходимо вывести сначала все фигуры первого уровня, затем второго и т.д. Вообще говоря, порядок вывода уровней не важен, главное, чтобы фигуры одного уровня были выведены последовательно. Реализовать быстрый вывод можно с помощью опять же кучи минимумов, где ключом будет выступать номер уровня, а вторым элементом структуры - номер фигуры.
Подробный разбор задачи можно прочитать в книге "Московские олимпиады по информатике" на страницах 181-183.
Дополнительная олимпиадная задача B "Конвейер"
Эта задача очень похожа на задачу "Сортировка вагонов". Опять же здесь есть стек-накопитель, но немного изменено условие удаление элемента из стека. Если в задаче "Сортировка вагонов" номер вагона должен был на 1 превышать количество успешно загнанных вагонов, то в этой задаче необходимо было организовать кучу минимумов, в которую поместить все срочности. Если элемент на вершине стека равен элементу на вершине кучи, то удаляем элемент из стека и из кучи. Сохранения ответа в этой задаче не требовалось, так что нужно было проверить был ли стек пуст или нет в конце обработки последовательности.
Дополнительная олимпиадная задача C "Трехмерные ладьи"
Автор задачи и разбора – А.Шестимеров
Построим три проекции расстановки ладей на грани куба. Тогда, фиксированная клетка (x,y,z)
бьется хотя бы одной ладьей, если какая-то из ладей бьет хотя бы одну из клеток (x,y), (y,z), (x,z)
на соответствующих проекциях. Таким образом, проверку одной клетки можно организовать за
O(1).
for x:=1 to n do
for y:=1 to n do
for z:=1 to n do
if (xy[x,y]=0)and (zy[z,y]=0) and (xz[x,z]=0) then // …. нашли небьющуюся клетку.
Но такое решение работает за время N^3 и при заданных ограничениях на N не проходит повремени. Чтобы оптимизировать решение, можно использовать битовые операции, тогда за одну
операцию мы проверим сразу несколько клеток (например, 32 или 64):
for y:=1 to n do
for z:=1 to n do
if yz[y,z]=0 then
for k:=1 to n div 64 do
if (yx[y,k] or zx[z,k])<>264-1 then // … группу клеток, в которых есть небьющиеся.
Тогда время работы будет N^3/64 или для максимального N порядка 10^7.