Тренировка #15 [Меньшиков]

[Условия задач]                   [Список тренировок]

15A. Игра с калькулятором
[calcgame]
Пожалуй самая сложная задача на тему последовательности в данном задачнике. Самый интересный момент – это как определить, что нужно выводить “Impossible”. Один из подходов – искать решение, пока позволяет TLE, и если такого ответа не найдено за отведенное время, то считаем, что решений нет. Как показывает практика, если асимптотика решения допустимая, то такой подход “канает”. Но все равно остается чувство сомнения и неуверенности. Вот чтобы такого чувства не было, сводим решение к поиску остатков от деления. Решение соответствует первому разбору на эту задачу.
15B. Площадь треугольника
[tria-abm]
Очень интересная задача. Немножко поколдовав сводим решение к бинарному поиску по ответу.
15C. Формирование поезда
[train-ab]
Пожалуй самая сложная задача на ДП, если пытаться решить способом, который предложил Никита Рыбак. Это способ, в котором все ответы на подзадачи для заданной длины храним в матрице [40][40][2].
15D. Стена
[wall]
Очередная задача на выпуклую оболочку. В предложенной реализации был использован алгоритм Грехема-Эндрю. Реализация самого алгоритма, была взята здесь. Она потрясла меня своей лаконичностью.
15E. Семечки
[seeds]
Признаюсь долго придумывал решение. Хотя задача по хорошему вообще несложная. И отсечение перебора довольно легко придумать.
15F. Умножение многочленов
[polymul]
Такие задачи для нас уже не должны представлять серьезной угрозы =).

[Все решения]

P.S: 17 января 2011 года в 02:43:58 по серверному времени была зачтена последняя нерешенная задача. Ну чтож, СПАСИБО автору за столь шикарный задачник.

Тренировка #14 [Меньшиков]

[Условия задач]                   [Список тренировок]

14A. Марковский цикл
[markovc]
Довольно интересная задача. Во-первых нужно придумать механизм быстрого перебора всех подстрок заданной длины. Лобовой алго за O(N*N) не принимается. Следует подумать как это можно сделать за O(N). Один из самых распространённых методов по решению этой подзадачи – это использование хэш-функции. Дело облегчается тем, что длина максимальной строки не превышает 12, а сама строка состоит из алфавита {A,B,C}. Следовательно любую строку такого вида можно закодировать числом <= 3^12 = 531441.
14B. Д-44
[d44]
Необычная задача. Нужно вспомнить все формулы по физике на тему “бросание тела под углом к горизонту”. Затем промоделировать движение, фиксирую только некоторые дискретные моменты времени и рассчитать в них параметры тела(например проекцию стрости на ось OX и OY). Некоторую сложность может вызвать поиск коэффициента сопротивления воздуха(k). В авторском разборе предлагается это сделать “ручками”. Признаюсь, еле хватило терпения сделать это.  В первую очередь это связано с тем, что в проверяющей системе нужно подобрать такой k, чтобы результирующая длина совпадала вплоть до метра, вместо заявленной погрешности в 10 метров.
14C. Упаковка символов
[folding]
Я очень хорошо помню, когда я был зеленым студентом, какой ужас наводила на меня эта задача. Казалось, что ее может сделать только Петр Митричев. Конечно и сейчас решение представляется каким-то волшебством, но мы уже многому научились за прошлые тренировки и думаю сделаем ее, немного подумав. Как и прошлые задачи на двумерное ДП, эту задачу решаем интервально, постепенно увеличивая интервал до длины исходной строки. Ответ восстанавливаем по аналогичной схеме, как в 13С.
14D. Пирамиды
[pyramids]
Первое мое решение было очень тяжеловесным, но корректным. Опишу его вкратце: на плоскость OXY кладем треугольник ABC. A=(0,0), B= (AB,0). Координаты точки С можно вычислить. Точка D находилась над плоскостью OXY, т.е. Zd>0. Затем нужно было найти проекцию точки D на плоскость OXY. Эта задача сводилась в нахождению точки пересечения двух отрезков. Первый отрезок был возможной проекцией точки D при повороте треугольника ABD на произвольный угол относительно плоскости OXY. Второй отрезок получался из аналогичных рассуждений с треугольником ACD. Когда увидел авторское решение, понял, что перемудрил =). Здесь привожу именно авторское решение, т.к. в данной задаче оно куда уместнее. 
14E. Поле для крикета
Суть решения в переборе нижнего левого угла(O(N*N)) и последующий подбор максимально возможной длины поля с заданным углом. Именно подбор длины является очень интересной задачей.
[cricket] O(N*N*N*logN)
Первое, что пришло в голову это подобрать длину бинарным поиском, что затребует N*logN операций для каждого угла. Общая сложность нас устраивает и при аккуратной реализации получаем законный Accepted.
[cricket] O(N*N*N) 
Но есть более изящное и красивое решение за O(N).
14F. Электронная таблица
[sprsheet]
Задача, которая требует уже неплохой подготовки. Для начала давайте вспомним/узнаем:
1) Топологическую сортировку, которая поможет в нахождении циклических ссылок.
2) Подсчет арифметического выражения методом рекурсивного спуска (второй подход).
Значения ячейки можно хранить не в матрице, а в одномерном массиве.
Я попался на тесте, на котором была циклическая ссылка, не участвующая в подсчете ячейки A1. Получил досадный штраф =).

 
[Все решения]

Тренировка #13 [Меньшиков]

[Условия задач]                   [Список тренировок]

13A. Двойная решетка
[dlattice]
В данной задаче можно использовать принцип сетки, который был описан при решении 6D. Текущая задача является логическим продолжением задач 11A и 12A, где мы имели дело с начальной ацикличной и последующей периодической частью. Здесь ацикличной части нет, но ситуация осложняется тем, что последовательности две: по оси OX и OY. Это пугать никак не должно. Обработку последовательностей будем проводить отдельно. В приведенной реализации предложен механизм обнаружения последнего элемента первого цикла. Используя этот подход, можно по аналогичной схеме решить задачу для N решеток. 
13B. Последовательность Фибоначчи
[fiboseq] Бинарный поиск
Если особо не углубляться в природу чисел Фибоначчи и пытаться решить эту задачу с наскоку, то решение с помощью бинарного поиска - то что надо. И нужно еще не забыть, что число n может быть меньше min(i,j).
[fiboseq] Формула
Если же немного углубиться в эту самую природу, то можно получить формулу, которая однозначно восстанавливает элемент рассматриваемый последовательности с индексом min(i,j) + 1. Этих данных более чем достаточно для получения ответа.
13C. Скобки (3)
[bracket3]
Очередная “волшебная” задача на ДП. Учитывая бесценный опыт, по решению прошлых задач на эту тематику, особых трудностей возникнуть не должно. На первом этапе заполняем квадратную матрицу размерностью N*N, где N – длина исходной строки, куда в элемента [i][j] кладем длину ответа на исходную задачу для интервала исходной строки с i-ого символа по j-ый. Затем в обратном порядке восстанавливаем ответ.
13D. Центр тяжести
[centgrav]
Были проблемы с мат. частью, поэтому я ознакомился с решением авторского разбора и привел реализацию по нему.
13E. Сумма произведений
Что требуется в задаче осилил не сразу. Привожу два решения 
[prodsum] O(N*N)
Суровый перебор. Такое решение не должно было пройти по задумке автора. Но сейчас мощности возросли и мы можем себе это позволить. Но стоит N увеличиться на порядок и нас может спасти только второе решение.
[prodsum] O(N)
Оказывается для получения ответа необходимо перебирать только количество нулей(z). Отсюда можно однозначно определить общее количество(k) единиц и минус единиц. Для получения количества единиц(p) необходимо решить квадратное уравнение(a*p*p + b*p + c = 0), где коэффициенты a,b,c выражаются через k и s. Весь смак в получении этого квадратного уравнения.
13F. Статическая сложность
[icomplex]
В последнее время прям нравятся задачи на разбор выражения. Здесь, как и в 12F был реализован рекурсивный спуск.


[Все решения]

Тренировка #12 [Меньшиков]

[Условия задач]                   [Список тренировок]

12A. Последовательность (2)
[seq2]
Данная задача, решается аналогично 11A. Есть два принципиальных отличия. Во-первых, цикл в данной последовательности наступит тогда, когда повторится тройка подряд идущих цифр. Поэтому, максимальное количество элементов в цикле не более 1000. Во-вторых, экспериментальным путем было выявлено, что в данной последовательности нет ацикличной начальной части, т.е. первая повторяющаяся тройка совпадает с первой тройкой последовательности. Правда второе наблюдение не было отражено в решении, сохраняя общность подхода к решению подобных задач. 
12B. Гирлянда
[garland]
Интересная задача. Долго не мог понять условия. Главное уловить принцип прогибающейся гирлянды: чем ближе находится самый нижний из узлов гирлянды к оси OX, тем ниже будет находится точка B. Подход к решению аналогичен 11B.
12C. Головоломка умножения
[mpuzzle]
Хорошее двумерное ДП. Суть подхода – ищем ответ на поставленную задачу сначала для интервала длины 2, постепенно увеличивая длину. Когда длина интервала будет равно длине первоначальной последовательности – решение найдено. Остается главное – продумать переход от меньших интервалов к более большим.
12D. Точки в многоугольнике
[polygonp]
Несложная задача, если знаешь мат.часть, которая в данном случае заключается в формуле Пика.

S = В + Г/2 − 1

где
S – Площадь многоугольника (4D),
Г – Количество целочисленных точек на границе(10D),
B – Количество целочисленных точек внутри многоугольника.
Учитывая полученную информацию, найти значение B – дело техники.
12E. Водопровод
Оба подхода делают примерно одно и тоже. Пытаемся набрать длины dx = |x2-x1| и dy = |y2-y1|, используя набор предложенных труб.
[wpipe] Рекурсивный перебор с отсечением
В первом решении сначала пытаемся набрать длину dx, и только если это удалось – пытаемся набрать длину dy из оставшихся труб. Итак как можно набрать длину dx? Предположим, что имеем дело с крайним случаем, т.е. имеется 4 типа труб. Рассмотрим формулу:

a*L[0] + b*L[1] + c*L[2] + d*L[3] = dx

где a,b,c,d некоторые коэффициенты, которые по модулю не превышают C[0], C[1], C[2] и C[3] соответственно.
L[i] – длина трубы типа i.
C[i] – количество труб типа i. 1<=i<=K.
Перебор можно уменьшить, если перебирать только первые K-1 коэффициентов, т.к. последний K-ый коэффициент однозначно можно восстановить по первым K-1 коэффициентам и значению dx. Итак для нахождения замощения длины dx понадобится максимум 20*20*20 = 8000 итераций. Аналогично для dy - тоже 8000 итераций. Общее количество действий будет значительно меньше 8000*8000 действий.
[wpipe] Нерекурсивный перебор с использованием ДП
Второе решение начнем с того, как можно представить набор труб, которыми можно набрать определенную длину, если положить все трубы на одной прямой. Очевидно, что это будет картеж максимум из 4 элементов: {X,Y,Z,P}, где X<=C[0], Y<=C[1], Z<=C[2] и P<=C[3]. Если используем все трубы, то получаем картеж {10,10,10,10} в худшем случае. Если не используем ни одной трубы, то – {0,0,0,0}. Такой картеж можно упаковать в десятичное число равное числу XYZP в 11-ричной системе счисления. Картеж {10,10,10,10} будет эквивалентен 14640.
Если выложить все трубы в одном направлении, то получим длину не более MAX_LEN = 4*10*1000 = 40000.
Заполним рванную матрицу vector<vector<int> > dp(MAX_LEN * 2), где в dp[len] будут хранится упакованные в число наборы труб, которыми можно набрать длину len.
После чего достаточно будет взять наборы dp[dx] и dp[dy] и перебрать все возможные пары в поисках нужного ответа.
12F. Химические реакции
[chem]
Первая задача на рекурсивный спуск. Также эту задачу можно было сделать с помощью конечного автомата. Для начала нужно ознакомится с нотацией Бэкуса-Наура а дальше проявить внимательность и аккуратность. В таких задачах я практикую принцип “Тише едешь – дальше будешь”. Исходных код ответит на все остальные вопросы.

[Все решения]

Тренировка #11 [Меньшиков]

[Условия задач]                   [Список тренировок]

11A. Последовательность
[seq]
Довольно любопытная задача на выявление закономерности в последовательностях. Первый раз всплывает принцип Дирихле.
11B. Провода
[cable]
Классический пример задач на “Бинарный поиск по ответу”. Эта тема хорошо описана в 3 лекции курса Михаила Густокашина
11C. Палиндромы
[palindr]
Двумерное ДП. Один из тех удачных примеров, доказывающий, что ДП много не бывает. Придется немножко подумать.

Тренировка #10 [Меньшиков]

[Условия задач]                    [Список тренировок]

10A. Анти-QuickSort
[antiqs]
Нетипичная задача, требующая глубокого понимания работы быстрой сортировки.
10B. Строки Фибоначчи
[fibostr]
Классная задача на ДП. В наличием определенного опыта в решении подобных задач не представляет больших сложностей. Но есть ряд нюасов, которые нужно учесть.
10C. Игра в зачеркивание
Задача, которая не давала спокойно жить 2 дня. На нее было получено 4 решения, а все описание изложено в отдельном посте
[crossgam] TLE
[crossgam] ДП с запоминанием + vector   [0.105 с.]
[crossgam] ДП с запоминанием + multiset [0.322 с.]
[crossgam] на основе функции Grundy
10D. Граница многоугольника
[border]
Задача скорее на знания, чем на умения. Используем тот факт, что у прямоугольного треугольника количество точек с целочисленными координатами на гипотенузе равно НОД’у(Наибольшему общему делителю) катетов + 1. Представив каждую сторону за гипотенузу, обходим все стороны и получаем результат.
10E. Путь спелеолога
[speleo]
Задача на пространственное воображение и на трехмерный BFS. Особых сложностей быть не должно. Главное не забыть что здесь будет 6 измерений, в отличии от двумерного случая.
10F. Дырявая ткань
[holey]
Предложенное решение сделано полностью по авторскому разбору. Стоит обратить внимание на “приемчик”, как избежать TLE на максимальном тесте.


[Все решения]

10С–Игра в зачеркивание [Меньшиков]

[Тренировка 10]                      [Список тренировок]

Крайне любопытная задача.
Расскажу как мне далось ее решение. Рассказ будет не очень коротким, поэтому наберитесь терпения.

Итак мое первое решение было довольно тривиальным. Основывалось оно на опыте предыдущих задач. Суть заключалось в следующем:

1) Каждое состояние кодировалось числом. (X – единичка, O - нолик). В итоге получается 40 битное число, поэтому оно хранилось в типе long long.
2) Строилась матрица смежности, т.е. матрица переходов. Для каждого числа хранился список чисел, в которые можно попасть из текущего состояния.
3) Также отдельно хранился список всех возможных состояний(чисел) в игре.
4) После чего сортируем массив из п. 3) в порядке возрастания и начинаем его заполнять с конца.
5) Ответ будет находится в первом элементе массива из п. 3)

Чтож – неплохой план! Кодируем. Получаем нечто похожее на это. Каков же вердикт? На 9-и тестах из 31 получаем TLE.

И только после этого я начал ДУМАТЬ!

Тренировка #9 [Меньшиков]

[Условия задач]                   [Список тренировок]

9A. Диалог компьютеров
[dialogue]
Первая задача на моделирование процесса. Большое, немного непонятное условие(на первый взгляд), поэтому советую его читать несколько раз. Тщательно продумываем структуры данных перед тем, как начинать писать.
9B. Бросание кубика
[die]
Первая задача на теорию вероятностей. Для начала вспомним правило сложение вероятностей, и когда его нужно применять. Здесь изложена суть. Понятно, что если с двух бросков шестигранного кубика было набрано 8 очков, то это могло случиться, если выпала одна из комбинаций: 2-6, 3-5, 4-4, 5-3, 6-2. Находим вероятность каждой из этой комбинации и плюсуем в итоговую.

Тренировка #8 [Меньшиков]

[Условия задач]                    [Список тренировок]

8A. Несоставляемое число
[nosum]
Хорошая задача, сродни Рюкзаку. Нужно быть внимательным и не ошибиться с выбором типа данных для хранения ответа.
8B. SMS
Очень хорошая задача, которая является логическим продолжением серии задач на динамическое программирование. Первая задача на двумерное ДП. Над ней думал пару дней, в результате чего получилось следующее решение:
[sms] локаничная запись
В книге Павловской вычитал следующий девиз: “Better simpler than clever” (лучше по-простому, чем по-умному). В результате чего увидел в авторском разборе более понятную реализацию, которая делает тоже самое:
[sms] понятная запись
8C. Дерево игры
[gametree]
3-я задача на тему антагонистические игры. Не должна вызывать серьезных затруднений. Решается по аналогии с  предыдущими задачами. В ходе решения явно использовалась рекурсия. Если по условию задачи видно, что глубина рекурсии будет непозволительно большой, то можно модернизировать решение до неявного использования рекурсии или, если это поможет, увеличить глубину стека. Мы такое уже делали раньше.
8D. Дуга на сфере
[spherarc]
Задача на знание формул. А формулы, как говорится, надо знать или уметь их выводить.
8E. Путь коня
[knightw]
Эта задача уже была подробно рассмотрена в тренировках Михаила Долинского. Но решить ее еще раз будет крайне полезно.
8F. Грядки
[beds]
Очередная задача на DFS/BFS. Долго не мог понять, зачем автор дал столько много однотипных задач. Но когда ознакомился с разборами стало ясно, что на маленьких ограничениях можно успешно сдать решение с большой алгоритмической сложностью, но более лаконичной записью. В наших разборах я их не упомянул, поэтому всех заинтересовавшихся перенаправляю в книгу.  

[Все решения]

Тренировка #7 [Меньшиков]

[Условия задач]                    [Список тренировок] 

7A. Упорядоченные дроби
[ordfrac] Лобовая реализация
Т.к. число N не превышает 255, то общее количество дробей будет невелико, поэтому можно получить все дроби двойным циклом, отбрасывая “повторки”.
[ordfrac] Ряд Фарея
Ряд Фарея предоставляет механизм генерации нужного ряда дробей сразу в отсортированном виде
7B. Сообщение
[message]
ДП + длинная арифметика. Подобная задача и некоторые ее вариации часто встречаются на школьных контестах.
7C. Игра умножения
[multgame] ДП с использованием map
Очередная задача на антагонистические игры. Чуть более сложней чем предыдущая 6С. Данная реализация более лаконичная, но требует логарифмического времени для получения ответа к решенной подзадаче.
[multgame] ДП + бинарный поиск
Разница от предыдущей реализации в том, что все возможные шаги в игре находятся в одном массиве. Тем самым задача по своей сути сводится к задаче 6С. Но тем не менее получение ответа на решенную подзадачу также выполняется за логарифмическое время, т.к. при этом приходится использовать бинарный поиск.
7D. Прямая и квадраты
[sqline] O(N*N)
Квадратичная реализация, наиболее уместная для предложенных ограничений. Используем факт, что прямая не пересекает многоугольник тогда и только тогда, когда он полностью находится либо в правой, либо в левой полуплоскости от прямой.
[sqline] O(N)
Линейная реализация, которая требует внимательности и аккуратности. Необходимо учесть 3 случая: горизонтальная, убывающая и возрастающая прямая. Будем двигаться по прямой небольшими шагами, равными стороне маленького квадрата, вдоль оси X. При этом будем анализировать значения Y. Рассмотрим 3 основных случая для возрастающей прямой:

	Прямая пересекает только один квадрат
	Прямая пересекает два квадрата
	Прямая пересекает 4 квадрата

Остальные случае предлагается рассмотреть самостоятельно.
7E. Lines(2)
[lines2]
Решение, аналогичное задаче 6E.Lines
7F. Удаление клеток
[remsquar]
Несложная задача. В качестве основных алгоритмов, решающих эту задачу на ум приходят DFS и BFS. Оба имею квадратичную сложность, но DFS писать проще. Торопится не стоит. Размерности матрицы таковы, что придется делать 250*250 рекурсивных вызовов. Поэтому вовремя одумываемся и быстро пишем BFS.


[Все решения]

Тренировка #6 [Меньшиков]

[Условия задач]                   [Список тренировок] 

6A. Закраска прямой 
[cover]
Полезная задача. Является фундаментальным “кирпичиком”. Другая вариация этой задачи встречается в задаче Музей. Нужно научиться корректно, а главное быстро обрабатывать случай когда часть отрезка принадлежит нескольким интервалам, а также грамотно откидывать пустоты. 
6B. Суммы
[sums]
Переборная задача, требующая знания и понимая “Рюкзака”.
6C. Игра “Даты”
[dategame]
Первая задача на теорию игр. Крайне полезно при первом прорешивании догадаться самому до правильного решения, воспользовавшись фактом, что решается она методом Динамического программирования. Мне такого сделать не удалось. Текущая позиция для первого игрока является выигрышной, если есть хотя бы одна позиция, куда он может пойти, которая является проигрышной для второго игрока.
6D. Площадь прямоугольников
[rectarea]
Эта задача еще один фундаментальный “кирпичик”. Ее решение изложено в книге Окулова. Рассмотрим рисунок.
Как видно дано 4 прямоугольника. Каждый из них дает по 2 проекции на оси X и Y. Избавляемся от дубликатов проекций. После чего получаем сетку, образованную этими проекциями. Эта сетка разбила первоначально пустой прямоугольник на N маленьких прямоугольников. В нашем случае N = 28. Чтобы найти суммарную площадь нужно перебрать каждый прямоугольник сетки и проверить, не является ли он вложенным хотя бы в один из первоначальных прямоугольников.
6E. Lines
[lines]
Отличная задача на одновременное применение поиска в ширину(BFS) для получения наилучшего ответа и поиска в глубину(DFS) для восстановление ответа.
6F. Покраска лабиринта
[paintlab] Рекурсивный DFS
Эту задачу можно делать как поиском в глубину, так и в ширину. Т.к. ограничения невелики и DFS пишется быстрее, то выбираем именно этот путь.
[paintlab] Нерекурсивный DFS
Была предпринята попытка показать, как можно реализовать DFS без явного использования рекурсии. Для этого был использован стек, в котором хранились предыдущие состояния. На больших размерностях такой подход будет работать быстрее. Но в боевых условиях, чтобы избежать использования рекурсии лучше писать BFS, если это возможно.


[Все решения]

Тренировка #5 [Меньшиков]

[Условия задач]                   [Список тренировок] 

5A. Дружественные числа 
[friendly] Precalc
Лобовое решение не проходит по времени. Поэтому воспользуемся “грязным приемчиком”, и подсчитаем все что нам нужно заранее и запишем все ответы в исходник.
5B. Скобки(2)
[brackets2]
Крайне полезная задача на понимание работы рекурсии. Рекурсивно получаем следующую скобочную последовательность. На каждом шаге храним количество открытых скобок и позицию, куда нужно ставить очередную скобку. Для получения корректных скобочных последовательностей нужно хранить стек, со всеми незакрытыми скобками.

Тренировка #4 [Меньшиков]

[Условия задач]                   [Список тренировок] 

