Решение задачи Уменьшение суммы цифр с Codeforces

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


Вам задано целое положительное число n. За один ход вы можете увеличить n на единицу (то есть сделать n:=n+1). Ваша задача — найти минимальное количество ходов, которое надо совершить, чтобы сделать сумму цифр n не превышающей s.

Вам необходимо ответить на t независимых наборов тестовых данных.

Код

#include <bits/stdc++.h>

using namespace std;

int sum(long long n) {
	int res = 0;
	while (n > 0) {
		res += n % 10;
		n /= 10;
	}
	return res;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		long long n;
		int s;
		cin >> n >> s;
		long long ans = 0;
		if (sum(n) <= s) {
			cout << 0 << endl;
			continue;
		}
		long long pw = 1;
		for (int i = 0; i < 18; ++i) {
			int digit = (n / pw) % 10;
			long long add = pw * ((10 - digit) % 10);
			n += add;
			ans += add;
			if (sum(n) <= s) {
				break;
			}
			pw *= 10;
		}
		cout << ans << endl;
	}
	
	return 0;
}

         

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


Сначала давайте проверим, что изначальное n подходит под ограничения. Если это так, выведем 0 и продолжим. Иначе давайте решать задачу жадно. Для начала давайте попробуем выставить последнюю цифру в ноль. Пусть dig=nmod10. Нам необходимо ровно (10−dig)mod10 ходов, чтобы это сделать. Давайте добавим это число к n и к ответу и проверим, что текущее n подходит под ограничения. Если это не так, давайте попробуем выставить предпоследнюю цифру в ноль. Пусть dig=⌊n10⌋mod10. Тогда нам нужно ((10−dig)mod10)⋅10 ходов, чтобы это сделать. Давайте добавим это число к n и к ответу и проверим, что текущее n подходит под ограничения. Если это не так, повторим это с третьей цифрой и так далее. Этот цикл может сделать не более 18 итераций. И мы можем найти сумму цифр n также за не более чем 18 итераций (десятичный логарифм n).



Комментарии

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