There are N points on a plane. Convex hull is such a
convex polygon with the least possible area, that all the given points
are either within its interior or belong to its border.
Let's say that one convex polygon is smoother that the other one
if it's sharpest angle is more obtuse than the sharpest angle of the other
one.
Your task is to make the convex hull of the given set of points as smooth
as possible. To do it you are allowed to exclude no more than one point
from the given set.
Input file format
Input file contains integer N, then N
pairs of real numbers xiyi describing given points.
There are no duplicate points in the input file.
Output file format
Output file must contain a single number: the sharpest angle (in radians)
in the most smooth convex hull with absolute error less than 0.01.
Восьмая всероссийская командная олимпиада школьников по программированию
Ограничение времени:
2 сек
Входной файл:
convex.in
Ограничение памяти:
256 Мб
Выходной файл:
convex.out
Условие
Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно
содержит также и отрезок, соединяющий эти точки.
Минимальное по включению множество, содержащее
заданное множество точек X, называется выпуклой оболочкой множества X.
В этой задаче вам требуется найти выпуклую оболочку множества точек,
принадлежащих заданному набору углов.
Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной
точки. Эта точка называется вершиной угла.
На рисунке слева приведены два угла, на рисунке справа изображена их выпуклая оболочка.
Формат входного файла
Первая строка входного файла содержит число n — количество углов.
Каждая из следующих n строк описывает углы.
Каждый угол описывается координатами трех точек: вершины
и двух отличных от вершины точек — по одной на каждом из лучей.
Формат выходного файла
Выведите в выходной файл границу выпуклой оболочки в виде последовательности
направленных лучей, прямых и отрезков. Никакие два объекта в выходном файле
не должны лежать на одной прямой. Все отрезки должны иметь длину больше нуля.
Объекты должны быть перечислены в таком порядке, чтобы начало каждого следующего
совпадало с концом предыдущего. Все числа в выходном файле должны быть целыми
и не превосходить 105 по абсолютной величине. При проходе
вдоль описанной границы выпуклая оболочка углов должна быть справа.
На первой строке выведите l — количество объектов в ответе. Следующие l строк должны со-
держать описание объектов. Объекты описываются следующим образом:
Отрезок: "segmentx1y1x2y2", где (x1, y1) и (x2, y2) —
концы отрезка, отрезок считается направленным от (x1, y1) к (x2, y2).
Луч, направленный от начала: "outrayx1y1x2y2",
где (x1, y1) — начало луча, а (x2, y2) —
произвольная точка на луче, отличная от начала.
Луч, направленный к началу: "inrayx1y1x2y2",
где (x2, y2) — начало луча, а (x1, y1) — произвольная точка на луче,
отличная от начала.
Прямая: "linex1y1x2y2", где (x1, y1) и (x2, y2) —
две точки на прямой, причем при движении вдоль прямой в ее
направлении точка (x1, y1) следует ранее точки (x2, y2).
Если выпуклой оболочкой является вся плоскость, то выведите l = 0.
Ограничения
1 ≤ n ≤ 1000
Все координаты целые и не превышают 104 по абсолютной величине.
Величина угла находится в диапазоне от 0 до 180 градусов, не включительно.
You are to write a program that receives two strings and finds position where the second string appears in the first
one as a substring.
Input file format
First and second lines of input file contain given strings. Each string is a sequence of lower-case Latin letters from 'a'
to 'z' and spaces.
Output file format
Output file must contain a single integer — position of the first occurrence of the substring in a string, or − 1 if there is none. Positions are numbered from 1.
Constraints
Length of each string does not exceed 100000 characters.
A computer programmer and mathematician Kumar Harikrishnan
develops a new data compression system —
ACM (Advanced Compression Method) — which will incorporate all of his brilliant ideas.
The first component of ACM will be a modification of well-known RLE algorithm, called
Improved RLE. Since Kumar have much more difficult tasks to accomplish (such as to write
Improved Hamming and Improved Lempel-Ziv),
he asks you to implement this simple, yet important part of a system.
An algorithm should replace repeating substrings of source string
with a single instance of substring concatenated with the number of repetitions.
If some substring should not be repeated, it is concatenated with number 1.
Your program must find the shortest possible compression of the given string.
Input file format
A single line of input file contains the string to be compressed.
It may contain spaces, but does not contain digits as Kumar has invented a complex
digit-escaping system to prevent uncompressing ambiguity.
Output file format
Output file must contain minimal length compression of the source string.
There should be no extra whitespace characters before or after the string.
Constraints
Length of the source string is from 1 to 1000 characters.
The game of fool is played with a small set of cards, which includes nine
ranks - 6, 7, 8, 9, 0 (10), J (Jack), Q (Queen), K (King), A (Ace) of the four suits
each - h (Hearts), s (Spades), d (Diamonds) and c (Crosses). So, for example a queen
of spades is denoted Qs, and a ten of diamonds is 0d. One of the suits is declared a
trump. During the game, the card beats another card, if either it has the same suit and
higher rank, or it is a trump, while the beaten card is not.
In the game, a move proceeds as following. First player puts one of his cards on
the desk, and the second player can either beat it with one of his cards, putting his card
over it, or take it, if he has no suitable card. If the card is beaten, first player may flip in
any of his remaining cards, which has same rank as any card already on the desk. This
card, in turn, may be beaten or taken together with all other cards on the desk, etc. For
example, if first player has cards 6s6dQhKd, the second player has 6h7h0sQd and
hearts are the trumps, then first player can move with Kd, which is beaten with 6h, then
flip in 6s, beaten by 0s, then 6d, beaten by Qd and at last Qh, which can not be beaten
with 7h, so the second player has to take it.
Your task is to write a program that, given the trump suit and first and second
playerTs cards, determines for the first player such a move as to eventually make the
second player take.
Your task is to write a program that, given the trump suit and first and second
playerTs cards, determines for the first player such a move as to eventually make the
second player take.
If there is more than one such move, the program must find one with smallest
rank. If there is several moves with smallest rank, program must choose the card with
the first suit in the order mentioned in the first paragraph (i.e. h < s < d < c). In the
example above, second player could beat Kd with 7h, thus preventing further flips. On
the other hand, move of Qh will be immediately taken.
Input file format
In the first line of input file there is a single character h, s, d, or c, determining a
trump suit. On the second line there is a string denoting first playerTs cards, and on the
third line S the string with the second playerTs cards. All cards are different, and the
players have equal number of cards.
Output file format
Output file must contain a single line with either a card to move or a string "NO",
if a program was unable to find it.
По мотивам романа А. и Б. Стругацких “Понедельник начинается в субботу”.
Очередной понедельник выдался в НИИЧАВО
(Научно-Исследовательский Институт ЧАродейства и ВОлшебства) на удивление беспокойным.
Началось все с проблем в отделе исследования живой, мёртвой и водопроводной воды,
куда на прошлой неделе завезли новый аквариум.
Туда и вошел Привалов в самый интересный момент беседы между
Амвросием Амбруазовичем Выбегалло и заведующим отделом смысла жизни Кристобалем Хозевичем Хунтой.
Сейчас Кристобаль Хозевич в красках описывал,
какие могут возникнуть повреждения всей новейшей системы безопасности,
недавно установленной в институте, от всего того количества воды,
которым сейчас затапливался его отдел.
— Подождите, остановил его речь Выбегалло, вот закончим проверку и выключим воду.
— Да какая же это проверка, это же чистой воды саботаж! —
возмущался Хунта, вот сейчас заделаю все дырки в вашем аквариуме, и тогда будем разговаривать.
— Нет, это категорически невозможно! — Возражал Выбегалло, — как вы себе это представляете?
Мы проводим важнейший эксперимент!
— Может быть, объясните, что здесь все-таки происходит? - вмешался в разговор Привалов
— Позвольте, я объясню, начал было Выбегалло, но Кристобаль Хозевич не дал ему закончить,
и, сделав руками несколько пассов, произнес, — вот теперь порядок, ничего не вливается и не выливается, можете объяснять.
— Ну, раз вы все-таки запечатали отверстия, то спешки особой нет, —
продолжил Амвросий Амбруазович, — на прошлой неделе мне, доставили новый большой аквариум,
необычной конструкции, а если быть точным, с несколькими прямоугольными
отверстиями на лицевой стороне, вот посмотрите.
Привалов, наконец, осмотрел новый аквариум. Он представлял собой
прямоугольный параллелепипед размерами W × H × L метров без верхней крышки,
на лицевой стороне которого было вырезано N квадратных отверстий
c длиной стороны ai метров. Сверху над аквариумом висела большая труба,
через которую в него поступало M кубических метров воды в секунду.
— Так вот, — продолжил Выбегалло, —
до появления здесь Кристобаля Хозевича мы проводили эксперимент,
целью которого было определить уровень воды в этом аквариуме при заданной конфигурации отверстий.
— А более сухого способа вы не нашли, — вставил свою реплику Хунта
Привалов, как программист, прекрасно понимал,
что для таких экспериментов вовсе не обязательно затапливать пол-института.
Нужно лишь определить скорость вытекания воды из отверстий и
описать весь эксперимент очень простой компьютерной моделью.
Свои соображения он и изложил собравшимся.
— Замечательная идея, молодой человек, — произнес Выбегалло, — это ж сколько средств то можно сэкономить, да и воду тратить не придется.
Через несколько минут он передал Привалову формулу расчета потока воды из отверстий в аквариуме.
Поскольку аквариум до эксперимента был специально заколдован, формула была оказалась простой:
через отверстие площадью b квадратных метров
в одну секунду будет вытекать V × b кубических метров воды.
В начале эксперимента аквариум пуст. Через некоторое время после того, как
из трубы начнёт поступать вода, уровень в воды в аквариуме стабилизируется
(либо аквариум переполнится).
Теперь осталось только написать программу, определяющую высоту стабильного уровня воды.
Формат входного файла
Входной файл содержит числа VMN —
соответственно скорость вытекания воды (в м / с), поток втекающей воды (м3 / c)
и количество отверстий в лицевой стороне аквариума. Далее следует N троек
чисел xiyiai — координаты нижнего левого угла и длина стороны. отверстия номер i.
Отверстия не пересекаются и не соприкасаются друг с другом.
Формат выходного файла
Выходной файл должен содержать единственно число — высоту уровня воды в аквариуме
с точностью до четырех знаков после запятой, либо − 1, если аквариум переполнится.
Ограничения
0 < V, M ≤ 1000,
0 ≤ N ≤ 100,
0 ≤ xi, yi, ai ≤ 106.
Прямоугольная рамка была разрезана на N кусков.
Каждый кусок может представлять собой либо отрезок прямой, либо "уголок" — два отрезка,
соединённых под прямым углом.
По данным длинам отрезков требуется восстановить исходную рамку или определить,
что это невозможно.
Куски можно поворачивать, но нельзя отражать. Требуется использовать все куски.
Формат входного файла
Входной файл содержит число кусков N, за которым следуют N пар целых чисел aibi,
описывающих длину двух отрезков "уголка" i-го куска.
Если кусок является отрезком, то ai = 0 либо bi = 0.
Формат выходного файла
Выходной файл должен содержать два положительных целых числа WH —
ширину и высоту рамки, при этом W ≥ H.
Если решения не существует, следует выдать число − 1.
Если решений несколько, следует выдать решение с максимальным значением W.
Пешеход переходит дорогу, состоящую из K полос автомобильного движения. Он заметил N автомобилей, каждый из
которых движется по своей полосе движения wi и пересечет место перехода дороги через bi секунд.
Пешеход НЕ может останавливаться между полосами дороги. Он может остановиться только у одного из краев
дороги. Если же он находится на разграничителе полос, то он обязан переходить одну из соседних полос,
то есть двигается вперед или назад.
При этом, если он уже начал переходить полосу, то он не может остановиться и пересечение очередной
полосы движения займет у него время t.
В начальный момент времени пешеход находится на
краю дороги, ближайшая к которому полоса имеет номер 1. Дорога считается бесконечной в обе стороны.
Пешеход может двигаться только по прямой, перпендикулярной дороге, то есть, он идет или ждет на
одном из краев дороги,
или идет прямо, или назад. Найдите минимальное время, за которое пешеход может перейти дорогу (пересечь все ее
полосы движения) и не оказаться сбитым машиной. Пешеход считается сбитым машиной i, если момент времени
bi он оказался на полосе wi. Но если он в это время находился между полосами или в начале и в конце
пути, то машина его не задевает.
Формат входного файла
Во входном файле содержатся числа K,N,t, за которыми следует N пар чисел wi и bi
Формат выходного файла
В выходной файл выведите единственное число - минимальное время, за которое переход может перейти дорогу.
В приведенном ниже примере пешеход ждет десять секунд, после чего переходит обе полосы не останавливаясь.
Ограничения
0 ≤ N ≤ 2 * 105, 1 ≤ K,t ≤ 100, 0 ≤ bi ≤ 104,
1 ≤ wi ≤ K
Чтобы наловить шушанчиков, Крокодил Гена отправляется в лес с чемоданом и ружьём, стреляющим усыпляющими дротиками.
В лесу он становится в точку с координатами (XG; YG) и начинает внимательно смотреть по сторонам.
Как только Гена видит шушанчика, он тут же стреляет в него, и скоро спящий шушанчик оказывается в чемодане Крокодила.
Гена всегда стреляет мгновенно и точно.
Лес состоит из N деревьев. На плане i-ое дерево можно представить в виде
круга с координатами центра (Xi; Yi) и радиусом Ri. Гена видит все точки с координатами (x, y), такие, что
отрезок (x; y) − (XG; YG) не пересекает ни одно дерево.
Один шушанчик, гуляя по лесу, пришёл в точку с координатами (XS; YS).
Услышав, что Крокодил Гена в лесу, он бросился бежать в нору с координатами (XH; YH).
Требуется определить, сможет ли шушанчик добраться до норы так, чтобы Гена его не увидел.
Формат входного файла
Входной файл состоит из K тестов. В первой строке входного файла содержится число K.
Далее следуют описания тестов.
Каждый тест описывается числами XSYSXHYHXGYGN, за которыми следуют
N троек чисел XiYiRi.
Формат выходного файла
В выходном файле должно содержаться K строк, каждая из которых
должна равняться ESCAPE, если шушанчик из соответствующего теста сможет
добраться до норы, или CATCH, если не сможет.
Ограничения
1 ≤ K ≤ 10
− 100 ≤ XS, YS, XH, YH, XG, YG, Xi, Yi≤ 100
1 ≤ Ri ≤ 100, 0 ≤ N ≤ 100
Деревья не пересекаются и не касаются. Позиции Гены, шушанчика и норы различаются и не находятся внутри деревьев.
В далеком будущем российские ученые собрали и отправили аппарат
для исследования поверхности Марса — "Марсоход-1".
Поверхность кратера, в который высадился марсоход, разбита на участки размером 1 x 1 метр каждый.
Программа движения марсохода состоит из последовательности команд:
w — передвинуться на 1 метр на запад,
e — передвинуться на 1 метр на восток,
s — передвинуться на 1 метр на юг,
n — передвинуться на 1 метр на север.
Координаты юго-западного угла кратера — (0, 0).
Оси координат направлены с запада на восток и с юга на север.
Известно, что марсоход высадился где-то в прямоугольнике с координатами (x1, y1) − (x2, y2).
К сожалению связь с марсоходом была потеряна по неизвестным причинам, но
он успел передать, что полностью выполнил программу движения.
Удалось также определить, что последний сигнал был послан из
прямоугольника с координатами (x3, y3) − (x4, y4).
Ученые хотят сократить зону поиска и просят вас написать программу,
определяющую, на каких участках этого прямоугольника может находиться марсоход.
Формат входного файла
В первой строке входного файла содержатся целые числа x1y1x2y2x3y3x4y4,
во второй строке содержится программа марсохода.
Формат выходного файла
Выходной файл должен содержать abs(y4 − y3) + 1 строк по abs(x4 − x3) + 1
символов в каждой — изображение зоны поиска, на котором участки, где
может находиться марсоход, отмечены символом 'x' (ASCII 120),
а остальные — символом '.' (ASCII 46).
Ограничения
0 ≤ xi, yi ≤ 1000,
количество команд в программе не превышает 30000.
Два радара, расположенные в точках с координатами (0, 0) и (100, 0),
обнаружили неопознанный объект.
По таинственной причине, связанной, возможно, с внеземной природой объекта,
радары оказались способны определить только направление на объект (пеленг),
но не расстояние до объекта.
Пеленг измеряется в градусах, против часовой стрелки,
начиная от направления "на восток"
(т. е. пеленг второго радара относительно первого равен 0°,
пеленг первого радара относительно второго — 180°).
Требуется найти координаты НЛО или определить, что это невозможно.
Формат входного файла
Во входном файле содержатся вещественные числа a и b, разделенные пробелами.
Формат выходного файла
В выходном файле должны содержаться два вещественных числа, x и y,
представляющие координаты объекта с точностью до 4 знаков после запятой.
Если определить координаты невозможно, следует вывести два числа 0 (нуль).
Вам задан связный ориентированный граф с N вершинами и M ребрами.
Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.
Формат входного файла
Граф задан во входном файле следующим образом: первая строка содержит числа N и M.
Каждая из следующих M строк содержат описание ребра - два целых числа из диапазона от 1 до
N - номера начала и конца ребра.
Формат выходного файла
На первой строке выведите число K - количество компонент сильной связности в заданном графе.
На следующей строке выведите N чисел - для каждой вершины выведите номер компоненты сильной связности,
которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом,
чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты
сильной связности его конца.
Хакер Вася решил собрать карманный персональный компьютер (КПК).
Согласно найденной им в Интернет инструкции компьютер собран правильно тогда,
когда ток из каждой микросхемы может пройти в каждую и притом единственным путем.
Вася собрал компьютер, но сомневается в правильности сборки. Напишите программу,
которая по данному Васей описанию схемы определит,
какие провода нужно удалить, какие оставить и
какие придется добавить, чтобы компьютер был собран правильно.
Так как Васе не хочется выполнять много работы, он просит вас удалять и добавлять провода
таким образом, чтобы суммарное число добавленных и удаленных проводов было минимально.
Формат входного файла
Входной файл содержит числа N и M — соответственно число микросхем и проводов в КПК, за
которыми следуют M пар чисел aiaj, означающие, что i-ая и j-ая микросхемы
соединены проводом. Ток по проводу может течь в любом направлении.
Формат выходного файла
Выходной файл содержит сначала число K1 — количество проводов, которые нужно оставить в схеме,
затем K1 пар чисел aiaj — описание проводов. После этого следует
число K2 — число проводов, которые нужно добавить в схему,
затем K2 пар чисел aiaj — описание проводов.
Если решений несколько, выведите любое из них.
Alex is administrator of IP networks.
His clients have a bunch of individual IP addresses and he decided to group all
those IP addresses into the smallest possible IP network.
Each IP address is a 4-byte number that is written byte-by-byte in a decimal dot-separated notation
"byte0.byte1.byte2.byte3" (quotes are added for clarity). Each byte is written as a decimal number from
0 to 255 (inclusive) without extra leading zeroes.
IP network is described by two 4-byte numbers - network address and network mask.
Both network address and network mask are written in the same notation as IP addresses.
In order to understand the meaning of network address and network mask you have to consider their
binary representation.
Binary representation of IP address, network address, and network mask consists
of 32 bits: 8 bits for byte0 (most significant to least significant),
followed by 8 bits for byte1, followed by 8 bits for byte2, and followed by 8 bits for byte3.
IP network contains a range of 2n IP addresses where 0 ≤ n ≤ 32.
Network mask always has 32 − n first
bits set to one, and n last bits set to zero in its binary representation. Network address has arbitrary
32 − n first bits, and n last bits set to zero in its binary representation.
IP network contains all IP addresses whose 32 − n first bits are equal to 32 − n
first bits of network address with arbitrary n last bits.
We say that one IP network is smaller than the other IP network if it contains fewer IP addresses.
For example, IP network with network address 194.85.160.176 and network mask 255.255.255.248 contains
8 IP addresses from 194.85.160.176 to 194.85.160.183 (inclusive).
Input file format
The first line of the input file contains a single integer number m.
The following m lines contain IP addresses, one address on a line.
Each IP address may appear more than once in the input file.
Output file format
Write to the output file two lines that describe the smallest possible IP network
that contains all IP addresses from the input file.
Write network address on the first line and network mask on the second.
line.
A well known algorithm called heapsort is a
deterministic sorting algorithm taking O(n log n) time
and O(1) additional memory. Let us describe ascending sorting
of an array of different integer numbers.
The algorithm consists of two phases. In the first phase,
called heapification, the array of integers to be sorted
is converted to a heap. An array a[1…n] of integers
is called a heap if for all 1 ≤ i ≤ n the following heap conditions
are satisfied:
- if 2i ≤ n
then a[i] > a[2i];
- if 2i + 1 ≤ n then a[i] > a[2i + 1].
We can interpret an array as a binary tree, considering children
of element a[i] to be a[2i] and a[2i + 1]. In this case
the parent of a[i] is a[i div 2], where i div 2 = floor(i / 2).
In terms of trees
the property of being a heap means that for each node its value is greater
than the values of its children.
In the second phase the heap is turned into a sorted array.
Because of the heap condition the greatest element
in the heapified array is a[1]. Let us exchange it with a[n],
now the greatest element of the array is at its correct position
in the sorted array. This is called extract-max.
Now let us consider the part of the array a[1 ... n-1]. It may be
not a heap because the heap condition may fail for i=1.
If it is so (that is, either a[2] or a[3], or both are greater
than a[1]) let us exchange the greatest child of a[1] with it, restoring
the heap condition for i=1. Now it is possible that the heap condition
fails for the position that now contains the former value of a[1]. Apply the same
procedure to it, exchanging it with its greatest child. Proceeding so
we convert the whole array a[1 ... n-1] to a heap.
This procedure is called sifting down.
After converting the part a[1 ... n-1] to a heap by sifting, we
apply extract-max again, putting second greatest element of
the array to a[n-1], and so on.
For example, let us see how the heap a=(5, 4, 2, 1, 3) is converted to
a sorted array. Let us make the first extract-max. After that the array
turns to (3, 4, 2, 1, 5). Heap condition fails
for a[1] = 3 because its child a[2] = 4 is greater than it.
Let us sift it down, exchanging a[1] and a[2]. Now the array is
(4, 3, 2, 1, 5). The heap condition is satisfied
for all elements, so sifting is over. Let us make extract-max again.
Now the array turns to (1, 3, 2, 4, 5). Again
the heap condition fails for a[1]; exchanging it with its greatest
child we get the array (3, 1, 2, 4, 5) which is
the correct heap. So we make extract-max and get
(2, 1, 3, 4, 5). This time the heap condition
is satisfied for all elements, so we make extract-max, getting
(1, 2, 3, 4, 5). The leading
part of the array is a heap, and the last
extract-max finally gives (1, 2, 3, 4, 5).
It is known that heapification can be done in O(n) time. Therefore,
the most time consuming operation in heapsort algorithm is sifting,
which takes O(n * log (n)) time.
In this problem you have to find a heapified array containing
different numbers from 1 to n, such that when
converting it to a sorted array, the total number of exchanges in
all sifting operations is maximal possible. In the example above the
number of exchanges is 1+1+0+0+0 = 2, which is not the maximum.
(5, 4, 3, 2, 1) gives the maximal number of 4 exchanges for n=5.
Input file format
Input file contains n.
Output file format
Output the array containing n different integer
numbers from 1 to n, such that it is a heap,
and when converting it to a sorted array,
the total number of exchanges in sifting operations is
maximal possible. Separate numbers by spaces.
You are to write a program that finds shortest distances from vertex S
to all other vertices in a given directed weighted graph.
Graph consists of N vertices, numbered from 1 to N, and M edges.
Input file format
Input file contains two integers NMS, followed my M triplets of integers
ui vi wi — starting vertex, ending vertex and weight or the edge.
There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.
Output file format
Output file must contain a vector of N integers — distances from vertex S to other vertices.
The distance from any vertex to itself is considered to be 0.
If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.
Constraints
0 ≤ N, M ≤ 1000.
All weights are less than 1000 by absolute value.
Joseph likes taking part in programming contests.
His favorite problem is, of course, Joseph's problem. It is stated as follows.
There are n persons numbered from 0 to n. 1 standing in a circle. The person number
k, counting from the person number 0, is executed. After that the person number k of the
remaining persons is executed, counting from the person after the last executed one. The
process continues until only one person is left. This person is a survivor. The problem is,
given n and k detect the survivor's number in the original circle.
Of course, all of you know the way to solve this problem.
The solution is very short, all you need is one cycle:
r := 0;
for i from 1 to n do
r := (r + k) mod i;
return r;
Here "x mod y" is the remainder of the division of x by y
But Joseph is not very smart. He learned the algorithm, but did not learn the reasoning behind it.
Thus he has forgotten the details of the algorithm and remembers the solution just approximately.
He told his friend Andrew about the problem, but claimed that the solution can be found using the
following algorithm:
r := 0;
for i from 1 to n do
r := r + (k mod i);
return r;
Of course, Andrew pointed out that Joseph was wrong.
But calculating the function Joseph described is also very interesting.
Given n and k, find ∑ki = 1(kmodi).
Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно
содержит также и отрезок, соединяющий эти точки.
Минимальное по включению множество, содержащее
заданное множество точек X, называется выпуклой оболочкой множества X.