4A. Совершенные числа
[perfect]
Хорошая несложная задача. Есть один подвох, на который натыкаются многие. Желаю наткнуться на него всем начинающим, чтобы глубже проникнуться задачей. 
4B. Разложение на слагаемые
[decomp]
Компактная рекурсивная реализация. В ходе решения встает только одна проблема: как не генерировать комбинации слагаемых, которые уже были до этого? Для этого, по рекомендации Меньшикова, условимся, что в получаемой комбинации предыдущее слагаемое не превышает текущего. Этим приемом можно пользоваться и в других подобных задачах для обеспечения уникальности последовательностей.

Тренировка #3 [Меньшиков]

[Условия задач]                   [Список тренировок]

3A.Разложение на простые множители
[pfactor] Типовая соптимизированная реализация
Оптимизация заключается в пересчете верхней границы цикла(корень квадратный из N) при переходе к новому делителю.
3B.Перестановки(2)
[permut2] Рекурсивная реализация с подсчетом элементов
Реализация основана на разборе этой задачи из книги Меньшикова. Первоначально подсчитываем количество вхождений символов из первоначальной перестановки. Затем на i-ое место текущей перестановки ставим ближайший в лексикографическом порядке символ, счетчик которого имеет ненулевое значение, и декрементируем счетчик на единицу.
[permut2] Идентично [permut] next_permutation
Важный факт того, что генерация алгоритмом next_permutation не зависит от того есть ли дублирующие символы во входном наборе или нет. Общий вывод: любая корректная реализация задачи 3B пройдет на задаче 2B.

Тренировка #2 [Меньшиков]

[Условия задач]                   [Список тренировок]

2A. Простые числа
[primes2] Идентично [primes]
Первая задача [primes] проходит даже если перебирать в качестве делителей все числа в интервале [2,sqrt(n)]. Вторая же задача [primes2] проходит только, если перебирать нечетные делители.
[primes2] Precalc всех простых чисел
Предыдущую реализацию можно ускорить если в качестве делителей использовать не просто нечетные числа, а простые. Ускорение ~ в 2 раза.
[primes2] Решето Эратосфена
Решето Эратосфена упоминается в учебниках по математики за 6 класс. Сам подход несложен и вполне понятен. Реализация лаконична и не представляет сложности. Ко всему прочему это наиболее эффективный подход к нахождению простых чисел в заданном интервале. 

Тренировка #1 [Меньшиков]

[Условия задач]                    [Список тренировок]

1A. Простые числа
[primes]
Незамудренная реализация с одной фишкой: при нахождении делителей числа перебираем только нечетные из них. Как показала практика при этом достигается экономия по времени в 4 раза.
1B. Выражение
[expr]
Лаконичная рекурсивная реализация. Помимо этого решение имело место решение с генерацией всех комбинаций ‘+’ и ‘–’ для текущего набора чисел, которое требовало пересчета всего выражения целиком для каждой комбинации. Это решение не прошло по времени. К достоинству рекурсивного решения относится то, что перерасчет всего выражения не требуется. Нужно пересчитать только его изменившийся конец.

Олимпиадные задачи по программированию [Федор Меньшиков]

Начинаем марафон по всем задачам из этой замечательной книги. На каждую задачу будет предложен как минимум один вариант решения. Задачи буду выкладывать по мере их решения и по мере прохождения материала на субботних тренировках. 

Тренировка #1   [08Mar10] 
Тренировка #2   [11Mar10]  
Тренировка #3   [18May10]
Тренировка #4   [20May10] 
Тренировка #5   [19Nov10] 
Тренировка #6   [23Nov10] 
Тренировка #7   [29Nov10]
Тренировка #8   [08Dec10]
Тренировка #9   [18Dec10] 
Тренировка #10  [24Dec10] 
Тренировка #11  [28Dec10] 
Тренировка #12  [06Jan11] 
Тренировка #13  [08Jan11]
Тренировка #14  [11Jan11] 
Тренировка #15  [17Jan11]

Все задачи тестируются в online-judge системе [informatics.mccme.ru], и если будет указано время работы любого из решений, то стоит считать, что эти данные были получены именно оттуда.

P.S: Исходники первых 4 тренировок могут давать ошибку компиляции на указанном сервере. Это связано с обновлением компилятора. Большую часть проблем может решить подключение заголовочного файла <cstdio>