OCPC2021 K: Нобелевская премия

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени: 500 мс
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Нобелевская премия

Дед Архип и дед Игнат, постояльцы палаты номер 17 заведения «Покосившийся Скворечник», убеждены, что они – великие математики – Блез Паскаль и Пьер Ферма соответственно. А как ещё должны проводить время математики, если не играя друг с другом в азартные игры? Вот и дед Архип с дедом Игнатом придумали себе развлечение – они раздобыли три баночки с таблетками умиротворения: по одной им вручили санитары, а третью прикарманил дед Архип («Во имя науки!» – воскликнул он, унося таблетки), воспользовавшись тем, что их соседа, деда Панаса, сморило прослушивание доказательства Великой теоремы Игната.

Правила игры следующие: игроки ходят по очереди в порядке старшинства. За один ход великий математик выбирает целое положительное число x и съедает x таблеток из какой-то одной баночки, либо съедает по x таблеток из всех трёх баночек сразу. Проигрывает тот, кто не может сделать ход, а его противник награждается магарычем от деда Пахома, убеждённого, что он – Альфред Нобель. Магарычем в области экономики, разумеется, ведь именно так награждают лучших математиков.

Дед Архип и дед Игнат с удовольствием бы сыграли, чтобы установить победителя, но предыдущий опыт подобных развлечений убедил их, что они необъяснимым образом теряют интерес к игре уже после первого хода. Поэтому они просят Вас назвать победителя по исходным данным, а таблетки они оставят для завтрашней игры. Не сомневайтесь, что великие математики всегда ходят оптимальным образом.

Единственная строка ввода содержит три целых числа abc (0 ≤ abc ≤ 1000) – количество таблеток в каждой из трёх баночек.

Выведите единственную строку «Ignat», если Нобелевскую премию получит дед Игнат, и «Arkhip», если удача на стороне деда Архипа.

Примеры

Входные данные Результат работы
2 0 2 Arkhip
1 2 4 Ignat

Видеоразбор решения задач здесь.

OCPC2021 J: Театр теней

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени: 3 с
Ограничение реального времени: 6 с
Ограничение памяти: 256M

Театр теней

Тиктокеры Стас и Ян, постояльцы палаты номер 66 заведения «Покосившийся Скворечник», решили устроить перфоманс в прямом эфире. Они разместили на прямоугольном полу своей палаты n свечей в разных точках и готовятся провести представление, состоящее из m актов. В каждом акте должен гореть только определённый набор свечей, который будет таким образом создавать новую картину из теней на стене палаты, остальные свечи должны быть потушены. Область, попадающая в кадр, имеет ширину w, длину l, по ширине перекрывает палату целиком, а по длине оставляет небольшое пространство слева и справа, как показано на рисунке.

Сами тиктокеры в кадре появляться не должны, с этой целью они могут находиться либо у левой, либо у правой стенки палаты за кадром. Чтобы тушить и зажигать свечи, Стас и Ян могут делать перерывы между актами перфоманса, во время которых стрим отключается, и они будут выбегать в кадр: Стас будет только зажигать свечи, а Ян – только гасить, после чего они должны успеть скрыться из кадра до начала нового акта. Перед перфомансом Стас находится за кадром слева, а Ян – за кадром справа. Также изначально зажжены свечи, необходимые для первого акта.

Чтобы подписота не заскучала без зрелища и не разбрелась смотреть рэп-батлы, перерывы между актами должны суммарно занимать как можно меньше времени. Найдите это время и тиктокеры подарят Вам золотую подписку на их канал!

Первая строка ввода содержит пять чисел – wlv1v2 и n (1 ≤ wl ≤ 50, 1 ≤ v1v2 ≤ 20, 1 ≤ n ≤ 15) – размеры кадра, скорости Стаса и Яна и количество свечей на полу. Далее идут n строк с координатами свечей xiyi (0 < xi < l, 0 < yi < w). Следующая строка содержит число m (1 ≤ m ≤ 104) – количество актов перфоманса. Далее идут m строк, каждая из которых начинается с количества свечей, которые должны гореть в очередном акте и продолжается номерами этих свечей.

Единственная строка вывода должна содержать число – минимально возможное суммарное время перерывов между актами перфоманса с точностью до 10-5.

Примеры

Входные данные Результат работы
5 6 1 1 3
1 2
3 4
5 3
1
1 3
0.000000
5 6 1 1 3
1 2
3 4
5 3
3
1 3
2 1 2
3 1 2 3
8.828427

Видеоразбор решения задачи здесь.

OCPC2021: I Белка в колесе

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени: 5 с
Ограничение реального времени: 10 с
Ограничение памяти: 256M

Белка в колесе

Журналистка Ксюша, постоялица палаты номер 13 заведения «Покосившийся Скворечник», убеждена, что она – белка. Сейчас, стоя у окна своей палаты, она смотрит на растущее за окном дерево (как известно любой белке, это связный граф без циклов) и воображает, как резвится, перебегая по нему с ветки на ветку и обратно. Главред Аркаша, сосед Ксюши, возмущён таким бесцельным и беспорядочным расходованием энергии, поэтому он хочет соорудить из какой-то части (возможно, всего) дерева колесо, то есть, добавить в граф несколько рёбер, чтобы создать цикл, по которому и будет бегать Ксюша, вырабатывая сверхценные идеи для издания. Но, к сожалению, у Аркаши есть всего две подтяжки, которые он готов пожертвовать на это благое дело, а значит, он может добавить не более, чем два ребра в дерево, при этом, он хочет получить цикл максимальной длины, и каждая вершина должна входить в него не более одного раза, не то Ксюша запутается и выдаст что-то не передовое или социально неодобряемое. Длина цикла, как знает любой главред, считается по количеству рёбер в нём. Поскольку Аркаша не привык работать сам, он ждёт, что Вы подскажете ему максимальную длину колеса для белки и между какими вершинами вешать подтяжки, а не то он Вас закенселит.

Первая строка ввода содержит единственное целое число n (3 ≤ n ≤ 105) – количество вершин дерева, растущего за окном. Следующие n-1 строк содержат пары целых чисел – номера вершин дерева, соединённых ребрами.

Первая строка вывода должна содержать одно число – максимальную достижимую длину колеса. Следующие 1 или 2 строки должны содержать пары целых чисел – какие пары вершин нужно соединить подтяжками, чтобы получить колесо нужной длины.

Примеры

Входные данные Результат работы
4
1 2
2 3
3 4
4
1 4
4
1 2
1 3
1 4
4
2 3
2 4

Видеоразбор решения задачи здесь.

OCPC2021 H: Счастья всем даром!

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени: 1 с
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Счастья всем даром!

В заведении «Покосившийся Скворечник» проходит традиционная воскресная перекличка. Во время этого мероприятия все постояльцы выстраиваются в ряд и по очереди, начиная с самого правого, выкрикивают свой порядковый номер в ряду. Кондуктор Кондрат, постоялец палаты номер 11, убежден, что если сегодня он выкрикнет счастливый номер, то удача наконец-то повернётся к нему лицом, и ему наконец-то выплатят зарплату за все те годы, что он обилечивал каждого встречного в «Покосившемся Скворечнике». Любому кондуктору известно, что счастливое число – это такое число, сумма цифр на чётных позициях которого совпадает с суммой на нечётных. Только что Кондрат услышал номер, который выкрикнул его сосед справа и теперь у кондуктора есть всего две секунды, чтобы понять, какой следующий номер – счастливый и, сломя голову, побежать занимать соответствующее место в ряду. Вы – его сосед слева, шепните правильный ответ Кондрату и на радостях он подарит Вам проездной!

Единственная строка ввода содержит натуральное число – номер, который выкрикнул сосед Кондрата. Этот номер содержит не более 100 цифр.

Выведите одно число – следующий по порядку счастливый номер.

Примеры

Входные данные Результат работы
123123 123134
99 110

Видеоразбор решения задачи здесь.

OCPC021 G: Электрик возвращается

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени: 1 с
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Электрик возвращается

Электрик Геннадий, постоялец палаты номер 404 заведения «Покосившийся Скворечник», прокрался ночью к ближайшей ЛЭП, чтобы наконец воплотить в жизнь свой план – отрезать кусок провода, находящийся между двумя соседними опорами, и отомстить лживой розетке из предыдущей задачи.

Он планирует реализовать это следующим образом: сначала просто забраться на вершину одной из опор, отрезать провод, закреплённый там, после чего спуститься на некоторую высоту вниз, возможно до земли. Далее Геннадий рассчитывает воспользоваться способностями человека-паука, которые, по его убеждению, открылись в нём после недавнего удара током: он выстрелит паутиной в некоторую произвольную точку соседнего столба, оттолкнется от первого столба и спустится по дуге окружности либо до второго столба, либо до земли. Разница высот в начале и конце такого спуска не должна превышать некоторую величину l, иначе наш новоявленный человек-паук рискует слишком сильно разогнаться и превратиться в человека-лепёшку. Затем электрик поднимется на вершину второго столба, чтобы отрезать закреплённый там провод, и спустится на землю.


Высоты столбов – h1 и h2, расстояние между ними – d. Геннадий не очень любит лазать вверх, поэтому он хочет разработать план таким образом, чтобы суммарная дистанция подъёмов была минимально возможной. Раз уж Вы взялись помогать ему, то доведите начатое до конца!

Единственная строка ввода содержит четыре целых числа dh1h2l (1 ≤ dh1h2l ≤ 106).

Выведите одно число – минимальную суммарную дистанцию подъёма Геннадия с точностью не хуже 10-5.

Примеры

Входные данные Результат работы
5 5 5 5 10.00000
4 5 8 5 10.00000
4 8 5 1 13.00000
3 4 6 1 9.00000

Видеоразбор решения задачи здесь.

OCPC2021 F: Электрик наносит ответный удар

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени: 1 с
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Электрик наносит ответный удар

В заведении «Покосившийся Скворечник» главврач экономит на зарплате системного администратора, поэтому эту должность в свободное от уколов время занимает электрик Геннадий из палаты номер 404. На сегодняшнем дежурстве одна из розеток внезапно заговорила с Геннадием и посулила тому суперспособности, если он её раскрутит. Результатом их общения, однако, стал лишь удар тока по нерадивому электрику, и теперь Геннадий задумал месть: он устроит лживой розетке Очень Длинное Замыкание!

Дата-центр «Покосившегося Скворечника» устроен следующим образом: помимо разной аппаратуры, из стены в ряд торчат 2∙n коннекторов: это n штепселей и n розеток. Геннадий планирует разбить их на пары розетка-штепсель и соединить каждую пару одним проводом таким образом, что штепсель всегда находится левее соответствующей розетки – эту идею ему навеяли правила средневекового этикета. Чтобы замыкание было Очень Длинным, Геннадий хочет, чтобы суммарная длина проводов, использованных для его коварного замысла, была максимально возможной. Помогите ему! Ну, или не мешайте хотя бы, и просто подскажите, провод какой длины он должен отрезать от соседней линии электропередач, чтобы распилить его на столь нужные ему провода.

Первая строка ввода содержит целое число n (2 ≤ n ≤ 1000). Вторая строка содержит n целых чисел – координаты штепселей слева направо. Третья строка содержит n чисел – координаты розеток слева направо. Все числа во второй и третьей строках различны и находятся в диапазоне от 0 до 105.

Выведите одно число – суммарную длину проводов, необходимых, чтобы устроить Очень Длинное Замыкание. Гарантируется, что существует хотя бы один способ соединения штепселей с розетками без нарушения правил средневекового этикета.

Примеры

Входные данные Результат работы
2
1 4
6 8
9
2
1 4
2 5
2

Видеоразбор решения задачи здесь.

OCPC2021 E: Объясните теперь нам, вахтёры…

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени: 500 мс
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Объясните теперь нам, вахтёры…

В заведении «Покосившийся Скворечник» ЧП: на фоне ежеквартального обострения синдрома вахтёра из палаты номер 99 вырвался ночной сторож Михалыч и перегородил вход в уборную. Для пропуска внутрь он требует пароль, который он тут же записал на стене в виде строки из m строчных латинских символов. Но не всё так просто: недостаточно назвать пароль тщеславному Михалычу – нужно составить его из букв стихотворения, сочиненного ночным сторожем. И действительно, над паролем Михалыч записал стихи: n строк по m строчных латинских символов каждая. Чтобы получить искомый пароль, над ними разрешено проделывать следующую операцию: выбрать две различные строки с номерами i и j, выбрать номер символа k, а затем поменять местами k-й символ в строках номер i и j. Например, если мы меняем 3-й символ в паре строк «abcde» и «fghij», то получим «abhde» и «fgcij». Так нужно делать до тех пор, пока одна из строк не совпадёт с паролем.

Проверено, что санитары не в состоянии совладать с Михалычем, поэтому единственный способ разблокировать проход – это написать программу, которая по заданным строкам и паролю найдёт самый быстрый (мы же в уборную пытаемся попасть!) способ получить пароль из заданных строк.

Первая строка ввода содержит целое число n (2 ≤ n ≤ 100) – количество строк в стихотворении Михалыча. Каждая из последующих n строк состоит из строчных латинских символов и имеет одинаковую длину m (2 ≤ m ≤ 100). Последняя строка содержит пароль Михалыча длины m.

Первая строка вывода должна содержать минимальное число x операций над строками. Если получить пароль никак невозможно, выведите -1. В следующих x строках, если возможно получить пароль, выведите последовательность операций в формате i j k – номера первой и второй строк стихотворения Михалыча, над которыми производится операция обмена и номер символа в этих строках.

Примеры

Входные данные Результат работы
3
cab
abc
bca
cba
2
1 3 3
1 2 2
3
dbc
aeb
cca
acd
-1

Видео разбор решения задачи здесь.

OCPC2021 D: Столовая

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени: 2 с
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Столовая

В столовой заведения «Покосившийся Скворечник» имеется ровно k тарелок, а в самом заведении – n палат. По старой традиции, чтобы постояльцы не пугались новых знакомых и не обменивались симптомами, их приводят в столовую так, чтобы одновременно там находились только обитатели одной палаты. При этом, порядок посещения столовой палатами строго зафиксирован – от меньшего номера к большему.

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

Первая строка ввода содержит два целых числа n и k (1 ≤ n ≤ 105, 1 ≤ k ≤ 105) – количество палат и тарелок, соответственно. Следующие n строк содержат по 2 целых числа ai и bi (0 ≤ ai + bi ≤ k) – количество постояльцев в очередной палате, моющих и не моющих за собой посуду, соответственно.

Выведите одно число – количество тарелок, оставшихся чистыми к концу смены, при оптимальной раздаче посуды.

Примеры

Входные данные Результат работы
2 4
1 2
1 1

3

Видеоразбор решения здесь.

OCPC2021 C: Перепись чисел

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени: 1 с
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Перепись чисел

Учительница младших классов Марь Ивановна, постоялица палаты номер 9 3/4 заведения «Покосившийся Скворечник», насмотрелась «Гарри Поттера» и теперь боится, что Волдеморт сотрёт у неё из памяти какое-нибудь число. Чтобы не допустить этого преступления, Марь Ивановна решила выписать все числа от 1 до n (числа, большие, чем n, ей для работы всё равно не пригодятся) подряд в одну строку на стене палаты. При этом, для экономии времени (Волдеморт уже рядом!), она решила приписывать очередное число к своей строке только в том случае, если его десятичная запись еще не содержится в уже записанной строке. Например, в строке «1234567891011» уже содержится запись числа 12, а значит, приписывать это число не нужно.

Сосед Марь Ивановны, трудовик Василий Семёныч, убеждён, что Волдеморт уже стёр какое-то число из памяти учительницы младших классов. Чтобы удостовериться в своей правоте, он требует, чтобы Вы показали ему, как должна выглядеть верная строка, составленная по правилам Марь Ивановны, для сравнения с тем, что в итоге появится на стене палаты. В награду за помощь он обещает выстрогать бузинную палочку для вас. Поскольку в руках у Василия Семёныча лобзик, лучше с ним не спорить!

На ввод поступает единственное целое число n (1 ≤ n ≤ 105) – максимальное число, важное для работы учительницы младших классов.

Выведите одну строку, содержащую запись всех чисел от 1 до n по правилам Марь Ивановны.

Примеры

Входные данные Результат работы
1 1
4 1234
15

Видеоразбор решения здесь.

OCPC2021 B: Палиндромонойя

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени: 500 мс
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Палиндромонойя

Студент Илья, постоялец палаты номер 101 заведения «Покосившийся Скворечник», попавший сюда во время сессии на почве экзамена по программированию, убеждён, что его повсюду преследуют затаившиеся палиндромы. «Они среди нас! Как же вы этого не замечаете?!» – то и дело слышат от него нянечки Алла и Анна. По убеждению Ильи, палиндром – это слово, читающееся одинаково, как слева направо, так и справа налево. Если же на первый взгляд слово таковым не является, то студент не опускает рук и переносит буквы по одной из начала слова в конец, пока оно не станет палиндромом. Если из слова таким образом удалось получить палиндром за 0 или более операций, Илья называет его затаившимся палиндромом, после чего студент начинает бегать по потолку с воплями отчаяния, чем доставляет неудобства окружающим. Например, Илью может довести до исступления слово «масса», ведь из него можно получить «самас», перенеся 3 буквы из начала в конец. Главврач хочет выкинуть из палаты номер 101 Илью, но вместо этого выкинет все предметы, названия которых являются затаившимися палиндромами. Осталось только проверить их все, а здесь без программы не обойтись!

На ввод поступает строка, содержащая одно слово, длиной от 1 до 100 латинских строчных букв.

Выведите одну строку: «yes» без кавычек, если предмет с этим названием стоит выбросить и «no» без кавычек, если его стоит оставить в палате номер 101.

Примеры

Входные данные Результат работы
array yes
iliya no
anna< yes<

Ссылки

OCPC2021 A: Колёса деда Панаса

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени: 500 мс
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Колёса деда Панаса

Дед Панас, постоялец палаты номер 17 заведения «Покосившийся Скворечник», срочно должен был принять свои таблетки умиротворения. К сожалению, нянечка рассыпала их по столу и теперь дед Панас твёрдо уверен, что он – Генри Форд, а на столе лежат колёса, из которых нужно собирать автомобили и мотоциклы. Сосед деда Панаса, дед Архип, также не дождавшийся своих таблеток, убеждён, что он – Блез Паскаль, и, заметив, что колёс на столе четное количество, донимает нянечку вопросом: «Сколькими способами можно распределить эти колёса между автомобилями и мотоциклами так, чтобы не оставалось лишних?» Поскольку дед Архип не уймётся, пока не получит ответа, и будет мешать нянечке собирать таблетки со стола, на помощь позвали вас и просят подсказать ей правильный ответ.

На ввод поступает единственное целое четное число n (2 ≤ n ≤ 109) – количество таблеток на столе.

Выведите одно число – количество способов распределить колёса между автомобилями и мотоциклами. Помните, что для автомобиля нужно 4 колеса, для мотоцикла – 2. Два способа считаются различными, если в одном из них количество автомобилей не совпадает с количеством автомобилей в другом; то же самое справедливо и для мотоциклов.

Примеры

Входные данные Результат работы
6 2

Видеоразбор решения здесь.

Алгоритмы поиска

Search Algorithms

Search Algorithms

Хочу предложить простой, но достаточно общий взгляд на алгоритмы поиска в ширину BFS (Breadth-first Search), в глубину DFS (Depth-first Search) и бесконечное количество других с общей схемой. Фактически это алгоритмы обхода соседних вершин графа в которых последовательно строятся пути из некоторой исходной вершины ко всем остальным.
Сначала сформулируем общую схему алгоритмов этого типа. И без обычных для учебников избыточных сложностей в виде белых-серых-черных вершин.

  1. Заводим PLAN поиска — контейнер данных, где будем хранить вершины в которых мы планируем побывать. Изначально он пуст.
  2. Добавляем в PLAN поиска исходную вершину с которой нам предписано начать.
  3. Пока PLAN не пуст и цель поиска не достигнута делаем следующее
    1. GET: Извлекаем из PLAN какую-нибудь вершину v.
    2. Посещаем вершину v. Если мы не просто обходим вершины, а что-то ищем, то здесь самое время обыскать вершину v на предмет достижения цели поиска.
    3. Как-то отмечаем, что вершина v уже посещена.
    4. PUT: Добавляем в PLAN все соседние с v вершины, которые еще не были посещены.
  4. Выводим результат поиска.

Самым важным для реализации этой схемы является PLAN. Это контейнер данных в котором нам нужны две функции GET — чтобы что-то из контейнера достать и PUT — чтобы в контейнер что-то положить. Конечно лучше использовать уже готовые контейнеры. Выбор контейнера будет определять стратегию поиска.
DFS (Depth-first Search). Например, если в качестве контейнера выбрать СТЕК, то мы реализуем алгоритм поиска в глубину. Ведь организация доступа к элементам стека такова, что мы в первую очередь будем посещать те вершины, которые попали в план последними. Посмотрим на код решения задачи
Обход в глубину:

Единственное важное пояснение. Чтобы отметить, что вершина уже посещалась, я использую диагональ матрицы смежности графа. в условии специально подчеркнули, что там всегда нули, а значит я могу поставить matrix[v][v] = 1, чтобы обозначить вершину v как уже посещенную.

BFS (Breadth-first Search). Стоит нам немного изменить код и использовать для хранения плана ОЧЕРЕДЬ, алгоритм меняет стратегию и осуществляет поиск в ширину. Поскольку вершины будут посещаться в том порядке в котором мы их добавляли, это очень похоже на распространение волны из начальной точки. Отсюда другое название таких алгоритмов — заливки (flood) или волновые алгоритмы.

Если для хранения плана написать свой контейнер или хотя бы переопределить методы GET и PUT, то вы получите новый алгоритм поиска. Например, можно извлекать вершину из плана случайным образом. В этом случае мы получим один из рандомизированных алгоритмов семейства Монте-Карло.

Задание: Найдите все четыре места, где код поиска в глубину отличается от кода поиска в ширину.
Подсказка: Если не смогди найти четвертое отличие — оно в комментариях 🙂

Задачи Областной школьной олимпиады 2018

На Одесской областной олимпиаде школьников 2018 года мы предложили 12 задач различной степени сложности. Результаты можно найти здесь.
Условия задач, их короткий разбор мы попытались сделать на этой странице.
Решать задачи можно на сайте acm.pp.ua после простой регистрации. Соревнование №12.


Первые три задачи получились разбиением одной задачи, на три этапа для последовательного решения.

Задача A. Секунды

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

На часах сейчас $s$ секунд. Сколько секунд они будут показывать через $t$ секунд?

Входные данные: Два целых числа через пробел – $s \left(0 \le s \le 59\right)$ и $t \left(0 \le t \le 2^{31}\right).$

Выходные данные: Одно целое число – новые показания секунд на часах.

Вход Выход
2 3 4
25 50 15

На что обратить внимание

  • Значения параметра t выходит за пределы знакового 32-битного числа $\left[-2^{31};2^{31}-1\right]$
  • . Необходимо знать как кодируются целые числа и выбрать такой тип, чтобы данные и результаты вычислений не выходили за его пределы.

  • Нужно заметить, что каждые $60$ секунд показания возвращаются к исходному значению. Значит для решения следует использовать операцию остатка от деления на $60.$
A. Решение на С++
A. Решение на Java
A. Решение на C#

Задача B. Минуты и секунды

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Часы сейчас показывают $s$ секунд и $m$ минут. Сколько они будут показывать через $t$ секунд?

Входные данные: Три целых числа через пробел – $s, m \left(0 \le s, m \le 59\right)$ и $t \left(0 \le t \le 2^{31}\right).$

Выходные данные: Два целых числа через пробел – новые показания минут и секунд.

Вход Выход
44 25 22 26 6
59 58 121 1 0

На что обратить внимание

  • Если предыдущая задача решена, то следует разобраться только с минутами. Нужно разобраться сколько пройдёт минут, если было $s$ секунд и прошло ещё $t$. Для этого придётся суммарное количество секунд разделить на $60$ — число секунд в минуте.
  • Поскольку минутная стрелка через $60$ минут вернётся к тем же показаниям, нужно снова взять остаток от деления на $60.$
  • Хотя условие задачи укладывается всего в пару строк, читать его нужно внимательно. Небольшое упражнение на внимательность состоит в том, что минуты и секунды на входе и выходе должны следовать в различном порядке.
B. Решение на C++

Задача C. Часы, минуты, секунды

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

На часах сейчас $h$ часов, $m$ минут и $s$ секунд. Сколько они будут показывать через $t$ секунд?

Входные данные: Четыре целых числа через пробел – $h \left(0 \le h \le 23\right), m, s \left(0 \le s, m \le 59\right)$ и $t \left(0 \le t \le 2^{31}\right).$

Выходные данные: Три целых числа через пробел – новые показания часов, минут и секунд.

Вход Выход
23 59 59 66 0 1 5

На что обратить внимание

  • Кроме того, что период повторения часов составляет $24 \times 60 \times 60$ секунд особенно добавлять здесь нечего.
C. Решение на C++
В решении предлагается другой подход решения задачи. Предлагается перевести текущие показания часов в секунды. После этого увеличим текущее время на требуемое число секунд. Полученный результат можно будет снова перевести в часы, минуты и секунды. такой подход работает для самых разных задач в которых данные задаются в сложной системе единиц. Например, фунт стерлингов, шиллинг, пенс, фартинг, гинея, крона. Достаточно перевести все в наименьшие единицы, если все остальные соответствуют их целому числу. В общем случае, такой универсальной единицей может стать наибольший общий делитель всех используемых единиц.

Следующие две задачи также укладываются в некоторую цепочку. Вторая задача отличается от первой снятием ограничения на направление вырезания и это делает ее гораздо более сложной.

Задача D. Вырезаем прямоугольник в клеточку

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Имеется лист из тетради в клеточку размером $H \times W$ клеток. Определите, можно ли из него вырезать прямоугольник размером $h \times w$. Резать можно только по линиям.

Входные данные: Четыре целых числа через пробел – $H, W, h, w$. Все числа положительные и меньше $2^{31}.$

Выходные данные: Выведите $1$ если требуемый прямоугольник вырезать можно или $0$ если нельзя.

Вход Выход
5 8 10 1 0
5 8 6 4 1

На что обратить внимание

  • Вырезать можно двумя способами — вдоль листа или поперек. Нужно убедиться, что в каком-то из этих положений все поместится.
D. Решение на C++

Задача E. Вырезаем прямоугольник снова

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Имеется лист бумаги размером $H \times W$ миллиметров. Определите, можно ли из него вырезать прямоугольник размером $h \times w$ миллиметров.

Входные данные: Четыре целых числа через пробел – $H, W, h, w.$ Все числа не превышают $500$.

Выходные данные: Выведите $1$ если требуемый прямоугольник вырезать можно или $0$ если нельзя.

Вход Выход
5 8 7 7 0
8 8 10 1 1

На что обратить внимание

  • Конечно главное отличие задачи от предыдущей совсем не в том, что клеточки заменили на миллиметры.
  • В этой задаче вырезать можно не только вдоль сторон листа, но и под любым углом к ним.
  • Если Вы уже знаете тригонометрию, то вам достаточно разместить прямоугольник под некоторым углом $\alpha$ и просчитать ширину и высоту охватывающего его листа. Останется только подобрать правильный угол. Недостаток этого способа состоит в том, что необходимо уметь пользоваться тригонометрическими функциями и обратными к ним.
  • Школьники в 8-м классе ещё не знают тригонометрических функций. Но есть возможность получить более изящное решение, без их использования. Это решение приводится под спойлером, но лучше попытайтесь найти его самостоятельно.
E. Решение на C++

И снова две задачи, вторая из которых лишена одного из ограничений. И снова, снятие ограничения делает вторую задачу более сложной. Точнее менее очевидной.

Задача F. Режем масло

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Имеется прямоугольный брусок масла размером $X \times Y \times Z.$ Плоскими разрезами его нужно разделить на кубики со стороной $1.$
Какое минимальное число разрезов нужно будет сделать если каждый из полученных при разрезании кусочков нужно резать отдельно от остальных?

Входные данные: Три целых положительных числа через пробел – $X, Y$ и $Z$ каждое из которых не превышает $2^{21}.$

Выходные данные: Одно целое число — минимальное количество разрезов.

Вход Выход
1 1 2 1
3 2 5 29

На что обратить внимание

  • Я сторонник аналитического подхода к этой задаче. Рассуждаем так. У нас один кусочек. Каждый разрез добавляет ещё один кусочек. Т.е. кусочков получается на $1$ больше, чем разрезов. Но мы легко можем вычислить сколько должно получиться кусочков — мы ведь знаем размеры.
F. Решение на C++

Задача G. Режем масло снова

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Имеется прямоугольный брусок масла размером $X \times Y \times Z.$ Плоскими разрезами его нужно разделить на кубики со стороной 1.
Какое минимальное число разрезов нужно будет сделать если разрезать можно сразу стопку из любого количества кусочков?

Входные данные: Три целых положительных числа через пробел – $X, Y$ и $Z$ каждое из которых не превышает $2^{21}.$

Выходные данные: Одно целое число — минимальное количество разрезов.

Вход Выход
1 1 2 1
3 2 5 6

На что обратить внимание

  • Теперь можно резать по несколько кусков сразу. Если не знаете как это, понаблюдайте как мама нарезает картошку маленькими кубиками. Она ведь режет сразу несколько пластинок, а не по одной?
  • Представьте, что у на некоторой стадии у Вас получилось два кусочка и один из них больше другого по всем размерам. Если Вы будете резать больший из них, то при этом заодно разрежется и второй.
    Это справедливо для любого числа кусков. Значит стоит рассматривать только самый большой кусок.
  • Стоит резать так, чтобы больший из кусков был поменьше. Т.е. примерно пополам (с округлением вверх).
  • Делим на два каждую из сторон до тех пор пока не получим единицу. Количество делений и есть ответ.
G. Решение на C++
Я привожу решение, которое использует логарифм по основанию два. Логарифмы изучаются только в конце выпускного класса. Если вы еще не добрались до логарифмов в школе, не беда. Просто напишите функцию f() при помощи цикла деления пополам с округлением в большую сторону и сосчитайте сколько раз придется делить. Код от этого не станет намного длиннее и работать будет также с близкой скоростью.

Задача H. Ибн аль-Хайсам задумался!

Лимит времени: 0.5 сек
Лимит памяти: 128MiB

Дано целое число $n$. Вычислите остаток от деления на $n$ произведение всех чисел от $1$ до $n-1.$

Входные данные: Целое число $n \left( 1 \lt n \lt 2^{31}\right).$

Выходные данные: Выведите значение выражения, требуемое в условии.

Вход Выход
7 6
10 0

На что обратить внимание

  • Если $n$ не является простым, то все его делители обязательно встретятся в качестве сомножителей при вычислении этого длинного произведения. Значит остаток будет равен нулю.
  • Ой! Число $4$ явно исключение из этого правила. Добавим для него условный оператор.
  • Остались простые числа. Понаблюдаем за ними написав цикл вычисления требуемого значения.
    Везде получается $n-1$? Попробуем отправить решение.
  • Если Вас заинтересовал последний факт и Вы хотите доказать его (хотя на соревновании достаточно простого удачного наблюдения), то Вы повторяете путь, который проделал в своё время Ибн аль-Хайсам. Сейчас этот результат принято называть теоремой Вильсона. Для неё напридумывали много простых и изящных доказательств. Даже геометрических. Но гораздо интереснее попытаться доказать ее самому. Там совсем не сложно догадаться.
H. Решение на C++
Функция prime() осуществляет прямую проверку числа на простоту. Т.е. просто перебираются все возможные нетривиальные делители. В приведенной ниже реализации сделаны некоторые весьма наивные попытки ускорить работу. Например, сразу исключены числа десятичная запись которых заканчивается на 0, 2, 4, 5, 6 или 8. Конечно, кроме самих чисел 2 и 5, которые являются простыми. Далее в цикле проверяются все возможные нечетные делители, т.к. чётные уже исключены. Перебор ведётся до $\sqrt{n}$. Из-за погрешности вычислений может быть пропущен делитель в точности равный $\sqrt{n}$. Чтобы избежать этой ситуации проверка ведется до $\sqrt{n+1}$. Задание единицы в виде 1.L приводит к тому, что вычисления выполняются с повышенной точностью ( long double). В данном случае эта перестраховка используется только как повод упомянуть этот полезный иногда тип данных.

Задача I. Настолько ли просты эти числа?

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

Число называется простым если оно делится только на 1 и на само себя. Найдите наибольший общий делитель всех введенных простых чисел.

Входные данные: В первой строке указывается количество простых чисел 1 < n < 10000. Во второй строке через пробел следуют n простых чисел меньших 231.

Выходные данные: Одно целое число — наибольший общий делитель всех введенных простых чисел.

Вход Выход
4
2 3 5 7
1

На что обратить внимание

  • В предыдущей задаче пришлось поработать с простыми числами. В этой почти тривиальной задаче мы закрепляем понимание их определения. Те участники, которые не смогли справится с предыдущей задачей получают эту в качестве некоторого утешительного приза.
  • Простые числа делятся только на 1 и на само себя. Значит наибольшим общим делителем может быть только один из этих двух вариантов.
  • Типичная ошибка — всегда выводить 1. Правильно было бы заметить, что если все числа одинаковы, то НОД всё же не 1, а само число.
I. Решение на C++

Задача J. Деньги

