Георгий и раунд

@andreinorma5 · 21.11.2021, 23:25. **Показов** 974. **Ответов** 5

Студворк — интернет-сервис помощи студентам

Георгий решил подготовить раунд для Codesecrof, поэтому он подготовил m задач. Пронумеруем подготовленные задачи целыми числами от 1 до m. Сложность задачи с номером i Георгий оценивает целым числом bi.

Чтобы раунд получился хорошим, он должен состоять как минимум из n задач. Кроме этого он должен иметь хотя бы одну задачу со сложностью ровно a1, хотя бы одну со сложностью ровно a2, ..., и хотя бы одну задачу со сложностью ровно an. Конечно, в раунде дополнительно могут быть задачи и с другими сложностями.

Георгий обладает плохой фантазией, поэтому ему проще упростить некоторую уже подготовленную задачу, чем придумать новую и подготовить ее. В упрощении задач Георгий виртуоз. Он может упростить любую уже подготовленную задачу со сложностью c до любой целой положительной сложности d (c ≥ d), изменив ограничения на входные данные.

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

Входные данные:
В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 3000) — минимальное количество задач в хорошем раунде и количество подготовленных Георгием задач. Во второй строке заданы целые числа через пробел a1, a2, ..., an (1 ≤ a1 < a2 < ... < an ≤ 106) — требования на сложности задач в хорошем раунде. В третьей строке заданы целые числа через пробел b1, b2, ..., bm (1 ≤ b1 ≤ b2... ≤ bm ≤ 106) — сложности задач, подготовленных Георгием.

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

Примеры:
входные данные
3 5
1 2 3
1 2 2 3 3
выходные данные
0

входные данные
3 5
1 2 3
1 1 1 1 1
выходные данные
2

входные данные
3 1
2 3 4
1
выходные данные
3

@eaa · 21.11.2021, 23:36

andreinorma5, и какие идеи по решению? Что не получается?

@Val Rubis · 22.11.2021, 01:35

Такое себе решение:

Python
1
2
3
4
5
6
7
8
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for x in range(n-1,-1,-1):
    if a[x] in b:
        b.remove(a[x])
        a.remove(a[x])
print(len(a))

@КулХацкеръ · 22.11.2021, 01:45

норм решение, все примеры выше решает верно.

@Val Rubis · 22.11.2021, 02:12

КулХацкеръ, это и настораживает.
Можно короче:

Python
1
2
3
4
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(len(list(set(a) - set(b))))

@eaa · 22.11.2021, 06:26

Новые блоги и статьи Все статьи Все блоги /
10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .

@andreinorma5 Заблокирован

	Георгий и раунд 21.11.2021, 23:25. Показов 974. Ответов 5 Метки нет (Все метки) Георгий решил подготовить раунд для Codesecrof, поэтому он подготовил m задач. Пронумеруем подготовленные задачи целыми числами от 1 до m. Сложность задачи с номером i Георгий оценивает целым числом bi. Чтобы раунд получился хорошим, он должен состоять как минимум из n задач. Кроме этого он должен иметь хотя бы одну задачу со сложностью ровно a1, хотя бы одну со сложностью ровно a2, ..., и хотя бы одну задачу со сложностью ровно an. Конечно, в раунде дополнительно могут быть задачи и с другими сложностями. Георгий обладает плохой фантазией, поэтому ему проще упростить некоторую уже подготовленную задачу, чем придумать новую и подготовить ее. В упрощении задач Георгий виртуоз. Он может упростить любую уже подготовленную задачу со сложностью c до любой целой положительной сложности d (c ≥ d), изменив ограничения на входные данные. Однако не все так просто. Георгий понял, что даже в том случае, если он упростит некоторые задачи, ему может не хватить задач для хорошего раунда. Поэтому он решил узнать у вас, какое минимальное количество задач ему необходимо придумать дополнительно к уже подготовленным m задачам, чтобы из всех задач можно было собрать хороший раунд. Учтите, что Георгий может придумывать задачи любой сложности. Входные данные: В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 3000) — минимальное количество задач в хорошем раунде и количество подготовленных Георгием задач. Во второй строке заданы целые числа через пробел a1, a2, ..., an (1 ≤ a1 < a2 < ... < an ≤ 106) — требования на сложности задач в хорошем раунде. В третьей строке заданы целые числа через пробел b1, b2, ..., bm (1 ≤ b1 ≤ b2... ≤ bm ≤ 106) — сложности задач, подготовленных Георгием. Выходные данные: Выведите единственное целое число — ответ на задачу. Примеры: входные данные 3 5 1 2 3 1 2 2 3 3 выходные данные 0 входные данные 3 5 1 2 3 1 1 1 1 1 выходные данные 2 входные данные 3 1 2 3 4 1 выходные данные 3 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	21.11.2021, 23:36
	andreinorma5, и какие идеи по решению? Что не получается? 0

@КулХацкеръ 710 / 356 / 104 Регистрация: 09.02.2018 Сообщений: 805
	22.11.2021, 01:45
	норм решение, все примеры выше решает верно. 0

Опции темы