Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 96 97 98 99 100 101 102 >> Отображать по:
#878
Перекраска
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дано прямоугольное поле, каждая клетка которого покрашена в какой-то цвет. За один ход необходимо перекрасить все клетки одного цвета в другой цвет. Стоимость перекраски одной клетки зависит от номера хода и задается функцией: \(F(i) = ((A \cdot F(i-1)+B) \bmod~C) + 1\), \(F_1\) – известная стоимость первого хода.

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

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

В первой строке натуральные задаются числа \(F_1\), \(A\), \(B\) и \(C\) (\(1 \leq F_1, A, B, C \leq 10000\)) – параметры функции \(F\). Во второй строке задаются два натуральных числа \(M\) и \(N\) (\(1 \leq N, M \leq 50\)) – размеры поля. В последующих \(M\) строках записано по \(N\) натуральных чисел, не превосходящих \(2^{31}\) – цвета клеток.

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

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

Примеры
Входные данные
1 3 1 5
4 4
1 2 3 6
2 1 1 2
3 1 1 3
2 2 2 2
Выходные данные
4
6 2 3 1
#883
Театр
  

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

Чтобы ничего не перепутать, мастера договорились, что Олег будет только включать лампы, а Сергей только выключать.

Театральная сцена представляет собой прямоугольник \(W\) на \(L\) метров, внутри которого расположено \(N\) ламп подсветки.

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

Олег может перемещаться по сцене с максимальной скоростью \(V_1\) метров в секунду, а Сергей \(-\) \(V_2\) метров в секунду. Мастера могут находиться на сцене только в перерывах между действиями. Во время действия они могут переместиться в любую точку в пределах той части кулис, в которой они оказались перед началом действия.

Перед началом спектакля Олег и Сергей получили подробный сценарий, в котором указано количество действий \(M\) и для каждого действия свой набор ламп подсветки, которые должны быть включены. Лампы, которые не входят в этот набор, должны быть выключены. Перед первым действием Олег должен находиться в левой части кулис, а Сергей \(-\) в правой. Изначально включены лампы, необходимые для первого действия.

Задача Олега и Сергея \(-\) организовать работу так, чтобы суммарное время всех перерывов между действиями было бы минимальным.

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

На первой строке входного файла находится пять чисел \(-\) \(W, L, V_1, V_2\) и \(N\) (\(1 \le W, L \le 50\), \(1 \le V_1, V_2 \le 20\), \(1 \le N \le 15\))\(-\) размеры сцены, максимальные скорости мастеров и число ламп подсветки соответственно.

Далее идут \(N\) строк с координатами ламп подсветки в метрах \(x_i, y_i\) (\(0 < x_i < L\), \(0 < y_i < W\)).

Следующая строка содержит число \(M\)(\(1 \le M \le 10\,000\)) \(-\) число действий в спектакле. Далее идут \(M\) строк, каждая из которых содержит число ламп подсветки, которые должны быть включены в соответствующем действии, и номера ламп подсветки. Все числа во входном файле целые.

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

В выходной файл выведите единственное число \(-\) минимальное суммарное время перерывов между действиями в секундах с точностью \(10^{-5}\).

Примеры
Входные данные
5 6 1 1 3
1 2
3 4
5 3
1
1 3
Выходные данные
0.000000000000000
Входные данные
5 6 1 1 3
1 2
3 4
5 3
3
1 3
2 1 2
3 1 2 3
Выходные данные
8.828427124746190
#887
Электрик-ковбой Джо
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Джо - электрик-ковбой. Как у всех ковбоев у него есть лассо, как всем электрикам ему иногда приходиться залезать на столбы, и как все он ленив.

Вот и сейчас ему поручили проверить два стоящих на расстоянии \(d\) друг от друга столба высоты \(h_1\) и \(h_2\) соответственно. Чтобы убедиться, что все хорошо, Джо должен побывать на вершинах обоих столбов.

Электрик-ковбой посещает столбы следующим образом: сначала он выбирает один из столбов и просто взбирается на него. Выполнив все работы на вершине, он спускается по этому столбу на некоторую высоту (возможно до самой земли), достает свое лассо и цепляется им за некоторую точку второго столба (это может быть произвольная точка). После этого Джо прыгает и двигается вниз по дуге окружности с центром в точке, за которую зацепилось лассо, пока не достигнет либо другого столба, либо земли.

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

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

