Информатика

7 592 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
ХЕШ-ФУНКЦИЯ#49404
Для быстрого распознавания идентификаторов в современных трансляторах  используются хеш-функции. Хеш-функция сопоставляет строке целое число из некоторого промежутка. Критерием оценки хеш-функции является количество коллизий, то есть ситуаций, когда различным встретившимся строкам сопоставляется одно и то же число.

Вы должны построить хеш-функцию для заданного множества слов русского языка и реализовать ее в программе, которая будет вычислять хеш-значения из интервала от 1 до 255 для всех слов из входного файла. Ваша функция будет оцениваться в зависимости от максимального количества слов, хеш-значения которых оказались одинаковыми: чем это количество меньше, тем лучше функция.

На время тура вам предоставляется файл words.txt, содержащий перечисленные в алфавитном порядке 10 000 слов. Слова из этого файла будут использоваться при тестировании вашего решения. Это означает, что во всех тестах слова будут выбираться только из этого множества. Во время тестирования файл words.txt будет вашей программе недоступен.

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



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

Выходные данные
Для каждого слова из заданного списка требуется вывести соответствующее хеш-значение. Числа должны быть записаны по одному в строке.
 
реализацияХеш
—Войти и решать
Игра в напёрстки#49293

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

Бомбослав заметил, что ребята во дворе не очень изобретательны в своих действиях, и всегда меняют местами левый напёрсток со средним на нечётных действиях (то есть на первом, третьем, пятом и так далее) и средний с правым на чётных действиях (то есть на втором, четвёртом и так далее).

Пронумеруем напёрстки от \(0\) до \(2\) слева направо. То есть левый напёрстком имеет номер \(0\), средний номер \(1\), а правый номер \(2\). Бомбослав не успел увидеть начало игры, но посчитал, что ведущий совершил \(n\) действий и в итоге шарик оказался под напёрстком \(x\). Под каким напёрстком находился шарик в самом начале?

Формат входных данных
В первой строке входных данных записано одно цело число \(n\) (\(1 \leq n \leq 2 \cdot 10^9\)) — количество действий, совершённых ведущим.

Во второй строке записано одно целое число \(x\) (\(0 \leq x \leq 2\)) — номер напёрстка, под которым оказался шарик через \(n\) действий.

Формат выходных данных
Выведите одно целое число от \(0\) до \(2\), означающее номер напёрстка, под которым находился шарик в самом начале.

Замечание

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

  1. Первым действием ведущий поменял местами левый и средний напёрстки. В результате шарик оказался под левым напёрстком.

  2. Вторым действием ведущий поменял местами средний и правый напёрстки. Шарик остался под левым напёрстком.

  3. Третьим действием ведущий снова поменял местами левый и средний напёрстки. В результате шарик снова оказался посередине.

  4. Последним четвёртым действием ведущий опять поменял местами средний и правый напёрстки и шарик оказался под правым напёрстком.

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, верно работающие при \(n \leq 100\,000\) будут набирать не менее 50 баллов.

Вывод формулы
✓ 3✗ 11—Войти и решать
Устранение массива#49028

Дан массив \(a\) длины \(n\). Каждый элемент массива — \(0\), \(1\) или \(2\). Известно, что нули находятся только строго в левой половине массива, то есть на индесах от \(1\) до \(\left\lfloor\frac{n}{2}\right\rfloor\). Все оставшиеся элементы могут быть равны только \(1\) или \(2\).

С массивом разрешается выполнять следующие два вида действий:

  1. Заплатить две монеты и удалить из массива любое число \(a_i\). После такого действия массив \([a_1, a_2, \ldots, a_k]\) превращается в \([a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_k]\).

  2. Заплатить одну монету и заменить два стоящих рядом числа \(a_i\) и \(a_{i+1}\) на \(a_i\) копий числа \(a_{i+1}\). То есть, возможны следующие преобразования:

