Информатика

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

Игра начинается с последовательности \(N\) положительных целых чисел (\(2 \leq N \leq 248\)), каждое в диапазоне \(0 \ldots 40\). На каждом ходу Беси может взять два числа с равными величинами и заменить их число на 1 больше. (Например, она может заменить две соседние 7 на одну 8). Цель игры - максимизировать наибольшее число, которое она может получить. Помогите Беси.

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

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

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

Выведите максимальное число, которое может сгенерировать Беси.

Динамическое программирование по подстрокам
—Войти и решать
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—Войти и решать
Trapped in the Haybales (Gold)#89958
Фермер Джон получили груз из N больших стогов сена (\(1 \le N \le 100,000\)), и разметил их в различных положениях вдоль дороги, ведущей к амбару. К несчастью, он полностью забыл, что корова Беси пасётся вдоль дороги и может попасть в ловушку между стогами сена.

Каждый стог \(j\) имеет размер \(S_j\) и позицию \(P_j\) определяющую его положение вдоль дороги. Беси может двигаться вдоль дороги вплоть до позиции стога, но не может пересечь эту позицию. Исключение – если она прошла в этом направлении \(D\) единиц расстояния, тогда она набрала достаточно скорости, чтобы протаранить стог любого размера строго меньше чем \(D\). Конечно после этого она может продолжить движение и таранить другие стога.

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

ФОРМАТ ВООДА (ФАЙЛ trapped.in):

Первая строка ввода содержит \(N\). Каждая из последующих \(N\) строк описывает стог, и содержит два целых числа определяющих размер и позицию в диапазоне \(1\ldots 10^9\). Все позиции различны.

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

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

Жадный алгоритм
—Войти и решать
Palindromic Paths#89957
Ферма Джона представлена решёткой \(N \times N\) полей (\(1 \le N \le 500\)). Каждое поле представлено символом латинского алфавита. Например: 

ABCD
BXZX
CDXB
WCBA

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

Пожалуйста, помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 1,000,000,007.

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

Первая строка ввода содержит \(N\), и последующие \(N\) строк содержат \(N\) строк решётки, описывающей поля. Каждая строка содержит \(N\) символов в интервале A..Z.

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

Выведите количество различных путей Беси, формирующих палиндромы по модулю 1,000,000,007.

Динамическое программирование
—Войти и решать
Trapped in the Haybales (Bronze)#89955
Фермер Джон получил груз из \(N\) больших стогов сена (\(1 \le N \le 4000\)) и разместил эти стога в различных точках дороги, ведущей к его амбару. К несчастью, он совсем забыл, что Беси пасётся вдоль этой дороги и может оказаться в ловушке из этих стогов.

Каждый стог с номером \(j\) имеет размер \(S_j\) и уникальную позицию\(P_j\), задающую его положение вдоль одномерной дороги. Беси начинает движение в некоторой позиции, где не было стога и может передвигаться свободно вдоль дороги, вплоть до позиции, где размещён стог сена, но она не может перейти эту позицию. В качестве исключения, если она движется в некотором направлении \(D\) единиц расстояния, она набирает достаточно скорости, чтобы протаранить любой стог сена с высотой строго меньше, чем \(D\). Конечно, после того, как она сделает это, перед ней открывается пространство с другими стогами сена, которые она тоже может протаранить.

Беси может выйти на свободу как после самого левого, так и после самого правого стога сена. Пожалуйста, определите общую длину дороги, состоящую из тех позиций, из которых Беси не сможет выбраться. Например, если Беси не может выбраться если она начинает с позиции между стогами в позициях 1 и 5, тогда ответ будет 4 (поскольку эти позиции ограничивают область размером 4).

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

Первая строка ввода содержит \(N\). Каждая из последующих \(N\) строк описывает стог и содержит два целых числа, определяющих его размер и позицию, каждое в диапазоне \(1\ldots 10^9\).

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

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

Жадный алгоритм
—Войти и решать
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):

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

Вывод формулы
—Войти и решать
Odometer#89951

Коровы Фермера Джона путешествуют. Одометр в их автомобиле показывает целое значение преодолённого расстояния в милях, начиная с X (100 <= X <= 10^18) миль в начале путешествия и Y (X <= Y <= 10^18) миль в конце путешествия. Когда одометр показывает «интересное» число, коровы мычат. Число является интересным, если у него все цифры одинаковые, кроме одной (ведущие нули не рассматриваются в качестве цифр). Например, числа 33323 и 110 – «интересные», а числа 9779 и 55555 – нет.
Помогите ФД посчитать, сколько раз коровы промычат во время путешествия,
Help FJ count how many times the cows will moo during the trip.
PROBLEM NAME: odometer
Формат ввода:
* Строка 1: Первая строка содержит два целых числа, X и Y, разделённых пробелом.
Примечание
В начале путешествия на одометре 110, а в конце – 133.
Формат вывода:
* Строка 1: Одно целое число – сколько раз промычат коровы во время путешествия.


Примечание Коровы промычат, когда на одометре будут следующие числа: 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122, 131, 133.

Комбинаторика
—Войти и решать
Fair Photography#89950

N (2 <= N <= 100,000) коров Фермера Джона стоят в различных позициях вдоль длинной изгороди. I-ая корова стоит на позиции xi (целое число в диапазоне 0...1,000,000,000) и является либо чисто белой коровой, либо коровой с пятном. Никакие две коровы не занимают одну и ту же позицию и имеется хотя бы одна белая корова.
ФД хочет сделать фото непрерывного интервала коров, так чтобы на фото было одинаковое количество белых и пятнистых коров. ФД хочет определить максимальный размер такого фото, где размер равен разности между максимальной и минимальной позициями коров на фото.
Чтобы дать себе шанс увеличить размер фото, ФД может пририсовать пятно произвольному подмножеству белах коров, тем самым превращая их в пятнистых.
Пожалуйста, определите наибольший размер фото, которое ФД может сделать, с учётом возможности перекрашивания коров из белых в пятнистые. (Конечно, ФД может и не красить коров, если ему так выгоднее)
PROBLEM NAME: fairphoto
Формат ввода:
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит xi и либо W (для белой коровы) либо S (для пятнистой коровы).
Примечание
Всего есть 5 коров. Одна из них белая на позиции 8 и т.д.

Формат вывода:
* Строка 1: Максимальный размер фото, которое может сделать ФД с учётом возможности перекрашивания белых коров в пятнистых.


Примечание
ФД фотографирует коров с позиции 3 по позицию 10. В этом интервале имеется 4 коровы 3 белых и 1 пятнистая, поэтому он перекрасит одну корову из белых в пятнистую.

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

Фермер Джон недавно купил новую машину с двумя навигационными
системами GPS. Что ещё хуже, они часто конфликтуют при выборе
Маршрута.

Карта региона, в котором живёт ФД представляет собой N перекрёстков
(2 <= N <= 10,000) и M двунаправленных дорог (1 <= M <= 50,000).
Дорога I соединяет перекрёстки Ai (1 <= Ai <= N) и Bi (1 <= Bi <= N).

Множество дорого может соединять одну и ту же пару перекрёстков.
Двунаправленные дороги представлены двумя раздельными
однонаправленными дорогами в противоположных направлениях.

Дом ФД находится в перекрёстке 1, а его ферма распложена в перекрёстке
N. Существует путь из дома на ферму, по серии однонаправленных дорог.

Обе GPS-системы используют карту описанную выше, однако они дают
различные значения времени проезда по каждой дороге. Дорога I
требует Pi единиц времени по первой GPS-системе и Qi единиц времени
по второй (каждая из величин – целое число в интервале 1..100,000).

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

Пожалуйста, помогите ФД определить минимальное количество предупреждений,
которое он может получить соответствующим выбором маршрута.
Если две SPS-системы предупреждают одновременно, к ответу в этом случае
нужно прибавлять число 2.

PROBLEM NAME: gpsduel

Формат ввода:

* Строка 1: целые числа N и M.
* Строка 2-N+1: Строка i описывает дорогу i четырьмя
целыми числами: Ai Bi Pi Qi.

Примечание

Всего имеется 5 перекрёстков и 7 однонаправленных дорог. Первая
дорога идёт от перекрёстка 3 к перекрёстку 4, первая GPS считает,
что нужно 7 единиц времени для проезда по этой дороге, а вторая GPS
- полагает, что требуется одна единица времени.

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

* Строка 1: Минимальное количество предупреждений, которое
может получить ФД при оптимальном проезде от дома до фермы.

Примечание

Если ФД выберет путь 1 -> 2 -> 4 -> 5, тогда первая GPS пожалуется на
дороге 1->2 (она предпочитает путь 1>3). Однако в остальной части маршрута
2 -> 4 -> 5, обе GPS промолчат, поскольку обе считают такой маршрут
кратчайшим от 2 до 5.

Алгоритм Дейкстрыграфыкратчайшие пути
—Войти и решать
Odometer#89945

Коровы Фермера Джона путешествуют. Одометр в их автомобиле показывает целое значение преодолённого расстояния в милях, начиная с X (100 <= X <= 10^16) миль в начале путешествия и Y (X <= Y <= 10^16) миль в конце путешествия. Когда одометр показывает «интересное» число, коровы мычат. Число является интересным, если у него все цифры одинаковые, кроме одной (ведущие нули не рассматриваются в качестве цифр). Например, числа 33323 и 110 – «интересные», а числа 9779 и 55555 – нет.
Помогите ФД посчитать, сколько раз коровы промычат во время путешествия,
Help FJ count how many times the cows will moo during the trip.
Для половины тестов X <= Y <= 10^6.
Заметим, что для хранения таких чисел, как 10^16 требуется тип «64-битное целое Число», такой как long long в C/C++.
PROBLEM NAME: odometer
Формат ввода:
* Строка 1: Первая строка содержит два целых числа, X и Y, разделённых пробелом.
Примечание
В начале путешествия на одометре 110, а в конце – 133.
Формат вывода:
* Строка 1: Одно целое число – сколько раз промычат коровы во время путешествия.


Примечание Коровы промычат, когда на одометре будут следующие числа: 110, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122, 131, 133.

Перебор
—Войти и решать
Fair Photography#89944

N коров (1 <= N <= 100,000) Фермера Джона стоят на различных позициях вдоль длинной прямой изгороди. I-ая корова стоит на позиции xi (целое число в диапазоне 0...1,000,000,000) и имеет породу Bi (‘G’ либо ‘H’). Никакие две коровы не занимают одну и ту же позицию.
ФД хочет сделать фото непрерывного интервала коров, но так чтобы породы были справедливо представлены на фото. Справедливо это значит, что все типы представлены одним числом, Например фото где все коровы имеют тип ‘H’ – подходит и фото где 27 ‘H’ и 27 ‘G’ тоже подходит, а фото с 10 ‘H’ и 9 ‘G’ – не подходит. Помогите ФД найти справедливое фото максимального размера. Размером фото называется разность между максимальной и минимальной позицией коров на фото. Возможно, что справедливое фото будет состоять из одной коровы, тогда ответ 0.
PROBLEM NAME: fairphoto
Формат ввода:
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит xi и bi.
Примечание
Имеется 6 коров с породами слева направо G, H, G, G, H, G.
Формат вывода:
* Строка 1: Одно целое число – максимальный размер справедливого фото.
Примечание
Наибольшее справедливое фото содержит 4 средних коровы, 2 ‘H’ и 2 ‘G’.
Префиксные суммы(минимумы, ...)
—Войти и решать
Decorating the Pastures#89943

У Фермера Джона имеется N (1 <= N <= 50,000) пастбищ, последовательно пронумерованных от 1 до N, соединённых M (1 <= M <= 100,000) двунаправленными дорогами. Дорога I соединяет пастбища Ai (1 <= Ai <= N) и Bi (1 <= Bi <= N), Ai != Bi. Возможны две дороги соединяющие одну и ту же пару пастбищ.
Беси хочет украсить пастбища к дню рождения ФД. Она хочет разместить на каждом пастбище огромный знак содержащий либо букву ‘F’ либо букву ‘J’, но чтобы не огорчать ФД, должно быть выполнено правило, Пастбища декорируются разными знаками, если они соединены дорогой.
Компания, изготавливающая знаки, требует больше денег за знак ‘F’ и меньше денег за знак ‘J’, поэтому Беси хочет максимизировать количество знаков ‘J’, которые она использует. Пожалуйста, определите это число или выведите -1, если невозможно расставить знаки по описанным правилам.
uses. Please determine this number, or output -1 if there is no valid way to arrange the signs.
PROBLEM NAME: decorate
Формат ввода:
* Строка 1: Два целых числа N и M.
* Строки 2..M+1: Два целых числа, Ai и Bi указывающих наличие двунаправленной дороги между пастбищами Ai и Bi.
Примечание
Пастбища и дороги представляют собой вершины и стороны квадрата.
Формат вывода:
* Строка 1: Одно целое число, указывающее максимальное количество знаков ‘J’ которые сможет использовать Беси. Если нет решения, то выводить -1.
Примечание
Беси может пометить пастбища 1 и 3 знаком ‘J’ (или альтернативно - пастбища 2 и 4).
графыпоиск в глубину и подобноеПоиск компонент связности
—Войти и решать
Watering the Fields#89942

В связи с недостатком дождей Фермер Джон хочет построить ирригационную систему для доставки воды на N его полей (1 <= N <= 2000).
Все поля описываются различными точками (xi,yi) на плоскости, где 0<=xi,yi<=1000. Цена постройки трубы для доставки воды из точки i в точку j равна квадрату евклидового расстояния между ними:
(xi - xj)^2 + (yi - yj)^2
ФД хочет проложить минимальную по стоимости систему труб так, чтобы все его поля были соединены таким образом, чтобы водя из любого поля могла достичь любого другого поля по некоторой последовательности из проложенных труб.
К несчастью, подрядчик, у которого ФД заказал эту систему, отказывается прокладывать трубы стоимостью меньше чем C (1 <= C <= 1,000,000).
Пожалуйста, помогите ФД определить минимальное количество денег, которые ФД должен заплатить, чтобы проложить задуманную систему труб.
PROBLEM NAME: irrigation
Формат входных данных
* Строка 1: Целые числа N и C.
* Строки 2..1+N: Строка i+1 содержит целые числа xi и yi.
Формат выходных данных
* Строка 1: Минимальная стоимость задуманной сети труб , или -1 если такая сеть не может быть построена.
Примечание
ФД не может построить трубу между полями в точках (4,3) и (5,0), поскольку её стоимость не более 10. Поэтому он построит трубы между (0,2) и (5,0) со стоимостью 29 и трубу между (0,2) и (4,3) со стоимостью 17.
Минимальный каркас
—Войти и решать
The Lazy Cow#89941

Сегодня жаркий летний день, и корова Беси чувствует себя утомлённой. Она хочет так расположиться на поле, чтобы она находилась на коротком расстоянии от как можно большего количества вкусной травы.
Поле, на котором живёт Беси, описывается решёткой N*N квадратных ячеек (1 <= N <= 400). Ячейка в строке r и колонке c (1 <= r,c <= N) содержит G(i,j) единиц травы (0 <= G(i,j) <= 1000). От своей начальной ячейки Беси хочет сделать не более K шагов (0 <= K <= 2*N). Каждый шаг – это переход в соседнюю ячейку (на север, юг, запад или восток от текущей).
Например, предположим задана такая решётка где B описывает начальную позицию Беси (строка 3, колонка 3)
50 5 25* 6 17 14 3* 2* 7* 21 99* 10* 1*(B) 2* 80* 8 7* 5* 23* 11 10 0 78* 1 9
Если K=2, то для Беси достижимы только ячейки, помеченные *.
Пожалуйста, помогите Беси определить максимальное количество травы, которое она может достичь, если выберет оптимальное положение на решётке.
PROBLEM NAME: lazy
Формат входных данных
* Строка 1: Целые числа N и K.
* Строки 2..1+N: Строка r+1 содержит N целых чисел, описывающих строку r решётки.
Формат выходных данных
Примечание
В примере выше Беси может достичь 342 единицы травы, если разместится в середине решётки.
Префиксные суммы(минимумы, ...)
—Войти и решать
Mooo Moo#89940

Фермер Джон совершенно забыл, сколько у него коров. Он хочет их пересчитать с помощью микрофонов на полях, на которых собираются его коровы, поскольку он может определить количество коров по уровню шума.
N полей ФД (1 <= N <= 100) организованы в ряд вдоль длинной прямой дороги. Каждое поле может содержать различные виды коров. Всего у ФД имеется B видов коров (1 <= B <= 20), и корова вида I шумит с уровнем V(i) (1 <= V(i) <= 100). Кроме того, уровень шума распространяется строго в одном направлении по следующему закону: Если в некотором поле уровень шума X, то в следующем поле этот уровень становится X-1, следующем за ним, X-2 и т.д.
По заданному уровню шума, зафиксированном на каждом из полей, определите минимально возможное количество коров у ФД.
Уровень зафиксированного шума на каждом из полей не более 100,000.
PROBLEM NAME: mooomoo
Формат входных данных
* Строка 1: Целые числа N и B.
* Строки 2..1+B: Строка i+1 содержит целое число V(i).
* Строки 2+B..1+B+N: Строка 1+B+i содержит суммарный уровень шума всех коров, мычащих в поле i.
Формат выходных данных
* Строка 1: Минимальное количество коров у ФД, или -1, если не существует конфигурации коров, соответствующей входным данным


Примечание
Всего имеется 2 коровы вида #1 и 1 корова вида #2 на поле 2 и ещё есть 1 корова вида 1 в поле 4.

Задача о рюкзаке
—Войти и решать
The Lazy Cow#89939

Сегодня жаркий летний день, и корова Беси чувствует себя утомлённой. Она хочет так расположиться на поле, чтобы она находилась на коротком расстоянии от как можно большего количества вкусной травы.
Имеется N участков с травой (1 <= N <= 100,000) на поле Беси. i-ый из этих участков содержит gi единиц травы (1 <= gi <= 10,000) и расположен в различных точках (xi, yi) поля (0 <= xi, yi <=1,000,000). Беси хочет выбрать точку для своего начального расположения так, что бы максимальное количество травы было достижимо не более чем за K шагов от этого положения (1 <= K <= 2,000,000).
Шаг Беси – это перемещение на 1 единицу к северу, югу, востоку или западу от текущей позиции. Например, перемещение из точки (0,0) в точку (3,2) требует 5 шагов.
Пожалуйста, помогите Беси определить максимальное количество травы, Которое она сможет достичь, если выберет наилучшее начальное расположение.
PROBLEM NAME: lazy
Формат входных данных
* Строка 1: Целые числа N и K.
* Строки 2..1+N: Строка i+1 опсиывает i-ый участок травы используя 3 целых числа: gi, xi, yi.
Формат выходных данных
* Строка 1: Максимальное количество травы, которое может достичь Беси за K шагов, если он выберет наилучшее начальное положение.
Примечание
Расположившись в точке (3,0) Беси обеспечит себе доступ к траве в позициях (0,0), (6,0), и (4,2) – все на расстоянии не превышающем K.
Клеточная геометрия
—Войти и решать
Sabotage#89938

Фермер Пауль решил саботировать доильное оборудование Фермера Джона. Доильное оборудование составляет ряд из N (3 <= N <= 100,000) доильных машин, где i-ая машина производит Mi единиц молока. ФП планирует отсоединить непрерывный блок этих машин от i-ой до j-ой (2 <= i <= j <= N-1). Заметим, что ФД не собирается отключать первую и последнюю машины, поскольку это очень заметно и легко обнаружить. Цель ФП – минимизировать среднее производство молока оставшимися машинами.
Пожалуйста, помогите ФД определить минимальное среднее значение производства молока оставшимися машинами в случае оптимальных действий ФП.
PROBLEM NAME: sabotage
Формат входных данных
* Строки 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит Mi.
Формат выходных данных
* Строка 1: Минимально возможное среднее, которого может достичь ФП, округлённое до 3 цифр после десятичной точки и с выводом 3 цифр после десятичной точки.
Примечание
Оптимальное решение – удалить машины 7 т 8 оставив 5 1 2, среднее которых равно 8/3.

Бинарный поиск по ответу
—Войти и решать
The Lazy Cow#89936

Сегодня жаркий летний день, и корова Беси чувствует себя утомлённой. Она хочет так расположиться на поле, чтобы она находилась на коротком расстоянии от как можно большего количества вкусной травы.
Имеется N (1 <= N <= 100,000) участков травы на поле Беси, которое представляется числовой прямой. I-тый участок травы содержит gi единиц травы (1<=gi<=10,000) и находящихся в различных точках на расстоянии xi от начала поля (0 <= xi <= 1,000,000). Беси хочет выбрать на поле такую точку, (возможно некоторую точку из тех, что с травой), чтобы максимальное количество травы находилось на расстоянии не более K шагов от этой точки (1 <= K <= 2,000,000).
Пожалуйста, помогите Беси определить максимальное количество травы если она выберет наилучшее расположение этой точки.
PROBLEM NAME: lazy
Формат входных данных
* Строка 1: Два целых числа N и K.
* Строки 2..1+N: Строка i+1 описывает i-ый кусок травы, используя 2 Целых числа: gi и xi
Формат выходных данных
* Строка 1: Максимальное количество травы на расстоянии не превышающем K от оптимальной позиции Беси.


Примечание
Беси должна расположиться на позиции x=4, тогда количества травы, находящиеся в позициях x=1, x=2 и x=7 ,будут достижимы для неё.

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

Известно, что коровы не различают красный и зелёный цвета. Это затрудняет создание картин, которые бы одинаково воспринимались коровами и людьми.
Например, рассмотрим квадрат, описанный N*N решёткой символов (1 <= N <= 100), каждый из которых либо R (красный), G(зелёный) или B(синий). Рисунок интересен, если в нём много цветовых «регионов» которые могут отличаться друг от друга. Два символа считаются принадлежащими одному и тому же региону, если они являются непосредственно соседними (на восток, запад, север или юг) и если они неразличимы по цвету. Например, рисунок
RRRBB GGBBB BBBRR BBRRR RRRRR
для человека имеет 4 региона (2 красных, 1 синий, 1 зелёный), а для коровы только 3 (2 красно-зелёных и 1 синий) .
Для заданного на вводе рисунка определите количество регионов в нём для человека и коровы.
PROBLEM NAME: cowart
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Каждая строка содержит строку из N символов, описывающих одну строку рисунка.
Формат выходных данных
* Строка 1: Два разделённых пробелом целых числа, описывающих количество регионов в этом рисунке для человека и коровы.
Поиск компонент связности
—Войти и решать
Поделиться
Класснуть