Информатика

7 600 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Fruit Feast#90346
Беси забралась на кухню Фермера Джона и обнаружила там кучу лимонов и апельсинов там (неограниченное количество и того и другого) и хочет съесть как можно больше .

Максимум сытости Беси равен \(T\) (\(1 \le T \le 5,000,000\)). Поедание апельсина увеличивает её сытость на \(A\), а поедание лимона увеличивает её сытость на \(B\) (\(1 \le A, B \le T\)). Дополнительно, если она хочет, Беси может попить воды не более одного раза, что мгновенно уменьшит её сытость вдвое (с округлением вниз).

Помогите определить Беси максимальную сытость, которую она сможет достичь.

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

Первая и единственная строка содержит три целых числа \(T\), \(A\), and \(B\).

Формат выходных данных:

Одно целое число, представляющее максимальную сытость, которую может достичь Беси.

Динамическое программирование: один параметр
—Войти и решать
Fence Painting#90345
Несколько сезонов жарких лет и холодных зим изрядно подпортили изгородь Фермера Джона, и он решил перекрасить её с помощью своей любимой коровы Беси. Беси отлично красит, но к несчастью плохо понимает команды ФД.

Если мы рассмотрим изгородь ФД как одномерную числовую прямую, то ФД закрашивает интервал между \(x=a\) and \(x=b\). Например, если \(a=3\) and \(b=5\), то ФД закрашивает интервал длиной 2. Беси, не понимая команды ФД, закрашивает интервал от \(x=c\) to \(x=d\), который может частично или полностью перекрываться с интервалом ФД. Пожалуйста, определите общую длину изгороди которую покрасят ФД и Беси.

Формат ввода (файл paint.in):

Первая строка ввода содержит целые числа \(a\) и \(b\), разделённые одним пробелом (\(a < b\)).

Вторая строка содержит целые числа \(c\) и \(d\), разделённые одним пробелом (\(c < d\)).

Значения \(a\), \(b\), \(c\), \(d\) все лежат в интервале \(0 \ldots 100\), включительно.

Формат вывода (файл paint.out):

Выведите в одной строке общую длину изгороди, покрытой краской.

Разбор случаев
—Войти и решать
Counting Haybales#90344

Ферма Джона состоит из \(N\) полей в ряд последовательно пронумерованных \(1 \ldots N\). На каждом поле может быть произвольное количество стогов сена. Инструкции ФД бывают трёх видов:

1) Добавить один стог к каждому полю в указанном интервале

2) Определить минимальное количество стогов сена внутри указанного непрерывного интервала полей.

3) Посчитать суммарное количество стогов сена внутри указанного непрерывного интервала.

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

Первая строка содержит два положительных целых числа \(N\) (\(1 \leq N \leq 200,000\)) и \(Q\) (\(1 \leq Q \leq 100,000\)).

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

Каждая из следующих \(Q\) строк содержит одну большую латинскую букву M, P или S, за которой следуют два положительных целых числа \(A\) and \(B\) (\(1 \leq A \leq B \leq N\)), или три положительных целых числа \(A\), \(B\), and \(C\) (\(1 \leq A \leq B \leq N\); \(1 \leq C \leq 100,000\)). 3 числа будет только в том случае, если первая буква P.

Если первая буква M выведите минимальное количество стогов сена в интервале полей \(A \ldots B\).

Если первая буква P, добавьте по \(C\) стогов сена в каждое поле в интервале \(A \ldots B\).

Если первая буква S, выведите суммарное количество стогов сена в интервале полей \(A \ldots B\).

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

Строка в выводе должна появится в ответ на каждый запрос вида M или S.

Дерево отрезков, RSQ, RMQ
—Войти и решать
Contaminated Milk#90343
Фермер Джон, известный качеством молока, производимого на его ферме, проводит молочную вечеринку для \(N\) своих лучших друзей (\(1 \leq N \leq 50\)). Из \(M\) сортов молока, подготовленных к вечеринке , (\(1 \leq M \leq 50\)) ровно один испортился, но ФД не знает какой. Тому, кто его выпьет, станет плохо.