Иными словами, \(0\) можно удалить вместе со следующим числом, \(1\) можно удалить саму по себе, если она стоит не в конце массива, а \(2\) можно заменить на следующее за ней число.

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

Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют \(T\) наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное число \(n\) — изначальную длину массива. В следующей строке через пробел перечислены целые числа \(a_1\), …, \(a_n\) — элементы массива (\(0 \le a_i \le 2\)).

Гарантируется, что сумма длин массивов по всем наборам входных данных не превосходит \(10^6\).

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

 
Задачи на моделированиереализация
✓ 3✗ 0—Войти и решать
Сдача - 2#47748
Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P1, P2, ..., PN рублей. У продавца есть M банкнот номиналом Q1, Q2, ..., QM. рублей. Определите, смогут ли они рассчитаться.

Входные данные
Программа получает на вход сумму S. Далее идет число N затем P1, P2, ..., PN. Далее идет число M, затем Q1, Q2, ..., QM.Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

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

Если они не могут рассчитаться, выведите число -1.
Задача о рюкзаке
✓ 1✗ 10—Войти и решать
Весы#47747
Если в продаже нет стандартного набора гирь, измерение массы становится большой проблемой. Ваш набор содержит n гирь массой 1 грамм, 4 грамма, 16 грамм, ..., 4n - 1 грамм. Кроме того, у вас есть две чаши весов. Чтобы взвесить объект, надо положить его на левую чашу весов и поставить некоторые гири на левую и правую чашу для достижения равновесия. Требуется найти, сколько целых масс в диапазоне [1; m ] возможно измерить, используя весы и данный набор гирь.

Входные данные
В единственной строке содержаться 2 целых числа m и n (1 ≤ n , m ≤ 109 ) .

Выходные данные
Выведите одно число - количество масс, которые можно измерить с помощью этих гирь.
Задача о рюкзаке
✓ 1✗ 7—Войти и решать
Гармоничная последовательность lite - 2#47740
Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1]  является гармоничной, поскольку 2=1+1, и 1=2+(–1) .

Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\)   и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)

В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .

Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.

Входные данные
Первая строка содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 500\)).
Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .

Выходные данные
Выведите одно целое число: минимальное возможное расстояние от исходной до гармоничной последовательности.
 
Примеры
№ Входные данные Выходные данные
1 4
1 2 0 0		 2
Перебор
—Войти и решать
Магическая энергия - 2#46737

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

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

Входные данные
В первой строке записано число n - количество домой вдоль улицы. Во второй строке - n целых чисел ai - количество магической энергии в i-м доме.

Ограничения на входные данные 

  • 1 <= n <= 100
  • 0 <= a[i] <= 1000
  • 1 <= i <= n



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

Примеры
№ Входные данные Выходные данные
1 3
2 3 2		 3
2 4
1 2 3 1		 4
3 3
1 2 3		 3
Динамическое программирование: один параметр
✓ 3✗ 35—Войти и решать
Range Minimum Query#44992

Компания Giggle открывает свой новый офис в Судиславле, и вы приглашены на собеседование. Ваша задача — решить поставленную задачу.

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

  • запрос: «? i j» — возвращает минимальный элемент между i-ым и j-м, включительно;
  • изменение: «+ i x» — добавить элемент x после i-го элемента списка. Если i=0, то элемент добавляется в начало массива.

Конечно, эта структура должна быть достаточно хорошей.


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

Первая строка входного файла содержит единственное целое число n — число операций над массивом (1<=n<=200000). Следующие n строк описывают сами операции. Все операции добавления являются корректными. Все числа, хранящиеся в массиве, по модулю не превосходят 109.


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

Для каждой операции в отдельной строке выведите её результат.


Комментарий к примеру тестов

Нижеследующая таблица показывает процесс изменения массива из примера.
Операция Массив после её выполнения
изначально пуст
+ 0 5 5
+ 1 3 5, 3
+ 1 4 5, 4, 3
+ 0 2 2, 5, 4, 3
+ 4 1 2, 5, 4, 3, 1

 

Примеры
№ Входные данные Выходные данные
1 
8
+ 0 5
+ 1 3
+ 1 4
? 1 2
+ 0 2
? 2 4
+ 4 1
? 3 5
 
