Информатика

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

Фермер Джон хочет записать как можно больше телетрансляций о Му-олимпийских играх.
График трансляций состоит из N различных программ (1 <= N <= 150), для каждой из которых указано время начала и время конца. Видео-записывающий тюнер ФД может записывать две программы одновременно. Помогите ФД определить максимальное количество программ, которое он сможет записать.

PROBLEM NAME: recording
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Каждая строка содержит время начала и время завершения программы (целые числа в интервале 0..1,000,000,000))


Формат выходных данных
* Строка 1: Максимальное количество программ, которое сможет записать ФД.
Примечание
ФД может записать не более 4 программ. Например, он может записать программы 1 и 3 на первом тюнере, И программы 2 и 4 на втором тюнере.

Жадный алгоритм
—Войти и решать
Bessie Slows Down#89931

Бесси участвует в лыжной гонке через всю страну. Он начала движение со скоростью 1 м/сек. Однако по мере уставания, она замедляет ход по следующим правилам. После первого замедления её скорость становится 1/2 м/сек, после второго замедления – 1/3 м/сек и т.д.
Вам говорится когда и где Беси замедляется в терминах серии таких событий:
T 17
Означает, что Беси замедлилась в конкретное время после 17 секунд гонки.
D 10
Означает, что Беси замедлилась на дистанции 10 метров от старта.
По заданному списку из N таких событий (1 <= N <= 10,000), пожалуйста определите количество времени в секундах, которое потребуется Беси, чтобы преодолеть расстояние в 1 километр. Округлите свой ответ до ближайшего целого (0.5 округляется к 1).
PROBLEM NAME: slowdown
Формат входных данных
* Строка 1: Значение N.
* Строки 2..1+N: Каждая строка имеет вид "T x" или "D x", указывая на событие по времени или событие по расстоянию. В обоих случаях, х – целое число. Гарантируется, что все события произойдут, прежде чем она пройдёт 1 км. Возможно такое, что несколько событий произойдут одновременно, вынуждая Беси замедляться “quite a bit all at once” (?сразу несколько раз). События могут идти не по порядку.


Формат выходных данных
* Строка 1: Общее время, которое потребуется Беси, чтобы преодолеть расстояние в 1 км.
Примечание
Беси путешествует первые 10 метров со скоростью 1 м/сек, и это займёт у неё 10 секунд. Затем она замедлится до ? м/сек, и она потратит 20 сек на следующие 10 метров. В этот момент она достигнет отметки в 30 сек, где скорость уменьшится до 1/3 м/сек. Оставшиеся 980 метров займут у неё 980*3 = 2940 сек. Общее время = 10 + 20 + 2940 = 2970.

Задачи на моделирование
—Войти и решать
Cow Curling#89929

В коровий кёрлинг вовлечены две команды, каждая из которых двигает N тяжёлых камней (3 <= N <= 50,000) по льду. В конце игры имеется 2N камней на льду, каждый из которых расположен в различной точке плоскости.
Подсчёт очков в коровьем кёрлинге ведётся следующим образом: Камень считается «захваченным», если он содержится внутри треугольника, по углам которого находятся камни противника (камень, который находится на границе такого треугольника, также считается захваченным). Счёт команды есть количество камней команды противника, которые «захвачены».
Вычислите финальный счёт матча по коровьему кёрлингу, по заданному расположению всех камней.
PROBLEM NAME: curling
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды A (каждая координата лежит в диапазоне -40,000 .. +40,000).
* Строки 2+N..1+2N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды B (каждая координата лежит в диапазоне -40,000 .. +40,000).


Формат выходных данных
* Строка 1: Два разделённых пробелом целых числа, представляющих счета команд A и B
Примечание
Команда A захватила камень противника в точке (1,1). Команда B захватила камни противника в точках (0,2) и (2,2).

Многоугольники. Выпуклые оболочки
—Войти и решать
Building a Ski Course#89928

Фермер Джон помогает превратить его большое поле в лыжный маршрут для предстоящих Му-олимпийских игр. Поле имеет размеры M x N (1 <= M,N <=100) и его целевое финальное состояние описывается решеткой из M x N символов таких как:
RSRSSS RSRSSS RSRSSS
Каждый символ описывает состояние снега на этом участке R – грубый, S – гладкий (организаторы считают, что в таком случае - чередования грубых и гладких участков, гонка будет интересней).
Для выполнения этой задачи ФД планирует модифицировать свой трактор так, чтобы тот мог «отштамповать» любой фрагмент размером B x B (B<=M,B<=N) грубым снегом или гладким снегом. ФД хочет сделать B как можно большим. С B=1 он может подготовить поле, штампуя индивидуально квадраты в соответствии с заданным финальным состоянием. Однако для бОльших значений B может оказаться невозможным выполнить задачу. Каждый квадрат поля должен быть обработан трактором. Невозможно оставить ячейку поля в исходном состоянии.
Помогите ФД определить максимально возможное значение B, которое он сможет успешно использовать.
PROBLEM NAME: skicourse
Формат входных данных
* Строка 1: Два разделённых пробелом целых числа M и N.
* Строки 2..M+1: M строк ровно по N символов (каждый R или S), описывающих желаемое финальное состояние поля.
Формат выходных данных
* Строка 1: Максимальное значение B, которое ФД может использовать, чтобы создать нужное поле.


Примечание
ФД может отштамповать R колонках 1-3, затем S в колонках 2-4, затем R в колонках 3-5, и наконец, S в колонках 4-6.

Задачи на моделирование
—Войти и решать
Ski Course Design#89927

У Фермера Джона на ферме N склонов (1 <= N <= 1,000), каждый с целое высотой в диапазоне от 0 до 100. Зимой, когда выпадает снег, ФД организует на них лыжный тренировочный лагерь.
Однако сейчас ФД вычитал, что по новому закону придётся платить налог, если разница между его самым высоким и самым низким склоном строго больше чем 17. Поэтому если он срежет самый высокий склон или увеличит высоту самого низкого склона, так чтобы соответствовать закону (разница не больше 17), он избежит оплаты соответствующего налога за нарушение закона.
Если x^2 – стоимость изменения высоты склона на x единиц, какое минимальное количество денег придётся заплатить ФД, Чтобы привести свои склоны в соответствие с новым законом. Высоты меняются только на целую величину x.
PROBLEM NAME: skidesign
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Каждая строка содержит высоту одного склона.
Формат выходных данных
* Строка 1: Минимальное количество денег, которое нужно заплатить, чтобы разница между самым высоким и самым низким склонами стала не более чем 17 единиц.
Примечание
ФД оставит высоты 4, 20, и 21 как они были. Он добавит высоту склону с высотой 1 до высоты 4 (цена = 3^2=9) Он уменьшит высоту 24 до высоты 21 (цена = 3^2=9)
Жадный алгоритм
—Войти и решать
Bessie Slows Down#89926

Бесси участвует в лыжной гонке через всю страну. Он начала движение со скоростью 1 м/сек. Однако по мере уставания, она замедляет ход по следующим правилам. После первого замедления её скорость становится 1/2 м/сек, после второго замедления – 1/3 м/сек и т.д.
Вам говорится когда и где Беси замедляется в терминах серии таких событий:
T 17
Означает, что Беси замедлилась в конкретное время после 17 секунд гонки.
D 10
Означает, что Беси замедлилась на дистанции 10 метров от старта.
По заданному списку из N таких событий (1 <= N <= 10,000), пожалуйста определите количество времени в секундах, которое потребуется Беси, чтобы преодолеть расстояние в 1 километр. Округлите свой ответ до ближайшего целого (0.5 округляется к 1).
PROBLEM NAME: slowdown
Формат входных данных
* Строка 1: Значение N.
* Строки 2..1+N: Каждая строка имеет вид "T x" или "D x", указывая на событие по времени или событие по расстоянию. В обоих случаях, х – целое число. Гарантируется, что все события произойдут, прежде чем она пройдёт 1 км. Возможно такое, что несколько событий произойдут одновременно, вынуждая Беси замедляться “quite a bit all at once” (?сразу несколько раз). События могут идти не по порядку.