Вам дали протокол вечеринки - кто что и когда пил, а также кому стало плохо. Основываясь на этой информации, Вы должны определить какие сорта молока возможно плохие.

Формат входных данных:

Первая строка ввода содержит числа \(N\), \(M\), \(D\), \(S\).

Каждая из следующих \(D\) строк (\(1 \leq D \leq 1000\)) содержит три целых числа \(p, m, t\), указывающих, что персона \(p\) выпила сорт молока \(m\) в момент времени \(t\). Значение \(p\) находится в интервале \(1 \ldots N\), \(m\) в интервале \(1 \ldots M\), и \(t\) в интервале \(1 \ldots 100\). Кажды человек может пить один и тот же сорт молока несколько раз, и может пить несколько сортов молока в один и тот же момент времени.

Каждая из следующих \(S\) строк (\(1 \leq S \leq N\)) содержит два целых числа \(p, t\), указывающих, что персона \(p\) заболела в момент времени \(t\). Значение \(p\) в интервале \(1 \ldots N\), а значение \(t\) в интервале $1 \ldots 100$. Каждый человек заболеет не более одного раза, как следствие того, что он выпил плохое молоко в какой-то строго более ранний момент времени.

Формат вывода (файл badmilk.out):

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

Перебор
—Войти и решать
Breed Counting#90342
\(N\) коров Фермера Джона, последовательно пронумерованных от \(1 \ldots N\), выстроены в ряд. Каждая корова имеет ID породы: 1 - Holsteins, 2 - Guernseys, 3 - Jerseys. ФД просит Вас посчитать количество коров каждой породы, внутри некоторого интервала этого порядка.

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

Первая строка ввода содержит \(N\) и \(Q\) (\(1 \leq N \leq 100,000\), \(1 \leq Q \leq 100,000\)).

Следующие \(N\) строк содержат целое число 1,2, или 3 - ID породы соответствующей коровы.

Следующиеt \(Q\) строк описывают запрос в виде двух целых чисел \(a, b\) (\(a \leq b\)).

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

Для каждого из \(Q\) запросов \((a,b)\), выведите строку, содержащую три целых числа количество коров в интервале \(a \ldots b\), имеющих номера пород 1,2,3.

Префиксные суммы(минимумы, ...)
—Войти и решать
Bessie's Dream#90341
После столь обильного поедания фруктов на кухне Фермера Джона, Беси посетили странные мечты. Она попала в лабиринт в форме решётки клеток \(N \times M\) (\(1 \le N, M \le 1,000\)). Она начинает в левой верхней клетке и хочет попасть в правую нижнюю. Когда она стоит в клетке, он может шагнуть в любом из четырёх направлений (вверх, вниз, вправо, вверх).

Однако подождите! Каждая клетка имеет свой цвет, и каждый цвет имеет различные свойства:

  • Если клетка red (красная), то в неё ходить нельзя
  • Если клетка pink (розовая), то в неё можно ходить
  • Если клетка orange (оранжевая), то в неё можно ходить, но Беси станет пахнуть как апельсин.
  • Если клетка blue (синяя) , то она содержит пираний, которые позволят Беси пройти только если она пахнет как апельсин.
  • Если клетка purple (пурпурная), то Беси проскальзывает в следующую клетку в этом направлении (если только в следующую клетку можно заходить). Если следующая клетка также пурпурная, Беси продолжает скользить, пока не попадёт в не пурпурную клетку или остановится перед непроходимой клеткой. Скольжение одной клетки засчитывается как один шаг. Пурпурные клетки также удаляют запах.

(Пример ниже подробнее поясняет "пурпурные" клетки)

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

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

Первая строка ввода содержит два целых числа \(N\) и \(M\), представляющие количество строк и столбцов лабиринта.

Каждая из следующих \(N\) строк имеет по \(M\) целых чисел, представляющих лабиринт:

  • Целое число '0' это красная клетка
  • Целое число '1' это розовая клетка
  • Целое число '2' это оранжевая клетка
  • Целое число '3' это синяя клетка
  • Целое число '4' это пурпурная клетка

Левая-верхняя и правая-нижняя клетки всегда будут '1'.

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

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

Обход в ширину
—Войти и решать
High Card Low Card (Gold)#90340
Беси и Эльза играют в простую карточную игру. Берётся колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\), и делят их поровну - \(N\) карт Беси и \(N\) карт Эльзе. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте. В первых \(N/2\) раундах очко зарабатывает тот игрок, у которого карта больше. А в последних \(N/2\) раундах очко выигрывает тот игрок, у которого карта меньше.

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

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

Первая строка ввода содержит значение N (\(2 \leq N \leq 50,000\); \(N\) чётное).

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

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

Выведите одну строку дающую максимальное количество очков, которое может заработать Беси.

Жадный алгоритм
—Войти и решать
Fruit Feast#90339
Беси забралась на кухню Фермера Джона и обнаружила там кучу лимонов и апельсинов там (неограниченное количество и того и другого) и хочет съесть как можно больше .

Максимум сытости Беси равен \(T\) (\(1 \le T \le 5,000,000\)). Поедание апельсина увеличивает её сытость на \(A\), а поедание лимона увеличивает её сытость на \(B\) (\(1 \le A, B \le T\)). Дополнительно, если она хочет, Беси может попить воды не более одного раза, что мгновенно уменьшит её сытость вдвое (с округлением вниз).

Помогите определить Беси максимальную сытость, которую она сможет достичь.

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

Первая и единственная строка содержит три целых числа \(T\), \(A\), and \(B\).

Формат выходных данных:

Одно целое число, представляющее максимальную сытость, которую может достичь Беси.

Динамическое программирование: один параметр
—Войти и решать
Bessie's Dream#90338
После столь обильного поедания фруктов на кухне Фермера Джона, Беси посетили странные мечты. Она попала в лабиринт в форме решётки клеток \(N \times M\) (\(1 \le N, M \le 1,000\)). Она начинает в левой верхней клетке и хочет попасть в правую нижнюю. Когда она стоит в клетке, он может шагнуть в любом из четырёх направлений (вверх, вниз, вправо, вверх).

Однако подождите! Каждая клетка имеет свой цвет, и каждый цвет имеет различные свойства:

  • Если клетка red (красная), то в неё ходить нельзя
  • Если клетка pink (розовая), то в неё можно ходить
  • Если клетка orange (оранжевая), то в неё можно ходить, но Беси станет пахнуть как апельсин.
  • Если клетка blue (синяя) , то она содержит пираний, которые позволят Беси пройти только если она пахнет как апельсин.
  • Если клетка purple (пурпурная), то Беси проскальзывает в следующую клетку в этом направлении (если только в следующую клетку можно заходить). Если следующая клетка также пурпурная, Беси продолжает скользить, пока не попадёт в не пурпурную клетку или остановится перед непроходимой клеткой. Скольжение одной клетки засчитывается как один шаг. Пурпурные клетки также удаляют запах.

(Пример ниже подробнее поясняет "пурпурные" клетки)

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

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

Первая строка ввода содержит два целых числа \(N\) и \(M\), представляющие количество строк и столбцов лабиринта.

Каждая из следующих \(N\) строк имеет по \(M\) целых чисел, представляющих лабиринт:

  • Целое число '0' это красная клетка
  • Целое число '1' это розовая клетка
  • Целое число '2' это оранжевая клетка
  • Целое число '3' это синяя клетка
  • Целое число '4' это пурпурная клетка

Левая-верхняя и правая-нижняя клетки всегда будут '1'.

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

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

Обход в ширину
—Войти и решать
Speeding Ticket#90337
Беси, которая всегда создаёт проблемы, украла трактор Фермера Джона и помчалась вниз по дороге!

Дорога имеет длину ровно 100 миль и Беси едет по ней, пока её не остановит офицер полиции и не вручит ей квитанцию о превышении скорости.

Дорога поделена на \(N\) участков, каждый описывается положительной длиной в милях, а также целым числом - пределом скорости на этом участке, в диапазоне \(1 \ldots 100\) миль в час. Поскольку длина дороги 100 миль, суммарная длина всех \(N\) участков равна 100. Например, дорога может начаться участком в 45 миль со скоростным пределом 70 миль в час, и затем будет участок в 55 миль, со скоростным пределом 60 миль в час.

Движение Беси тоже может быть описано серией участков - \(M\) штук. На каждом участке она проезжает определённое количество миль с определённой целочисленной скоростью. Например, она может ехать 50 миль со скоростью 65, а затем 50 миль со скоростью 55. Суммарная длина всех этих \(M\) участков также равна 100. Трактор ФД может двигаться со скоростью не более 100 миль в час.

По заданной выше информации, определите максимальное превышение скорости, которое допустила Беси во время путешествия.

Формат ввода (файл speeding.in):

Первая строка ввода содержит \(N\) и \(M\), разделённые одним пробелом.

Каждая из следующих \(N\) строк содержит два целых числа, описывающих участок дороги: задавая его длину и предел скорости

Каждая из следующих \(M\) строк содержит два целых числа, описывающих участок путешествия Беси: задавая его длину и скорость, на которой двигалась Беси.

Формат вывода (файл speeding.out):

Выведите одну строку, содержащую максимальное превышение предела скорости, которое допустила Беси. Если она никогда не превысила скорость, выведите 0.

Задачи на моделирование
—Войти и решать
Fence Painting#90336
Несколько сезонов жарких лет и холодных зим изрядно подпортили изгородь Фермера Джона, и он решил перекрасить её с помощью своей любимой коровы Беси. Беси отлично красит, но к несчастью плохо понимает команды ФД.

Если мы рассмотрим изгородь ФД как одномерную числовую прямую, то ФД закрашивает интервал между \(x=a\) and \(x=b\). Например, если \(a=3\) and \(b=5\), то ФД закрашивает интервал длиной 2. Беси, не понимая команды ФД, закрашивает интервал от \(x=c\) to \(x=d\), который может частично или полностью перекрываться с интервалом ФД. Пожалуйста, определите общую длину изгороди которую покрасят ФД и Беси.

Формат ввода (файл paint.in):

Первая строка ввода содержит целые числа \(a\) и \(b\), разделённые одним пробелом (\(a < b\)).

Вторая строка содержит целые числа \(c\) и \(d\), разделённые одним пробелом (\(c < d\)).

Значения \(a\), \(b\), \(c\), \(d\) все лежат в интервале \(0 \ldots 100\), включительно.

Формат вывода (файл paint.out):

Выведите в одной строке общую длину изгороди, покрытой краской.

Разбор случаев
—Войти и решать
Contaminated Milk#90335
Фермер Джон, известный качеством молока, производимого на его ферме, проводит молочную вечеринку для \(N\) своих лучших друзей (\(1 \leq N \leq 50\)). Из \(M\) сортов молока, подготовленных к вечеринке , (\(1 \leq M \leq 50\)) ровно один испортился, но ФД не знает какой. Тому, кто его выпьет, станет плохо.

Вам дали протокол вечеринки - кто что и когда пил, а также кому стало плохо. Основываясь на этой информации, Вы должны определить какие сорта молока возможно плохие.

Формат входных данных:

Первая строка ввода содержит числа \(N\), \(M\), \(D\), \(S\).

Каждая из следующих \(D\) строк (\(1 \leq D \leq 1000\)) содержит три целых числа \(p, m, t\), указывающих, что персона \(p\) выпила сорт молока \(m\) в момент времени \(t\). Значение \(p\) находится в интервале \(1 \ldots N\), \(m\) в интервале \(1 \ldots M\), и \(t\) в интервале \(1 \ldots 100\). Кажды человек может пить один и тот же сорт молока несколько раз, и может пить несколько сортов молока в один и тот же момент времени.

Каждая из следующих \(S\) строк (\(1 \leq S \leq N\)) содержит два целых числа \(p, t\), указывающих, что персона \(p\) заболела в момент времени \(t\). Значение \(p\) в интервале \(1 \ldots N\), а значение \(t\) в интервале $1 \ldots 100$. Каждый человек заболеет не более одного раза, как следствие того, что он выпил плохое молоко в какой-то строго более ранний момент времени.

Формат вывода (файл badmilk.out):

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

Перебор
—Войти и решать
Piggyback#90334

Беси и её сестра Эльза пасутся на различных полях в течение дня, а вечером обе хотят вернуться в амбар отдыхать. Будучи умными коровами, они хотят составить план, чтобы минимизировать суммарное количество энергии, которое они обе потратят на это путешествие.
Беси тратит B единиц энергии, когда она переходит с одного поля на соседнее поле, а Эльза тратит E единиц энергии при переходе на соседнее поле. Однако, если Беси и Эльза оказались на одном поле, то Беси может нести Эльзу на своих плечах, и тогда обе могут переместиться на соседнее поле, потратив только P единиц энергии, (где P может быть существенно меньше, чем B+E - количество энергии, которое затрачивается двумя коровами вместе, если они перемещаются на соседнее поле по отдельности). Если P очень маленькое, то коровам выгоднее перемещаться вместе, а если P очень большое - то по отдельности.
По заданным B, E, P и расположению полей на ферме, вычислите минимальное количество энергии, которое потребуется Беси и Эльзе, чтобы добраться до амбара.
Формат входных данных
Первая строка ввода содержит положительные числа B, E, P, N, M. Все они не превышают 40,000. B, E, P описаны выше. N - количество полей на ферме, пронумерованных от 1 до N, N>=3. M - количество дорожек между полями. Беси и Эльза начинают в полях 1 и 2 соответственно. Амбар расположен в поле N.
Каждая из следующих M строк ввода описывает дорожку между парой различных полей, указанную номерами этих полей. Дорожки двунаправленные. Всегда можно добраться от поля 1 до поля N и от поля 2 до поля N посредством некоторого количества дорожек.

Формат выходных данных
Одно целое число, указывающее минимальное количество энергии, которое суммарно потратят Беси и Эльза, чтобы добраться до амбара. В примере, приведенном выше, Беси перемещается от 1 к 4, Эльза перемещается от 2 к 3, затем к 4. Потом они перемещаются вместе от 4 к 7, затем к 8.

Обход в ширину
—Войти и решать
Marathon#90333

Беси участвует в марафоне.
Маршрут марафона состоит из N контрольных точек (3 <= N <= 500),
которые надо посетить по порядку, причём контрольная точка 1 -
старт, контрольная точка N - финиш.

Беси решил пропустить до K (K сократить себе маршрут. Она не может пропустить контрольные точки
1 и N.

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

Поскольку марафон проводится на улицах Манхэттена, то и расстояние
между точками (x1, y1) и (x2, y2) нужно определять манхэттенское:
|x1-x2| + |y1-y2|.

INPUT: (файл marathon.in)

В первой строке задаются N и K.
Каждая из следующих N строк содержит два разделённых пробелом целых
числа x и y, представляющих контрольную точку (-1000 <= x <= 1000,
-1000 <= y <= 1000). Контрольные точки даны в порядке, в котором они
должны посещаться.

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

Формат выходных данных

Выведите миниальное расстояние, которое Беси может пробежать,
пропустив до K контрольных точек. В данном примере, пропустив
точки (8,3) и (10,-5) она пробежит минимальное растояние, равное 4.

Задача на реализацию
—Войти и решать
Cow Jog#90332

N (1 <= N <= 100,000) коров бегут по одной бесконечно длинной дорожке.
Все коровы начинают в различных позициях и некоторые коровы бегут с
разной скоростью.

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

Забег длится T минут (1 <= T <= 1,000,000,000).
Определите, сколько групп образуется к концу забега.
Две коровы рассматриваются принадлежащими к одной группе, если
они окажутся в одной позиции в конце T минут.

Формат входных данных

Первая строка ввода содержит два целых числа N и T.

Каждая из следующих N строк содержит начальную позицию и скорость
одной коровы. Позиция - неотрицательное целое число, а скорость -
положительное целое число. Оба числа не превысят 1 миллиард.
Все коровы начинают в различных позициях, заданных на вводе в порядке
возрастания.

Формат выходных данных

Одно целое число, указывающее сколько групп останется после T минут.

Жадный алгоритм
—Войти и решать
Marathon#90331

Беси спланировала марафон, специфицировав N контрольных точек
(1 <= N <= 100,000), которые нужно последовательно посетить.

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

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

Поскольку марафон проходит на улицах Манхэттена, расстояние между двумя
контрольными точками с координатами (x1, y1) и (x2, y2) надо вычислять
как манхэттенское: |x1-x2| + |y1-y2|.

Формат входных данных

В первой стоке хадаются N и Q (1 <= Q <= 100,000).
Последующие N строк содержат (x,y)- положение N контрольных точек в порядке
их посещения вдоль маршрута. Все координаты в интервале -1000 .. 1000.
Последующие Q строк состоят из изменений и запросов по одному в строке,
которые необходимо обрабатывать в том порядке, в котором они заданы.
Эти строки имеют вид "U I X Y" или "Q I J".

Строка в форме "U I X Y" указывает, что местоположение точки с номером
I (1 <= I <= N) должно быть изменено на (X Y).

Строка в форме "Q I J" спрашивает минимальное время прохождения подмаршрута
от контрольной точки I до контрольной точки J (I<=J), с учётом того, что
коровы могут выбрать пропустить одну контрольную точку вдоль этого подмаршрута
(кроме точек I и J).

Формат выходных данных

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

Префиксные суммы(минимумы, ...)
—Войти и решать
Guard Mark#90330

Фермер Джон и его стадо играют в фрисби. Беси бросает фрисби в поле,
и соирается бежать прямо к Марку.
Марк имеет высоту H (1 <= H <= 1,000,000,000), но имеется также N
(2 <= N <= 20) коров из команды Беси вокруг Марка . Они могут поймать
Фрисби, только если став друг на друга, они построят пирамиду высотой
не менее, чем высота Марка.
Каждая из N коров имеет высоту, вес и силу.
Сила указывает максимальный суммарный вес, который может находиться
выше её.

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

Максимальный коэффициент безопасности пирамиды - количество веса,
которое может быть добавлено, на её вершину, так чтобы не превысить
силу ни одной из коров.

Формат входных данных

Первая строка ввода содержит N и H.

Каждая из следующих N строк ввода описывает одну корову, задавая
её высоту, вес и силу. Все числа положительные, не превышающие
1 миллиард.

Формат выходных данных

Если команда Беси может построить пирамиду, достаточную, чтобы поймать
фрисби, выведите максимально достижимый фактор безопасности для такой
пирамиды. Иначе выведите фразу "Mark is too tall" (без кавычек).

Задача о рюкзаке
✓ 1✗ 2—Войти и решать
Cow Jog#90329

N (1 <= N <= 100,000) коров фермера Джона бегут по бесконечной
трассе. Все коровы начинают в различных позициях и некоторые
коровы бегут с различной скоростью.

Трасса поделена на дорожки, поэтому коровы могут обгонять друг
друга. Никакие две коровы на одной и той же дорожке не могут
занимать одну и ту же позицию.

Фермер Джон хочет, чтобы никакая корова не меняла свою дорожку
или изменяла свою скорость. И он интересуется, сколько дорожек
ему нужно, если коровы будут бежать T минут (1 <= T <= 1,000,000,000).

Формат входных данных

Первая строка ввода содержит N и T.
Каждая из последующих N строк содержит начальную позицию и скорость
одной коровы. Позиция - это неотрицательное целое число, а скорость -
положительное целое число, оба не более 1 миллиарда. Все коровы начинают
в различных позициях, заданных в порядке возрастания на вводе.

Формат выходных данных

Одно целое число, указывающее минимальное количество дорожек,
необходимое, чтобы никакие две коровы не занимали на одной и той же
дорожке одну и ту же позицию в течение времени T (включительно).

Жадный алгоритм
—Войти и решать
Learning by Example#90327

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

К несчастью, ФД не ученье удачно собрал данные о своих коровах
Для каждой из его N(1 <= N <= 50,000) коров, всё что он знает, это
вес коровы и имеет или нет она пятна. Все его коровы имеют
различный вес. По этим данным он построил то, что он назвал,
"классификатор ближайшего соседа". Чтобы угадать, есть у новой
коровы C пятно или нет, он сначала находит в своём стаде корову С'
такую, что её вес ближайший к C'. Если корова C' имеет пятна,
то ФД предполагает, что корова C имеет пятна, если корова C'
не имеет пятен, то ФД предполагает, что и корова C не имеет пятен.
Если же уникального ближайшего соседа нет, а есть две коровы
на одинаковом минимальном расстоянии от C', тогда ФД предполагает,
что корова C имеет пятна, если одна из двух ближайших коров
также имеется пятна.

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

Пожалуйста, определите, сколько из этих коров будут классифицированы
как имеющие пятна. Заметим, что классификатор делает предсказание,
основываясь на данных об N существующих коровах.
Также заметим, что A и B могут быть достаточно большими числами,
так что просто проверка всех чисел по одному от A до B не пройдёт
по времени.

Формат входных данных

Первая строка ввода содержит три целых числа N,A,B
(1 <= A <= B <= 1,000,000,000).

Каждая из следующих N строк описывают одну корову. Каждая строка
содержит либо S W, означающее, что корова с весом W имеет пятна
или NS W, означающее, что корова с весом W не имеет пятен.
Все веса - целые числа в интервале 1 ... 1 000 000 000.

Формат выходных данных

Одно целое число - количество коров из прибывших,
которых алгоритм ФД классифицирует как пятнистых.

В приведенном примере новые коровы с весами
1, 2, 7, 8, 9, 10
будут классифицированы как пятнистые.

Классификация по фиксированному правилу
—Войти и решать
Crosswords#90326

Беси любит разгадывать кроссворды.
Однако её сестра Эльза пролила молоко на кроссворд,
и теперь Вам предстоит его восстановление (номеров
загаданных слов).

Вам даётся кроссворд, как решётка N*M (3 <= N <=
50, 3 <= M <= 50). Некоторые из клеток пусты (обычно они
белые), а некоторые заблокированы (обычно они чёрные).

Теперь процесс присвоения номеров загаданным словам -
это простой процесс из двух логических шагов:

Шаг 1: Для каждой ячейки мы определяем, начинает ли она
горизонтальное загаданное слово, или вертикальное
загаданное слово. Чтобы ячейка начинала горизонтальное
загаданное слово, нужно, чтобы её левая соседка была
заблокированной ячейкой или лежала вне кроссворда и две
клетки вправо от неё должны быть пустыми. (То есть
горизонтальное загаданное слово всегда содержит 3 или более
символов). Правила для ячейки, начинающей вертикальное
загаданное слово аналогичны: ячейка сверху должна быть
заблокирована или вне кроссворда и две клетки вниз
должны быть пустыми.

Шаг 2: Мы назначаем номер каждой ячейке, которая начинает
слово, последовательно от 1 в том же порядке, в котором
мы читаем книгу.
В первой строке назначаем числа слева направо, затем во
второй строке назначаем числа слева направо и т.д.
Числа назначаются только ячейкам, начинающим слова.

Например, рассмотрим кроссворд, где пустые ячейки отмечены
символами '.'. а блокированные ячейки отмечены символами '#'.

...
#..
...
..#
.##

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

!!!
#..
!..
..#
.##

Номера должны быть таковы:

123
#..
4..
..#
.##

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

Формат входных данных

Первая строка ввода содержит N и M, разделённые
одиночным пробелом.

Последующие N строк ввода описывают строки
решётки. Каждая состоит из M символов, каждый из которых
либо '.' (пустая ячейка) либо '#' (блокированная ячейка).

Формат выходных данных

На первой строке выведите количество загаданных слов.
На каждой из оставшихся строк выведите строку и колонку
дающую позицию одного слова (в порядке, описанном выше).
Верхняя левая ячейка имеет позицию (1,1). Нижняя правая
ячейка имеет позицию (N,M).

Задача на реализацию
—Войти и решать
Поделиться
Класснуть