Решение задачи "Георгий и раунд" с Codeforces

С пояснением   Просмотров: 10


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

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

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

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

Код

#include <cstdio>

const int N = 3005;

int a[N], b[N];

int main() {
 	int n, m;
 	scanf("%d %d", &n, &m);
 	for(int i = 0; i < n; i++)
 		scanf("%d", &a[i]);
   	for(int i = 0; i < m; i++) 
   		scanf("%d", &b[i]);

   	int bestPossible = n;
   	if (bestPossible > m) bestPossible = m;
   	for(int i = bestPossible; i >= 0; i--) {
   	 	bool ok = true;
   	 	for(int j = 0; j < i; j++)
   	 	 	if (a[j] > b[m - i + j]) ok = false;
   		if (ok) {
   			printf("%d\n", n - i);
   			return 0;
   		}	 
   	}
}

         

 Администратор Photo Автор: Администратор


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

Сложность решения: O(n 2) по времени / O(n) по памяти. Отмечу, существует решение и за линейную сложность O(n + m).

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться