В школе номер 932 проходят выборы в школьный совет. Выборы проходят по следующей системе. Завуч рассматривает список всех классов школы и разбивает их на группы. Каждая группа состав- лена из одного или нескольких классов, которые идут подряд в списке, каждый класс в результате разбиения попадает ровно в одну группу.
Каждая группа классов выдвигает двух кандидатов в школьный совет — одного мальчика и одну девочку. Далее каждый школьник голосует за одного из двух кандидатов своей группы. При этом известно, что мальчики всегда голосуют за кандидата-мальчика, а девочки — за кандидата- девочку. В каждой группе результаты голосования подводятся независимо. Кандидат, набравший наибольшее количество голосов в своей группе, считается избранным в школьный совет. В случае равенства голосов оба кандидата, выдвинутых в этой группе, считаются избранными в школьный совет.
Пусть в результате выборов в школьный совет пройдет B мальчиков и G девочек. По опыту прошлых лет завуч думает, что совет будет работать тем эффективней, чем больше разность \(B − G\) числа мальчиков и числа девочек в совете. Обратите внимание, что эта величина может оказаться и отрицательной, завуч хочет максимизировать именно само значение этой величины, а не ее модуль. Например, из вариантов \(B = 2, G = 5\), при котором \(B − G = −3\), и \(B = 3, G = 4\), при котором \(B − G = −1\), второй вариант предпочтительнее.
Всего в школе \(n\) классов, и завуч уже подготовил их список. Теперь ему предстоит разбить их на группы. Группа не может содержать меньше чем \(l\) классов, иначе совет будет очень большим. В то же время группа не может содержать больше чем \(r\) классов, иначе учащиеся не смогут договориться о выдвигаемых кандидатах. Напомним, что каждая группа должна быть составлена из классов, которые идут подряд в списке завуча.
Помогите завучу найти оптимальное по его мнению разбиение на группы.
В первой строке входного файла содержится два целых числа \(n, l\) и \(r (1 \le n \le 10^5, 1 \le l \le r \le n)\) — количество классов в школе, максимальное и минимальное допустимое количество классов в одной группе соответственно. В следующих \(n\) строках содержится по два целых числа \(b_i\) и \(g_i (1 \le b_i , g_i \le 10^4)\) — количество мальчиков и девочек в \(i\)-м классе, соответственно.
В первой строке выведите целое число \(x\) — количество групп в оптимальном по мнению завуча разбиении. В следующих \(x\) строках выведите по два числа \(s_i\) и \(f_i\) (\(1 \le s_i \le f_i \le n\)). Это означает, что в \(i\)-ю группу следует включить классы с \(s_i\)-го по \(f_i\)-й, включительно. Группы можно выводить в любом порядке. Каждый класс должен войти ровно в одну группу.
Гарантируется, что существует хотя бы одно разбиение, удовлетворяющее всем ограничениям. Если существует несколько оптимальных ответов, выведите любой.
5 1 2 7 5 10 1 2 3 2 6 4 3
4 1 1 2 3 4 4 5 5
Поля участвует в международной олимпиаде по парапланеризму. Каждому участнику олимпиады необходимо выполнить следующее задание. Стартовав из заданной точки, необходимо пролететь \(d\) километров на юг, затем \(d\) километров на запад и затем \(d\) километров на север. И в результате этого полета участник должен вернуться в исходную точку!
При этом участнику запрещается подлетать ближе чем на километр к южному полюсу, так как там расположена вышка, на которой находится жюри олимпиады.
Значение \(d\) участник олимпиады выбирает самостоятельно, необходимо только, чтобы выполнялось условие \(d \ge 1\). Поля быстро сообразила, что выбрать \(d\) не так то просто, и обратилась к вам за помощью.
Будем считать Землю шаром с центром в точке (0, 0, 0) и радиусом 6371 километр. Северный и южный полюса имеют координаты (0, 0, 6371) и (0, 0, −6371), соответственно. Стартовая точка имеет трехмерные координаты \((x, y, z)\), где \(x\), \(y\) и \(z\) — целые числа, причем старт находится на поверхности Земли, то есть \(x^2 + y^2 + z^2 = 63712\) .
Помогите Поле выбрать такое вещественное число \(d \ge 1\), что стартовав из заданной точки и пролетев \(d\) километров на юг, затем \(d\) километров на запад, и затем \(d\) километров на север, она вернется в стартовую точку, при этом не пролетая близко к южному полюсу.
В единственной строке входного файла содержится три целых числа \(x, y, z\) — координаты старта в описанной системе координат.
Гарантируется, что старт находится на поверхности Земли, и расстояние от стартовой точки до южного полюса не менее 10 километров.
Выведите одно вещественное число — искомое \(d\). Ответ будет считаться верным, если \(d \ge 1\), а расстояние между стартовой точкой и концом пути не больше \(10^{−6}\) .
Если возможных \(d\) несколько, выведите любое из них. Гарантируется, что существует хотя бы одно \(d\), удовлетворяющее условиям задачи.
0 0 6371
17187.68138668338
Однажды на перемене, во время дежурства по классу, Дима написал на доске несколько строчных английских букв и позвал Гришу на них посмотреть. Грише очень понравилась композиция на доске, но к началу урока доска должна быть идеально чистой. Ребятам жалко просто стирать буквы, и чтобы сделать этот процесс интереснее, Гриша предложил занимательную игру.
Ребята делают ходы по очереди. В свой ход игрок стирает с доски две одинаковые буквы, а вместо них записывает на доску одну любую букву. Так, например, из набора букв \({a, b, a}\) можно получить наборы \(\{a, b\}, \{b, b\}, \{b, c\}, \dots , \{b, z\}\). Проигрывает тот, кто не может сделать ход, поскольку все записанные на доске буквы различны. Проигравший моет доску. Гриша ходит первым.
За происходящим внимательно наблюдает строгая учительница Дарья Владимировна. Она хочет узнать, кто выиграет в придуманной ребятами игре, если оба игрока будут придерживаться оптимальной стратегии.
Ваша задача — помочь ей узнать ответ на этот вопрос.
В единственной строке входного файла находится набор строчных английских букв, который был исходно записан на доске (число букв в наборе от 1 до 100 000, буквы не разделены пробелами).
В выходной файл выведите Grisha, если выиграет Гриша, и Dima в противном случае.
abc
Dima
aba
Grisha
В одной крупной компании работает \(n\) сотрудников. Сотрудники компании пронумерованы последовательными целыми числами от 1 до \(n\) в порядке, в котором они ежедневно приходят на работу. Никакие два сотрудника не приходят на работу одновременно, таким образом, первым приходит сотрудник с номером 1, вторым приходит сотрудник с номером 2 и так далее.
Некоторые пары сотрудников являются друзьями, при этом отношение дружбы симметрично, то есть если сотрудник с номером \(i\) считает своим другом сотрудника с номером \(j\), то и сотрудник с номером \(j\) считает своим другом сотрудника с номером \(i\). Известно, что когда очередной сотрудник приходит на работу, он быстро обходит весь офис и жмёт руку всем своим друзьям, уже находящимся в офисе, то есть тем, кто пришёл раньше него. Неизвестно, какие именно пары сотрудников являются друзьями, но для каждого сотрудника известно количество рукопожатий, которое он ежедневно совершает сразу после своего прихода на работу.
Директор компании хотел бы побеседовать с кем-нибудь из сотрудников о текущем состоянии дел. Для этого он хочет выбрать наиболее социально активного человека, а именно сотрудника с максимальным количеством друзей. По имеющейся информации определите, какое максимальное количество друзей может быть у одного из сотрудников.
В первой строке входных данных записано единственное число \(n (1 \le n \le 200 000)\) — количество сотрудников в компании.
Во второй строке входных данных записаны \(n\) целых чисел \(h_i (0 \le h_i < i)\) — \(i\)-е число соответствует количеству рукопожатий, которое совершил сотрудник с номером \(i\) сразу после своего прихода на работу, то есть до прихода сотрудника с номером \(i + \)1.
Выведите единственное число — максимально возможное количество друзей у одного из сотрудников компании.
В первом примере есть всего одна пара сотрудников, и они, как следует из того, что \(h_2 = 1\), являются друзьями.
Во втором примере, если все сотрудники 3, 4 и 5 здоровались с одним и тем же сотрудником, то у этого сотрудника 3 друга.
2 0 1
1
5 0 0 1 1 1
3
Это интерактивная задача. Ваша программа будет взаимодействовать с программой жюри, используя стандартный ввод и вывод.
Программа жюри решила сыграть с вашей программой в игру. На доске \(n \times n\) в двух различных клетках находятся две фишки. Ваша программа должна определить положение фишек. Для этого она может пытаться двигать фишки, а программа жюри будет сообщать результаты передвижений.
За один ход можно выбрать фишку и попросить переместить её на одну клетку влево, вправо, вверх или вниз. Программа жюри сообщает результат перемещения — если клетка в выбранном направлении существует и свободна, то перемещение считается успешным и фишка перемещается в эту клетку. В противном случае перемещение считается неудачным и фишка остается на той же клетке.
Вы выигрываете, если после очередного хода можете назвать исходное положение фишек на доске. Ваша задача — выиграть не более чем за \(6n\) ходов. Введем на доске систему координат таким образом, что клетки имеют координаты \((1, 1),(1, 2), \dots ,(1, n),(2, 1), \dots ,(n, n)\). Команды для перемещения фишки кодируются латинскими буквами следующим образом:
- «U» — переместиться с клетки \((x, y)\) на клетку \((x, y + 1)\).
- «D» — переместиться с клетки \((x, y)\) на клетку \((x, y − 1)\).
- «R» — переместиться с клетки \((x, y)\) на клетку \((x + 1, y)\).
- «L» — переместиться с клетки \((x, y)\) на клетку \((x − 1, y)\).
В самом начале программа жюри сообщает вашей программе натуральное число \(n (2 \le n \le 50)\) — размер доски.
Далее ваша программа должна повторять следующие ходы, выводя в стандартный поток вывода соответствующее сообщение и переводя строку. Перемещение фишки кодируется строкой «0 id c», где id — номер фишки, которую ваша программа хочет переместить (1 или 2), а символ c — направление движения. После каждого перемещения программа жюри сообщает вашей программе результат попытки перемещения:
• «1», если передвижение успешно;
• «0», если нет.
Когда ваша программа считает, что определила начальное положение фишек, следует вывести 5 чисел: «1 \(x_1 y_1 x_2 y_2\)» (\(1 \le x_1, y_1, x_2, y_2 \le n\)) — начальное положение первой фишки \((x_1, y_1)\) и второй фишки \((x_2, y_2)\), соответственно. После вывода этой команды ваша программа должна завершиться. Вывод этой команды не считается ходом и не включается в ограничение \(6n\) на число ходов.
В каждом тесте исходное положение фишек зафиксировано, и программа жюри честно отвечает на запросы вашей программы.
После каждого действия вашей программы выводите символ перевода строки. Если вы используете «writeln» в Паскале, «cout << ... << endl» в C++, «System.out.println» в Java или «print» в Python, сброс потока вывода у вас происходит автоматически, дополнительно делать «flush» не обязательно. Если вы используете другой способ вывода, рекомендуется делать «flush», но все равно обязательно требуется выводить символ перевода строки.
Ниже приведены наиболее типичные причины получения тех или иных сообщений об ошибке.
Если ваша программа соблюдает протокол, но неверно определяет начальное положение фишек, либо выполняет слишком много ходов, вы получите результат «Wrong Answer».
Если ваша программа выводит некорректно отформатированные сообщения программе жюри, то вы получите результат «Presentation Error», либо «Wrong Answer».
Если ваша программа нарушила протокол и ждет ввода в то же время, когда его ждет и программа жюри, то вы получите результат «Idleness Limit Exceeded». Обратите внимание, что к такому же результату может привести и то, что вы не переводите строку после каждого выведенного сообщения, или выводите не тем способом, который описан в начале раздела, и не делаете «flush».