Городской школьник Лёша поехал на лето в деревню и занялся выращиванием цветов. Он посадил \(n\) цветков вдоль одной длинной прямой грядки, и они успешно выросли. Лёша посадил различные цветки, \(i\)-й от начала грядки цветок имеет вид \(a_i\), где \(a_i\) - целое число, номер соответствующего вида в «Каталоге юного агронома».
Теперь Лёша хочет сделать фотографию выращенных им цветов и выложить ее в раздел «мои грядки» в социальной сети для агрономов «ВКомпосте». На фотографии будет виден отрезок из одного или нескольких высаженных подряд цветков.
Однако он заметил, что фотография смотрится не очень интересно, если на ней много одинаковых цветков подряд. Лёша решил, что если на фотографии будут видны три цветка одного вида, высаженные подряд, то его друзья — специалисты по эстетике цветочных фотографий — поставят мало лайков.
Помогите ему выбрать для фотографирования как можно более длинный участок своей грядки, на котором нет трех цветков одного вида подряд.
В первой строке содержится целое число \(n (1 \le n \le 200 000)\) — количество цветков на грядке.
Во второй строке содержится n целых чисел \(a_i (1 \le a_i \le 10^9 )\), обозначающих вид очередного цветка. Одинаковые цветки обозначаются одинаковыми числами, разные — разными.
Выведите номер первого и последнего цветка на самом длинном искомом участке. Цветки нумерются от 1 до \(n\).
Если самых длинных участков несколько, выведите описание любого из них.
6 5 6 6 6 23 9
3 6
В парке развлечений «Пуперленд» открылся огромный верёвочный парк. Особая гордость парка — трасса, состоящая из \(n\) платформ, соединённых \(n − 1\) верёвками: первая платформа соединена со второй, вторая — с третьей, \(\dots\) , \(n − 1\)-я — с \(n\)-й, верёвка, соединяющая \(i\)-ю платформу с \(i + 1\)-й имеет длину \(l_i\) .
В парке серьёзно относятся к технике безопасности, так что для трассы были разработаны следующие правила эксплуатации:
Все люди разные и будут проходить трассу с разной скоростью. Пронумеруем посетителей от 1 до \(m\) в том порядке, в котором они выстроились в очередь. Для \(j\)-го посетителя известна скорость \(v_{i,j}\) м/c — максимальная скорость, с которой он может проходить по верёвке, соединяющей \(i\)-ю и \(i + 1\)-ю платформы. Таким образом, \(j\)-й посетитель может перемещаться по \(i\)-й верёвке с любой скоростью от 0 до \(v_{i,j}\) , соблюдая при этом условия про минимальное расстояние до других посетителей, идущих по той же верёвке.
Администрация парка не ожидала такого наплыва посетителей и теперь опасается, что все посетители могут не успеть пройти трассу до закрытия парка. Помогите им посчитать минимальное время, которое потребуется всем посетителям, чтобы пройти трассу
В первой строке заданы два целых числа \(n (2 \le n \le 100)\) и \(m (1 \le m \le 100)\) — число платформ на трассе и число посетителей.
Во второй строке заданы \(n − 2\) целых числа \(p_2, \dots , p_{n−1} (1 \le p_i \le 100)\) — ограничения на число людей на платформах. Обратите внимание, что если \(n = 2\), то эта строка пуста.
В следующей строке задано \(n − 1\) целое число \(r_1, r_2, \dots , r_{n−1} (1 \le r_i \le 100)\) — ограничение на число людей на \(i\)-й верёвке.
В следующей строке задано \(n − 1\) целое число \(l_1, l_2, \dots , l_{n−1} (1 \le l_i \le 100)\) — длины верёвок в метрах.
В следующей строке задано \(n − 1\) целое число \(d_1, d_2, \dots , d_{n−1}\) — ограничение в метрах на расстояние между людьми на \(i\)-й верёвке. Гарантируется, что \(1 \le d_i \le l_i\).
В оставшихся \(n − 1\) строке находится по \(m\) целых чисел: \(\)v_{1,1}, v_{1,2}, \dots , v_{1,m}\(\) \(\)v_{2,1}, v_{2,2}, \dots , v_{2,m}\(\) \(\)\dots\(\) \(\)v_{n−1,1}, v_{n−1,2}, \dots , v_{n−1,m},\(\) где \(v_{i,j}\) — скорость в м/с \(j\)-го посетителя на \(i\)-й верёвке (\(1 \le v_{i,j} \le 100\)).
Выведите единственное число — время в секундах, которое необходимо, чтобы все посетители прошли трассу
Ваш ответ должен иметь относительную или абсолютную погрешность не больше \(10^{−6}\).
Таким образом, он будет засчитан, если \(|a−p|/max(a,1) \le 10^{−6}\) , где \(p\) — ваш ответ, а \(a\) — правильный ответ
2 1 1 30 2 2
15.0
3 2 1 2 2 10 10 5 5 2 2 1 2
17.5
В школе номер 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