Ковбой

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

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

Входной файл содержит четыре положительных целых числа: \(d\), \(h_1\), \(h_2\) и \(l\) - расстояние между столбами, высоту первого и второго столбов и максимальный допустимый перепад высот при прыжке, соответственно. Все числа во входном файле не превышают \(10^6\).

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

Выведите ответ с максимальной возможной точностью. Ответ будет проверяться с точностью до \(10^{-5}\).

Примеры
Входные данные
5 5 5 5
Выходные данные
10.0
Входные данные
4 5 8 5
Выходные данные
10.0
Входные данные
4 8 5 1
Выходные данные
13.0
Входные данные
3 4 6 1
Выходные данные
9.0
#888
Фитнесс-клуб
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Имя входного файла: fitness.in
Имя выходного файла: fitness.out

В последнее время фитнесс-клубы стали очень популярны среди жителей столицы Флатландии. В такие клубы люди ходят после работы для того, чтобы поддерживать себя в хорошей физической форме. В фитнесс-клубe «Флат» каждому из посетителей на время посещения выделяется один из \(k\) шкафчиков, в который он может убрать свои вещи на время тренировки.

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

Некоторые из посетителей уходя закрывают шкафчик, а другие не закрывают. Так как все посетители фитнесс-клуба посещают его уже достаточно давно, то про каждого из них персонал клуба знает, закроет ли он свой шкафчик, когда будет уходить. Таким образом, для каждой трени- ровки известно два числа: число \(a_i\) посетителей, которые закроют шкафчик, и число \(b_i\) посетителей, которые не закроют.

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

Необходимо найти максимальное число шкафчиков, которые окажутся закрытыми, в случае оптимальных действий персонала фитнесс-клуба.

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

Первая строка входного файла содержит два целых числа: \(n\) (\(1 \leq n \leq 100\)) и \(k\) (\(1 \leq k \leq 1000\)) Каждая из последующих \(n\) строк содержит по два целых числа \(a_i\) и \(b_i\) (\(0 \leq a_i, b_i \leq k\), \(a_i + b_i \leq k\)).

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

В выходной файл выведите одно число — ответ на задачу.

Примечание
Пронумеруем шкафчики числами от 1 до 4. Посетителям, пришедшим на первую тренировку выдадим ключи так: тому, кто закроет, от шкафчика 1, тем, кто не закроет, от 2 и 3. Посетителям, пришедшим на вторую тренировку, выдадим ключи так: тому, кто закроет, номер 2, тому, кто не закроет, номер 3. В итоге открытым после окончания дня останется только шкафчик номер 3.
Примеры
Входные данные
2 4
1 2
1 1
Выходные данные
3
#889
Большой огромный коллайдер
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Приехав в Хоббитанию, белый маг Гэндальф принялся рассказывать Бильбо последние новости из Средиземья. Больше всего впечатлительного хоббита поразил рассказ о Большом огромном коллайдере - только представить себе гигантских размеров кольцо, зарытое под землей!

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

Бильбо хочет прокопать новые коридоры в норе, но так как копать будут только Фродо и сам Бильбо (не Гэндальф же!) , есть возможность прокопать только один или два новых коридора.

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

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

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

В первой строке входного файла содержится целое число \(n\) (\(3 \le n \le 100\,000\)) - число комнат в норе Бильбо.

В следующих \(n - 1\) строках содержатся по два целых числа - номера комнат, соединенных коридорами. Комнаты нумеруются от \(1\) до \(n\).

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

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

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

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

Примечание

В первом примере коллайдер состоит из комнат с номерами 1, 2, 3 и 4 (именно в этом порядке), во втором примере - 1, 3, 2, 4.

Примеры
Входные данные
4
1 2
2 3
3 4
Выходные данные
4
4 1
Входные данные
4
1 2
1 3
1 4
Выходные данные
4
2 3
2 4
Страница: << 96 97 98 99 100 101 102 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест