Информатика

Мы можем описать эту сторону амбара как двумерную плоскость, на которой ФД рисует \(N\) прямоугольников, стороны которых параллельны осям координат, Прямоугольники описываются координатами левого нижнего и правого верхнего углов.

ФД хочет покрасить амбар в несколько слоёв, так чтобы не пришлось вскорости снова красить. Однако, он не хочет тратить время на лишнюю покраску. Сначала он решил, что оптимально покрасить \(K\) раз. Однако оглядев область Амбара, покрашенную ровно \(K\) раз, он решил добавить два прямоугольника, Так, чтобы максимально увеличить площадь, покрашенную ровно \(K\) раз, так чтобы эти прямоугольники не имели общей ненулевой площади пересечения. Заметим, что он может рисовать ноль новых прямоугольников или только один прямоугольник, если это может улучшить результат.

Как и уже нарисованные прямоугольники, новые должны иметь положительную площадь, а координаты их углов \(x\) и \(y\) должны быть в интервале \(0 \ldots 200\).

Всего имеется \(N\) различных аттракционов (\(2 \leq N \leq 10^5\)). Определённые пары аттракционов связаны дорожками, которых всего \(N-1\) штук, таким образом, что существует единственный путь, состоящий из различных дорожек между любыми двумя аттракционами. Каждый аттракцион \(i\) имеет целую величину удовольствия \(e_i\), которая может измениться в течение дня, поскольку некоторые аттракционы более привлекательны утром, а некоторые - вечером.

Корова, которая проходит от аттракциона \(i\) до аттракциона \(j\) получает удовольствие всех аттракционов маршрута от \(i\) до \(j\). Забавно, что общее удовольствие от всего маршрута вычисляется как побитовое XOR всех удовольствий в течение маршрута, включая удовольствия в аттракционах \(i\) и \(j\).

Помогите коровам определить величины удовольствий маршрутов, которые коровы собираются пройти в CowLand.

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

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

К несчастью, ФД уронил свои датчики в молоко, и теперь они работают не очень хорошо. Вместо вывода точного значения трафика, датчик теперь выдаёт диапазон возможных значений. Например, датчик может показывать диапазон \([7, 13]\), означающий, что плотность трафика на этом участке не меньше чем 7 и не больше чем 13.

Шоссе вдоль фермы имеет протяжённость в \(N\) миль и движение происходит в одном направлении от мили 1 к миле \(N\). ФД хочет установить \(N\) датчиков, по одному на каждом одномильном сегменте шоссе. В некоторых из этих сегментов имеются пандусы для въезда, которые позволяют трафику вливаться на шоссе; в каждом из таких случаев ФД устанавливает свой датчик так, чтобы измерять (примерно) входящий трафик. В некоторых сегментах имеются пандусы для выезда, здесь ФД устанавливает датчик так, чтобы измерять выходящий трафик. Каждый сегмент содержит не более одного пандуса. Если на сегменте нет пандусов, ФД устанавливает датчик на собственно шоссе.

По заданным показаниям \(N\) датчиков, определите наиболее точно диапазоны, описывающие движение на шоссе от мили 1 к миле \(N\). Эти диапазоны должны не противоречить показаниям всех \(N\) датчиков.

ФОРМАТ ВВОДА:

4
on 1 1
none 10 14
none 11 15
off 2 3

ФОРМАТ ВЫВОДА:

10 13
8 12

В этом примере, комбинация считываний датчиков с сегментов 2 и 3 сужает интервал до \([11, 14]\), поскольку только показания в этом интервале соответствуют обоим считываниям \([10,14]\) и \([11,15]\). На миле 1 ровно значение 1 представляет входящий трафик, поэтому входящий трафик может быть в диапазоне \([10, 13]\). На миле 4 от 2 до 3 единиц потока может покинуть трафик, поэтому выходной поток после мили 4 может быть \([8,12]\).

Автор: Brian Dean

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 \)-ое число, которое говорят в этой игре.

Беси добавила нос к одному из снежков, поэтому он представляет собой голову этой абстрактной снежной коровы. Она обозначила это снежок числом 1. Чтобы усилить визуальный эффект, она планирует покрасить некоторые из снежков различными цветами. Цвета обозначаются числами в интервале \(1 \ldots 10^5\), и у Беси неограниченное количество красок всех цветов.

Когда Беси красит снежок в определённый цвет, все снежки в его поддереве также красятся в этот же цвет. (Снежок \(y\) находится в поддереве снежка \(x\), если \(x\) находится на пути от \(y\) к головному снежку). Занимаясь покраской, Беси обеспечивает, чтобы все цвета, которыми она красила снежки, оставались видимыми. Например, если у снежка есть цвета \([1,2,3]\) и Беси красит цветом \(4\), на снежке останутся следы цветов \([1,2,3,4]\).

После некоторого количества раскрашиваний, Беси хочет узнать, как раскрашена часть её коровы. Полнота цветов("colorfulness") снежка \(x\) равно количеству различных цветов \(c\), которыми раскрашен этот снежок \(x\). Если Беси спросит Вас о снежке \(x\), Вы должны ответить сумму полноты цветов всех снежков в поддереве \(x\).

Помогите Беси определить полноту цветов в определённые моменты времени.

1 x c

2 x

Вдоль дороги имеется \(N\) ферм (\(1 \leq N \leq 100\)). На фермах нет номеров, поэтому ФД тяжело ориентироваться. Зато на каждой ферме имеется цветной почтовый ящик со стороны дороги. поэтому ФД надеется, что если он посмотрит на цвета ближайших почтовых ящиков, он сможет однозначно определить, где он находится.

Каждый цвет почтового ящика обозначается буквой в интервале A..Z, таким образом, последовательность \(N\) почтовых ящиков вдоль дороги представляется строкой длины \(N\), содержащей символы в интервале A..Z. Некоторые почтовые ящики могут иметь одинаковые цвета. ФД хочет узнать минимальное число \(K\) такое, что если он посмотрит на любую последовательность из \(K\) последовательных ящиков, он уникально определит местоположение этой последовательности на дороге.

Например, предположим, что последовательность ящиков вдоль дороги есть 'ABCDABC'. ФД не может выбрать \(K=3\), поскольку если он увидит 'ABC', то имеется два расположения такой строки вдоль дороги. Минимальное значение \(K\), которое работает, \(K=4\), поскольку любые последовательные 4 символа уникально определяют его позицию вдоль дороги.

К несчастью, коровы довольно разборчивы и требуют, чтобы ФД доил их в порядке, который соответствует \(N\) ограничениям (\(1 \leq N \leq 7\)). Каждое из ограничений имеет вид "\(X\) must be milked beside \(Y\)" ("\(X\) необходимо подоить рядом \(Y\)"), что означает, что в порядке дойки корову \(X\) нужно доить сразу после коровы \(Y\) или непосредственно перед коровой \(Y\).

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

Чтобы улучшить свои фигуры коровы занялись гимнастикой. Фермер Джон назначил любимую корову Бесси тренером для \(N\) других коров. В каждом из \(K\) практических занятий (\(1 \leq K \leq 10\)), Бесси ранжирует \(N\) коров в соответствии с их результатами (\(1 \leq N \leq 20\)).

Сейчас она интересуется состоятельностью этих ранжировок. Пара различных коров называется "состоятельной", если одна корова выполняла лучше другой все практические упражнения.

Помогите Бесси вычислить количество состоятельных пар.

Её любимый алгоритм - пузырьковая сортировка. Ниже приведена его реализация в коровьем коде, которая сортирует массив \(A\) длины \(N\).

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Команда "moo" выводит слово "moo".

По данному массиву предскажите, сколько раз будет напечатано слово "moo" этим кодом Беси.

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

Беси знает, что у поезда есть \(N\) вагонов(\(1 \leq N \leq 10^6\)), последовательно пронумерованных \(0 \dots N-1\). Вагон \(i\) имеет ID номер \(c_i\), написанный на нём (\(0 \le c_i \le 10^9\)). Все номера видны и утром, и вечером, поэтому номер каждого вагона можно увидеть два раза. Когда поезд едет утром, Беси видит вагоны в таком порядке \(c_0\), \(c_1\), ... \(c_{N-1}\). Когда поезд едет вечером, Беси видит их в том же порядке: \(c_0\), \(c_1\), ... \(c_{N-1}\).

Беси выбрала целое число \(K\) (\(1 \leq K \leq N\)), и она хочет определить минимальный ID-номер для каждого непрерывного множества из \(K\) вагонов. У Беси есть ноутбук, на котором она может производить вычисления. Но он довольно маленький, а её копыта - большие. Например, она не может написать все \(N+1-K\) минимумов. Беси мычит ответы, после того, как вычислит их.

Поезд скоро прибудет, Помогите Беси определить \(N + 1 - K\) минимумов когда поезд проезжает дважды, будьте уверены , что она использует свой ноутбук эффективно. Её ноутбук поделен на \(5500\) секций, последовательно пронумерованных \(0 \dots 5499\), и каждая секция имеет место, чтобы хранить ровно одно целое число из интервала \(-2^{31}\) ... \(2^{31}-1\) включительно. Изначально в каждой секции хранится число \(0\).

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

void helpBessie(int ID);

Ваша функция будет вызываться с номером проходящего вагона в качестве параметра.

Ваша реализация функции \(\texttt{helpBessie}\) должна вызывать следующие функции:

• int get(int index): получает значение целого числа, которое хранится в ноубуке беси в данной ячейке index.
• void set(int index, int value): устанавливает значение целым числом value в ячейке index
• void shoutMinimum(int output): говорит Беси промычать данное число
• int getTrainLength(): возвращает \(N\), количество вагонов поезда.
• int getWindowLength(): возвращает \(K\), длину окна.
• int getCurrentCarIndex(): возвращает индекс вагона, который сейчас проходит.
• int getCurrentPassIndex(): возвращает \(0\) если Беси наблюдает утренний поезд и \(1\), если Беси наблюдает вечерний поезд.

Чтобы помочь Вам начать писать свой код, мы даём начальные шаблоны для C/C++ и Java. Python и Pascal не поддерживаются в этой задаче.

Минимумы окон должны выводится в таком порядке, что минимум из вагонов \(0, 1, \dots, K-1\) нужно вывести раньше чем минимум вагонов \(1, 2, \dots, K\) и т.д. Но помимо этого ограничения упорядочения,Ваша функция может выводить минимумы во время любого из её вызовов, в любое время. Например, Ваша функция может не выводить ответов во время некоторых вызовов или выводить множество ответов во время других вызовов.

Беси имеет фантастическую кратковременную память, по этой причине нет ограничения на использование памяти в функции \(\texttt{helpBessie}\) кроме обычного на 256 Мбт. Однако между вагонами Беси не способна помнить ничего не содержащегося в её ноутбуке. Поэтому между вызовами функции, Ваша программа не может хранить состояния - а только использовать вызовы \(\texttt{get}\) и \(\texttt{set}\) calls.

Это означает:

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

Общее количество вызовов \(\texttt{set}\) плюс общее количество вызовов \(\texttt{get}\), сделанные Вашей программой должны быть ограничены \(25 \cdot 10^6\) для каждого теста.

Назовём позицию между элементами \(i\) и \(i+1\) массива \(A\) точкой разбиения если максимум из \(A[...i]\) не больше чем минимум \(A[i+1 \ldots]\). Беси помнит, что быстрая сортировка реорганизует массив так, чтобы у него появилась точка разбиения, а затем рекурсивно сортирует две стороны \(A[...i]\) и \(A[i+1 \ldots]\). Однако хотя она помнит, что все точки разбиения можно найти за линейное время, она забыла как в быстрой сортировке реорганизуется массив, чтобы быстро создать точку разбиения. Она решила использовать пузырьковую сортировку для решения этой задачи

Ниже приведен алгоритм Беси Сначала она написала простую функцию, которая делает один проход пузырьковой сортировки:

bubble_sort_pass (A) {
   for i = 0 to length(A)-2
      if A[i] > A[i+1], swap A[i] and A[i+1]
}

Рекурсивный код Беси для "быстрой" сортировки такой:

quickish_sort (A) {
   if length(A) = 1, return
   do { // Main loop
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (no partition points exist in A) 
   divide A at all partition points; recursively quickish_sort each piece
}

Теперь Беси интересно, насколько быстро работает её код. Для простоты она считает, что её итерация работает линейно и поэтому она просто инкрементирует глобальную переменную work_counter внутри цикла текущим размером массива так, чтобы оценивать общую работу, выполненную алгоритмом.

По заданному входному массиву, предскажите финальное значение величины work_counter после завершения алгоритма quickish_sort.

Её любимый алгоритм называется "пузырьковая сортировка". Ниже приведена начальная его версия в коровьем коде для сортировки массива \(A\) из \(N\) элементов.

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Команда "moo" выводит слово "moo".

После тестирования кода на нескольких массивах, Беси сделала интересное наблюдение: в то время ка большие элементы становятся в конец массива очень быстро, маленькие элементы становятся в начало массива очень медленно. Для дальнейшего исследования проблемы, Беси модифицировала свой код так, чтобы её код сканировал элементы вперёд а затем назад на каждой итерации главного цикла, так чтобы и большие элементы и маленькие элементы быстро достигали границ массива. Ниже представлен её код.

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

По заданному входному массиву предскажите, сколько раз слово "moo" будет напечатано этим модифицированным кодом.

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

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

COW
XXO
ABC

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

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

1. Некоторые коровы настаивают чтобы их доили раньше - в соответствии с их социальным статусом. Например, корова 3 имеет наивысший статус, корова 3 имеет средний статус, а корова 5 имеет низкий статус, то корову 3 нужно доить первой, затем корову 2 и затем корову 5.

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

По счастью, ФД всегда может подоить своих коров в порядке, удовлетворяющем всем условиям.

К несчастью, корова 1 заболела, поэтому ФД хочет подоить эту корову как можно раньше, чтобы раньше отпустить её в амбар отдыхать и выздоравливать. Помогите ФД определить самую раннюю позицию, в которой можно будет подоить корову 1.

Чтобы обеспечить безопасность, он нанял \(N\) коров спасателями, каждый из которых работает в течение некоторого интервала времени в течение дня. Для простоты, бассейн открыт с момента времени \(t=0\) до момента времени \(t = 1,000,000,000\) каждый день. Поэтому каждый интервал может быть описан двумя целыми числами - временем начала и конца работы спасателя. Например, спасатель, начинающий в момент времени \(t = 4\) и завершающий в момент времени \(t = 7\), покрывает интервал в три единицы времени.

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

В некоторых целочисленных координатах имеются двухглавые разбрызгиватели, оба разбразгивают воду и удобрения. Разбрызгиватель в координатах \((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\).

Чтобы обеспечить безопасность, он нанял \(N\) коров спасателями, каждый из которых работает в течение некоторого интервала времени в течение дня. Для простоты, бассейн открыт с момента времени \(t=0\) до момента времени \(10^9\) каждый день. Поэтому каждый интервал может быть описан двумя целыми числами - временем начала и конца работы спасателя. Например, спасатель, начинающий в момент времени \(t = 4\) и завершающий в момент времени \(t = 7\), покрывает интервал в три единицы времени.

К несчастью, ФД нанял на \(K\) спасателей больше чем может платить зарплату. При условии, что он должен уволить ровно \(K\) спасателей, какой максимальный интервал времени, будет покрыт оставшимися спасателями? Интервал времени покрыт, если присутствует хоть один спасатель в это время.

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

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