Информатика

”„ е®зҐв ўлЎа вм Ї®¤¬­®¦Ґбвў® Є®а®ў, Ё § вҐ¬ Їа®ЁвҐаЁа®ў вмбп Ї® н⮬㠯®¤¬­®¦Ґбвўг, ўл§лў п Є ¦¤го Ё§ нвЁе Є®а®ў Ї® ®зҐаҐ¤Ё (ў Ї®ап¤ЄҐ ў®§а бв ­Ёп Ёе ID), ®Їпвм Ё ®Їпвм ¤® вҐе Ї®а, Ї®Є  ўбҐ Є®а®ўл ­Ґ бв ­гв ®вб®авЁа®ў ­л. Ќ ЇаЁ¬Ґа, Ґб«Ё ®­ ўлЎҐаҐв Ї®¤¬­®¦Ґбвў® Є®а®ў б ID \(\{2, 4, 5\}\), в® ®­ б­ з «  ўл§®ўҐв Є®а®ўг \(2\), § вҐ¬ Є®а®ўг \(4\), § вҐ¬ Є®а®ўг \(5\). …б«Ё ўбҐ \(N\) Є®а®ў Ґйс ­Ґ ®вб®авЁа®ў ­л, ®­ Ўг¤Ґв ўл§лў вм нвЁе Є®а®ў ®Їпвм Ё ®Їпвм, бЄ®«мЄ® ­г¦­® а §.

”„ е®зҐв ¬Ё­Ё¬Ё§Ёа®ў вм а §¬Ґа нв®Ј® ¬­®¦Ґбвў . Ѓ®«ҐҐ в®Ј®, Ї®бЄ®«мЄг ®­ бзЁв Ґв зЁб«® \(K\) бз бв«Ёўл¬, Ї®¬®ЈЁвҐ Ґ¬г ®ЇаҐ¤Ґ«Ёвм \(K\)-®Ґ «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ё­Ё¬ «м­®Ґ Ї®¤¬­®¦Ґбвў® ¬Ё­Ё¬ «м­®Ј® а §¬Ґа  в Є®Ґ, зв® ўл§лў п Ї®б«Ґ¤®ў вҐ«м­® Є®а®ў нв®Ј® Ї®¤¬­®¦Ґбвў  ­г¦­®Ґ Є®«ЁзҐбвў® а § ¬®¦­® ®вб®авЁа®ў вм ўбҐе Є®а®ў.

Џ®¤¬­®¦Ґбвў® \(S\) Ё§ \(\{1,\dots,N\}\) ­ §лў Ґвбп «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ґ­миҐ, 祬 Ї®¤¬­®¦Ґбвў® \(T\) Ґб«Ё бЇЁб®Є н«Ґ¬Ґ­в®ў ў \(S\) (ў Ї®ап¤ЄҐ ў®§а бв ­Ёп) «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ґ­миҐ, зҐ бЇЁб®Є н«Ґ¬Ґ­в®ў Ё§ \(T\) (ў Ї®ап¤ЄҐ ў®§а бв ­Ёп). Ќ ЇаЁ¬Ґа, \(\{1, 3, 6\}\) «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ґ­миҐ, 祬 \(\{1, 4, 5\}\).

ЋжҐ­Ёў ­ЁҐ: ‚ вҐбв е ­  \(3/16\) Ў ««®ў \(N \leq 6\) and \(K = 1\). ‚ ¤®Ї®«­ЁвҐ«м­ле вҐбв е ­  \(5/16\) Ў ««®ў, \(K = 1\). ‚ ¤®Ї®«­ЁвҐ«м­ле вҐбв е ­  \(8/16\) Ў ««®ў, ­Ґв ¤агЈЁе ®Ја ­ЁзҐ­Ё©.

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

4 1
4 2 1 3

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

2
1
4

Њл ­ зЁ­ Ґ¬ б ¬ ббЁў  \(\mathtt{\:4\:\; 2\:\; 1\:\; 3\:}\). Џ®в®¬ ”„ ўл§лў Ґв Є®а®ўг б ID 1Ў Ї®«гзЁвбп ¬ ббЁў \(\mathtt{\:1\:\; 4\:\; 2\:\; 3\:}\). Џ®в®¬ ”„ ўл§лў Ґв Є®а®ўг б ID 4 Ї®«гзЁвбп ¬ ббЁў \(\mathtt{\:1\:\; 2\:\; 3\:\; 4\:}\). ‚ нв®© в®зЄҐ ¬ ббЁў ®вб®авЁа®ў ­.

Problem credits: Spencer Compton

\(N\) коров (\(1 \leq N \leq 10^4\)) ФД стоят в ряд, последовательно пронумерованные \(1 \ldots N\). Корова \(i\) имеет \(s_i\) - уровень мастерства в заворачивании подарков. ФД решил объединить коров в команды. Команда состоит из любого последовательного множества коров числом не более \(K\) коров (\(1 \leq K \leq 10^3\)), и корова не может быть более чем в одной команде. Поскольку коровы могут учиться друг у друга, уровень мастерства каждой коровы в команде может быть заменен на уровень мастерства самой мастеровитой коровы.

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

У ФД \(N\) коров (\(1 \leq N \leq 100\)), последовательно пронумерованных \(1 \ldots N\). I-ую корову необходимо доить в интевале от времени \(s_i\) до времени \(t_i\), и для дойки требуется \(b_i\) бидонов. Процесс дойки нескольких коров может проходить в одно и то же время. Если так, то не могут использоваться одни и те же бидоны для дойки разных коров. То есть, бидон, назначенный корове \(i\) не может для дойки других коров во время от \(s_i\) до \(t_i\). Вне этого временного окна, этот бидон может быть использован для дойки других коров. Для того, чтобы упростить себе работу, ФД обеспечивает, что в любой момент времени не более одна корова начинает или заканчивает дойку. (то есть все \(s_i\) и \(t_i\) различны)

У ФД есть место, где храняться все бидоны, последовательно пронумерованные 1, 2, 3 ... В текущей стратегии дойки, когщда некоторая корова (например корова \(i\)) начинает дойку (в момент времени \(s_i\)) ФД идёт в комнату хранения, берёт \(b_i\) баллонов с наименьшими номерами и назначает их для дойки коровы \(i\).

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

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

Чтобы смешать три различных вида молока, он берёт три бидона с молоком - по бидону от каждой коровы. Эти бидоны могут иметь различные размеры и могут быть заполнены не полностью. Он переливает часть молока из бидона 1 в бидон 2, затем из бидона 2 бидон 3, затем из бидона 3 в бидон 1, снова из бидона 1 в бидон 2 и т.д. циклически. Всего он выполняет 100 таких операций. (100-ая будет как раз из бидона 1 в бидон 2). Когда ФД переливает молоко из бидона \(a\) в бидон \(b\), он переливает переливает молоко пока это возможно то есть или пока бидон \(a\) станет пустым, или бидон \(b\) станем полным.

Пожалуйста, подскажите ФД, сколько молока будет в каждом бидоне, после того как он выполнит все 100 переливаний.

В понедельник ФД отмерял ровно \(1000\) галлонов молока в цистерну первого амбара, и ровно \(1000\) галлонов молока в цистерну второго амбара.

Во вторник он берёт бидон из первого амбара, наполняет его и переносит во второй амбар, где выливает это молоко в цистерну, а бидон оставляет во втором амбаре.

В среду он берёт бидон из второго амбара (возможно, тот, который он оставил во вторник), наполняет его, переносит молоко в первый амбар и выливает его в цистерну первого амбара. Он оставляет бидон в первом амбаре.

В четверг он берёт бидон из первого амбара (возможно тот, который оставил в среду), наполняет его и переносит во второй амбар, где выливает это молоко в цистерну, а бидон оставляет во втором амбаре.

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

ФД измеряет молоко в цистерне первого амбара. Сколько возможных вариантов такого измерения он может увидеть?

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

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

35 1234 -2
14 2345 +3

Первая строка означает, что в день 35 корова #1234 дала на 2 галлона меньше, чем при последнем измерении. Следующая запись означает, что в день 14 корова #2345 дала на 3 галлона молока больше, чем при последнем измерении. ФД каждый день делает не более одного измерения. И записывает их необязательно в хронологическом порядке.

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

Заметим, что у ФД огромное стадо коров, и хотя у некоторых из них делались замеры изменения надоя, всегда имеются другие коровы, чей надой остаётся \(G\) галлонов.

Имя каждой коровы содержит некоторое количество подстрок. Например, "amy" имеет подстроки {a, m, y, am, my, amy}, а "tommy" имеет подстроки: {t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy}.

Имя коровы имеет "фактор уникальности" - количество подстрок, которых нет у имён других коров. Например, если "amy" - единственная корова в стаде, её фактор уникальности равен 6. Если "tommy" - единственная корова в стаде, её фактор уникальности равен 1. Если в стаде 2 коровы "amy" и "tommy", то их факторы уникальности будут соответственно 3 и 11.

По заданному стаду коров определите фактор уникальности каждой коровы.

Сколькими способами ФД может покрасить оставшиеся амбары?

Беси хочет отдать один из своих пирогов Эльзе. Если Эльза получит пирог от Беси, она должна будет отдать один из своих пирогов Беси. Чтобы не оказаться ни скупой, ни щедрой, Эльза постарается выбрать пирог, как минимум, такой же вкусный (по мнению Эльзы) как она получила, но не более чем на \(D\) единиц вкуснее (\(0 \leq D \leq 10^9\)). Такой пирог может не существовать, в этом случае Эльза сбежит в Японию.

Но если Эльза отдаст Беси пирог взамен, то Беси аналогично постарается отдать Эльзе пирог, как минимум такой же вкусный (по мнению Беси), но не более чем на \(D\) единиц вкуснее, чем кусок, который она получила. Если Беси не сможет, то тоже сбежит. Иначе отдаст кусок Эльзе. Этот цикл продолжается, пока возможно, или пока одна из коров не получит кусок с величиной вкусности равной \(0\), в этом случае процесс заканчивается и обе коровы счастливы.

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

Для каждого из \(N\) кусков Беси может выбрать его как начальный подарок Эльзе. Определите минимальное количество кусков, которые могут быть подарены так, чтобы обе коровы оказались счастливы.

Он решил учить их танцу "Bovine Shuffle". Этот танец состоит из \(N\) коров (\(1 \leq N \leq 100\)) выстроенных в ряд в некотором порядке, после которого они снова будут выстроены в ряд, возможно в другом порядке. ФД отметил позиции \(1 \ldots N\), и первая корова становится на позицию 1, вторая - на позицию 2, ..., последняя на позицию \(N\).

Перестановка описывается N числами \(a_1 \ldots a_N\), где корова из позиции i перемещается на позицию \(a_i\) во время перестановки (и конечно каждое \(a_i\) есть число от 1 до N). Каждая корова двигается на свою новую позицию во время перестановки. К счастью, все \(a_i\) различны, поэтому никакие две коровы не пойдут в одну и ту же позицию во время перестановки.

Каждой из коров ФД назначен уникальный ID из 7 цифр. Вам даётся порядок коров после трёх перестановок, определите начальный порядок.

35 Bessie -2
14 Mildred +3

Первая строка означает, в что в день 35 Bessie дала на 2 галлона меньше, чем во время последнего измерения. Следующая строка означает, что в день 14 Mildred дала на 3 галлона молока больше, чем во время последнего измерения. ФД делает не больше одного измерения в день. К несчастью, записи идут у него не обязательно в хронологическом порядке.

Для мотивации коров, ФД отображает на стене амбара карточку коровы, которая сейчас даёт больше всех молока. (Если таких коров несколько, он отображает все карточки). Определите количество дней, в которые ФД должен будет менять это отображение.

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

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

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

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

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!

‘ ¤ б®бв®Ёв Ё§ Ї®б«Ґ¤®ў вҐ«м­®бвЁ Ё§ \(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|\). ‚лзЁб«ЁвҐ ¬Ё­Ё¬ «м­го бв®Ё¬®бвм, §  Є®в®аго ”„ ¬®¦Ґв ўлЇ®«­Ёвм бў®© Їа®ҐЄв.

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

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.

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

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

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