Лимит времени: 0.4 сек
Лимит памяти: 128MiB

В стране выпущены банкноты номиналом 500, 200, 100, 50, 20, 10, 5 и 1 гривну. А также монеты достоинством 0.5, 0.25, 0.1, 0.05, 0.02 и 0.01 гривны. Требуется найти способ выдать сумму в n гривен, используя наименьшее количество банкнот и монет.

Входные данные: Одно положительное действительное число n, не превышающее 1010, которое задаёт сумму с точностью до копеек.

Выходные данные: В одной строке следует вывести пары чисел через пробел — номинал банкноты (или монеты) и количество банкнот (или монет) этого номинала к выдаче. Значения следует перечислять в порядке увеличения номиналов денежных знаков.

Вход Выход
436.24 0.02 2 0.1 2 1 1 5 1 10 1 20 1 200 2

На что обратить внимание

  • Задача и простая и глубокая одновременно. Простая, поскольку решается интуитивно понятным жадным методом. Глубокая, поскольку может (и должна!) навести на мысли о поисках условия при которых этот жадный метод действительно даёт решение задачи. Т.е. каким условиям должны удовлетворять номиналы монет, чтобы жадный выбор давал оптимальное решение? Речь идёт о так называемых канонических монетных системах.
  • Жадный принцип требует начинать выдавать сумму с самых крупных купюр. Условие требует печатать ответ с самых мелких монет. Автор вредничает. Что делать? Конечно можно записать все количества в массив и напечатать его с конца. В приведенном ниже авторском решение используется другой подход — формируется строка ответа в которой новые данные вставляются в начало. Т.е. для формирования ответа можно использовать массивы или строки.
J. Решение на C++

Задача K. Одни плюсы

Лимит времени: 2 сек
Лимит памяти: 128MiB

Для заданного целого положительного числа n составьте равное ему арифметическое выражение, используя только операции сложения, умножения, скобки и число 1, содержащее минимально возможное число единиц.
Например, 7 = (1 + 1 + 1) * (1 + 1) + 1.

Входные данные: Одно целое положительное число n ≤ 104.

Выходные данные: Минимально возможное количество единиц.

Вход Выход
7 6

На что обратить внимание

  • Планировалась как самая сложная задача соревнования. Решение занимает целых 18 строк.
  • Задача относится к одному из самых красивых и популярных направлений в олимпиадном программировании. Имеется в виду так называемая «динамика» — динамическое программирование. Конечно, для решения задачи совсем не обязательно об этом знать, можно и так догадаться. Но знания и тренировка лучший помощник природной смекалке и сообразительности.
  • Для каждого числа есть возможность либо представить его в виде суммы единицы и числа на единицу меньшего, либо в виде произведения двух других чисел. Из этих двух вариантов выбираем тот в котором меньше единиц. А как узнать количество единиц в этих новых числах? Рекурсивным применением этого подхода. Рано или поздно мы получим просто 1 и процесс завершится.
  • Меморизация! Т.е. запоминание полученных результатов. Если мы уже вычислили кратчайшее представление некоторого числа (например, 2=1+1 или 5=(1+1)(1+1)+1), то это нужно запомнить и когда это число встретится в вычислениях снова, без повторных вычислений сразу использовать ранее полученный результат.
K. Решение на C++

Задача L. Комплексный обед

Лимит времени: 0.3 сек
Лимит памяти: 128MiB

В меню столовой имеется n блюд. Стоимость каждого блюда известна. Комплексный обед с точки зрения администрации должен состоять из двух блюд, имеющих общую стоимость не более k. Какое максимальное количество вариантов комплексных обедов можно составить если каждое блюдо может входить только в один комплексный обед.

Входные данные: В первой строке заданы два целых положительных числа n ≤ 105 и k ≤ 109. Во второй строке следуют через пробел целые положительные числа задающие стоимости каждого из этих n блюд.

Выходные данные: Максимально возможное количество вариантов комплексных обедов.

Вход Выход
5 8
1 9 7 2 4
2

На что обратить внимание

  • Задача «на сортировку» или «на жадные алгоритмы».
  • Если расположить все блюда по возрастанию (или убыванию) цены, то нам останется найти для каждого блюда из числа более дорогих парное из числа более дешевых.
  • Логика решения такова. Каждое блюдо из числа более дешевых (в порядке увеличения цены) должно найти себе пару из числа более дорогих. Если какое-то не нашло, то дальше нечего и пытаться — будет только дороже. Дорогие блюда просматриваем в порядке уменьшения цены. Если не подошло для данного блюда, то и для более дорогого тоже не подойдёт.
  • Никакого перебора не понадобится. Просто движемся по отсортированному массиву с двух сторон на встречу друг другу. Если текущее дорого блюдо образует с текущим дешевым пару, то увеличиваем счётчик комплексных обедов и переходим к следующему дорогому и следующему дешевому. Если цена этой пары блюд слишком велика, переходим к следующему блюду из числа дорогих.
L. Решение на C++

В завершение вставим таблицу результатов соревнования:

С чего начать?

Будем предполагать, что Ваша цель не просто изучить программирование, но и научиться решать задачи. Это означает, что Вы вероятно хотите получить в дальнейшем какую-то пользу от своих новых знаний и навыков, а не просто убиваете время. Сразу должен предупредить, что это потребует во много раз больше усилий, чем простое изучение синтаксиса и лексики С++, урду или клингонского языка.

Нам понадобится не только хороший учебник, но и хороший задачник с системой автоматической проверки. Ещё для занятия потребуют довольно много времени. А значит иногда придется работать не за привычным компьютером с установленной средой разработки, а с планшета или телефона. Предлагаю воспользоваться таким комплектом:

  • В качестве учебника возьмём книгу Липмана или Прата. — СКАЧИВАЕМ
  • В качестве задачника и тестирующей системы используем сайт e-olymp.com. — РЕГИСТРИРУЕМСЯ
  • Вместо установки на компьютер компилятора и среды разработки воспользуемся облачными технологиями через одну из простых онлайн IDE: IdeOne, TutorialsPoint C++, jDoodle. — РЕГИСТРИРУЕМСЯ при желании.
  • В качестве справочника стоит выбрать сайт cplusplus.com. Те немногие английские слова, которые придется запомнить для чтения материалов сайта в дальнейшем будут встречаться постоянно. — ИСПОЛЬЗУЕМ

Более подробные рекомендации и важные дополнения можно найти здесь.

Вы наверняка заметили, что в качестве языка программирования я без долгих пояснений выбрал С++. Вокруг выбора первого языка для начального изучения программирования ведутся бесконечные споры. Я не хочу даже пытаться включиться сейчас в эти святые войны. Хотя признаюсь, я не считаю, что у Вас в этом вопросе реально есть какой-то выбор. Даже если вам придется в дальнейшем перейти, например, на Java или C#, попытка использования С++ вероятно будет вполне рациональным расходованием времени.

Начинать следует с чтения учебника. Все понятные вещи стоит тут же попытаться закодировать и проверить на примерах. Если что-то не поняли, то тем более стоит попытаться закодировать. Прочитав две-три главы стоит взяться за решение задач. Я рекомендую прочесть этот текст и решать задачи по приведенному в нем списку. Здесь Вас будет ожидать неприятный сюрприз — во многих задачах придется много думать не о самом программировании, а о задаче. Не спешите писать 100500 строк лапшеобразного кода — подумайте. Практически все перечисленные задачи решаются в несколько строк.

План решения задач может быть таким
1. Линейные вычисления (182)
2. Программы с ветвлением (232)
3. Циклы (282)
4. Потоковая обработка (121)
5. Массивы (121)
6. Многомерные массивы (106)
7. Строки c-string (58)
8. Строки string (99)
9. Последовательные контейнеры (41)
A. Сортировки и жадность (17)
B. Стеки-деки-очереди (52)
C. Ассоциативные контейнеры (13)
D. Графы (56)
E. Дерево отрезков (18)
F. Динамическое программирование (22)
Спортивное программирование (19)

Как не нужно решать задачи

Есть довольно подробные рекомендации, как нужно решать задачи по программированию (в т.ч. для студентов). В конце заметки я дам ссылки на одну из таких статей.
Но я хотел бы сейчас привести наглядный пример того, как не надо решать задачи.
Вот довольно простая задача про разрезание брусочка сыра (точнее прямоугольного параллелепипеда) на кубики со стороной 1. Это одна из задач с которых первокурсники начинают у нас изучать программирование. Решается она одной формулой:

Моделирование и системный подход. Вся супер идея решения состоит в наблюдении, что разрезая что-либо несколькими параллельными разрезами, вы получаете на один кусок больше чем было разрезов. Например, один разрез — два куска. Правда сложно заметить?
Да, придется понаблюдать за тем, что происходит если производить дополнительные разрезы в перпендикулярном направлении. Т.е. после разрезов в одной плоскости получаются пластины, во второй — соломка, в третьей — кубики. Понаблюдайте:

    Именно так человек решает задачи.

  1. Читает условие — иногда несколько раз и обязательно все буквы. Отделяет существенное от неважного.
  2. Представляет себе описанный процесс и его конечный результат отсекая ненужные для решения детали.
  3. Пытается описать формулами процесс или результат. Упрощает формулы.
  4. И наконец — кладет руки на клавиатуру и кодирует.

Возможно Вы заметили, что в первом коротком решении мы не выполнили собственную рекомендацию — не упростили формулу. Действительно, хотя все измерения абсолютно равнозначны, формула не выглядит симметричной. Это сделано чтобы понятнее был процесс вывода формулы. Первое слагаемое [latex]A-1[/latex] в общем числе разрезов показывает как мы резали перпендикулярно оси [latex]Ox[/latex]. Мы сделали [latex]A-1[/latex] разрез и получили [latex]A[/latex] пластин. Второе слагаемое [latex]A\cdot\left(B-1\right)[/latex] показывает как мы резали перпендикулярно оси [latex]Oy[/latex]. Мы сделали [latex]B-1[/latex] разрез в каждой из [latex]A[/latex] пластин полученных при предыдущей серии разрезов. И наконец, на последнем этапе, мы режем каждый из [latex]A\cdot B[/latex] брусочков на кубики при помощи [latex]С-1[/latex] разрезов. Получаем [latex]A\cdot B\cdot\left(C-1\right)[/latex] разрезов. Конечно, результат не должен измениться, если резать в каком-то другом порядке. Если раскрыть скобки и привести подобные мы увидим короткую симметричную относительно измерений формулу.

[latex]\left(A-1\right) + A \cdot \left(B-1\right) + A \cdot B \cdot \left(C-1\right) = ABC-1[/latex]

Аналитический подход. Эта новая формула может быть получена другими очень простыми рассуждениями.

Вначале был один большой кусок. После каждого разреза количество кусочков увеличивается на 1. В самом конце получится [latex]ABC[/latex] кусочков, значит разрезов было на 1 меньше — [latex]ABC-1[/latex].

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

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

Код программы с новой формулой

Это правильный подход. Но как решает задачу человек, который полностью сконцентрирован на программировании. А он её вообще не решает! Он её программирует. Прочитав про разрезание пространственной фигуры в трех областях он уже кодирует трехмерный массив.

Я позаимствовал это решение с форума, но у нас имеются и свои подобные решения. Они работают правильно. Вот только долго. Но это еще не всё. Представляете количество времени потраченное на его качественную отладку и тестирование? А в реальных проектах этот код возможно потом придется долгие годы поддерживать и переписывать на новые языки программирования!
Чтобы разобраться как работает это второе решение достаточно посмотреть следующее видео

Пожалуйста! Не решайте задачи так!

В продолжение обсуждения этой темы советую прочесть, пока не очень вникая в детали этот текст на английском языке. Здесь довольно простая, но актуальная лексика. Т.е. от чтения двойная польза — и программирование, и английский.
Если чего-то не поняли, то лучше прочесть еще несколько раз. Но некоторые принципиально не читают на английском языке и для них сделали перевод.

Ровно 20 простых делителей

Задача. За 2 секунды проверить предположение о том, что у некоторого числа [latex]n \le 10^{18}[/latex] имеется ровно 20 простых делителей.
Попытаться решить задачу и проверить своё решение можно здесь.

Тесты

Вход Выход Примечание
10000000000 Yes [latex]2^{10}\cdot 5^{10}[/latex]
1048576 Yes [latex]2^{20}[/latex]
999999999987679232 Yes [latex]2^19 \cdot 1907348632789[/latex]
2 No [latex]2^{1}[/latex]
1000000000000000003 No Простое число. Немного выходит за пределы ограничения задачи, но допустимо для типов unsigned long long
1000000000012845056 Yes [latex]2^{19}\cdot 1907348632837[/latex] Немного выходит за пределы ограничения задачи, но допустимо для типов unsigned long long
99999989699999923 No [latex]99999989 \cdot 1000000007[/latex]
8388608 No [latex]2^{23}[/latex] — слишком много делителей

Решение

Идея решения состоит в попытках деления исходного числа [latex]n[/latex] на последовательно увеличивающиеся целые числа [latex]d,[/latex] начиная с двойки. Если удается произвести деление без остатка, то очередной делитель найден. Исходное число можно разделить на этот делитель и в дальнейшем искать делители полученного частного, т.е. [latex]n \leftarrow \frac{n}{d}.[/latex] Теперь нам остается найти на один делитель меньше. Такая процедура должна будет успешно завершиться ровно 19 раз. Частное от последнего 19-го деления должно оказаться простым числом — тогда простых делителей окажется ровно 20.
При подготовке тестов выяснилось, что трудности могут вызывать следующие ситуации:

  1. No — отрицательный вердикт: слишком мало делителей. В худшем случае одно большое простое число.
  2. Yes — положительный вердикт: 19 небольших делителей и большой 20-й. В худшем случае рассматривается число [latex]2^{19} \cdot 1907348632789 = 999999999987679232[/latex]

В обоих случаях трудности вызывает поиск делителей довольно большого простого числа. Необходимо аккуратно ограничить диапазон поиска возможных делителей так, чтобы не выполнять излишней работы, но и не пропустить делителей.
Зададимся вопросом, как долго нам придётся перебирать возможные делители (начиная с числа 2) пока не встретим первый (наименьший) делитель?
Рассмотрим первый случай (слишком мало делителей). Пусть нам известно, что число имеет [latex]m[/latex] делителей. Первый, встретившийся нам делитель (т.е. наименьший) должен быть таким, чтобы [latex]d^{m} \le n, [/latex] т.е. [latex]d \le n^{\frac{1}{m}} = \sqrt[m]{n}.[/latex] Это очень хорошее ограничение, т.к. в первом случае нам придется перебирать возможные делители до [latex]\left( 10^{18} \right)^{\frac{1}{20}} = 10^{\frac{18}{20}} \le 7.[/latex] Это совсем немного вариантов. Т.е. достаточно проверить деление на 3, 5 и 7 для самого большого возможного [latex]n[/latex]. При правильном выборе границ поиска «страшный» случай огромного простого числа [latex]n[/latex] оказывается очень лёгким.

Границы поиска делителей в худшем случае
Чуть сложнее оказывается ситуация когда есть один маленький делитель (например, 2). Тогда при поиске следующего делителя нам придутся работать с числами [latex]n \le \frac{10^{18}}{2} = 5 \cdot 10^{17}.[/latex] Поскольку теперь останется найти не 20 а только 19 делителей? то ограничение на возможное значение минимального делителя станет таким: [latex]\left( 5 \cdot 10^{17} \right)^{\frac{1}{19}} = \sqrt[19]{5 \cdot 10^{17}} \le 8.[/latex] Что даёт тот же набор возможных простых делителей. Давайте посмотрим, как у нас будут изменяться границы поиска в худшем случае. Т.е. для максимально большого [latex]n[/latex] и делителях равных 2. Рассуждая аналогичным образом можно рассчитать границы поиска остальных делителей в худшем случае:

[latex]m[/latex] Граница поиска в худшем случае
20 7
19 8
18 9
17 10
16 11
15 12
14 14
13 16
12 19
11 24
10 31
9 42
8 62
7 102
6 198
5 497
4 1976
3 19686
2 1 953 125
1 1 381 067

Как видим значения вполне доступны для полного перебора за 1-2 секунды на обычном персональном компьютере.
Случай с последним делителем будет рассмотрен отдельно далее.

Теперь рассмотрим второй случай. У нас имеется 19 маленьких делителей (в худшем случае это двойки) и одно большое простое число. Насколько большие делители нужно проверить прежде чем заключить, что оставшееся число простое?
Оставшееся после 19 делений на два число не может превышать [latex]\frac{10^{18}}{2^{19}}=0.5 \cdot 5^{18}.[/latex] Если оставшееся число не является простым, то у него должен быть делитель не превышающий квадратного корня из этого числа. Т.е. поиск делителей в этом последнем случае не может продлиться дольше чем до [latex]\sqrt{0.5 \cdot 5^{18}} = 1381067.[/latex]

Код

Составим простую программу по описанному алгоритму.
Код программы можно запустить здесь.
В программе есть два нюанса, на которые следует обратить внимание. Оба они относятся к 8-й строке кода и касаются вычисления верхней границы в цикле подбора делителей.

  • При извлечении корня может быть получено неточное значение. Это связано как с ошибкой округления. Например, при работе с числами типа double [latex]\sqrt[3]{1000000}[/latex] оказывается не 100, как мы ожидаем, а примерно [latex]99.9999999999999716.[/latex] Из-за этого мы можем не найти делитель в точности равный правой границе интервала поиска. Для компенсации возможной ошибки к правой границе была добавлена некоторая небольшая величина. Конкретное значение выбирается на основании пессимистической оценки возможной погрешности.
  • Верхняя граница поиска делителей не превышает [latex]\sqrt[m]{n}[/latex] если число делителей [latex]m \ge 2.[/latex]. Когда мы хотим убедиться, что последнее [latex]\left(m=1\right)[/latex] оставшееся число является простым, мы ищем его делители до [latex]\sqrt[2]{n}.[/latex]. Т.е. предполагаем, что число не простое и ищем его делители.

Задание

Существенным недостатком программы является то, что она перебирает в качестве возможных простых делителей все чётные числа. Естественно, ни одно из них (кроме 2) не может оказаться простым делителем и работа выполняется впустую. Можно надеяться существенно уменьшить время работы программы за счёт правильной организации перебора возможных делителей.
Попытайтесь это сделать.

Числа Фибоначчи

Рассмотрим общеизвестный ряд чисел A000045:
[latex]0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, \ldots[/latex] Этот ряд представляет собой неотрицательную ветвь последовательности Фибоначчи. Будем считать, что последовательность задаётся следующим рекуррентным соотношением
[latex]f_n=\left\{\begin{matrix}
0, & n=0\\
1, & n=1\\
f_{n-1}+f_{n-2}, & n>1
\end{matrix}\right.[/latex]

Давайте напишем функцию, которая вычисляет [latex]n[/latex]-е по порядку число Фибоначчи, используя приведенное соотношение:

Для теста мы вывели на печать вычисленное этим способом 6-е по порядку число Фибоначчи. Программа напечатала 8. И не ошиблась. Давайте посмотрим как происходили вызовы функций:

Порядок вызовов при вычислении шестого по счёту числа Фибоначчи по прямому рекурсивному алгоритму

Порядок вызовов при вычислении шестого по счёту числа Фибоначчи по прямому рекурсивному алгоритму

Легко видеть, что для вычисления каждого числа Фибоначчи (кроме двух первых) выполняется строго два вызова функции. Т.е. если нам понадобится вычислить, следующее (седьмое) число Фибоначчи, то количество вызовов практически удвоится. И действительно, каждое следующее число вычисляется вдвое дольше, чем предыдущее. При наличии терпения ещё можно как-то дождаться конца вычисления 50-го числа, но дальше вычисляется уж очень долго.
В чём причина? Почему человек, вычисляя на листе бумаги, легко обгоняет компьютер?
Конечно, неэффективный алгоритм.
На рисунке цветом выделены те блоки, вычисление которых действительно необходимо. Число таких блоков растёт с увеличением номера числа линейно, говорят [latex]O\left( n\right)[/latex]. А вот остальные блоки — сплошные повторы и их число растёт как [latex]O\left( 2^n\right)[/latex].
Попробуйте изменить программу так, чтобы она работала быстро (без повторных вычислений.
В качестве упражнения, я попрошу не использовать циклов.
После того, как у Вас всё получится (или окончательно опустятся руки), загляните под спойлер и постарайтесь разобраться с моим вариантом решения задачи.
Рекурсивное решение без повторов

Мотивация

Мотивация это то, что заставляет нас поступать так, как мы поступаем. В этой заметке я хотел бы предложить несколько причин, по которым стоит глубоко изучать (и практиковать!) математику, алгоритмы и программирование именно с точки зрения студентов нашего университета.
Конечно, основной мотивацией является хорошее трудоустройство, интересные проекты, высокая зарплата и хорошее интересное общение. Всем этим не обделены специалисты в области информационных технологий и разработки программного обеспечения. Я уже рассказывал о наших студентах, успешно занимающихся спортивным программированием, которые проходят стажировки в Google, Facebook и конечно в местных филиалах компьютерных фирм. Рассказывал также об основанном нашими студентами успешном стартапе Looksery, который весной этого года был приобретён компанией Snapchat за 150 миллионов долларов.

Письмо из Google

Письмо из Google

Недавно появилось ещё одно свидетельство внимания крупных компаний к нашим выпускникам.
За последнюю неделю выпускники прикладной математики разных лет получили похожие письма от компании Google с приглашением на работу. Приглашение в частности обосновывается высоким уровнем подготовки выпускников ОНУ уже работающих в компании. Здесь приводится копия экрана с текстом письма Андрею Терещенко. Аналогичные письма получили Кирилл Чеканов, Михаил Герасименко, Денис Щелконогов и др. Поиск наших выпускников Google провёл по профессиональной социальной сети linked.in.

Какие не очевидные выводы должен (или может?) сделать студент младших курсов?
Конечно, основный вывод в том, что нужно учиться и наш университет для этого подходит.
Второй вывод — не следует ограничиваться обязательной программой. Подготовки «по конспектам» совершенно недостаточно. Нужно читать книги, использовать интернет для самообразования, посещать дополнительные занятия по субботам и искать другие профессиональные мероприятия. В частности очень полезно участие в спортивных соревнованиях программистов. И дело тут не только в соревновательном аспекте. Контесты хороший повод попытаться решать задачи, а не учебные примеры на определённую тему. На соревновании Вы должны выбрать задачу, которую вероятно сможете решить и выбрать те из своих знаний и навыков, которые приведут Вас к цели. Это позволяет трезво оценить накопленные навыки и знания, а при необходимости внести корректировки в процесс своего обучения.
И третий вывод — сообщайте миру о себе и своих возможностях. Для этого хорошо подходит linked.in. Обязательно фиксируйте там все свои достижения — прохождение учебных курсов, освоение новых технологий, языков (и человеческих и машинных).

Это всё со стороны студента. А какая мотивация у преподавателя? Стыдно признаться, но единственный разумный ответ мне подсказывает неизвестный переводчик одиннадцатого сонета Шекспира

Ничто не вечно под луной. Но жизнь
Бессмертна эстафетой поколений.
Коль этим даром, друг мой, дорожишь,
Оставь свой след, отбросив яд сомнений.

Пусть красота живительной струёй
В преемнике, как Феникс, возродится,
А бездарь обойдёт вас стороной.
И злу чтоб не дано было свершиться.

Иначе человечеству конец
и жить ему лишь шесть десятилетий.
Хвала природе, ты – её венец,
За сохраненье рода ты в ответе.

Да не иссякнет мудрости печать,
Что ты сумел потомкам передать!

Related Images:

Дистанционные учебные курсы

stepik.org

stepik.org

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

  • Ввыедение в С++ — для не очень уверенных в себе студентов. Решение простых задач без привлечения серьезных возможностей яззыка.
  • Программирование на языке C++ — обязательный для всех. Действительно что-то говориться о С++ и ООП.
  • Основы программирования на C. Задачи. Этот курс относится к языку Си, а не С++. Но он достаточно полезен для нас тем, что мы увидим классические средста ввода вывода и научимся отличать новые возможности С++ от классики императивного программирования. В этом курсе только ссылки на теоретический материал но огромное количество задач. Иногда число однотипных задач очень велико и это несколько утомляет, но судя по комментариям, многим это полезно. Если набраться терпения и пройти все 270 заданий, вы обоснованно почувствуете себя достаточно уверенно.
coursera.org

coursera.org

В продолжение хочу порекомендовать пройти некоторые дистанционные учебные курсы на сайте Coursera.
Чтобы не актуализировать постоянно ссылки и даты буду просто вставлять в начало ссылки. Надеюсь разберетесь на месте.

http://www.princeton.edu/

http://www.princeton.edu/

Продолжение может быть таким:

  • 10 октября 2016 стартует курс по Структурам данных. Довольно полезный. К сожалению, все больше учебных курсов становятся платными. Однако, есть возможность получить его бесплатно как вольный слушатель. Сертификата Вам в этом случае не выдадут, но знания получите
  • Во-первых, 3 октября 2016 началась первая часть учебного курса по Алгоритмам. Один из ведущих преподавателей знаменитый Роберт Седжвик. Даже если Вы опоздали к указанной дате (даже на год или два) стоит записаться и пройти.
  • Во-вторых, одновременно с предыдущим запускается ещё один курс Седжвика — Анализ алгоритмов

Заявленная трудоёмкость каждого из этих курсов 6-8 часов в неделю. Продолжительность — до начала марта.
Хочу предупредить, что оба курса очень сложны и реально придётся потратить много больше времени, чтобы во всём полностью разобраться.

По обоим курсам указано, что

No certificates, statements of accomplishment, or other credentials will be awarded in connection with this course.

Однако, за успешное прохождение курса я буду начислять баллы в рамках второго семестра курса по программированию.

http://online.stanford.edu/

http://online.stanford.edu/

Наша выпускница Татьяна Полунина порекомендовала другой курс, который только начался 3 октября 2016. Я не знаком детально с этим курсом, но полностью полагаюсь на рекомендацию и добавляю курс в список:

Это курс из Стэнфордского университета и по окончании можно получить сертификат от преподавателя.

Также можно пройти курс Основы алгоритмов. Это первый из набора в шесть курсов. Если брать все шесть, то нужно платить. Если брать каждый по очереди и без сертификата, то получится бесплатно.

Не все студенты морально готовы проходить онлайн курсы на английском языке. Я уверен, что это стоит делать при любом уровне невладения английским. Однако, идя на уступки этой нерешительности, рекомендую несколько полезных курсов на русском языке. Все они стартуют с понедельника 10 октября 2016 и подготовлены для Coursera сотрудниками МФТИ.

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

Решаем задачи

Чтобы тренироваться решать задачи мы будем чаще всего использовать сайт e-olymp.com. Также можно обратиться к

  • codewars.com — Решаем задачи («ката») разного уровня сложности и набираем уровень.
  • programmr.com — Будьте внимательны, есть ошибки в тестах. Например, задача на площадь треугольника предполагает целочисленное деление при вычислении полупериметра. (Проверялось 11.5.2017).
  • tutorialspoint.com — учебный курс с задачами.

Образец: Принадлежит ли точка треугольнику?

Задача. Даны три попарно не совпадающие и не лежащие на одной прямой точки [latex]A, B[/latex] и [latex]C[/latex], заданные своими координатами. Определить принадлежит ли точка [latex]D(x_d,y_d)[/latex] треугольнику [latex]ABC[/latex].
Сразу заметим, что задача легко обобщается для любого выпуклого многоугольника.

Тесты

В тестах нужно обязательно отразить следующие случаи:

  1. Точка строго вне треугольника
  2. Точка строго внутри треугольника
  3. Точка совпадает с одной из вершин треугольника
  4. Точка лежит на одной из сторон треугольника
  5. Точка лежит на продолжении одной из сторон треугольника
  6. Одна из сторон треугольника параллельна одной из осей координат
  7. Две стороны треугольника параллельны осям координат
xa ya xb yb xc yc xd yd Принадлежит?
-1 -1 1 -1 0 1 2 2 нет
-2 -2 1 -1 0 1 0 0 да
-1 -1 1 -1 0 1 0 1 да
-1 -1 1 -1 0 1 0.5 0 да
-1 -1 1 -1 0 1 1 3 нет
-1 -1 1 -1 0 1 0 0 да
0 0 2 0 0 2 1 1 да
0 0 2 0 0 2 5 5 нет

Плохое решение

В школьных учебниках такие задачи часто рекомендуют решать проверкой условия [latex]S_{ABC}=S_{ABD}+S_{BCD}+S_{CAD}[/latex]. При компьютерной реализации это приводит к необходимости сравнения двух действительных чисел на равенство. Эта крайне неприятная операция может быть проделана только с определённой степенью достоверности. Т.е. придётся проверять не превышает ли некоторого «с потолка» выбранного малого числа абсолютное [latex] \left| S_{ABD}+S_{BCD}+S_{CAD}-S_{ABC} \right| < \varepsilon[/latex] или относительное [latex]\left| 1-\frac{S_{ABD}+S_{BCD}+S_{CAD}}{S_{ABC}} \right| < \varepsilon[/latex] отклонение. Оставим эти вопросы для курса численных методов и методов приближённых вычислений и не будем идти по этому пути.

Неплохое решение

Начнём с простого наблюдения:

Все точки треугольника (и любого выпуклого многоугольника) должны лежать по одну сторону от прямой, проходящей через каждую его сторону.

Запишем уравнение прямой, проходящей, например, через точки [latex]A[/latex] и [latex]B[/latex]. Получим [latex] \left( x-x_A \right) \left( y_B-y_A \right)-\left( y-y_A \right) \left( x_B-x_A \right) = 0[/latex]. Уравнение я записал в такой форме, чтобы не приходилось выполнять деление и переживать о нуле в знаменателе.

Неважно как называть стороны, важно научиться их различать.

Неважно как называть стороны, важно научиться их различать.

Теперь для любой точки [latex] \left( x;y \right)[/latex] мы можем вычислить левую часть приведенного равенства. Для точек, лежащих на прямой мы должны получать ноль. В тоже время прямая разобьёт плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения. А точки из другой полуплоскости — отрицательные.
Мы готовы проверить первое условие — принадлежит ли точка [latex]D \left( x_d,y_d \right) [/latex] той же полуплоскости, что и точка [latex]C \left( x_c,y_c \right) [/latex] относительно прямой [latex] \left( AB \right) [/latex]? Для этого подставим обе точки в левую часть приведенного выше уравнения прямой и убедимся, что получены значения одного и того же знака. А если одна из точек даст точно ноль? Это означает, что точка лежит на прямой. По условию задачи это может быть только точка [latex]D[/latex]. Тогда она принадлежит треугольнику независимо от знака выражения, вычисленного для точки [latex]C[/latex].

Обратите внимание, что мы не утверждаем, что для любой точки на прямой наши приближённые вычисления обязаны дать точный ноль. Это было бы неверно. Мы только утверждаем, что если проведенные с доступной нам точностью вычисления всё же дали точный ноль, то мы вынуждены считать данную точку лежащей на данной прямой.

Естественно, что нам придётся записать аналогичные условия для двух оставшихся сторон треугольника (или для всех оставшихся сторон выпуклого многоугольника).

Плохой код

Начнём с того, что объявим переменные и прочитаем их значения. После этого запишем одно очень громоздкое условие, которое и проверяет принадлежность.

Нажмите здесь, чтобы выполнить этот код.

Приведенный код имеет существенные недостатки. Нам пришлось трижды записывать уравнение прямой проходящей через две точки и дважды подставлять в каждое из них координаты, чтобы проверить знак. Это значит, что нам пришлось шесть раз написать некоторую формулу с различными подстановками. При том подходе, что мы использовали имеем две проблемы. Во-первых, условие стало слишком сложным, чтобы его можно было легко воспринять. Во-вторых, и это гораздо хуже, такой код в [latex]\frac { 1-{ \left( 1-p \right) }^{ 6 } }{ p }[/latex] раз увеличивает вероятность совершить ошибку. Забавно, но это означает, что вероятность ошибки начинающего программиста увеличивается вдвое, а у опытного — в шесть раз. Хорошо, что опытные программисты не пишут такой код.

Неплохой код

Воспользуемся тем, что мы уже умеем создавать собственные функции для того, чтобы несколько сократить объём кода и сделать его более лёгким для восприятия.
Запишем условие на языке программирования С++:

Нажмите здесь, чтобы выполнить этот код.
Трудно сказать, стал ли код боле понятным или лаконичным. Однако можно точно сказать, что в нём отсутствуют повторяющиеся алгоритмические блоки. Все участки кода написаны строго по одному разу. Это уменьшает вероятность ошибки.

Чеширский код

Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать...

Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать…

Возможно слишком смело называть это хорошим кодом, но мы сделаем ещё один шаг в нужном направлении. В прошлом коде мы избавились от повторов в кодировании алгоритма. Однако остались повторы в кодировании данных. Вы заметили, что у нас четыре пары переменных? Т.е. просматривается структура состоящая из пары координат x и y, которую стоит объединить и назвать «точкой». Такие структуры в программировании на Си описывают с помощью ключевого слова struct. Это полезная промежуточная структура перед переходом к объектно-ориентированному программированию при помощи классов.

Нажмите здесь, чтобы выполнить этот код.
Вы заметили как забавно увеличивается размер программы по мере того, как мы пытаемся сделать его более логичным и наглядным? Это характерно для маленьких программ. Такие дополнительные структуры становятся всё более оправданными для больших и огромных программ.