4
3
1
Деревья
✓ 1✗ 11—Войти и решать
Переворот#44989

Дан массив. Надо научиться обрабатывать два типа запросов.

* 1 L R - перевернуть отрезок [L,R]

* 2 L R - найти минимум на отрезке [L,R]


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

Первая строка файла содержит два числа n, m. (1<=n,m<=105) Во второй строке находится n чисел ni (1<=ai<=109) - исходный массив. Остальные m строк содержат запросы, в формате описанном в условии. Для чисел L, R выполняется ограничение (1<=L<=R<=n).


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

На каждый запрос типа 2, во входной файл выведите ответ на него, в отдельной строке.

 
Примеры
№ Входные данные Выходные данные
1 
10 7
5 3 2 3 12 6 7 5 10 12
2 4 9
1 4 6
2 1 8
1 1 8
1 8 9
2 1 7
2 3 6
 
3
2
2
2
Деревья
✓ 1✗ 5—Войти и решать
Бинарное дерево (вставка, поиск, удаление)#44987

Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить», «удалить» и «найти» (по значению). Программа должна обрабатывать запросы четырёх видов:

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

DELETE n — если указанное число есть в дереве, удалять его и выводить слово «DONE», если нет — оставлять дерево как было и выводить слово «CANNOT». При удалении элемента, имеющего два сына, обязательно обменивать значение с максимальным элементом левого поддерева.

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

 

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

В каждой строке входных данных записан один из запросов ADD n или DELETE n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

 

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

Для каждого запроса выводите ответ на него. Для запросов ADD, DELETE и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:

template void print_tree(Node *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i < level; i++)

    cout << ".";

  cout <<  p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

 
Примеры
№ Входные данные Выходные данные
1 
ADD 2
ADD 7
ADD 5
PRINTTREE
ADD 5
DELETE 3
ADD 0
PRINTTREE
DELETE 7
PRINTTREE
 
DONE
DONE
DONE
2
..5
.7
ALREADY
CANNOT
DONE
.0
2
..5
.7
DONE
.0
2
.5
 
Деревья
✓ 0✗ 3—Войти и решать
Бинарное дерево (вставка, поиск)#44985

Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить» и «найти» (по значению). Программа должна обрабатывать запросы трёх видов:

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

 

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

В каждой строке входных данных записан один из запросов ADD n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

 

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

Для каждого запроса выводите ответ на него. Для запросов ADD и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:
 

template void print_tree(Node *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i < level; i++)

    cout << ".";

  cout <<  p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

 
Примеры
№ Входные данные Выходные данные
1 
ADD 2
ADD 3
ADD 2
SEARCH 2
ADD 5
PRINTTREE
SEARCH 7
 
DONE
DONE
ALREADY
YES
DONE
2
.3
..5
NO
Деревья
✓ 6✗ 9—Войти и решать
Промежуток на числовой оси#44940
На числовой оси, в промежутке от L до R, Василий нарисовал N вертикальных палочек. Подумав, Василий решил, что ему на числовой оси необходим пустой промежуток шириной не менее W.
Помогите определить Василию, какое минимальное количество палочек необходимо стереть Василию и какие именно.
После того как Василий сотрет некоторое количество палочек, должен найтись промежуток шириной больше или равной W. Промежуток может располагаться между двумя оставшимися палочками, или между оставшейся палочкой и концом промежутка числовой оси, или между двумя концами промежутка числовой оси.

Входные данные
Первая строка содержит два целых числа N и W — количество нарисованных палочек и минимально необходимую ширину промежутка соответственно. Гарантируется, что 0 <= N <= 1 000 000 и 0 <= W <= 1 000 000.
Во второй строке находятся два числа L и R — координаты левого и правого конца промежутка числовой оси (L <= R). В третьей строке записаны N чисел — координаты нарисованных палочек. Все координаты (включая L и R) — различные целые числа, по модулю не превосходящие 1 000 000. Гарантируется, что все палочки нарисованы между левым и правым концами стороны.


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

Если решений несколько, то вы можете вывести любое. Если решения нет, то выведите одну строку, содержащую число  - 1.
 
Примеры
№ Входные данные Выходные данные
1 
3 2
2 6
3 4 5
 
1
1
2 
3 2
1 6
4 3 5
 
0
3 
3 5
1 7
5 3 4
 
3 
2
3
1
Бинарный поиск по ответу
✓ 1✗ 5—Войти и решать
Ральф любит пончики#44712

Громила Ральф вот уже 30 лет живёт в игровом автомате, и вы его можете увидеть на экране того самого автомата. 
Сегодня Ральф гуляет по экрану, на котором отображается прямоугольное изображение, разбитое на N x N клеток. В каждой клетке находится тарелка с его любимыми блинчиками (на всех тарелках разное количество блинчиков). Ральф начинает перемещаться с левой нижней клетки прямоугольника. Съев все блинчики в текущей клетке, он перемещается на одну клетку вправо или на одну клетку вверх, всегда выбирая ту из клеток, где больше блинчиков в тарелке (за пределами прямоугольника тарелок с блинчиками нет). В конце концов Ральф приходит в правую верхнюю клетку. Вам же предстоит определить, сколко всего блинчиков съел Ральф пока путешествовал по экрану. Блинчики в начальной и конечной клетках Ральф тоже съел с большим удовольствием.


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

Программа получает на вход в первой строке целое число N – размер изображения (2 <= N <= 10). В следующих N строках задаются через пробел числа, обозначающие количество блинчиков на тарелках, начиная с верхнего ряда и заканчивая нижним. Все числа – различные, натуральные, не превосходящие 100.


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

Выведите одно число - количество блинчиков, которое съест Ральф, добравшись до правой верхней клетки.

 

Примеры
№ Входные данные Выходные данные
1 
2
37 82
23 52
 
157
Двумерные массивы
✓ 3✗ 1—Войти и решать
Эффективные сборы#43870

Лука часто ездит на сборы по программированию. Сборы длятся n дней. Лука фиксирует количество решенных задач в каждый день сборов. Лука считает сборы «эффективными», если только один непрерывный не нулевой промежуток дней (от l до r), когда выполнялись следующие условия по числу решенных задач:

  • 1 <= l <= r <= n;
  • al = al+1 = al+2 =…=ar;
  • l = 1 или al-1 > al;
  • r = n или ar < ar+1;
Примеры 

Пусть массив A хранит информацию о решении задач за каждый день сборов, тогда:

1) массив A = [5, 3, 3, 2, 3, 3, 4] описывает «эффективные», по мнению Луки, сборы (промежуток в 1 день l = r = 4 удовлетворяет условию);

2) массив А = [2, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8] также описывает «эффективные» сборы (промежут l = 1, r = 3 удовлетворяет условию);

3) массив А = [1, 2, 3, 4, 3, 2, 1] описывает не «эффективные» сборы (есть два промежутка удовлетворяющих условию l = r = 1 и l = r = 7).

Лука только что вернулся с очередных сборов по программированию и рассказал вам сколько задач ежедневно он решал. Определите, являются ли сборы, с которых вернулся Лука «эффективными» по его же мнению.



Входные данные
Первая строка содержит одно целое число n (1 <= n <= 2·105) — длину массива. Вторая строка n целых чисел ai (1 <= ai <= 109) — количество решенных Лукой задач в i-й день .

Выходные данные
Выведите YES, если сборы Луки оказались эффективными, и NO в противном случае.
 
