Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 240 241 242 243 244 245 246 >> Отображать по:
#3678
Сушка
  

Тетя Люба только что постирала все белье, и теперь перед ней стоит непростая задача: как его высушить, чтобы ни одна вещь не успела испортиться. Сразу после стирки \(i\)-я постиранная вещь имеет влажность \(w_i\). Если она сушится на веревке, то за минуту ее влажность уменьшается на \(1\), а если на батарее— то на \(r\) (если влажность была меньше \(r\), то она становится равной \(0\)). Причем веревок у тети Любы много (хватает для одновременной сушки всех вещей), а батарея только одна, причем такая маленькая, что на ней нельзя сушить две вещи одновременно. \(i\)-я вещь испортится, если не высохнет за время \(d_i\). Помогите тете Любе составить план, когда какую вещь повесить на батарею.

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

Первая строка входного файла содержит целые числа \(n\) (\(1 \leq n \leq 10^5\)) (количество мокрых вещей) и \(r\) (\(1 \leq r \leq 10^9\)). Следующие \(n\) строк содержат описания постиранных вещей — пары чисел \(w_i\) и \(d_i\) (\(1 \leq w_i, d_i \leq 10^9\)).

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

Выведите план сушки в виде пар целых чисел \(t_i\) и \(k_i\), где \(t_i\) — измеренное в минутах время от начала сушки, а \(k_i\) — номер вещи, которую нужно повесить на батарею в этот момент. Выводите пары в порядке увеличения \(t_i\). Пар не должно быть больше \(100\,000\). Не выводите числа больше \(10^9\).

Если высушить все вещи невозможно, выведите слово Impossible.

Примеры
Входные данные
3 3
2000 1000
2000 2000
2500 1500
Выходные данные
0 1
500 3
Входные данные
3 3
2000 1000
2000 1000
2000 1000
Выходные данные
Impossible
#3683
Алгоритм Евклида
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Андрей недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел \(a\) и \(b\) называется наибольшее натуральное число \(x\), такое, что и число \(a\), и число \(b\) делится на него без остатка. Алгоритм Евклида заключается в следующем:

  1. Пусть \(a\), \(b\) – числа, НОД которых надо найти.
  2. Если \(b = 0\), то число \(a\) – искомый НОД.
  3. Если \(b > a\), то необходимо поменять местами числа \(a\) и \(b\).
  4. Присвоить числу \(a\) значение \(a - b\).
  5. Вернуться к шагу 2.

Андрей достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Поняв, что надо дальше совершенствоваться, ему пришла идея решить новую задачу. Пусть заданы числа \(a\), \(b\), \(c\) и \(d\). Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (\(a\), \(b\)) такой момент, когда перед исполнением шага 2 число \(a\) будет равно \(c\), а число \(b\) будет равно \(d\).

Требуется написать программу, которая решает эту задачу.

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

Первая строка входных данных содержит количество наборов входных данных \(K~(1 \le K \le 100)\). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: \(a\), \(b~(1 \le a, b \le 10^{18})\). Вторая строка – два целых числа: \(c, d~(1 \le c, d \le 10^{18})\).

Все числа в строках разделены пробелом.

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

Для каждого набора входных данных выведите слово "YES", если в процессе применения алгоритма Евклида к паре чисел (\(a\), \(b\)) в какой-то момент получается пара (\(c\), \(d\)). В противном случае выведите слово "NO".

Система оценки

Тесты к данной задаче состоят из двух групп:

  1. \(1 \le K \le 5\), \(1 \le a, b, c, d \le 10^6\). Эта группа оценивается в 60 баллов.
  2. Дополнительных ограничений нет. Эта группа оценивается в 40 баллов.
#3706
Immediate Delivery
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

Вася и Петя работают курьерами в фирме "Мгновенная доставка". Сегодня им надо доставить огромное количество посылок по всему городу.

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

Вася и Петя должны посетить все перекрестки, чтобы доставить посылки. Они хотят разделить все задание на две части так, чтобы минимизировать время последней доставки.

Офис компании "Мгновенная доставка" расположен на перекрестке номер 1.

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

В первой строке заданы целые числа n (1 ≤ n ≤ 18) и m - количество пунктов и дорог.

Следующие m строк описывают дороги. Каждая дорога задается тремя целыми числами: номерами перекрестков xi и yi, которые она соединяет, (1 ≤ x i, yi ≤ n) и временем ti, которое нужно, чтобы по проехать по ней (1 ≤ ti ≤ 1000). Между каждой парой перекрестков не более чем одна дорога. Никакая дорога не соединяет перекресток с самим собой.

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

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

Примечание
В примере выводить нужно только одно число. Здесь приведён пример разбиения, но его выводить не нужно.
Примеры
Входные данные
6 6
1 2 10
2 3 10
3 4 5
4 5 10
5 6 20
2 5 10
Выходные данные
40
4 1 2 3 4 3
3 1 2 5 6
#3711
Большой, белый, очень прямоугольный
  
ограничение по времени на тест
6.0 second;
ограничение по памяти на тест
256 megabytes

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

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

Во входном файле записана сначала высота \((N)\), а затем ширина \((M)\) таблицы \(((1 \le N \le 5000)\), \((1 \le M \le 5000))\), а затем записано \((N)\) строк по \((M )\) чисел в каждой строке, где \(0\) означает, что соответствующая клетка таблицы выкрашена в белый цвет, а \(1\) – что в черный.

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

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

Примеры
Входные данные
5 6
1 0 0 0 1 0
0 0 0 0 1 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
Выходные данные
9
#3712
Логическое дерево
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Каждая вершина дерева имеет связанное с ней логическое значение (1 или 0). Кроме этого, каждая внутренняя вершина имеет связанную с ней логическую операцию („И“ или „ИЛИ“). Значение вершины с операцией „И“ — это логическое „И“ значений её детей. Аналогично, значение вершины с операцией „ИЛИ“ — это логическое „ИЛИ“ значений её детей. Значения всех листьев задаются во входном файле, поэтому значения всех вершин дерева могут быть найдены.

Наибольший интерес для нас представляет корень дерева. Мы хотим, чтобы он имел заданное логическое значение \(v\), которое может отличаться от текущего. К счастью, мы можем изменять логические операции некоторых внутренних вершин (заменить „И“ на „ИЛИ“ и наоборот).

Дано описание логического дерева и набор вершин, операции в которых могут быть изменены. Найдите наименьшее количество вершин, которые следует изменить, чтобы корень дерева принял заданное значение \(v\). Если это невозможно, то выведите строку «IMPOSSIBLE» (без кавычек).

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

В первой строке входного файла находятся два числа \(n\) и \(v\) (\(1 \le n \le 10\,000, 0 \le v \le 1\)) — количество вершин в дереве и требуемое значение в корне соответственно. Поскольку все вершины имеют ноль или двоих детей, то \(n\) нечётно. Следующие \(n\) строк описывают вершины дерева. Вершины нумеруются от \(1\) до \(n\).

Первые \((n-1)/2\) строк описывают внутренние вершины. Каждая из них содержит два числа — \(g\) и \(c\), которые принимают значение либо \(0\), либо \(1\). Если \(g=1\), то вершина представляет логическую операцию „И“, иначе она представляет логическую операцию „ИЛИ“. Если \(c=1\), то операция в вершине может быть изменена, иначе нет. Внутренняя вершина с номером \(i\) имеет детей \(2i\) и \(2i+1\).

Следующие \((n+1)/2\) строк описывают листья. Каждая строка содержит одно число \(0\) или \(1\) — значение листа.

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

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

Примеры
Входные данные
9 1
1 0
1 1
1 1
0 0
1
0
1
0
1
Выходные данные
1
Входные данные
5 0
1 1
0 0
1
1
0
Выходные данные
IMPOSSIBLE
Страница: << 240 241 242 243 244 245 246 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест