Занятие №6. Задачи на анализ таблиц.

Теория: Лекция                            [Все занятия]

Практика:                                 [Официальная страница]

Учебные задачи:
   Задача А.
   [Побочная диагональ]
Хорошая незатейливая задача =) 
   Задача В.
   [Шахматная доска]
Т.к. изначально сказано, что область является связной, то нет необходимости писать поиск в глубину(лишний расход памяти на рекурсию) или поиск в ширину(просто дольше писать). Достаточно перебрать 64 клетки поля и определить периметр, просмотрев все соседние клетки. В этой задаче не лишним будет обнести всё поле границей фиктивными клетками, чтобы не писать дополнительные проверки на выход за пределы шахматной доски.
   Задача С.
   [Поворот]
Если бы требовалось в результате программы получить матрицу, то предложенное решение требует дополнительно O(N*N) памяти. Можно придумать решение, в котором все манипуляции происходят на исходной матрице. Для этого вычленяем 4 угловые клетки и делаем их циклический сдвиг. Последовательно перебираем все возможные такие четверки и получаем ответ. Учитывая небольшие ограничения, данное решение не приводится.
Олимпиадные задачи:
  Задача А.
   [Сапер]
Классика жанра. Опять же очень удачной мыслью будет обнести поле фиктивными клетками, чтобы отдельно не проверять случай выхода за границы поля. 
  Задача В.
   [Игра с фишками]
Очень хорошая задача, чтобы попрактиковаться в реализации BFS на таблицах. В данной задаче я не обносил матрицу фиктивными элементами. Вместо этого использовалась функция correct(int x, int y) для проверки выхода за пределы игрового поля. 
   Задача С.
   [Вырезание фигуры]
Можно хранить всю матрицу целиком, а связные области находить BFS’ом. Но можно поступить более изящно. Можно искать углы фигуры. По условию сказано, что фигуры не пересекаются и не соприкасаются углами или сторонами, следовательно можно выделить двоичные маски углов, а именно:
0|1   1|0   1 1    1 1
1 1   1 1   0|1    1|0   - являются битовыми масками внешних углов(OUT) вырезанной фигуры.

также существуют внутренние углы(IN) фигуры. Битовые маски внутренних углов фигуры получаются инверсией битовых масок внешних углов. Показателен тот факт, что для любой вырезанной фигуры верна формула: OUT – IN = 4.
Дополнительные олимпиадные задачи:
  Задача А.
   [Восстанови многоугольник]
Лучше разбор наверное не придумать: [Автор: Владимир Гуровиц]
   Задача В.
   [Электронные часы]
Казалось бы несложная задача. Но здесь есть пара подводных камней. В частности количество часов может получиться больше 23, а количество минут больше 59. Эти две ситуации нужно корректно обработать. Я это сделал таким образом:
1) 4 списка возможных значений на каждое цифровое поле часов.
2) Получил все возможные комбинации часов перебрав все допустимые пары первой и второй цифры.
3) Получил все возможные комбинации минут перебрав все допустимые пары третьей и четвертой цифры
4) Отсеял все невалидные значения часов и минут.
Если хотя бы один из списков пуст, значит произошла ошибка. Выводим ERROR
Если хотя бы в одном списке больше 1 элемента, значит возможна двоякая интерпретация. Выводим AMBIGUITY.
В противном случае в каждом списке по одному элементу, т.е. удалось однозначно установить время. Выводим его. B здесь нас ждет еще один подводный камень. Нужно не забыть про ведущие нули.
   Задача С.
   [Историки и археологи]
Если присмотреться, то можно заметить, что процедура переселения представляет собой обычное транспонирование подматрицы. В результате чего происходит реверс элементов относительно главной диагонали. Вот собственно и на этом будет строиться наше решение. Для начала условимся, что будем приводить первую матрицу ко второй последовательно, подиагонально. Диагонали будем перебирать слева-направо, сверху-вниз, т.е. первая диагональ будет состоять из одного элемент (0,0), вторая диагональ из двух – (1,0) и (1,0) и т.д. Транспонирование нужно выполнять осторожно. Если в качестве подматрицы выбрать матрицу размером большим, чем 2*2, то произойдут обмены элементов прошедших и уже упорядоченных диагоналей. Поэтому в качестве подматрицы будем использовать только матрицы размером 2*2. А транспонирование подматрицы будет идентично реверсу побочной диагонали, или обмену двух соседних элементов текущей диагонали. При упорядочивании диагонали будем использовать принцип аналогичный сортировки пузырьком.

Занятие №5. STL

Теория: Лекция                                           [Все занятия]

Практика:                                                [Официальная страница]

Учебные задачи:
   Задача A.
   [Сортировка]
На этой задаче можно тестировать корректность работы “быстрых” сортировок.
   Задача B.
   [Хеширование с удалением]
На момент 26Sep2011 15:59 данная реализация получала RE на 8 тесте. Верное решение 2-х летней давности получала тот же вердикт. Проблема связана с нехваткой памяти, вызванное переходом на 64 битную версию линукса, стоящего на сервере проверяющей системы. 
Эту задачу можно сдать с текущими ограничениями с помощью хеширования(алгоритм Рабина-Карпа) или с помощью построения дерева(алгоритм Ахо-Корасик), но т.к. данная задача предусматривалась в рамках учебных задач на STL, то условимся, что решение с использованием set нас полностью устраивает.
   Задача С. 
   [Двоичный поиск]
А на этой задаче можно тестировать рукописную дихотомию.
Олимпиадные задачи:
   Задача A.
   [Сплоченная команда]
Решение получилось прям очень STL’вским) Сначала сортируем игроком по их ПП. Далее последовательно перебираем пары двух игроков G1 и G2, стоящих рядом. Сумма их ПП определяет значение ПП максимального игрока G3 в команде. G3<=G1+G2. Чтобы найти позицию игрока G3 максимально удовлетворяющему игрокам G1 и G2 можно воспользоваться функцией upper_bound на отсортированном массиве игроков. Чтобы найти сумму игроков в команде за O(1), можно заранее сделать подсчет интервальных подсумм. 
   Задача B.
   [Древние цивилизации] Ответ за O(NlogN): multiset
Написал небольшого монстрика, который сильно перегружен STL. Но зато я впервые попользовался обратными итераторами (reverse_iterator). Восстановление ответа использует multiset. Это связано с компаратором. На самом деле основная идея лучше реализована в исходнике двух летней давности, который находится ниже. Там восстановление ответа написано тоже за O(NlogN), но константа будет меньше. Этот исходник выкладываю исключительно для себя, чтобы в следующий раз такого не делать).
   [Древние цивилизации] Ответ за O(N)
Самая адекватная реализации данной задачи. Очередной пример того, что не надо нагружать программу красивыми фенечками, вместо того, чтобы немного подумать. Можно заметить, что нужный интервал будет образовываться между двумя соседними историческими событиями. Под историческим событием я понимаю либо зарождение, либо гибель одной из цивилизаций. При этом левой границей интервала будет зарождение, а правой – гибель цивилизации. Крайний случай будет если нужный интервал совпадает с периодом одной из цивилизации (назовем ее цивилизации A). В крайнем случае нужно найти вторую цивилизацию, которая существовала до цивилизации A а погибла после. Это можно сделать за O(N).
   [Древние цивилизации] Ответ за O(NlogN): set [25Nov2009]
Данное решение выкладываю тоже исключительно для себя. Логарифм в сложности вылезает из-за крайнего случая, описанного во втором решении. Я пытался сразу обрабатывать крайний случай для поиска второй цивилизации. Это приводило к тому, что все зародившиеся множества клались в множество, а при гибели они из этого множества удалялись. Как известно каждая операция выполняется за O(logN).
   Задача С.
   [Число]
Идентичная задача была на ACM ICPC Subregional Contest 2007 в Саратове. Вот она на сервере acm.sgu.ru. Приятно вспомнить, что тогда мы ее зачли). Спасибо Роману и Рамилю. 
Дополнительные олимпиадные задачи:
   Задача A.
   [Современники]
Задача на сканирующую линию. Создаем массив из дат. Для каждой даты храним метку, является ли она началом периода или концом. В качестве даты нужно добавлять день [18-летия](начало) и день [80-летия – 1 день](конец). Небольшая сложность состоит в подсчете даты [80-летия – 1 день]. Для этого нужно аккуратно выписать количество дней в месяцах и не забыть обработать случай високосного года.
   Задача B.
   [Контрольная по ударениям]
Задача на быстрое нахождение слова в словаре. По ходу решения удобно завести два множества. В первом будем хранить слова с ударением, а во втором – те же слова в нижнем регистре для определения наличия слова без проверки на ударение.
   Задача С.
   [Умный чертежник] Сложное решение =)
По условию задачи робот не может проехать по нарисованной ранее линии. Можно представить перемещения работа в виде графа. Этот граф будет представлен либо Эйлеровым путем, либо Эйлеровым циклом(справка). Следовательно либо все степени вершин графа являются четными(Эйлеров цикл), либо 2 вершины имеют нечетную степень,а все остальные четную(Эйлеров путь). Также отметим, что граф является связным. Суть данного решения заключается в том, что мы двигаемся по исходному графу как захотим. Во время движения не меняем направления только в том случае, если этого сделать нельзя. Т.е. избегаем комбинаций в маршруте типа “EE”, “WWW” и подобных, если это возможно. Такая тактика приведет к тому, что все вершины с нечетными степенями будут содержаться в нашем пути. Но может возникнуть ситуация, когда некоторые вершины будут не использованы в маршруте. Неиспользованные вершины будут образовывать конечное количество циклов. Чтобы все неиспользованные циклы добавить в ответ нужно найти место в ответе, куда нужно их вставить. Эту операцию можно сделать путем пересечения множеств использованных и неиспользованных вершин. Вершина считается использованной, если не осталось неиспользованных ребер, исходящих из нее. Поясним более наглядно вышесказанное.
Исходный путь: NNWSEE
Первоначальный путь: NE
В результате остался неиспользованный цикл WNES. Его нужно вставить после первого шага. В итоге получаем ответ: NWNESE
   [Умный чертежник] Простое решение !
Предыдущее решение было не очень продуманным в плане простоты реализации. Если подумать, можно заметить, что если робот наткнулся на самопересечение в точке P, то нужно двигаться в обратную сторону между двумя попаданиями в точку P в рамках первоначального пути. Важно учесть, что после такого “реверса” пути заново пройти весь путь с первоначального попадания в точку P, чтобы проверить наличие самопересечений последующего пути с “реверснутым” подпутем.

Занятие №4. Алгоритмы сортировки

Теория: Лекция                                                                                           [Все занятия]

Практика:                                         [Официальная страница]
Учебные задачи:
   Задача A. 
   [Пузырьковая сортировка: количество обменов]
   Классическая задача на пузырек. 
   Задача B.  
   [Разные]
   Еще одна классическая задача, для которой нужно применить квазилинейную сортировку. 
   Задача С. 
   [Объединение последовательностей]
   Задача на слияние двух отсортированных массивов. 
Олимпиадные задачи:
   Задача A. 
   [Ожерелье]  
   Довольно занятная задача. Пришлось подумать. Пока думал настрогал прожку, которая bfs’ом находит оптимальную стратегию. Только после этого решение стало очевидно).
   Задача B.
   [Головоломка] 
  Очень любопытная задача. Интересно всегда наблюдать за тем, как люди(и я в том числе) пишут симулятор разгадывания головоломки с помощью DFS или BFS, а потом с криками матерного содержания переписывают решение за 3 минуты и получают законные Accepted.  
  Задача С. 
  [НГУ-стройка]
  Задача кажется с первого взгляда неприступной. Но если хорошенько присмотреться, то все не так страшно. Первое что нужно понять, как будет выглядеть сечение блоков, если зафиксировать конкретное значение Z. Это будет набор взаимно непересекающихся прямоугольников. Чтобы проверить покрывают ли эти прямоугольники всю область достаточно найти сумму их площадей. Общая идея решения изложена в лекции п.9. Сканирующая прямая.
Дополнительные олимпиадные задачи:
   Задача A.  
   [Эльфы и олени] 
   Одна из тех задач, где жадность приводит к правильному ответу. Сортируем в порядке неубывания массив эльфов и оленей. Бинарным поиском подбираем K - количество оленей, которые попадут в упряжку. Чтобы проверить можно ли запрячь K оленей применяем следующую эвристику. Выбираем K минимальных эльфов и K максимальных. Группируем этих 2K эльфов по парам, чтобы обеспечить максимальное покрытие диапазона, которые занимают эльфы. Получаем: (1, N – K + 1), (2, N – K + 2) и т.д., где N – количество эльфов. С учетом выбранных пар утверждаем, что никакое другое деление на пары не увеличит количество оленей в ответе. Далее необходимо фиксировать выбранную пару эльфов и искать для него минимально возможного оленя.
Приведенное решения полностью идентично разбору Александра Чистякова с одним отличием, что для фиксированной пары эльфов можно находить оленя за O(logM) с помощью функции lower_bound, а не за O(M).
   Задача B.
   [Субботник]
   Сортируем человечков по росту. Бинарным поиском по ответу подбираем ответ на задачу, а именно наименьшее возможное значение максимального числа неудобства. Для того, чтобы проверить корректность выбранного ответа последовательно перебираем слева направо группы из подряд идущих С человечков. Считаем количество групп, которые удовлетворяют выбранному ответу. Если их количество не меньше заявленного в условии R, то выбранный ответ является корректным. Такая жадность дает корректный ответ.
   Задача С.
   [Палиндром]
   Довольно простая задача на сортировку подсчетом.

Занятие №3. Алгоритмы поиска в олимпиадных задачах

Теория: Лекция                                             [Все занятия]

Лекция шикарная. Особо понравилось описание “бинарного поиска по ответу”. Также произвел впечатление описанный подход с выявлением радиоактивного шарика и нахождения фальшивой монеты.

Практика:                                         [Официальная страница]
Учебные задачи: 
   Задача A. 
   [Номер максимального элемента]
   Классика жанра. Даже не знаю, что еще можно добавить.  
   Задача B. 
   [Сложность двоичного поиска]
   Суть задачи сводится к нахождению значения log(n) по основанию 2, округленного в большую сторону.
   Задача С. 
   [Двоичный поиск]
   Классическая задача на проверку корректной реализации на бинарный поиск. Базовую реализацию и частные случаи бинарного поиска мы уже рассматривали ранее в этом посте. 
Олимпиадные задачи: 
   Задача A. 
   [Забавный конфуз]
   Задача на умение работать с одномерным массивом. 
   Задача B. 
   [Черепаха]
   Решение полностью соответствует авторскому разбору. Главное в задаче выделить монотонную функцию, применив затем к ней бинарный поиск для нахождения корней. Хороший пример, иллюстрирующий подход бинарного поиска по ответу.
   Задача С.
   [Очень легкая задача]
   Казалось бы задача, как задача. И даже разбор полный дан в лекции и сама по себе задача несложная. Но есть в ней один интересный момент. Перед дихотомией нужно чем то инициализировать верхнюю границу подбираемого значения. В первом своем решение я взял n*max(x,y), т.е. печатаем все страницы на самом медленном принтере. С типами все в порядке. B вдруг получаем TLE на последнем тесте. В исходнике двухлетней давности я взял в качестве этого параметра n*min(x,y). Казалось бы какая разница? Но старое решение заходит, а новое нет. Отмечу, что вычисления идут в интах.
Рассмотрим граничный тест: 2e8 10 9.
Инициализация:   l = 0;       r = 1.8e9
Первая итерация: l = 0.9e9+1; r = 1.8e9
Вторая итерация: l + r = 2.7e9 – Переполнение типа.
В итоге середина сойдется к числу меньшему 1e9. В старом решении не происходило переполнения типа только потому что после первой итерации дихотомии правая граница становилась 1e9 и в дальнейшем переполнение исключалось.
Такие случаи конечно нужно просчитывать предварительно, но чтобы спать спокойно сейчас я решил ее в long long’ах =)
Дополнительные олимпиадные задачи:
   Задача A. 
   [Медиана объединения] merge 
   С ходу можно предложить слияние двух массив в один отсортированный. Сложность merge O(N)
   [Медиана объединения] kth_element
   Также данную задачу можно решить с помощью нахождения k-ой порядковой статистики. Данный алгоритм имеет ту же линейную сложность, что и первое решение, но константа будет больше, т.к. имеют место копирование двух подмассивов в один.
   Задача B. 
   [Столица]
   Умение находить k-ую порядковую статистику в этой задаче может ускорить решение, но ограничения позволяют сделать полную сортировку. 
   Задача С.
   [Выборы]
  Шикарная задача. Суть задачи сводится к нахождению стоимости политической партии. Для каждой партии бинарным поиском подбираем количество голосов, которые необходимо набрать этой партии для победы. Далее с помощью функции lower_bound проверяем корректность выбранного количества голосов. В итоге имеем 2 сортировки, 2 бинсерча + очевидное ДП.

Занятие №2. Битовые операции и структуры данных

Теория: Лекция                                             [Все занятия]

В очень компактной форме было затронуто большое количество тем.
Очень понравилась реализация битового вектора и механизм отыскания элемента массива, встречающегося нечетное количество раз =)

Практика:                                         [Официальная страница]
Учебные задачи: 
   Задача A.
   [Стек неограниченного размера] 
   Полезная задача. Т.к в условии сказано, что стек потенциально может занимать всю оперативную память, то лучшего его делать на основе односвязного списка, чтобы не получить RE на первых посылках. Но эта реализация будет расходовать в 3 раза больше памяти. Чтобы минимизировать расходы на память удачным решением является односвязный список массивов.
   Задача B.
   [Очередь неограниченного размера]
   Не менее полезная задача. Здесь дело приходится иметь уже с двусвязным списком. Необходимо внимательно рассмотреть случай, когда очередь становится пустой и возникает команда push.
   Задача С.
   [2^n+2^m]
   Задача на базовое понимание битовой арифметики. 
Олимпиадные задачи: 
   Задача A.
   [Забавная игра]
   Несложная задача. Нужно постараться сделать ее, не раскладывая число в двоичное представление. 
   Задача B.
   [Сортировка вагонов]
   Задача на понимание работы стека и умение его использовать в нестандартных ситуациях. Решение имеет сложность O(N). Во время решения пришла идея на проверку возможности сортировки входных данных предложенным способом, основанная на дереве Фенвика. Но в этом случае сложность становится O(NlogN), что делают эту идею бесперспективной на будущее. 
   Задача С.
   [Тупики]
   Шикарная задача на кучи. Из-за того, что по условию лошадиные размеры массивов, и то что они объявлены не глобально пришлось расширять размер системного стека. В реализации используется самописная структура данных “Куча” для int’ов(а надо было основанную на шаблонах), но по ходу решения еще нужно было использовать кучу для пары элементов, поэтому для них использовался STL аналог кучи priority_queue, который работает несколько медленнее рукописного варианта. Но как видим самописная куча и priority_queue имеют одинаковый набор функций + одинаковую сложность функций.
Дополнительные олимпиадные задачи:
   Задача A.
   [Strategy tetris] 2009 Edition
   [Strategy tetris] 2011 Edition
   Еще одна очень хорошая задача на применение кучи. Здесь привожу два решения, потому что показалось, что решение 2009 года получилось понятней =). Обрабатываем фигуры в порядке возрастания значения левой границы. На каждой итерации пытаемся вставить фигуру на такой уровень, на котором правая граница самого правого элемента меньше левой границы текущей фигуры. Если такого сделать не получается, то формируем новый уровень.
   Задача B.
   [Конвейер]
   Повторение – мать учения. Немного усложненный вариант задачи “B. Сортировка вагонов”. В сущности можно обойтись одним стеком + грамотно реализовать сравнение даблов. 
   Задача С.
   [Трехмерные ладьи]
   Хорошая такая задача. Правда далась она мне тяжеловато. Для начала нужно свести куб к трем проекциям: XY, YZ, XZ. Сами проекции можно представить в виде матриц размером N*N. Если имеем ладью с координатами a,b,c, тогда метим прямые XY[a][b], YZ[b][c], XZ[a][c], как прямые, не содержащие ответ на задачу. Тогда задача сводится к нахождению коэффициентов x,y,z таких что XY[x][y] == YZ[y][z] == XZ[x][z] == false (не помеченных). При таком раскладе получаем кубическое решение, которое не зайдет по времени.
Следует модерниризировать матрицы таким образом:
bool XY[N][N]
int  YZ[N][N/32]
int  XZ[N][N/32].
При таком раскладе мы можем при фиксированных x и y быстрее находить нужный z, а именно обрабатывать группу из 32 элементов, прибегнув к битовой арифметике.
Значение YZ[y][z] | XZ[x][z] в двоичном представлении должно состоять только из единиц. Если же это не так и XY[x][y] == false, значит мы нашли клетку, которая не бьется.

Занятие №1. Арифметика и теория чисел [Густокашин]

Теория: Лекция                                                  [Все занятия]

Лекция является вводной, но все равно много интересного можно оттуда почерпнуть. В частности:
1) Нахождения НОД’а длинных чисел на основе формул:
gcd(2a, 2b)     = 2gcd(a,b)
gcd(2a, 2b+1)   = gcd(a,2b+1)
gcd(2a+1, 2b+1) = gcd(2(a-b),2b+1)
Хорошие формулы, уменьшающие накладные расходы. Осталось их только запомнить =)

2) Умножение двух матриц с предварительным транспонированием второй.

Практика:                                              [Официальная страница]
Учебные задачи
  Задача A. 
   [A-B]
   Такие задачи мы уже решали раньше в рамках темы Длинная арифметика.
   Задача B.
   [Целые точки отрезка]
   Если отрезок не параллелен осям координат, то достраиваем его до прямоугольного треугольника, где этот отрезок является гипотенузой, а катеты параллельны осям координат. После чего можно выйти на следующую формулу:
gcd(A,B) + 1, где A и B катеты прямоугольного треугольника. Стоит отметить тот факт, что формула работает и в том случае, если отрезок параллелен любой из оси координат.
   Задача С.
   [Разложение на простые]
   Сложность O(sqrt(N)). Можно смело ввести одну оптимизацию. Стоит заметить, что в строке 34 каждый раз пересчитывается верхняя граница внешнего цикла.
Олимпиадные задачи
  Задача А. 
   [Представление чисел]
   Рассуждаем. N = A + B. При этом нужно максимизировать gcd(A,B). 
A = a * gcd(A,B) 
B = b * gcd(A,B)
=> N = gcd(A,B) * (a + b). Главный вывод в том, что N делится на gcd(A,B) без остатка. Если мы хотим максимизировать gcd(A,B), зная N, то необходимо мизировать (a+b). Следовательно (a+b) – минимальный множитель N, отличный от 1.
Неплохо =). Теперь мы можем найти максимальный gcd(A,B) для любого N. Подумаем как найти сами числа A и B. A = a * gcd(A,B); B = b * gcd(A,B). Но мы не знаем a и b, а знаем только их сумму. Какие же a и b нужно выбрать? Думаем.
Ответ: любые натуральные.
Обратимся к примерам: 
    1) N = 16. a + b = 2. gcd(A,B) = 8. Следовательно a = 1 и b = 1, поэтому A и B определяются однозначно.
    2) N = 35. a + b = 5. gcd(A,B) = 7. Здесь может быть несколько случаев:
a = 1, b = 4;
a = 2, b = 3;
a = 3, b = 2;
a = 4, b = 1;
Понятно, что последние два случая являются зеркальным отображением первых двух, поэтому можно рассматривать только первые два случая. Как видно не важно какой из них мы выберем в качестве ответа. Для того, чтобы не плодить лишние if’ы можно a всегда брать 1. 
    3) N = 17. a + b = 17. gcd(A,B) = 1. В данном случае можно брать любое разложение числа N на слогаемые.
   Задача В.
   [Кинотеатр]
   Судя по ограничениям обычное моделирование ситуации не канает. Начинаем думать. Ко мне решение пришло, когда я нарисовал оба случая для случая n=5,m=7. После чего появились следующие выводы:
1)  Все элементы, которые останутся на своих местах будут находится на виртуальной главной диагонали матрицы.
2) Задача сводится к задаче B из первого блока учебных задач.
   Задача С.
   [Степень]
   Для начала разобьем исходное число А на простые множители в формате, представленном в лекции. Например число 12:
osn  = {2,3}
step = {2,1}, т.е. 12 = 2^2 + 3^1.
Очевидно, что каждый просто множитель из числа A должен входить как минимум один раз в число N. Но не факт, что получившееся число N будет удовлетворять требованиям задачи. Например для такого числа A:
osn  = {2,3}
step = {19,1}
Как быть? Необходимо увеличить число N в минимальное число раз, так чтобы оно удовлетворяло условию задачи.
Дополнительные олимпиадные задачи
   Задача А.
   [Марсианские факториалы]
   Для решения этой задачи сначала можно рассмотреть более простой случай. Будем искать ответ пока только для основания системы счисления = 10. Понятно, что ноль в конце факториала получится, если в разложении факториала на простые множители найдутся 2 и 5. При этом общее количество нулей будет равно количеству 5-ок в разложении факториала на простые множители.
Рассмотрим пример: N = 128. Сколько нулей будет в конце N! ?
Переберем все числа кратные 5, которые не превышают N:
5, 10, 15, 20, 25, 30, … , 120, 125 – всего N/5.
Как можно заметить в этом ряду есть числа, которые в своем разложении имеют несколько 5. Найдем все числа, которые имеют в своем разложении две пятерки:
25, 50, 75, 100, 125 – всего N/25.
Затем найдем числа, которые имеют 3 пятерки в своем разложении:
125 – всего N/125
Сложив количество элементов в этих трех рядах, мы найдем ответ на поставленный вопрос.
Как быть в случае, когда основания системы счисления отлична от 10. 0 в конце числа появится, если в его разложении на простые множители найдутся все простые множители из разложения основания системы счисления. Так например для основания 6(2*3) число 100! будет иметь 48 нулей, потому что 100! содержит 97 двоек и 48 троек. Все вычисления можно проводить в 10-ой системе счисления.
Тонким моментом является ситуация, когда основание системы счисления в своем разложении имеет несколько одинаковых множителей. Например найдем 1000! для osn = 72 = (2^3 * 3^2)
В разложении 1000! имеется 994 двойки и 498 троек. Количество же нулей в конце будет 249.
   Задача В.
   [Скорая помощь]
   Задача на углубленное понимание операций целочисленного деления и взятия остатка от деления. Перебираем количество квартир(от 1 до 1000) на одном этаже и в совокупности с параметрами K2,P2 и N2 определяем корректность перебираемого значения. Если после перебора выяснится, что только одно значение количества этажей являлось корректным, то значит входные данные оказались непротиворечивыми. Т.е. параметры N1 и P1 определяются однозначно. Если же не удалось подобрать количество квартир на одном этаже, либо N2>M, то значит решений нет. Если в качестве количества квартир на одном этаже подошло более одного значения, тогда определяем насколько однозначно можно определить параметры N1 и P1, согласно условию задачи.
   Задача С.
   [Проверьте равенство]
   Кромоздкая задача, в которой помимо того, что нужно реализовывать длинную арифметику, так еще и учесть целую череду частных случаев. Особое внимание к:
0^0 и 0^-1. В решении можно реализовать деление длинного на длинное, а можно этого не делать, если немного подумать.

Очно-заочный кружок [Михаил Густокашин]

Начинаем плавное и методичное прорешивание задач из этого сборника. Стоит отметить качественную подборку задач по тематикам и уровню сложности. Материалы кружка доступны на сайте informatics.mccme.ru.

Занятие №1. Арифметика и теория чисел                          [20Apr2011]
Занятие №2. Битовые операции и структуры данных                [15May2011]
Занятие №3. Алгоритмы поиска в олимпиадных задачах             [22Sep2011] 
Занятие №4. Алгоритмы сортировки                               [25Sep2011]
Занятие №5. STL                                                [03Oct2011]
Занятие №6. Задачи на анализ таблиц                            [14Oct2011]
Занятие №7. ДП с одним параметром                              [23Oct2011]
Занятие №8. ДП с двумя и более параметрами                     [28Oct2011]
Занятие №9. Методы тестирования задач                          [01Nov2011]

P.S: Очень надеюсь, что список тренировок будет продолжен =)