Формат выходных данных
* Строка 1: Общее время, которое потребуется Беси, чтобы преодолеть расстояние в 1 км.
Примечание
Беси путешествует первые 10 метров со скоростью 1 м/сек, и это займёт у неё 10 секунд. Затем она замедлится до ? м/сек, и она потратит 20 сек на следующие 10 метров. В этот момент она достигнет отметки в 30 сек, где скорость уменьшится до 1/3 м/сек. Оставшиеся 980 метров займут у неё 980*3 = 2940 сек. Общее время = 10 + 20 + 2940 = 2970.

Задачи на моделирование
—Войти и решать
Balanced Teams#89925

12 коров Фермера Джона прибыли на зимние Му-олимпийские игры этого года, каждая с уровнем лыжного мастерства от 1 до 1,000,000.
ФД хочет разделить их на 4 команды по 3 так, чтобы получились команды, сбалансированные в смысле суммарного уровня мастерства (уровень мастерства команды определяется как сумма уровней мастерства коров в команде).
Точнее, он хочет минимизировать S – s, где S и s – максимальный и минимальный уровни мастерства команд. Это обеспечивает, что различие между самой сильной и самой слабой командой будет минимально.
Помогите ФД определить минимально возможное значение S-s.
PROBLEM NAME: bteams
Формат входных данных
* Строки 1..12: Каждая строка содержит уровень мастерства одной коровы.
Формат выходных данных
* Строка 1: минимально возможное значение S - s.
Примечание
Одно из возможных решений разделить коровы на команды так: (12,1,7), (9,8,3), (10,5,4), (11,2,6). У первых двух суммарный уровень мастерства 20, а у вторых двух – 19.
Перебор
—Войти и решать
Auto-Complete#89922
Problem 1: Auto-complete [Traditional]
У Беси есть новый мобильный телефон, и она любит посылать текстовые сообщения, хотя она часто совершает ошибки набора. Фермер Джон написал для неё приложение, которое автоматически дополняет набранную часть слова до полного слова.
Это приложение имеет доступ к словарю из W слов, каждое из которых состоит из маленьких латинских букв a..z. Общее количество букв во всех словах не превышает 1,000,000. На ввод этому приложению подаётся список из N частичных слов (1<=N<=1000), каждое из которых состоит не более чем из 1000 символов - маленьких латинских букв. Для каждого частичного слова I, также задаётся число Ki, которое означает, что приложение должно найти Ki-ое слово в алфавитном порядке, для которого частичное слово I является префиксом. То есть, если упорядочить все корректные дополнения i-го частичного слова, то приложение должно вывести Ki-ое слово в этой последовательности.
PROBLEM NAME: auto
Формат входных данных
* Строка 1: Два целых числа: W и N.
* Строки 2..W+1: Строка i+1: i-ое слово в словаре.
* Строки W+2..W+N+1: Строка W+i+1: Одно целое число Ki за которым через пробел следует i-ое частичное слово.
Формат выходных данных
* Строки 1..N: Строка i должна содержать индекс внутри словаря (целое число в диапазоне от 1 до W) – Ki-ое завершение (в алфавитном порядке) i-го частичного слова или -1, если имеется менее чем Ki завершений.
Примечание
Завершения a есть {aa,aaa,aab,ab,abc,ac}. 4-ое из них ab, которое перечислено под номером 3 в словаре. Завершения da есть {daa,dab,dadba}, 2-ое завершение – dab, перечисленное под номером 1 в словаре. Нет 4-го завершения строки dab.
Бор
—Войти и решать
Cow Decathlon#89920

Problem 2: Cow Decathlon [Lewin Gan]
N коров Фермера Джона (1 <= N <= 20), последовательно пронумерованных от 1 до 20 готовятся к десятиборью, в котором имеется N различных событий (из чего следует, что его правильнее было называть N-борьем, в отличие десятиборья, в котором традиционно ровно 10 событий).
Корова I имеет уровень мастерства S_ij (1 <= s_ij <= 1000), когда соревнуется в событии j. Каждая корова должна соревноваться в одном и только одном событии и каждом событии должна участвовать некоторая корова.
Общий счёт для всех коров - это сумма их уровней мастерства для тех соревнований, в которых они соревнуются. Однако жюри может также добавить бонусные баллы, если оно особенно впечатлено.
Всего имеется B бонусов (1<=B<=20), которые может дать жюри. Бонус I описывается 3 числами: - если коровы получат не менее чем Pi баллов(1 <= Pi <= 40,000) за первые Ki событий (включая другие бонусы, полученные на этих событиях), то они получат дополнительные Ai баллов (1 <= Ai <= 1000).
Например, рассмотрим N=3 коров со следующими уровнями мастерства:
E V E N T | 1 | 2 | 3 --+---+---+-- C 1 | 5 | 1 | 7 --+---+---+-- O 2 | 2 | 2 | 4 --+---+---+-- W 3 | 4 | 2 | 1
Например, корова 1 заработает 7 баллов команде, если она поучаствует в событии 3.
Предположим, что судьи дадут один бонус (B=1), такой что если коровы заработают не менее 7 баллов в первых двух событиях, то они получат дополнительные 6 баллов. Следовательно, оптимально будет назначить корову 1 событию 1, корову 2 событию 3 и корову 3 событию 2. За первые два события корова 1 получит 5 баллов и корова 3 получит 2 балла, что в сумме даст 7 и удовлетворяет бонусу 1. Поэтому, общее количество заработанных баллов будет 5+2+4+6=17.
Помогите распределиться коровам по событиям так, чтобы максимизировать их общий счёт.
PROBLEM NAME: dec
Формат входных данных
* Строка 1: Два разделённых пробелом целых числа: N, B
* Строки 2..B+1: Строка i+1 содержит информацию о бонусе i задаваемом тремя разделёнными пробелами целыми числами: Ki, Pi, Ai.
* Строки B+2..B+N+1: Строки B+1+j содержат информацию о том, как корова i выполняет каждое из событий, с помощью N разделённых пробелами целых чисел: s_j1...s_jN.


Формат выходных данных
* Строка 1: Максимальное количество баллов, которые коровы могут получить, включая бонусы.


Примечание
Корова 1 выполнит событие 1, корова 3 выполнит событие 2, и корова 2 выполнит событие 3.

Динамика по подмножествам
—Войти и решать
Airplane Boarding#89919
Problem 3: Airplane Boarding [Travis Hance]
Коровы прибыли в в аэропорт и столкнулись с интересной проблемой.
В самолёте имеется N мест, которые мы моделируем как точки от x=1 до x=N на числовой прямой. Все N коров (1 <= N <= 200,000) стоят в ряд, ожидая занятия своего места. Корова N стоит на позиции x=0, корова N-1 на позиции x=-1 и т.д. Корове I назначено место Si, где S1, S2, … - это перестановка чисел от 1 до N.
Каждую секунду каждая корова делает шаг вправо, если она может. Когда корова I достигает своего места Si, она останавливается, чтобы положить багаж в верхний отсек салона, это занимает у неё Ti секунд, затем она садится. В течение этих Ti секунд, следующая за этой корова (если она есть) блокируется и не может двигаться вперёд. Если за ней вплотную стоят коровы, то они тоже все блокируются.
Сколько времени займёт посадка?
Сумма всех Ti будет меньше чем 1,000,000,000.
PROBLEM NAME: boarding
Формат входных данных
* Строка 1: Одно целое число, N.
* Lines 2..N+1: Два разделённых пробелом целых числа, Si и Ti.
Формат выходных данных
* Строка 1: Одно целое число, задающее количество времени, которое потребуется, чтобы все коровы заняли свои места.
Примечание
После первой секунды, все сдвинутся на 1 вправо и корова 3 достигнет своего места:
123 123
Корове 3 потребуется 5 секунд, чтобы сесть, после чего она «исчезает».
12 123
Потребуется еще 3 секунды коровам 1 и 2 чтобы добраться до своих мест:
12 123
Корове 1 потребуется 5 секунд, чтобы сесть, корове 2 – 10, поэтому ВСЕ усядутся через 10 секунд.
Общее время посадки: 1 + 5 + 3 + 10 = 19 секунд
Задачи на моделирование
—Войти и решать
Auto-Complete#89916
Problem 2: Auto-complete [Traditional]
У Беси есть новый мобильный телефон, и она любит посылать текстовые сообщения, хотя она часто совершает ошибки набора. Фермер Джон написал для неё приложение, которое автоматически дополняет набранную часть слова до полного слова.
Это приложение имеет доступ к словарю из W слов, каждое из которых состоит из маленьких латинских букв a..z. Общее количество букв во всех словах не превышает 1,000,000. На ввод этому приложению подаётся список из N частичных слов (1<=N<=1000), каждое из которых состоит не более чем из 1000 символов - маленьких латинских букв. Для каждого частичного слова I, также задаётся число Ki, которое означает, что приложение должно найти Ki-ое слово в алфавитном порядке, для которого частичное слово I является префиксом. То есть, если упорядочить все корректные дополнения i-го частичного слова, то приложение должно вывести Ki-ое слово в этой последовательности.
PROBLEM NAME: auto
Формат входных данных
* Строка 1: Два целых числа: W и N.
* Строки 2..W+1: Строка i+1: i-ое слово в словаре.
* Строки W+2..W+N+1: Строка W+i+1: Одно целое число Ki за которым через пробел следует i-ое частичное слово.
Формат выходных данных
* Строки 1..N: Строка i должна содержать индекс внутри словаря (целое число в диапазоне от 1 до W) – Ki-ое завершение (в алфавитном порядке) i-го частичного слова или -1, если имеется менее чем Ki завершений.
Примечание
Завершения a есть {aa,aaa,aab,ab,abc,ac}. 4-ое из них ab, которое перечислено под номером 3 в словаре. Завершения da есть {daa,dab,dadba}, 2-ое завершение – dab, перечисленное под номером 1 в словаре. Нет 4-го завершения строки dab.
Бор
—Войти и решать
What's Up With Gravity#89915

Капитан (C) должен спасти доктора (D). Все происходит на двумернйо решетке NxM (1<=N,M<=500). Некоторые из ячеек пусты (и по ним можно двигаться), а некоторые блокированы (и по ним нельзя двигаться).
Движение подчиняется следующим законам:
1) Если под Капитаном нет ячейки (он находится на краю решетки), то он падает в бездну и миссия спасения не выполнена 2) если под Капитаном есть пустая ячейка, но падает в нее. 3) Иначе a) Капитан может двигаться влево или вправо, если соответствующая ячейка существует и пуста. б) Капитан может переключить направление гравитации.
Когда капитан переключает направление гравитации, ячейка которая "под ним" (в смысле правил 1 и 2) переключается между ячейками с большим индексом и ячейками с меньшим индексом. Первая строка имеет индекс 1, последняя строка имеет индекс N.
Помогите Капитану найти Доктора используя минимальное количество переключений гравитации. Если Капитан не может добраться до клетки с Доктором - выведите -1.
PROBLEM NAME: gravity
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа N и M.
* Строки 2..1+N: Строка i+1 описывает i-ую строку решетки: '.' обозначает пустую клетку, '#' обозначает блокированную клетку, 'C' обозначает стартовую позицию Капитана, 'D' обозначает позицию Доктора.
Формат выходных данных
* Строка 1: Одно целое число - минимальное количество раз, когда Капитан переключал гравитацию, или -1, если Капитану не возможно добраться до Доктора.
Примечание
Капитан начинает в позиции (4,2). Он переключает гравитацию и падает в позицию (2,2) затем двигается вправо дважды и попадает в точку (2,4). Переключает гравитацию снова и падает в позицию (4,4), затем двигается вправо в позицию (4,5). Переключает гравитацию опять и падает в позицию Доктора в клетке (3,5).
Обход в ширину
—Войти и решать
Luxury River Cruise#89914

Фермер Джон берет Беси и других коров в круиз по сети рек с N портами (1 <= N <= 1,000) пронумерованными от 1 до N, начиная в порту 1. Из каждого порта ведут ровно две реки и движение одностороннее.
В каждом порту нужно выбирать куда плыть - по левой реке или по правой реке, Туристический маршрут состоит из последовательности из M (1 <= M <= 500) направлений (каждое их которых влево или вправо), которую необходимо повторить K раз (1 <= K <= 1,000,000,000).
Помогите ФД определить, где закончится его маршрут.
PROBLEM NAME: cruise
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа N, M, K.
* Строки 2..N+1: Строка i+1 содержит два разделенных пробелом целых числа, представляющих номера портов влево и вправо соответственно.
* Сроки N+2..N+2: M разделенных пробелами символов, 'L' или 'R'. 'L' представляет выбор 'влево' и 'R' представляет выбор 'вправо'.

Формат выходных данных
* Строка 1: Одно целое число - номер порта, в котором завершится круиз
Примечание
После первой итерации последовательности, ФД окажется в порту 2 (1 -> 2 -> 3 -> 2), после второй - в порту 3 (2 -> 3 -> 4 ->3), после третьей - в порту 4 (3 -> 4 -> 1 -> 4).

Задачи на моделирование
—Войти и решать
Fuel Economy#89913

Фермер Джон решил в отпуске проехать через всю страну. Чтобы коровы не скучали, он решил арендовать огромный грузовик и взять коров с собой.
Грузовик имеет огромный бензобак, который может вместить до G (1 <= G <= 1,000,000) единиц топлива. Грузовик потребляет одну единицу топлива на одну единицу расстояния. ФД собирается проехать D (1 <= D <= 1,000,000,000) единиц расстояния.
ФД знает, что ему придется несколько раз останавливаться для дозаправки, поэтому он составил список всех N (1 <= N <= 50,000) заправочных станций вдоль маршрута. Для каждой станции i он записал ее расстояние Xi (0 <= Xi <= D) от начала маршрута, а также цену Yi (1 <= Yi <= 1,000,000) заправки единицы топлива на этой станции.
По заданной информации и тому факту, что ФД начинает свое путешествие имея ровно B (0 <= B <= D) единиц топлива, определите минимальное количество денег, которое он должен заплатить за дозаправки топливом чтобы достичь точки назначения. Если достичь точки назначения невозможно, выведите -1. Заметим, что ответ на задачу может не помещаться в стандартное 32-битное целое.
PROBLEM NAME: fuel
Формат входных данных
* Строка 1: Четыре разделенных пробелом целых числа: N, G, B, D.
* Строки 2..1+N: Каждая строка содержит два целых числа Xi и Yi , описывающих заправочную станцию i.
Формат выходных данных
* Строка 1: Минимальная цена, которую ФД должен заплатить, чтобы доехать до места назначения или -1, если доехать невозможно.
Примечание
ФД проезжает 2 единицы расстояния и останавливается, чтобы заправить 2 единицы топлива (цена 40*2), это позволяет доехать ему до станции в позиции 5, где он заправляет полный бак (цена 7*10). Когда он доезжает до позиции 10, он добавляет еще 2 единицы топлива (цена 12*2). Общая цена равна 174.
Жадный алгоритм
—Войти и решать
Photo#89911

Фермер Джон решил собрать панорамное фото ряда из своих N (1 <= N <= 200,000) коров, пронумерованных от 1 до N. Он сделал M M (1 <= M <= 100,000) снимков, каждый из которых покрывает непрерывный диапазон коров. Снимок i содержит коров с номерами от ai до bi включительно. Коллективное фото может и не покрывать каждую отдельную корову.
ФД заметил интересный феномен: каждый снимок содержит ровно одну корову с пятном. Основываясь на данных снимков, определите максимально возможное количество коров с пятнами. Выведите -1, если невозможно назначить пятна коровам так, чтобы соответствовать данным о снимках.
PROBLEM NAME: photo
Формат входных данных
* Строка 1: Два целых числа N и M.
* Строки 2..M+1: Строка i+1 содержит ai и bi.
Формат выходных данных
* строка 1: Максимально возможное количество коров с пятнами у ФД, или -1, если решения нет.
Примечание
Из последней фотографии мы получаем, что корова 3 или корова 4 обязательно должны быть с пятном. При любом выборе будет выполнено свойство и для первых двух снимков.
Жадный алгоритм
—Войти и решать
Photo#89909

ФД хочет сфотографировать все свои N коров (2 <= N <= 1,000,000,000), которые выстроились в линию и последовательно пронумерованы от 1 до N. Каждая фотография может вместить некоторый последовательный диапазон коров, и ФД хочет, чтобы каждая корова была, как минимум, на одной фотографии.
К несчастью, имеется K недружественных пар коров (1 <= K <= 1000), которые отказываются находиться на одной фотографии. Вам даны позиции этих недружественных пар коров, определите минимальное количество фотографий, которые придется сделать ФД.
PROBLEM NAME: photo
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и K.
* Строки 2..K+1: Строка i+1 содержит два целых числа, Ai и Bi, указывающих, что коровы на позициях Ai и Bi недружественные, и поэтому не могут быть на одной и той же фотографии.
Формат выходных данных
* Файл 1: Одно целое число, указывающее минимальное количество фотографий, которые должен сделать ФД
Примечание
ФД должен сделать 3 фотографии: - Одна в диапазоне от 1 до 2. - Одна в диапазоне от 3 до 5. - Одна в диапазоне от 6 до 7.
Отрезки
—Войти и решать
Haywire#89908

N коров (4 <= N <= 12, N четное), построили примитивную систему для проводной коммуникации пар дружественных коров
Каждая корова имеет ровно 3 друзей в амбаре и коровы должны занять один ряд в амбаре из N стойл. Провод длины L требуется, чтобы соединить друзей в стойлах на расстоянии L. Например, если друзья находятся в стойлах 4 и 7, то требуется провод длины 3, чтобы их соединить.
Каждая пара коров должна быть соединена отдельным проводом. Определите минимальную длину провода, требуемую для организации такой сети наилучшим образом.
PROBLEM NAME: haywire
Формат входных данных
* Строка 1: Цело число N. Коровы пронумерованы 1..N.
* Строки 2..1+N: Каждая строка содержит три разделенных пробелом целых числа в диапазоне от 1 до N. Строка i+1 содержит числовые идентификаторы трех друзей коровы i. Если корова i дружит с коровой j, то и корова j дружит с коровой i.
Формат выходных данных
* Строка 1: Минимальная суммарная длина провода, чтобы соединить все пары дружественных коров.
Примечание
Лучшее упорядочивание коров есть 6, 5, 1, 4, 2, 3, и оно требует только 17 единиц длины провода.
битмаскидпПеребор
—Войти и решать
Bovine Ballet#89907

Чтобы сломать стереотипное представление о коровах как о неловких созданиях, корова Беси пошла на балетные курсы. Ее финальное представление состоится на следующей неделе, и ФД хочет помочь ей, построив прямоугольную сцену, достаточную для всего ее представления.
Танец выполняется на прямоугольной сцене, состоящей из квадратных ячеек размером 1 х 1. Ноги Беси описываются следующим образом:
FR: передняя правая нога FL: передняя левая нога RR: задняя правая нога RL: задняя левая нога
В начале танца все 4 ноги находятся в соседних ячейках и формируют квадрат как показано ниже, причем Беси смотрит на север.
FL FR RL RR
Танец Беси - это последовательность из N инструкций (1 <= N <= 1000), где каждая инструкция предписывает либо переместить одну ногу на одну ячейку, или повернуться на 90 градусов по часовой стрелке.
Инструкции переместить ногу состоят из 3 символов, первые два описывают какую ногу перемещать, а последний символ указывает направление движения (F = вперед, B = назад, R = вправо, L = влево). Например, FRF означает переместить правую ногу вперед на одну ячейку, а RLR - означает переместить заднюю левую ногу вправо. Конечно направление движения относительно того направления, куда сориентирована Беси.
Инструкция на поворот также состоит из 3 символов, первые два указывают единственную ногу Беси, которая останется в той же клетке где была и вокруг которой она повернется на 90 градусов по часовой стрелке. В этом случае последний символ - P (поворот). Например, инструкция "FRP" означает, что Беси должна повернуться на 90 градусов по часовой стрелке вокруг своей стационарной передней правой ноги. Например, если Беси ориентирована на север, и ноги расположены так: .. .. .. .. .. FR .. FL .. .. RL RR
то после инструкции "FRP" ее ноги будут расположены так, а Беси будет ориентирована на восток:
RL FL .. RR .. FR .. .. .. .. .. ..
Вам даны N инструкций танца Беси, вычислите минимальную площадь сцены прямоугольной формы, необходимой для того чтобы ноги Беси находились на ней во время всего танца.
Если Беси шагнет в ту же ячейку, где сейчас находится другая нога, она упадет, и танец закончится, в этом случае выводите -1. Заметим, что это единственный случай, когда Беси упадет. Она хорошо напрактиковалась, и ее ноги могут находиться в самых разных, даже странных комбинациях, например, когда ее задние ноги находятся впереди передних.
PROBLEM NAME: ballet
Формат входных данных
* Строка 1: Цедое число N.
* Строки 2..1+N: Каждая строка содержит одну из 3-символьных инструкций.
Формат выходных данных
* Строка 1: Минимальная площадь прямоугольной сцены, содержащей ноги Беси во время всего танца, или -1, если Беси упадет.
Примечание
Беси нужна сцена 4 x 4, ее ноги будут располагаться так:
.. .. .. .. .. .. .. .. (смотрит на север) .. .. FL FR .. .. RL RR
After FRF:
.. .. .. .. .. .. .. FR (смотрит на север) .. .. FL .. .. .. RL RR
After FRP:
.. RL FL .. .. RR .. FR (смотрит на восток) .. .. .. .. .. .. .. ..
After RLB:
RL .. FL .. .. RR .. FR (смотрит на восток) .. .. .. .. .. .. .. ..
Задачи на моделирование
—Войти и решать
Blink#89906

Недовольный освещением своего амбара, Фермер Джон установил новый канделябюр состоящий из N (3 <= N <= 16) лампочек, размещенных по кругу.
Коровы играют в следующую игру: в момент времени T они переключают состояние всех лампочек, сосед которых слева был переключен в момент времени T-1. Они продолжают это процесс, в течение B единиц времени (1<=B<=10^15). Заметим, что B может быть таким большим, что не поместится в стандартное 32-битное целое.
По заданному начальному состоянию всех лампочек определите их конечное состояние по истечению B единиц времени.
PROBLEM NAME: blink
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и B.
* Строки 2..1+N: Строка i+1 содержит начальное состояние лампочки i, r 0 (off) или 1 (on).
Формат выходных данных
* Строки 1..N: Строка i должна содержать финальное состояние лампочки i, 0 (off) или 1 (on).
Примечание
Состояние лампочек переключалось следующим образом: Time T=0: 1 0 0 0 0 Time T=1: 1 1 0 0 0 Time T=2: 1 0 1 0 0 Time T=3: 1 1 1 1 0 Time T=4: 1 0 0 0 1 Time T=5: 0 1 0 0 1 Time T=6: 1 1 1 0 1
Задачи на моделирование
—Войти и решать
Pogo-Cow#89905

Для ускорения своей призовой коровы Беси, Фермер Джон имеет палку для каждой из ног Беси. Теперь Беси научилась ускоряться, но еще не научилась замедляться.
Для тренировки ФД разметил путь по прямой. В различных позициях этого пути он разместил N целей, в которых Беси должна приземляться (1 <= N <= 1000). Цель I расположена в позиции x(i) и имеет цену P(i) очков, которые получит Беси, если приземлится в этой точке.
Беси начинает прыжки из любой из этих целей по своему выбору, и ей разрешено двигаться только в одном направлении, прыгая от цели к цели. Каждый прыжок должен быть по расстоянию не меньше, чем предыдущий, и приземляться в целевой точке. Беси получает соответствующие очки за каждую цель, которой коснётся, включая ту, с которой начнёт. Определите максимальное количество очков, которое она может получить.

PROBLEM NAME: pogocow
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит x(i) и p(i), целые в диапазоне 0..1,000,000.
Формат выходных данных
* Строка 1: Максимальное количество очков, которое может получить Беси.
Примечание
Беси прыгает из позиции x=4 (8 очков) в позицию 5 (6 очков), в позицию 7 (6 очков), в позицию 10(5 очков).

Динамическое программирование
—Войти и решать
Поделиться
Класснуть