Решение задачи "Таня и игрушки" с Codeforces

Без пояснения   Просмотров: 7


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

Таня уже успела собрать n игрушек различных типов a 1, a 2, ..., a n из новой коллекции. Сегодня у Тани день рождения, и её мама решила потратить не более m бурлей на подарок дочери. Таня в качестве подарка выберет несколько игрушек различных типов из новой коллекции. Конечно, она не хочет получить в качестве подарка игрушку того типа, которая у неё уже есть.

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

Код

#include <cstdio>
#include <set>
#include <vector>
using namespace std;
int main() {
	int n, m, d, i = 1, sum = 0;
	vector<int> ans;
	set<int> has;
	scanf("%d%d", &n, &m);
	while (n--) {
		scanf("%d", &d);
		has.insert(d);
	}
	for (i = 1; sum + i <= m; i++) {
		if (has.find(i) == has.end()) {
			sum += i;
			ans.push_back(i);
		}
	}
	printf("%d\n", (int)ans.size());
	for (int& a : ans) printf("%d ", a);
	return 0;
}

         

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


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

Комментарии

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