С
bool foo(int n)
{
std::vector<int> nums { 111111111, 11111111, 1111111, 111111, 11111, 1111, 111, 11 };
for (int num : nums) {
while (n > num)
n -= num;
}
return n == 0;
}
Size: a a a
2021 May 28
MB
По-моему на 121 этот код сломается
VU
Из 1 очевидно можно получить любое число, сложив его сколько нужно раз.
С
возможно докрутить надо - не проверял.что-то такого тупенького абсолютно )) по аналогии перевода римских в обычные (иил наоборот).
MB
Я не уверен, что тут жадное решение сработает
VU
А, т.е. начиная с двухзначных?
MB
Вполне возможно, что для какого-то не очень большого N окажется, что все числа до N можно набрать, и тогда можно до него добить жадно а потом хвостик динамикой решить
MB
Собственно да, посмотрим на число вида 11x. Мы можем перейти к 11(x-10) + 111 и увеличить сумму на 1. Если x >= 100, то мы можем сделать так 10 раз.
Тогда получается, что мы можем набрать любое число начиная с 1100, с помощью одних лишь 10 и 11 (сначала берем 11-ки пока можем, потом пачки из 10 11-ок заменяем на одно 111).
Тогда получается, что мы можем набрать любое число начиная с 1100, с помощью одних лишь 10 и 11 (сначала берем 11-ки пока можем, потом пачки из 10 11-ок заменяем на одно 111).
MB
Ну а для чисел до 1100 можно сделать динамику
AK
Так же сломается
AK
Но на другом примере
AK
Например 11112
CD
А нельзя там что-нибудь заметить в стиле 9 * 111 + 1 = 1000?
MB
Возможно, можно.
Но мне кажется того что я написал уже должно хватить.
Но мне кажется того что я написал уже должно хватить.
CD
Ну я имею в виду: перебираем сумму цифр в 1+ричной системе счисления, там будет 9*x + \sum a[i] = \sum a[i] * (9 * base[i] + 1), таким образом для заданного параметра k = \sum a[i] перебора вопрос "число 9*x + k должно делиться на 100 и представляться в десятичной системе с суммой цифр k"
K
Начиная с 111*11 можно любое, до него - тривиальное дп
K
Первое - у нас для любого остатка k по модулю 11 k*111 имеет такой остаток, дальше дополняем слагаемыми 11
K
Да даже не дп
K
Представимо ли в виде 11а+111b - считаем остаток по модулю 11, полагаем b им, если не перебрались за число - представимо, иначе нет
K
11*111 < 2000