Алгоритмы

2 310 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Blocked Billboard#89976
Во время дойки Беси любит смотреть в окно амбара на два огромных прямоугольных рекламных щита: "Farmer Alex's Amazingly Appetizing Alfalfa" и "Farmer Greg's Great Grain". Продукты на них выглядят вкуснее, чем трава на ферме.

Однажды глядя в окно, Беси увидела огромный прямоугольный грузовик, паркующийся поперёк дороги. На боку грузовика была реклама для "Farmer Smith's Superb Steaks", которую Беси не могла понять, и которая заслоняла её любимые рекламы.

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

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

Первая строка ввода содержит четыре числа, разделённых одиночными пробелами: \(x_1\) \(y_1\) \(x_2\) \(y_2\), где \((x_1, y_1)\) и \((x_2, y_2)\) - координаты левого нижнего и правого верхнего углов первого щита. Следующая строка ещё четыре числа - аналогично координаты левого нижнего и правого верхнего углов второго щита. Третья и последняя строка ввода аналогично содержит четыре целых числа указывающих левый нижний и правый верхний углы грузовика. Все координаты в интервале -1000 1000. Гарантируется, что первые 2 щита не имеют положительной площади пересечения.

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

Выведите общую площадь двух щитов, которая остаётся видимой.

Элементарная геометрия
—Войти и решать
Diamond Collector#89974
Беси собрала \(N\) алмазов (\(N \leq 50,000\)) различных размеров. И хочет разместить их в двух ящиках в амбаре. Беси не будет включать в один ящик алмазы, если их размеры отличаются более чем на \(K\). По заданному \(K\) определите максимальное количество алмазов, которое Беси сможет разместить в двух ящиках вместе.

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

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

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

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

Использование сортировки
—Войти и решать
Problem_648#89972
ЃҐбЁ ЁЈа Ґв ў ЁЈаг.

€Ја  ­ зЁ­ Ґвбп б Ї®б«Ґ¤®ў вҐ«м­®бвЁ Ё§ \(N\) Ї®«®¦ЁвҐ«м­ле 楫ле зЁбҐ« (\(2 \leq N \leq 262,144\)), Є ¦¤®Ґ ў ¤Ё Ї §®­Ґ \(0 \ldots 40\). ‡  ®¤Ё­ 室 ЃҐбЁ ¬®¦Ґв ‚§пвм ¤ў  б®бҐ¤­Ёе а ў­ле зЁб«  Ё § ¬Ґ­Ёвм Ёе ­  зЁб«® ­  1 Ў®«миҐ (­ ЇаЁ¬Ґа, ®­  ¬®¦Ґв § ¬Ґ­Ёвм ¤ўҐ б®бҐ¤­ЁҐ 7 ­  ®¤­г 8). –Ґ«м ЁЈал - ¬ ЄбЁ¬Ё§Ёа®ў вм §­ зҐ­ЁҐ б ¬®Ј® Ў®«ми®Ј® зЁб« , Є®в®а®Ґ ®­  ¬®¦Ґв Ї®«гзЁвм. Џ®¬®ЈЁвҐ Ґ©.

”ЋђЊЂ’ ‚‚Ћ„Ђ (д ©« 262144.in):

ЏҐаў п бва®Є  ўў®¤  ᮤҐа¦Ёв \(N\),   б«Ґ¤гойЁҐ \(N\) бва®Є § ¤ ов Ї®б«Ґ¤®ў вҐ«м­®бвм Ё§ \(N\) зЁбҐ«, б Є®в®але ­ зЁ­ Ґвбп ЁЈа .

”ЋђЊЂ’ ‚›‚Ћ„Ђ (д ©« 262144.out):

‚뢥¤ЁвҐ ­ ЁЎ®«м襥 зЁб«®, Є®в®а®Ґ ЃҐбЁ ¬®¦Ґв бЈҐ­ҐаЁа®ў вм

Џђ€Њ…ђ ‚‚Ћ„Ђ:

4
1
1
1
2

Џђ€Њ…ђ ‚›‚Ћ„Ђ:

3

‚ ЇаЁ¬ҐаҐ ЃҐбЁ б­ з «  б«Ёў Ґв ўв®аго Ё ваҐвмо 1 Ё Ї®«гз Ґв Ї®б«Ґ¤®ў вҐ«м­®бвм 1 2 2 ,   § вҐ¬ б«Ёў Ґв ¤ўҐ ¤ў®©ЄЁ ў 3. ‡ ¬ҐвЁ¬, зв® ­Ґ ®ЇвЁ¬ «м­® б«Ёў вм ЇҐаўлҐ ¤ўҐ Ґ¤Ё­Ёжл.

Ђўв®а: Mark Chen Bessie likes downloading games to play on her cell phone, even though she does find the small touch screen rather cumbersome to use with her large hooves.

She is particularly intrigued by the current game she is playing. The game starts with a sequence of \(N\) positive integers (\(2 \leq N \leq 262,144\)), each in the range \(0 \ldots 40\). In one move, Bessie can take two adjacent numbers with equal values and replace them a single number of value one greater (e.g., she might replace two adjacent 7s with an 8). The goal is to maximize the value of the largest number she can create. Please help Bessie score as highly as possible!

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

The first line of input contains \(N\), and the next \(N\) lines give the sequence of \(N\) numbers at the start of the game.

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

Please output the largest integer Bessie can generate.

Динамическое программирование: один параметр
—Войти и решать
Landscaping#89971
”Ґа¬Ґа „¦®­ бва®Ёв б ¤ Ё Ґ¬г вॡгҐвбп ЇҐаҐ¬ҐбвЁвм ¬­®Ј® ¤са­ .

‘ ¤ б®бв®Ёв Ё§ Ї®б«Ґ¤®ў вҐ«м­®бвЁ Ё§ \(N\) Є«г¬Ў (\(1 \leq N \leq 100,000\)), ѓ¤Ґ Є«г¬Ў  \(i\) Ё§­ з «м­® ᮤҐа¦Ёв \(A_i\) Ґ¤Ё­Ёж ¤са­ . ”„ е®зҐв ८࣠­Ё§®ў вм б ¤ в Є, зв®Ўл Є ¦¤ п Є«г¬Ў  бв «  ᮤҐа¦ вм \(B_i\) Ґ¤Ё­Ёж ¤са­ . \(A_i\) Ё \(B_i\) - жҐ«лҐ зЁб«  ў Ё­вҐаў «Ґ \(0 \ldots 10\).

„«п Ё§¬Ґ­Ґ­Ёп « ­¤и дв  ”„ Ё¬ҐҐв ­ҐбЄ®«мЄ® ў аЁ ­в®ў: ®­ ¬®¦Ґв ЄгЇЁвм ®¤­г Ґ¤Ё­Ёжг ¤са­  Ё Ї®«®¦Ёвм Ґс ­  «оЎго Є«г¬Ўг §  \(X\) Ґ¤Ё­Ёж ¤Ґ­ҐЈ. Ћ­ ¬®¦Ґв б­пвм ®¤­г Ґ¤Ё­Ёжг ¤са­  б «оЎ®© Є«г¬Ўл Ё Їа®¤ вм Ґс §  \(Y\) Ґ¤Ё­Ёж ¤Ґ­ҐЈ. Ћ­ в Є¦Ґ ¬®¦Ґв ЏҐаҐ¬ҐбвЁвм ®¤­г Ґ¤Ё­Ёжг ¤са­  б Є«г¬Ўл \(i\) ­  Є«г¬Ўг \(j\) §  \(Z\) times \(|i-j|\). ‚лзЁб«ЁвҐ ¬Ё­Ё¬ «м­го бв®Ё¬®бвм, §  Є®в®аго ”„ ¬®¦Ґв ўлЇ®«­Ёвм бў®© Їа®ҐЄв.

”ЋђЊЂ’ ‚‚Ћ„Ђ (д ©« landscape.in):

ЏҐаў п бва®Є  ўў®¤  ᮤҐа¦Ёв \(N\), \(X\), \(Y\), \(Z\) (\(0 \leq X, Y \le 10^8; 0 \le Z \leq 1000\)). ‘ва®Є  \(i+1\) ᮤҐа¦Ёв жҐ«лҐ зЁб«  \(A_i\) Ё \(B_i\).

”ЋђЊЂ’ ‚›‚Ћ„Ђ (д ©« landscape.out):

‚뢥¤ЁвҐ ¬Ё­Ё¬ «м­го б㬬 а­го бв®Ё¬®бвм Їа®ўҐ¤Ґ­Ёп а Ў®в.

Џђ€Њ…ђ ‚‚Ћ„Ђ:

4 100 200 1
1 4
2 3
3 2
4 0

Џђ€Њ…ђ ‚›‚Ћ„Ђ:

210

‡ ¬ҐвЁ¬ зв® в Є п § ¤ з  ¤ ў « бм ў ®¤­®¬ Ё§ ЇаҐ¦­Ёе USACO-Є®­вҐбв®ў ­  га®ў­Ґ Silver. Ћ¤­ Є® ᥩз б бгйҐб⢥­­® 㬥­м襭® ўаҐ¬п ­  вҐбв.

Ђўв®а: Brian Dean Farmer John is building a nicely-landscaped garden, and needs to move a large amount of dirt in the process.

The garden consists of a sequence of \(N\) flowerbeds (\(1 \leq N \leq 100,000\)), where flowerbed \(i\) initially contains \(A_i\) units of dirt. Farmer John would like to re-landscape the garden so that each flowerbed \(i\) instead contains \(B_i\) units of dirt. The \(A_i\)'s and \(B_i\)'s are all integers in the range \(0 \ldots 10\).

To landscape the garden, Farmer John has several options: he can purchase one unit of dirt and place it in a flowerbed of his choice for \(X\) units of money. He can remove one unit of dirt from a flowerbed of his choice and have it shipped away for \(Y\) units of money. He can also transport one unit of dirt from flowerbed \(i\) to flowerbed \(j\) at a cost of \(Z\) times \(|i-j|\). Please compute the minimum total cost for Farmer John to complete his landscaping project.

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

The first line of input contains \(N\), \(X\), \(Y\), and \(Z\) (\(0 \leq X, Y \le 10^8; 0 \le Z \leq 1000\)). Line \(i+1\) contains the integers \(A_i\) and \(B_i\).

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

Please print the minimum total cost FJ needs to spend on landscaping.

Жадный алгоритм
—Войти и решать
Bull in a China Shop#89970
Фермер Джон решил украсить свой дом. Посетив китайский магазинчик, он нашёл стеклянную фигурку коровы и решил её купить.

Форма коровы описывается решёткой из \(N \times M\) (\(3 \leq N, M \leq 500\)) символов (на рисунке ниже приведён пример). Различные символы (маленькие латинские) обозначают различные цвета, а символ '.' - отсутствие фигуры.

 


...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa....
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............

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

Помогите ФД определить сколько наборов из 3 кусков (из \(K\) валяющихся на полу) могут составить сломанную фигуру.

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

 

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

Первая строка содержит одно целое число \(K\). Далее идут \(K + 1\) описаний. Первое описывает оригинальную фигурку, остальные \(K\) - описание кусков на полу.

Каждое описание начинается со строки, содержащей два целых числа \(R\) и \(C\) (\(1 \le R, C \le 100\)). Последующие \(R\) строк содержат по \(C\) маленьких латинских символов, описывающих цвет каждой ячейки. Каждый кусок соединяется горизонтально или вертикально и имеет хотя бы одну не-пустую ячейку.

 

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

Выведите количество триплетов \(i, j, k\) (\(i < j < k\)) таких, что куски \(i\), \(j\), и \(k\) могут составить исходную фигурку коровы.

 

ПРИМЕР ВВОДА:


5
5 5
aaaaa
..a..
bbabb
..a..
aaaaa
3 5
..abb
..a..
aaaaa
5 2
a.
a.
aa
a.
a.
1 2
bb
1 5
bbabb
2 5
aaaaa
..a..

ПРИМЕР ВЫВОДА:


3

Эти три решения используют куски \((0, 1, 2)\), \((0, 2, 4)\), \((1, 3, 4)\). Заметим, что эта задача имеет 6 секунд на тест (а для Питона и Java - 12)

 

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

Её особенно заинтересовала игра, в которую она сейчас играет. Игра начинается с последовательности из N положительных целых чисел (2 ≤ N ≤ 262144), каждое из которых находится в диапазоне от 1 до 40. За один ход Бесси может взять два соседних числа с одинаковыми значениями и заменить их на одно число на единицу больше (например, она может заменить две соседние семёрки на восьмёрку). Цель состоит в том, чтобы максимизировать значение наибольшего числа в последовательности в конце игры. Пожалуйста, помогите Бесси набрать как можно больше очков.

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

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

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

Пожалуйста, выведите наибольшее целое число, которое может сгенерировать Бесси.

Примечание
В приведенном здесь примере Бесси сначала объединяет вторую и третью единицы, чтобы получить последовательность 1 2 2, а затем объединяет двойки в тройку. Обратите внимание, что объединение первых двух единиц не является оптимальным.
 

Динамическое программирование: один параметр
✓ 1✗ 0—Войти и решать
Problem_647#89967
Беси любит играть на мобильном.

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

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

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

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

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

Динамическое программирование
—Войти и решать
Closing the Farm#89966
Фермер Джон и его коровы планируют уехать на длинные каникулы, и поэтому ФД хочет временно закрыть ферму.

Ферма состоит из \(N\) амбаров, соединённых \(M\) двунаправленными дорожками между некоторыми парами амбаров (\(1 \leq N, M \leq 200,000\)). ФД закрывает один амбар за раз. После того как амбар закрыт, все дорожки, прилегающие к нему тоже становятся закрытыми и не могут больше использоваться.

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

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

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

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

Вывод содержит \(N\) строк, каждая есть "YES" или "NO". Первая строка отвечает на попрос была ли ферма полностью связанной изначально, а далее строка \(i+1\) указывает, осталась ли ферма полностью связной после \(i\)-го закрывания.

графыПоиск компонент связностиснм
—Войти и решать
248#89965
Беси любит играть на мобильном.

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

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

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

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

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

Динамическое программирование по подстрокам
—Войти и решать
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):

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

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

Комбинаторика
—Войти и решать
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.

Алгоритм Дейкстрыграфыкратчайшие пути
—Войти и решать
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).

Вывод формулыграфыДеревья
—Войти и решать
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.

Перебор
—Войти и решать
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.
Минимальный каркас
—Войти и решать
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.

Задача о рюкзаке
✓ 1✗ 0—Войти и решать
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.
Клеточная геометрия
—Войти и решать
Поделиться
Класснуть