Примеры
№ Входные данные Выходные данные
1 7
5 3 3 2 3 3 4		 YES
2 11
2 2 2 3 4 4 5 6 7 7 8		 YES
3 7
1 2 3 4 3 2 1		 NO
"Два указателя"
✓ 6✗ 12—Войти и решать
K-mex#43131
Вы думали, что сможете спокойно выехать из Озёрска, погостив у друга? Конечно же, нет. Полицейский опять остановил вас и снова просит решить задачу, чтобы удостовериться, что вы можете выехать из города. Придётся вам решить очередную задачу.
Изначально у вас множество, в котором есть единственный элемент — это 0. Вам нужно будет поддерживать q запросов следующего вида:
•    + x — добавить число x в множество. Гарантируется, что раньше его там не было,
•    - x — удалить число x из множества. Гарантируется, что это число там есть,
•    ? k — найти k − mex множества.
В нашей задаче мы считаем, что k − mex множества — это наименьшее целое неотрицательное число x, которое делится на k и которого нет в множестве.
Входные данные
В первой строке находится целое число q (1 <= q <= 2 · 105) — количество запросов.
В следующих q строках находятся описания запросов. Если это запрос добавления, то в формате
+ x (1 <= x <= 1018), если запрос удаления, то - x (1 <= x <= 1018), если же запрос поиска, то ? k (1 <= k <= 1018). Гарантируется, что будет хотя бы один запрос типа ?.

Выходные данные
Для каждого запроса типа ? выведите k − mex множества.
 
Примеры
№ Входные данные Выходные данные
1 18
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 100000000
? 100000000
- 4
? 1
? 2		 3
6
3
3
10
3
200000000
3
4

Замечание
После первого и второго запроса во множестве будут элементы 0,1,2. Наименьшее неотрицательное число, которое не делится на 1 и которого нет в множества, равно 3.
После четвертого запроса во множестве будут элементы 0,1,2,4. Наименьшее неотрицательное число, которое не делится на 2 и которого нет в множества, равно 6
 
реализацияХеш
✓ 1✗ 2—Войти и решать
Лети, лети, лепесток...#43127
Лети, лети, лепесток,
Через запад на восток,
Через север, через юг,
Возвращайся, сделав круг.
Лишь коснёшься ты земли
Быть по-моему вели.
© Цветик-семицветик.

Во время осенних каникул, проходящих с 1 ноября по 8 ноября 2022 года, вы планируете совершить экскурсию в один из городов России. Вы даже выбрали город и даты полётов туда и обратно, но страница с результатами прогрузилась лишь частично. Вам требуется по имеющейся информации найти самый дешёвый вариант посетить выбранный город и вернуться, заодно посчитав, сколько у вас будет времени на осмотр достопримечательностей. Стоит учесть, что часто авиакомпании предоставляют скидку на перелёт туда-обратно.

Входные данные
В первой строке входного файла заданы два целых числа n и m — количество вариантов перелёта «туда» и «обратно» (1 <= n,m <= 1000). В следующих n строках описаны варианты перелёта «туда» в формате: CCxxxx yyyy.mm.dd hh:mm YYYY.MM.DD HH:MM TT:tt value, где:
•    CC — код авиакомпании, xxxx — номер рейса,
•    yyyy.mm.dd hh:mm — дата и время вылета,
•    YYYY.MM.DD HH:MM — дата и время прилёта,
•    TT:tt — время в пути, гарантируется, что время перелёта не превышает 24 часа,
•    value — целое число, стоимость перелёта (0 <= value <= 100000).
В следующих m строках описаны варианты перелёта «обратно» в том же формате. Дата вылета рейса «туда» во всех случаях как минимум на три дня раньше даты рейса «обратно».
Гарантируется, что все перелёты начинаются во время осенних каникул.
В последующих строках выписаны скидки, которые предоставляют авиакомпании за полёт тудаобратно. Каждая строка описывает одну авиакомпанию в формате: CC — код авиакомпании и value — целое число, размер скидки в процентах (0 <= value <= 100). Скидка рассчитывается с точностью до рублей, копейки отбрасываются в пользу клиента. Гарантируется, что у перечисленных компаний есть хотя бы один рейс либо «туда», либо «обратно», и что компании в данном списке не повторяются.

Выходные данные
В первой строке выведите два натуральных числа через пробел — оптимальные номера вариантов рейсов туда и обратно. Если существует несколько пар рейсов, дающих оптимальную стоимость, то нужно выбрать ту, которая позволяет провести за осмотром достопримечательностей как можно больше времени. Из всех таких пар выбрать ту, номера вариантов которой как можно раньше встретились в поисковой выдаче. Во второй строке выведите, сколько времени у вас будет на осмотр, в формате dd:hh:mm. Считается, что осмотр достопримечательностей начинается с момента прибытия и продолжается до момента отлёта.
 
Примеры
№ Входные данные Выходные данные
1 2 3
DP4160 2022.11.02 07:05 2022.11.02 07:35 02:35 4000
DP4130 2022.11.02 07:45 2022.11.02 08:10 02:36 3423
S71141 2022.11.07 05:55 2022.11.07 09:55 02:40 3432
S71042 2022.11.07 05:59 2022.11.07 09:59 02:45 3422
S71243 2022.11.07 04:25 2022.11.07 09:25 02:30 3432
DP 15
S7 10		 2 2
04:21:49
Замечание
Россия – большая страна с 11 часовыми поясами, поэтому, вполне возможно прилететь в город назначения раньше, чем вылетел, поскольку время отправления и прибытия самолетов всегда указывается по местному времени. Из Челябинска можно улететь в Калининград, с разницей -3 часа, или во Владивосток, с разницей +6 часов.
 
Вычисление по заданной формуле
✓ 0✗ 3—Войти и решать
Последовательности длины N#40064
Сколько целых последовательностей длины N, A = (A1,…,AN), удовлетворяют всем приведенным ниже условиям?
1) 1 <= Ai <= M (1 <= i <= N)
2)\(\sum\limits_{i=1}^NA_i \le K\)

Входные данные
На вход подается строка, содержащая три целых числа N, M (1 <= N, M <= 50), K (N <= K <= NM).

Выходные данные
Выведите на ответ на задачу.
 
Примеры
№ Входные данные Выходные данные Пояснения
1 
2 3 4
 
6
 (1,1) (1,2) (1,3) (2,1) (2,2) (3,1)
Динамическое программирование: два параметра
✓ 3✗ 4—Войти и решать
Социальное дистанцирование II#39389
Фермер Джон продолжает бороться за здоровье своих коров.
Имеется N cows (1≤N≤1000) коров, некоторые из которых больны. Коровы выстроены в ряд (на числовой прямой), корова i стоит на позиции xi. ФД знает что если другая корова находится в радиусе R от больной, то она тоже заболевает. А потом заболевают коровы, которые находятся в радиусе R от этой и т.д.

К несчастью, ФД не знает точное значение R. Однако он знает, какие из его коров больны. По этим данным определите минимальное количество изначально инфицированных болезнью коров.

Входные данные
Первая строка ввода содержит N. Каждая из последующих N строк описывает одну корову двумя числами x и s, где x - позиция коровы, а s равно 0 для здоровой коровы и 1 для больной. Как минимум 1 корова больна. И все коровы, которые могли стать больными от распространения болезни уже больны.
Выходные данные
Определите минимальное количество коров, которые изначально были больны, перед любым распространением болезни.
Примеры
№ Входные данные Выходные данные
1 6
7 1
1 1
15 1
3 1
10 0
6 1		 3
Сканирующая прямая
✓ 1✗ 4—Войти и решать
Одностороннее движение#38844
В городе, построенном во времена средневековья, ширина улиц стала препятствовать движению транспорта, которое изначально было двусторонним по каждой из улиц. Для решения этой проблемы было предложено сделать движение по каждой из улиц односторонним. Мэр поручил эту задачу своему первому заму. После долгих размышлений тот доложил, что на некоторых улицах движение придется оставить двусторонним, в противном случае будет невозможно проехать из любого места в городе в любое другое. По данной схеме города требуется найти все такие улицы.

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

Выходные данные
На первой строке выведите число B - количество улиц, на которых организовать одностороннее движение невозможно. На следующей строке выведите B целых чисел - номера этих улиц в возрастающем порядке. Улицы нумеруются с единицы в том порядке, в котором они заданы во входном файле.

 
 
Примеры
№ Входные данные Выходные данные
1 10 16
2 6
3 7
6 5
5 9
5 4
1 2
9 8
6 4
2 10
3 8
7 9
1 4
2 4
10 5
1 6
6 10		 1
4
Обход в глубину
✓ 2✗ 8—Войти и решать
Поделиться
Класснуть