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

Митя знаком с \(m\) юношами и \(n\) девушками и хочет пригласить часть из них на свой день рождения. Ему известно, с какими девушками знаком каждый юноша, и с какими юношами знакома каждая девушка. Он хочет добиться того, чтобы каждый приглашённый был знаком со всеми приглашёнными противоположного пола, пригласив при этом максимально возможное число своих знакомых.

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

Входной файл состоит из одного или нескольких наборов входных данных. В первой строке входного файла записано число наборов \(k\) (\(1\le k\le 20\)). В последующих строках записаны сами наборы входных данных. В первой строке каждого набора задаются числа \(0\le m\le 150\) и \(0\le n\le 150\). Далее следуют \(m\) строк, в каждой из которых записано одно или несколько чисел — номера девушек, с которыми знаком \(i\)-й юноша (каждый номер встречается не более одного раза). Строка завершается числом 0.

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

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

Примеры
Входные данные
2
2 2
1 2 0
1 2 0
3 2
1 2 0
2 0
1 2 0
Выходные данные
4
2 2
1 2
1 2

4
2 2
1 3
1 2
#111123
Доставка
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Город Прямой Рог, который пока что не находится на территории Российской Федерации, представляет собой одну прямую улицу. В городе работает компания, которая занимается доставкой товаров. Для удобства, адреса доставки представлены в виде чисел, которые задают расстояние от офиса компании. Положительные числа в одну сторону, а отрицательные – в другую. Заказы на доставку выполняются компанией последовательно, в том порядке, в котором они были заданы. В компании работает два курьера. В начале рабочего дня заказы распределяются между ними, и каждый отправляется по своему маршруту. Компании необходимо так спланировать распределение заказов, чтобы суммарное расстояние, которое будет пройдено курьерами на момент выполнения последнего заказа, была минимальным. Напишите программу, которая по расстояниям адресатов от офиса компании находит наименьшее суммарное расстояние, которое пройдут ее работники.

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

Первая строка входных данных содержит целое число N (1 ≤ N ≤ 100 000) — количество заказов. Далее следует N строк, каждая из которых содержит одно целое число — расстояние от офиса до адресата. Если расстояние положительное — то адресат находится в одной части города относительно офиса компании, а если отрицательное, то в другой. Расстояния по модулю не превышают 108.

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

Единственная строка должна содержать одно целое число — минимально возможное суммарное расстояние, которое пройдут оба работника компании.

Примеры тестов

Входные данные
5
1
-1
2
-2
3
Выходные данные
5

Подзадача 1.
\(N \le 100\). Решение оценивается в \(20\) баллов.
Подзадача 2.
\(N \le 2\,000\). Решение оценивается в \(30\) баллов.
Подзадача 3.
Дополнительные ограничения отсутствуют. Решение оценивается в \(50\) баллов.

#111134
Шахтеры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

На двух угольных шахтах работают шахтеры. Добыча угля — тяжелая работа, так что шахтерам необходимо доставлять еду прямо в шахты. Каждый раз, когда очередная порция продовольствия доставляется в шахту, шахтеры производят некоторое количество угля. Существует три типа еды для шахтеров: мясо, фрукты и бублики. Шахтеры любят разнообразие в еде и будут работать продуктивнее, если их диета будет разнообразной. Точнее, каждый раз, когда в шахту доставляется новая порция продовольствия, необходимо посмотреть на две предыдущие поставки (или меньше чем две, если их еще не было) и действовать по следующему правилу:

  • если вся еда была одинаковой — будет произведена одна тонна угля
  • если еды была двух типов — будет произведено две тонны угля
  • если трех типов — три тонны угля

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

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

Первая строка содержит число N (1 ≤ N ≤ 100 000) — количество поставок еды. Вторая строка содержит N символов — типы поставок в том порядке, в котором они будут осуществляться. Каждый из символов будет большой латинской буквой M (мясо), F (фрукты) или B (бублики).

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

Выведите единственное число — количество тонн угля, которое можно добыть.

Примеры тестов

Входные данные
6
MBMFFB
Выходные данные
12
Входные данные
16
MMBMBBBBMMMMMBMB
Выходные данные
29

Подзадача 1.
\(1 \le N \le 27\). Решение оценивается в \(30\) баллов.
Подзадача 2.
Дополнительные ограничения отсутствуют. Решение оценивается в \(70\) баллов.

#111145
Две подпоследовательности
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

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

Пусть {a1, a2, ..., an} — данная последовательность строк, которую необходимо сжать. Здесь и далее будем считать, что все строки имеют одинаковую длину и состоят только из символов 0 и 1. Определим функцию сжатия:

  • f(пустая последовательность) = пустая строка
  • f(s) = s.
  • f(s1, s2) = наименьшая по длине строка, у которой один из префиксов равен s1, а один из суффиксов равен s2. Например, f(001, 011) = 0011, f(111, 011) = 111011.
  • f(a1, a2, ..., an) = f(f(a1, a2, an - 1), an). Например, f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111.

Перед Валерой стоит серьезная задача — разделить данную последовательность {a1, a2, ..., an} на две подпоследовательности {b1, b2, ..., bk} и {c1, c2, ..., cm}, m + k = n, так, чтобы величина S = |f(b1, b2, ..., bk)| + |f(c1, c2, ..., cm)| приняла минимально возможное значение. Здесь |p| обозначает длину строки p.

Обратите внимание, что запрещается менять относительный порядок строк в подпоследовательностях. Разрешается делать одну из подпоследовательностей пустой. Каждый элемент исходной последовательности должен принадлежать ровно одной из получившихся подпоследовательностей. Элементы подпоследовательностей b и c не обязательно должны идти подряд в исходной последовательности a, то есть они могут чередоваться (смотрите примеры 2 и 3).

Помогите Валере найти минимальное возможное значение S.

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

В первой строке входных данных содержится целое число n — количество строк (1 ≤ n ≤ 2·105). Далее в n строках даны элементы последовательности — строки длиной от 1 до 20 символов, состоящие только из символов 0 и 1. На i + 1 строке входных данных находится i-ый член последовательности. Элементы последовательности разделены исключительно символом перевода строки. Гарантируется, что все строки имеют одинаковую длину.

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

Выведите единственное число — минимально возможное значение S.

Примеры тестов
Входные данные
3
01
10
01
Выходные данные
4
Входные данные
4
000
111
110
001
Выходные данные
8
Входные данные
5
10101
01010
11111
01000
10010
Выходные данные
17
Примечание

Подробные ответы к тестам:

  • Оптимальный вариант: сделать одну из подпоследовательностей пустой, а вторую — равной всей данной последовательности. S = |f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4.
  • Оптимальный вариант: b = {000, 001}, c = {111, 110}. S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8.
  • Оптимальный вариант: b = {10101, 01010, 01000}, c = {11111, 10010}. S = |10101000| + |111110010| = 17.

Подзадача 1. N ≤ 10. Решение оценивается в 30 баллов.

Подзадача 2. N ≤ 1 000. Решение оценивается в 30 баллов.

Подзадача 3. Дополнительные ограничения отсутствуют. Решение оценивается в 40 баллов.

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

#111152
Возрастает ли список?
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Выведите YES, если массив монотонно возрастает и NO в противном случае.

Решение оформите в виде функции IsAscending(A).В данной функции должен быть один цикл while, не содержащий вложенных условий и циклов — используйте схему линейного поиска.

Примеры
Входные данные
1 7 9
Выходные данные
YES
Страница: << 251 252 253 254 255 256 257 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест