Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Три лучшие коровы Фермера Джона Беси, Эльза и Милдред всегда уходят далеко от фермы. Помогите ФД "сгрудить их в стадо".

Главное поле фермы можно представить в виде числовой прямой, и каждая корова находится в целочисленной координате. Все три координаты различны. ФД хочет переместить их так, чтобы они заняли последовательные координаты (например, 6,7,8).

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

Определите минимальное и максимальное количество перемещений, которое возможно сделать прежде чем коровы расположатся в трёх последовательных позициях.

ФОРМАТ ВВОДА (файл herding.in):

Входной файл содержит одну строку с тремя разделёнными пробелами целыми числами, определяющими координаты Беси, Эльзы и Милдред. Каждая координата - целое число в интервале \(1 \ldots 10^9\).

ФОРМАТ ВЫВОДА (файл herding.out):

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

—Войти и решать

MooBuzz#90047

Коровы фермера Джона недавно стали поклонниками простой числовой игры под названием «FizzBuzz». Правила игры просты: стоя в кругу, коровы последовательно отсчитывают от одного, каждая корова произносит одно число, когда наступает ее очередь. Однако, если корова достигнет числа кратного 3, она должна сказать «Fizz» вместо этого числа. Если корова достигает кратного 5, она должна сказать «Buzz» вместо этого числа. Если корова достигает кратного 15, она должна сказать «FizzBuzz» вместо этого числа. Поэтому расшифровка первой части игры:

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16

Имея немного более ограниченный словарный запас, версия FizzBuzz, которую играют коровы, включает в себя выражение «Moo» вместо Fizz, Buzz и FizzBuzz. Поэтому начало коровьей версии игры

1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16

По заданному числу \( N \) (\( 1 \ leq N \ leq 10 ^ 9 \)), определите \( N \)-ое число, которое говорят в этой игре.

ОЦЕНИВАНИЕ

Тесты 2-5 удовлетворяют \( N \ le 10 ^ 6. \)

ФОРМАТ ВВОДА (файл moobuzz.in):

Ввод состоит из единственного целого числа, \( N \).

ФОРМАТ ВЫВОДА (файл moobuzz.out):

Выведите \( N \)-ое число, которое произнесли во время игры.

Вывод формулы

—Войти и решать

Team Tic Tac Toe#90026

У Фермера Джона 26 коров, имена которых начинаются с различных букв алфавита поэтому ФД обычно называет их по первым буквам \(A \ldots Z\).

Недавно эти коровы познакомились с игрой "крестики-нолики", но им не понравилась игра только с двумя участниками, поэтому они придумали модификацию этой игры чтобы одновременно множество коров могли играть. Как и в стандартной игре, игра ведётся на доске \(3 \times 3\) , только вместо X и 0 каждый квадратик помечается символом \(A \ldots Z\) той коровы, которая сделала ход в данное поле.

Пример доски с такой игрой:

COW
XXO
ABC

Коровы заполнили все 9 квадратиков, теперь они не могут понять, кто же победил в этой игре. Понятно, как и в обычной игре "крестики-нолики", если одна корова заняла строку, столбец или диагональ, она выиграла. Однако поскольку игроков может быть больше двух, они решили позволять коровам формировать команды из двух коров. Команда объявляется победительницей, если строка, столбец или диагональ состоят только из символов коров одной команды.

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

ФОРМАТ ВВОДА (файл tttt.in):

Ввод состоит из трёх строк, каждая из которых состоит из трёх символов из диапазона \(A \ldots Z\).

ФОРМАТ ВЫВОДА (файл tttt.out):

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

Задача на реализацию

—Войти и решать

Sprinklers#90020

У Фермера Джона есть большое поле, и он собирается посадить в некоторых его местах сладкую пшеницу. ФД представил поле квадратом с размерами \((N-1) \times (N-1)\). Юго-западный угол поля имеет координаты \((0,0)\), а северо-восточный конец поля имеет координаты \((N-1,N-1)\).

В некоторых целочисленных координатах имеются двухглавые разбрызгиватели, оба разбразгивают воду и удобрения. Разбрызгиватель в координатах \((i,j)\) разбрызгивает воду на часть поля к северу и востоку от себя и разбрызгивает удобрения к югу и западу от себя. Формально, он поливает водой все вещественные координаты \((x,y)\) для которых \(N \geq x \geq i\) и \(N \geq y \geq j\), и удобряет все вещественные координаты \((x,y)\) для которых \(0 \leq x \leq i\) and \(0 \leq y \leq j\).

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

Помогите ФД определить количество прямоугольников с положительной площадью, на которых он может растить сладкую пшеницу. Поскольку число может быть очень большим, выводите его по модулю \(10^9 + 7\).

ФОРМАТ ВВОДА (файл sprinklers.in):

Первая строка ввода содержит целое число \(N\), определяющее размер поля. (\(1 \leq N \leq 10^5\)).

Каждая из последующих \(N\) строк содержит два разделённых пробелом целых числа \(i\) и \(j\), (\(0 \leq i,j \leq N-1\)), они обозначают, что разбрызгиватель находится в позиции \((i,j)\).

Гарантируется, что ровно один разбрызгиватель находится в каждой колонке и ровно один разбрызгиватель находится в каждой строке. То есть, никакие два разбрызгивателя не имеют одинаковую \(x\)-координату, и никакие два разбрызгивателя не имеют одинаковую \(y\)-координату.

ФОРМАТ ВЫВОДА (файл sprinklers.out):

Вывод должен содержать одно целое число - количество прямоугольников положительной площади, которые полностью поливаются и удобряются, по модулю \(10^9 + 7\).

Вывод формулы

—Войти и решать

Cow Gymnasts#90006

Соскучившись от жизни на ферме, коровы ушли в бродячий цирк. И с ними готовится новое шоу.

Сцена для шоу представляет \(N\) платформ, размещённых по кругу. На каждой платформе от \(1\) до \(N\) коров формируют стек (корова становится на корову). По сигналу главного на манеже, все стеки параллельно "падают" по часовой стрелке так, что нижняя корова стека не движется, корова на ней движется на одну платформу по часовой стрелке, следующая корова - на две платформы и т.д. В результате получаются новые стеки коров.

Главный на манеже думает, что шоу будет лучше, если после того, как стеки упадут, новый стек на каждой платформе будет содержать такое же количество коров, что и исходный стек на манеже. Мы называем конфигурацию стеков на манеже "магической", если она удовлетворяет этому условию. Вычислите количество "магических" конфигураций. Поскольку это число может быть очень большое, выведите его остаток по модулю \(10^9 + 7\).

Две конфигурации считаются различными, если существует платформа, для которых у этих двух конфигураций различное количество коров.

ФОРМАТ ВВОДА (файл gymnasts.in):

Ввод - олдно целое число, \(N\) (\(1 \leq N \leq 10^{12}\)).

ФОРМАТ ВЫВОДА (файл gymnasts.out):

Одно целое число - количество магических конфигураций по модулю \(10^9 + 7\).

Вывод формулы Комбинаторика теория чисел

—Войти и решать

Taming the Herd#90005

Однажды утром Фермер Джон проснулся от звуков дробления древесины. Это коровы ломали амбар.

ФД рассердился. Он приделал к стене счётчик дней с последнего слома. Если слом случился утром, счётчик покажет 0. Если последний слом случился 3 дня назад, счётчик показывает 3. ФД тщательно записывал значение счётчика каждый день.

В конце года ФД решил действовать. Однако с логом некоторые проблемы.

ФД хочет определить, сколько слово зафиксировано. Однако он подозревает, что коровы подделали его лог и всё в чём он уверен, что он начало лог в день слома. Помогите ему определить, для каждого количества сломов какое минимальное количество записей должно быть подделано.

ФОРМАТ ВВОДА (файл taming.in):

Первая строка ввода содержит одно целое число \(N\) (\(1 \leq N \leq 100\)), обозначающее количество дней, с дня когда ФД начал логгирование.

Вторая строка содержит \(N\) целых чисел, разделённых одиночными пробелами. \(i\)-ое число это неотрицательное целое \(a_i\) (не более 100), указывающее что в день \(i\) на счётчике было \(a_i\) если коровы не подделали эту запись в логе.

ФОРМАТ ВЫВОДА (файл taming.out):

Вывод состоит из \(N\) целых чисел, по одному в строке. \(i\)-ое целое число должно содержать минимум из всех возможных последовательностей с \(i\) сломами количества записей, которые несостоятельны в этой последовательности.

Динамическое программирование: один параметр Жадный алгоритм Разбор случаев

—Войти и решать

Bessie Goes Moo#89959

Фермер Джон и корова Беси в свободное время любят обмениваться математическими головоломками. Последняя головоломка, которую ФД дал Беси была очень сложной и Беси не смогла решить ей. Теперь она хочет дать ФД очень сложную головоломку.

Беси даёт ФД выражение \((B+E+S+S+I+E)(G+O+E+S)(M+O+O)\), содержащее семь переменных \(B,E,S,I,G,O,M\) (the "\(O\)" это переменная, а не 0). Для каждой из переменных она даёт ФД список до 500 целых значений, которые та может принять. Она просит ФД посчитать количество способов, получить результат, кратный числу 7.

Заметим, что ответ на эту задачу может быть слишком большим, чтобы пометситься в 32-битную переменную, рекомендуется использовать 64-битную переменную типа long long в С/С++.

ФОРМАТ ВВОДА (файл bgm.in):

Первая строка ввода содержит целое число \(N\). Каждая из последующих \(N\) строк содержит переменную и возможное значение этой переменной. Каждая переменная появится в этом списке не менее одного и не более 500 раз. Для одной и той же переменной никакие значения не повторяются. Все возможные значения находятся в диапазоне \(-10^5\) до \(10^5\).

ФОРМАТ ВЫВОДА (файл bgm.out):

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

Вывод формулы

✓ 0✗ 1—Войти и решать

Moocryption#89953

Коровы увлекаются словесными пазлами. Например, таким

USOPEN
OOMABO
MOOMXO
PQMROM

Как коровам, им интересно только единственное слово "MOO", которое может появиться во многих местах горизонтально, вертикально или по диагонали. Пример сверху содержит 6 таких слов.

Фермер Джон тоже любитель таких пазлов. Поскольку коровы не хотят, чтобы он разгадывал пазлы раньше коров, они зашифровали пазл, используя заменяющий шифр, который заменяет каждую букву алфавита некоторой другой, отличающейся буквой. Например, A может заменяться буквой X, B - буквой A и т.д. Никакая буква не заменяется собой и никакие две буквы не заменяются одной и той же буквой (иначе расшифровка может стать неоднозначной).

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

ФОРМАТ ВВОДА (файл moocrypt.in):

Первая строка ввода содержит \(N\) и \(M\), описывающие количество строк и столбцов в пазле (оба не более 50). Каждая из следующих \(N\) строк содержит по \(M\) символов, описывающих одну строку зашифрованного пазла. Каждый символ - большая латинская буква в диапазоне A..Z.

ФОРМАТ ВЫВОДА (файл moocrypt.out):

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

Задача на реализацию

—Войти и решать

Bessie Gets Even#89952

Фермер Джон и корова Беси в свободное время любят обмениваться математическими пазлами. Последний пазл, который ФД дал Беси, был довольно сложный и Беси не смогла решить его. Теперь она хочет дать ФД очень сложный пазл.

Беси даёт ФД выражение \((B+E+S+S+I+E)(G+O+E+S)(M+O+O)\), содержащее семь переменных \(B,E,S,I,G,O,M\) ( "\(O\)" это переменная, а не 0). Для каждой переменной она даёт ФД список до 20 целых чисел, которые эта переменная может принять. Беси просит ФД посчитать количество различных способов назначить значения переменным, чтобы вычисленное выражение было чётным числом.

ФОРМАТ ВВОДА (файл geteven.in):

Первая строка ввода содержит целое число \(N\). Каждая из \(N\) следующих строк содержит переменную и возможное значение для этой переменной. Каждая переменная появится в этом списке не менее одного раза и не более 20 раз. Для одной и той же переменной все задаваемые значения различны. Все значения находятся в диапазоне \(-300\) to \(300\).

ФОРМАТ ВЫВОДА (файл geteven.out):

Выведите единственное целое число, задающее количество способов, которыми ФД может назначить значения переменным, чтобы выражение давало чётный результат.

Вывод формулы

—Войти и решать

Code Breaking#89946

Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой. Она организована как корневое дерево из N (1 <= N <= 20,000) вершин, каждая из которых требует цифру от 0 до 9. Вершины пронумерованы от 0 до N-1.
Единственная информация, которой владеют коровы – что определённая последовательность длины 5 не случается на путях в этом дереве.
Например, предположим, то дерево выглядит так (с корнем в A):
A <- B <- C <- D <- E ^ | F
Коровы могут знать, что последовательность 01234 не случится начиная от F, И что последовательность 91234 не случится, начиная от E. Эта информация приводит к тому, что возможными остаются 19 паролей, все такого вида:
The cows might know that the sequence 01234 does not occur starting at F, and that the sequence 91234 does not occur starting at E. This information rules out 19 possible passcodes: all those of the form
4 <- 3 <- 2 <- 1 <- * ^ | 0
или
4 <- 3 <- 2 <- 1 <- 9 ^ | *
Что даёт 19 паролей, поскольку такой
4 <- 3 <- 2 <- 1 <- 9 ^ | 0
появится дважды
По заданным M (1 <= M <= 50,000) последовательностям длины 5, вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет подходить. Вы должны выводить свой ответ по модулю 1234567.

PROBLEM NAME: code
Формат ввода:
* Строка 1: Два разделённых пробелом целых числа, N и M.
* Строки 2..N: Строка i+1 содержит одно целое число p(i), означающее родителя вершин I в дереве (0 <= p(i) < i).
* Строки N+1..N+M: Строка N+i описывает i-ую последовательность про которую известно, что она не произойдёт в коде. Строка содержит v(i) и s(i), разделённые пробелом. Здесь v(i) - стартовая вершина последовательности, s(i) – строка из 5 цифр, которая не встретится в шифре начиная с вершины v(i) если двигаться вверх по дереву. Гарантируется, что корень дерева находится не менее чем в 4 шагах от v(i).

Вывод формулы графы Деревья

—Войти и решать

Empty Stalls#89900

Новый амбар Фермера Джона представляет собой большой круг из N стойл (2 <= N <=3,000,000), пронумерованных от 0 до N-1, стойло N-1 соседствует со стойлом 0.
В конце каждого дня коровы ФД возвращаются в амбар, одна за одной, У каждой имеется предпочтительный номер стойла, который она хочет занять. Однако если это место уже занято другой коровой, она идёт вперёд последовательно от этого стойла, пока не найдёт первое не занятое стойло, которое она и займёт. Если она пройдёт стойло N-1, она продолжит поиск со стойла 0.
По заданному предпочтительному номеру для каждой коровы определите минимальный номер стойла, который останется незанятым после того как все коровы вернутся в амбар. Заметим, что ответ на этот вопрос не зависит от того, в каком порядке возвращаются коровы
Для того, чтобы избежать проблем с огромным вводом, данные вводятся в специальном формате, использующем K строк (1 <= K <=10,000) вида
X Y A B
Здесь описываются предпочтительные стойла X Y коров: X коров предпочитают каждое из стойл f(1) .. f(Y), где f(i)= (Ai + B) mod N. Значения A и B лежат в диапазоне 0...1,000,000,000.
Не забудьте про стандартное для всех задач ограничение на память – 64 Мбт.
PROBLEM NAME: empty
Формат входных данных
* Строка 1: Два разделённых пробелом целых числа: N и K.
* Строки 2..1+K: каждая строка содержит целые числа X Y A B, смысл которых описан выше. Общее количество коров описываемых этими числами не превысит N-1. Коровы могут добавляться в одно и тоже стойло разными из этих строк.
Формат выходных данных
* Строка 1: Минимальный индекс не занятого стойла.
Примечание
Все стойла будут заняты кроме стойла с номером 5.

Алгоритмы обработки

—Войти и решать

The Bessie Shuffle (gold)#89865

Беси практикуется в карточных фокусах. Она уже освоила Беси-тасование – тасование M (2 <= M <= 100,000) карт, так чтобы i-ая карта сверху становилась P[i]-ой картой сверху.
Теперь она переходит на бОльшие колоды. У неё есть колода из N (M <= N <= 1,000,000,000) карт, последовательно пронумерованных от 1 до N. Она тасует её следующим образом: берёт первые M карт, и выполняет их Беси-тасование, затем снова кладёт их наверх колоды. Далее она удаляет верхнюю карту из колоды и кладёт ее на стол значением вниз. Она повторяет этот процесс, выкладывая забираемые карты поверх друг друга, пока карты не кончатся. Когда у неё в исходной колоде остаётся меньше чем M карт, она прекращает выполнять Беси-тасование, но продолжает брать верхнюю карту и выкладывать её поверх ранее взятых.
Беси знает, что изначально колода находится в отсортированном порядке, Причём карта 1 наверху, карта 2 следующая и т.д. По заданному описанию Беси-тасования, вычислите какие карты окажутся на Q (1 <= Q <= N, Q <= 5,000) различных указанных позициях колоды.
В 50% тестов N<=100,000.
PROBLEM NAME: shufflegold
Формат входных данных
* Строка 1: Числа N, M и Q разделенные одиночными пробелами
* Строки 2..1+M: Строк i+1 указывает позицию сверху колоды, P[i], на которую переместиться i-ая карта после Беси-тасования (1 <= P[i] <= M).
* Строки 2+M..1+M+Q: Строка i+1+M содержит одно целое число q_i описывающее i-ый запрос. Вы должны вычислить значение на карте, которая окажется в позиции q_i сверху (1 <= q_i <= N).
Формат выходных данных
* Строки 1..Q: На i-ой строке, выведите одно целое число, указывающее карту, которая окажется на позиции q_i сверху.
Примечание
Тасование происходило так
[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (выкладываем 2 значением вниз) [3, 1, 4, 5] -> [1, 4, 3, 5] (выкладываем 1 значением вниз) [4, 3, 5] -> [3, 5, 4] (выкладываем 3 значением вниз) [5, 4] (выкладываем 5 значением вниз) [4] (выкладываем 4 значением вниз)
Финальный расклад [4, 5, 3, 1, 2]

Задача на реализацию

—Войти и решать

Record Keeping#89862

Фермер Джон детально записывает порядок прихода коров на дойку. Каждый час группа из трёх коров входит в амбар и ФД записывает их имена. Например, за 5 часов он имеет такой список, где каждая строка соответствует группе вошедших коров:
BESSIE ELSIE MATILDA FRAN BESSIE INGRID BESSIE ELSIE MATILDA MATILDA INGRID FRAN ELSIE BESSIE MATILDA
ФД заметил, что одна и та же группа коров может несколько раз появляться в этом списке. Например, группа BESSIE, ELSIE и MATILDA появляется три раза (ФД необязательно записывает их имена в одинаковом порядке при каждом входе в амбар).
Помогите ФД посчитать количество приходов той группы, которая пришла наибольшее количество раз.
PROBLEM NAME: records
Формат входных данных
* Строка 1: Количество часов, N, в течение которых ФД вёл запись (1 <= N <= 1000).
* Строки 2..1+N: Каждая строка содержит список из трёх разделенных одиночными пробелами имён. Каждое имя имеет длину от 1 до 10 символов и стоит только из символов A-Z.

Формат выходных данных
* Строка 1: Количество приходов той группы, которая пришла наибольшее количество раз.
Примечание
Группа {BESSIE, ELSIE, MATILDA} вошла в амбар 3 раза.

Словари

—Войти и решать

Cows in a Row#89851

У Фермера Джона N коров (1 <= N <= 1000) выстроены в ряд. У каждой коровы имеется ID породы. У коровы с номером i, ID породы B(i).
ФД думает, что его ряд коров выглядел бы более впечатляюще, если бы он имел как можно более длинный непрерывный блок коров с одинаковым ID коровы. Для того, чтобы создать такой блок, ФД решил удалить из своего ряда всех коров, имеющих конкретный ID породы, который он выберет.
Помогите ФД определить длину наибольшего непрерывного блока коров с одинаковым ID, который он может получить, удалив всех коров с некоторым ID, который выберет ФД.

PROBLEM NAME: cowrow
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит B(i), целое число в диапазоне 0...1,000,000.
Формат выходных данных
* Строка 1: Наибольший размер непрерывного блока коров, с одинаковым ID коровы, который он может создать.

Примечание
При удалении всех коров с ID=3, ФД может получить ряд 2, 7, 7, 7, 7, 5, 7. В этому ряду максимальный непрерывный блок состоит из 4 коров с ID 7.

Алгоритмы обработки

✓ 1✗ 1—Войти и решать

Clumsy Cows#89849

Определите минимальное количество символов в строке из круглых скобок, которые нужно заменить на противоположный ( левую скобку на правую, или наоборот) , чтобы получить сбалансированную строку.
Существует несколько способов определить сбалансированную строку скобок. Например, такой: В строке должно быть одинаковое количество левых и правых скобок, и для любого ее префикса количество левых скобок должно быть не меньше, чем количество правых скобок.
Например, эти строки - сбалансированные () (()) ()(()())
А эти - нет: )( ())( ((())))
PROBLEM NAME: clumsy
Формат входных данных
* Строка 1: строка из скобок длиной не более 100,000 символов.

Формат выходных данных
* Строка 1: Одно целое число - минимальное количество скобок, которые нужно "переключить" , чтобы конвертировать заданную строку в сбалансированную.

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

Линейные алгоритмы

—Войти и решать

Find the Cow!#89842

нн
Беси сбежала и прячется на холме, покрытом высокой травой. Фермер Джон, пытаясь поймать Беси решил ползти по траве на руках и коленях, так чтобы подобраться незамеченным.
Трава перед Фермером Джоном выглядит как строка из N круглых скобок (1 <= N <= 50,000), например
)((()())())
Фермер джон знает, что задние ноги Беси выглядят как две соседних левых скобок ((, а пара ее передних ног выглядит, как пара соседних праваых скобок )). Поэтому местоположение Бес,и может быть описано парой индексов x < y таких, что (( находятся на позиции x, а )) находятся на позиции y.
Вычислите количество различных позиций, в которых может находится Беси.
PROBLEM NAME: cowfind
Формат входных данных
* Строка 1: строка из скобок, длиной N (1 <= N <= 50,000).
Формат выходных данных
* Строка 1: Количество позиций, в которых Беси может стоять (то есть количество таких различных пар (x,y), что x < y и (( стоят на позиции x, а )) стоят на позиции y )

Примечание
Всего имеется четыре варианта расположения Беси, они указаны ниже:
1. )((()())()) ^^ ^^
2. )((()())()) ^^ ^^
3. )((()())()) ^^ ^^
4. )((()())()) ^^ ^^

Строки

—Войти и решать

Haybale Stacking#89826

Беси согласилась помочь ФД уложить пакеты с сеном. Она начинает с N (1 <= N <= 1,000,000, N нечетное) пустых стеков, пронумерованных от 1 до N. Затем ФД дает ей последовательность из K инструкций (1 <= K <= 25,000), каждая вида A B, означающая, что Беси должна добавить по одному пакету с сеном в каждый из стеков в диапазоне от A до B. Например, инструкция 10 13 означает, что Беси должна положить по пакету сеном в стеки 10, 11, 12, 13.
После того как вся работа закончена, ФД хочет узнать медианную высоту всех N своих стеков - то есть высоту среднего стека, если все стеки упорядочить по высоте. По условию N нечетно, поэтому этот стек уникален. Пожалуйста, помогите Беси ответить на этот вопрос.
PROBLEM NAME: stacking
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N K.
* Строки 2..1+K: Каждая строка содержит одну инструкцию ФД в виде двух целых (разделенных пробелом) чисел A B (1 <= A <= B <= N).

Формат выходных данных
* Строка 1: Медианная высота после того как Беси выполнит все инструкции

Примечание
После того, как Беси закончит, стеки будут иметь высоты 0,1,2,3,3,1,0. Если их упорядочить, получим: 0,0,1,1,2,3,3. Средний элемент равен 1.

Алгоритмы обработки Использование сортировки Префиксные суммы(минимумы, ...)

—Войти и решать

Contest Timing#89797

Problem 1: Contest Timing [Brian Dean]
Бесси надоело давать молоко, и она хочет сделать карьеру в компьютерной Индустрии. Чтобы улучшить свои навыки в кодировании, она решила поучаствовать в USACO-олимпиаде. Поскольку олимпиада начинается 11 ноября 2011 года (11/11/11), она решил загрузить условия и начать кодировать ровно в 11:11 утра 11/11/11.
К несчастью, Бесси не очень хорошо умеет планировать время, поэтому она хочет написать программу, которая поможет ей не превысить три часа (180 минут) во время выполнения заданий. По заданным дате и времени завершения работы, помогите Бесси вычислить общее количество минут, которое она потратит на контест.
PROBLEM NAME: ctiming
Формат входных данных
* Строка 1: Эта строка содержит три целых, разделенных одиночными пробелами, числа D H M, указывающих дату и время, когда Бесси закончит контест. D – целое число в диапазоне 11..14, указывает день месяца H и M часы и минуты на 24-часовыъх часах От 0 0 в полночь до H=23, M=59 в конце суток (момент времени 11:59 PM)
Формат выходных данных
* Строка 1: Общее количество минут, которое проведет Бесси на контесте, или –1, если время завершения раньше чем время начала.
Примечание
Бесси закончит контест через 1563 минуты после того как начнет.

Дата и время

✓ 1✗ 0—Войти и решать

Hay Bales#89789

Коровы вернулись! Фермер Джон аккуратно выстроил N (1 <= N <= 10,000) столбиков одинаковой высоты из пакетов сена. Однако пока он отошел ненадолго, коровы поперетаскивали некоторые пакеты между столбиками, так что теперь они необязательно имеют одинаковую высоту. По заданным новым высотам столбиков определите минимальное количество пакетов сена, которые нужно перенести, чтобы вернуть столбики к их исходным, одинаковым высотам.
PROBLEM NAME: haybales
Формат входных данных
* Строка 1: Количество столбиков, N (1 <= N <= 10,000). * Строки 2..1+N: Каждая строка содержит количество пакетов сена в одном столбике (целое число, от 1 до 10 000)
Формат выходных данных
* Строка 1: Одно целое число - минимальное количество пакетов сена, которое необходимо перенести, чтобы столбики стали одинаковой высоты.
Примечание
Переместив 7 пакетов сена, мы можем выровнять к 5 все высоты. 3 из столбика 2 в столбик 1, 2 из столбика 2 в столбик 4, 2 из столбика 3 в столбик 4.

Алгоритмы обработки

✓ 1✗ 3—Войти и решать

Победитель выборов#89748

На выборах мэра баллотируются три кандидата (номера 1, 2, 3). Побеждает кандидат, набравший строго больше голосов, чем каждый из остальных. Если два или три кандидата набрали одинаковое максимальное число голосов, выведите REPEAT (необходим второй тур).

Входные данные

Первая строка — целое число N (1 <= N <= 10000) - количество проголосовавших.
Каждая из следующих N строк содержит одно число (1, 2 или 3) - результат голосания каждого избирателя.

Выходные данные

Номер победителя или REPEAT.

Алгоритмы обработки

✓ 6✗ 11600лёгкаяВойти и решать