Алгоритмы

У нас было 2 набора юного химика, 75 мятных таблеток, 5 упаковок оберточной бумаги, полфунта детских драже и целое множество подарков всех сортов и расцветок, а также машинки, куклы,  мешок вкусного оленьего корма, пинта чистого сока и стадо быстрых оленей.
Не то что бы это был необходимый запас для поездки. Но если начал развозить подарки, становится трудно остановиться.
Единственное что вызывало у меня опасение - это олени. Нет ничего более непредсказуемого, чем стадо северных оленей, кто знает чего от них ожидать?  Я догадывался, что рано или поздно они дадут о себе знать.
Самое страшное, что домов, куда нужно доставить подарки, более 10^100000000 и ребенок сильно расстроится, узнав, что не получил подарка на Новый Год. Этого допускать нельзя, благо вы - не единственный Санта, и вам будет достаточно доставить подарки только в своем городе. Детишек в вашем городе не больше 10^4, но все они живут в разных домах. У вас есть список, в котором не больше 10^4 элементов, каждый элемент списка представляет собой 2 целых числа – координаты дома следующего ребеночка.  Доставив подарки в очередной дом, вы, как порядочный Санта, обязаны стирать координаты этого дома из своего списка. Но ваши олени не хотят спокойно доставлять подарки, они коллективно прокладывают на их взгляд более оптимальный и правильный маршрут, и выбирают номер следующего дома из вашего списка по своей очень логичной и тривиальной формуле:
N_next  = |(K₁  - K₂  ) *R|% L,
где N_next – номер следующего дома в вашем списке (Как делают настоящие ТРУ-программисты? Они считают элемент с  единицы нуля!)  K₁  - количество еще не посещенных домов, K₂ – количество уже посещенных домов, R – коэффициент рандомности стада и L – длина текущего списка. Заметим, что после посещения дома, количество элементов в вашем списке уменьшается, вы же порядочный Санта, верно? Вечером, после тяжелого трудового дня, вы, как и остальные труженики Новогоднего фронта,  выкладываете в свой блог количество  километров, которые сегодня преодолели. Изначально вы находитесь в доме с индексом 0 и считается, что подарок в этот дом уже доставлен.  Зная столь тривиальную, понятную и очевидную формулу расчета следующего дома, а также имея список домов и  хорошо зная свое стадо, вплоть до их коэффициента рандомности, скажите какое расстояние  вы пройдете за всю поездку? Ответ округлите вверх до целых, в таких вещах можно чуть-чуть  преувеличить.  
 
Входные данные:
В первой строке входного файла находятся целые положительные числа N, R (1<N<=10000,1< R <1000000) – количество детей в вашем списке и коэффициент рандомности вашего стада, соответственно.
В следующих N строках находятся по 2 целых числа X,Y (-100000<=X,Y<=100000) – координаты конкретного  дома.
Выходные  данные:
Выведете одно целое число – ответ на поставленную задачу.
 
Пример, как же без примера:
Входит:
4 2
1 1
0 0
2 0
2 1
Выходит:
6

(с) Ярослав Свиридов 10и

(с) Линд Владимир

Пример вывода:
2


(с) Даниил Кирионенко  8и

Примеры

№	Входные данные	Выходные данные
1	3 4 1 1 1 2 1 3 2 3	1
2	5 3 1 1 1 2 2 1	4
3	5 0	5

 

Примеры

№	Входные данные	Выходные данные
1	5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5	3 3 2 1 5

Примечание

 

Пример

№	Входные данные	Выходные данные
1	5 100 312 0 312 500	5 2 4 1 3

Входные данные
В первой строке задается число N - количество элементов массива (\(1<=N<=100000\)).
Далее идет N строк, по одному числу в строке - элементы массива.

Выходные данные 
Выведите на экран отсортированный массив в одну строку.
 

Примеры

№	Входные данные	Выходные данные
1	5 3 1 2 4 2	1 2 2 3 4

Феоктист Всеволодович — преподаватель физкультуры старой закалки, глубоко убеждённый, что в начале каждого урока школьников необходимо построить по росту. Для этого он сначала просит школьников построиться самостоятельно, после чего последовательно меняет местами про- извольную пару стоящих рядом учеников, пока шеренга не примет желанный вид.

Всего на урок пришло N детей, изначально построившихся таким образом, что рост стоящего на позиции i равен hi (используется нумерация c 1). Можно считать, что все числа hi различны и лежат в диапазоне от 1 до N. Шеренга считается упорядоченной, если на первой позиции стоит школьник ростом один, на второй позиции стоит школьник ростом два и так далее.

Феоктист Всеволодович получает большое удовольствие от процесса упорядочивания школьни- ков, поэтому он всегда выбирает наиболее длинную последовательность обменов. С другой стороны, он не хочет чтобы ученики догадались о том, что он умышленно затягивает построение, поэтому никогда не делает заведомо бессмысленных обменов. А именно, преподаватель никогда не меняет местами школьников на позициях i и j, если hi < h_j . Очевидно, что данное ограничение делает процесс сортировки шеренги по росту конечным.

Староста Саша очень любит играть в волейбол и прекрасно понимает, что чем дольше препо- даватель будет расставлять всех по местам, тем меньше времени останется для игры. Ученики уже построились некоторым образом, а Феоктист Всеволодович вышел поговорить по телефону, так что Саша может успеть поменять местами ровно двух школьников, необязательно стоящих рядом в ше- ренге. Разумеется, он хочет сделать это таким образом, чтобы преподаватель как можно быстрее закончил упорядочивать шеренгу (Саша давно уже раскусил, как именно действует Феоктист Всево- лодович). С информатикой у старосты всегда были определённые проблемы, поэтому ему требуется ваша помощь.

Формат входных данных
В первой строке ввода содержится единственное число N — количество школьников на уроке (1 <= N <= 1 000 000). Во второй строке записано N различных целых чисел h_i (1 <= h_i <= N). i-е число соответствует росту школьника стоящего на i-й позиции.

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

Ввод	Вывод
5 2 4 3 5 1	2 5
4 1 2 3 4	-1 -1
10 2 3 7 1 5 10 4 6 9 8	3 7

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

Кроме того, так как действие происходит в Лаборатории Исследования Природы Порталов, на каждой стене комнаты расположен портал, связанный с противоположной стеной. Формально: рас- смотрим комнату как прямоугольную сетку размера W × H и введем систему координат так, чтобы левая нижняя ячейка сетки имела координаты (0, 0), а правая верхняя — (W − 1, H − 1). За один шаг Челл может перейти в одну из четырёх соседних ячеек, причём попытка пройти сквозь стену приводит к тому, что Челл появляется с противоположной стороны комнаты. Например, шаг вниз из ячейки (x, 0) приведёт в ячейку (x, H −1), а шаг влево из ячейки (0, y) приведёт в ячейку (W −1, y).

Чтобы сделать испытание сложнее, GLaDOS не сообщила Челл ни размеры комнаты, ни коорди- наты её изначального положения, ни координаты торта. Более того, так как у Челл завязаны глаза, а портальная технология достигла совершенства в своём развитии, Челл даже не может определить, прошла ли она очередным ходом через портал или нет.

Челл может найти торт, только оказавшись в одной клетке с ним. Помогите ей пройти последнее испытание! Формат взаимодействия с тестирующей системой Это интерактивная задача. Ваша программа будет общаться с тестирующей системой по протоколу, описанному ниже. Вам разрешается произвести не более 200 000 ходов. Чтобы переместиться в соседнюю ячейку, выведите строку, содержащую ровно один символ, задающий направление перемещения: «U» — вверх; «D» — вниз; «L» — влево; «R» — вправо. Затем вы должны считать строку, в которой будет находиться ровно один символ, обозначающий результат перемещения: • «Y» — после произведённого хода Челл оказалась в клетке с тортом; • «N» — после произведённого хода Челл оказалась в клетке, не содержащей торт; • «E» — служебный символ, обозначающий, что после произведённого хода Челл всё ещё не нашла торт, а ваша программа превысила ограничение на количество ходов. Обратите внимание, после считывания символа «Y» или «E» вы обязательно должны сразу завершить вашу программу. В противном случае, вердикт тестирующей системы может быть некор- ректным! Гарантируется, что в клетке, в которой исходно находится Челл, нет торта. В точности соблюдайте формат выходных данных. После вывода каждой строки сбрасы- вайте буфер вывода — для этого используйте команды flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.

На протяжении многих лет Вася работает программистом в одной очень большой и очень из- вестной компании. Эта компания обеспечивает своих сотрудников всем необходимым для приятной и плодотворной работы: бесплатными обедами, транспортом от дома до места работы и многим, многим другим. И вот в один прекрасный солнечный день Вася понял, что ему очень наскучил вид из окна его офиса, и ему нужно, чтобы за окном было что-то новое и прекрасное. А что может быть лучше чудесного горного пейзажа? Придя к этой мысли, Вася попросил своего менеджера подобрать себе новый офис с красивым видом на горы.

В той местности, где располагается офис Васи, каждая гора принадлежит некоторой горной цепи. Так как Васе хочется, чтобы вид из окна его офиса был идеальным, то он попросил подобрать себе такой офис, чтобы никакие две горные цепи, видимые из окна, не пересекались. Менеджер Васи нашел прекрасный новый офис, из которого видно N горных цепей, но он никак не может определить, понравится ли Васе вид из окна этого офиса. Помогите ему!

Более формально, вид из окна офиса представляет собой набор горных цепей, пронумерованных от 1 до N, где горная цепь с номером i представляет собой ломаную на плоскости из li звеньев с вершинами в точках (x_i,j , y_i,j ), причем для любых i, j выполнено x_i,j < x_i,j+1.

Кроме этого, окно в офисе имеет фиксированную ширину, поэтому все горные цепи начинаются и заканчиваются на одной вертикали, то есть существуют такие числа A и B, что для любого номера i горной цепи выполнено x_i,0 = A, x_i,li = B.

Отметим, что из определения горной цепи следует, что для любого значения абсциссы A <= x <= B на ломаной с номером i существует единственная точка (x, yi(x)) с этим значением абсциссы, при- надлежащая этой ломаной. Будем говорить, что горная цепь i находится строго выше горной цепи j в точке x, если выполнено строгое неравенство y_i(x) > y_j (x).

Естественно считать, что цепь под номером i пересекается с цепью под номером j, если су- ществуют такие два значения абсциссы x1, x2, что цепь i находится строго выше цепи j в точке x1, но при этом цепь j находится строго выше цепи i в точке x2, то есть выполнены неравенства y_i(x₁) > y_j (x₁) и y_j (x₂) > y_i(x₂). Обратите внимание на поясняющие рисунки, расположенные в примечании к задаче.

Вам необходимо определить, подойдет ли подобранный офис Васе, и, если нет, то найти любую пару пересекающихся горных цепей.

Формат входных данных 
В первой строке входных данных через пробел идут два целых числа: A и B (−10⁹<=A < B<=10⁹ ).
Во второй строке входных данных находится единственное число N — количество горных цепей, видимых из окна подобранного менеджером Васи офиса (1 <= N <= 100 000).
Далее следуют описания N горных цепей. В первой строке i-го описания содержится число l_i => 1 — количество звеньев ломаной, из которых состоит соответствующая горная цепь. В следую- щих li + 1 строках описания содержатся два целых числа — координаты (x_i,j , y_i,j ) вершин ломаной (0 <= j <= l_i). Суммарное число звеньев всех ломаных не превосходит 200 000.
Гарантируется, что для каждой горной цепи вершины соответствующей ей ломаной идут во входных данных в порядке возрастания абсциссы, причем для любого i выполнено x_i,0 = A, x_i,li = B.

Формат выходных данных 
Если же офис подходит Васе, то есть никакие две горные цепи из входных данных не пересека- ются, в единственной строке выходных данных выведите слово "Yes" (без кавычек).
Иначе выведите в первой строке слово "No" (без кавычек), а на следующей строке выведите два числа — номера двух пересекающихся горных цепей. Горные цепи нумеруются согласно их появлению во входных данных, начиная с 1.

Примеры

Ввод	Вывод
-3 3 2 1 -3 2 3 1 2 -3 2 0 4 3 2	Yes
0 4 2 3 0 3 1 3 3 1 4 1 1 0 2 4 2	No 1 2

Замечание

Напоминаем, что абсциссой точки называется её x-координата, а ординатой — её y-координата. В первом примере хотя ломаные и касаются друг друга в точке (−3, 2), но, согласно данному выше определению, они не пересекаются. Во втором примере в точке x₁ = 1 одна ломаная выше другой, а в точке x₂ = 3 — наоборот, то есть горные цепи пересекаются.

 

Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки «+», «–», «*» и «/»). На вход подается символьная строка, представляющая собой арифметическое выражение. Все числа целые. Операция «/» выполняется как целочисленное деление 
 

Примеры

№	Входные данные	Выходные данные
1	12*3+45	81
2	12-45/3	-3

Какая система счисления используется в компьютерной технике?

1. двоичная
2. унарная
3. шестнадцатеричная
4. десятичная

Вдохновившись исследованием британских учёных о восприятии человеком текста, Вася решил, что современная письменность нуждается в серьёзном упрощении. В частности, в лексиконе Васи все слова состоят только из букв a, b и c. Кроме того, память у Васи плохая, поэтому Вася помнит лишь слова, которые содержат не более L букв.

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

Британские учёные очень заинтересовались исследованиями Васи. Они вступили с молодым учё- ным в активную переписку, однако, получив очередное Васино сообщение были несколько озадачены тем, что же он имел ввиду. Так как разобраться они так и не смогли, а очередное революционное открытие уже было проанонсировано в СМИ, они решили как-то оценить уровень гениальности автора. Для этого они решили понять, а из какого минимального количества слов может состоять словарный запас Василия?

Формат входных данных
В первой строке входных данных содержится целое число L — максимальная длина слова, кото- рое может содержаться в лексиконе Васи (1 <= L <= 10 000). В следующей строке содержится непустое сообщение, полученное учеными. Длина сообщения не превосходит 20 000 символов.

Формат выходных данных
В первой строке выведите единственное число K — минимальное количество слов, которые дол- жен знать Василий, чтобы написать данное сообщение. В следующих K строках выведите сами сло- ва, каждое из которых должно иметь длину не превосходящую L. В случае, если ответов несколько, разрешается выдать любой из них.

Пример
Ввод:
3
ababaabab

Вывод:
2
aba
ab

Замечание
В первом примере из условия одним из возможных способов проинтерпретировать Васино сооб- щение является: ab aba ab ab.