Задача: "Интересные числа"
Софья считает число интересным, если его цифры идут в неубывающем порядке. Например, числа 123, 1111 или 888999 — интересные.
Софья заинтересовалась, сколько существует интересных положительных чисел, лежащих в диапазоне от L до R включительно. Это число может оказаться довольно большим для больших L и R, поэтому Софья хочет найти остаток от деления этого числа на 10^9+7.
Требуется написать программу, которая по заданным L и R определяет количество интересных чисел, лежащих в диапазоне от L до R включительно, и выводит остаток от деления этого числа на 10^9+7.
Ограничения: 1 <= L <= R <= 10^100
Пример: Ввод: 1\n100 Вывод: 54
Я написал такой код на python:
def f(n):
res, min_num = 0, 0
for i, j in enumerate(n):
j = int(j)
if j < min_num:
return res
elif j > min_num:
res += sum(a[len(n) - i][9 - x] for x in range(min_num, j))
min_num = j
return res + 1
L = input()
R = input()
p = 10 ** 9 + 7
s = len(R)
a = [[0] * 10 for _ in range(s + 1)]
a[0][0] = 1
for k in range(1, s + 1):
for i in range(10):
a[k][i] = sum(a[k - 1][j] for j in range(i + 1))
print((f(R) - f(str(int(L) - 1))) % p)
Вот тот же алгоритм, только на С++:
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <numeric>
using namespace std;
const long long p = pow(10, 9) + 7;
string decrease(string str)
{
//Уменьшает число в строке на 1
int l = str.length();
if (str[l - 1] == '0')
{
int i = l - 1;
while (str[i] == '0' && i > 0)
{
str = str.substr(0, i) + "9" + str.substr(i + 1, l);
i--;
}
str = str.substr(0, i) + to_string(str[i] - '0' - 1) + str.substr(i + 1, l);
return str;
}
else
return str.substr(0, l - 1) + to_string(str[l - 1] - '0' - 1);
}
long long f(string n, vector<vector<long long>> a)
{
long long res = 0; long long min_num = 0;
for (int i = 0; i < n.length(); i++)
{
int j = n[i] - '0';
if (j < min_num)
return res;
else if (j > min_num)
{
vector<long long> tmp (0);
for (int x = min_num; x < j; x++)
tmp.push_back(a[n.length() - i][9 - x]);
res = (res + accumulate(tmp.begin(), tmp.end(), 0)) % p;
min_num = j;
}
}
return res + 1;
}
int main()
{
string l; string r;
cin >> l;
cin >> r;
long long s = r.length();
vector<long long> tmp (10, 0);
vector<vector<long long>> a (s + 1, tmp);
a[0][0] = 1;
for (int k = 1; k <= s; k++)
{
for (int i = 0; i < 10; i++)
{
vector<long long> tmp (0);
for (int j = 0; j <= i; j++)
tmp.push_back(a[k - 1][j]);
a[k][i] = accumulate(tmp.begin(), tmp.end(), 0) % p;
}
}
cout << (f(r, a) - f(decrease(l), a)) % p;
}
Код на Python проходит все тесты, но код C++ падет (выдаёт неверный ответ) на первом же тесте за 0 секунд. Помогите пожалуйста, что не так в коде C++? (Тестовые данные мне не известны) Код С++ изменил. Переделал to_str(stoll(l) - 1) в функцию, которая делает то же самое, но отставляя l строкой. Всё равно не проходит....
Ответы (3 шт):
C++. int: представляет целое число. В зависимости от архитектуры процессора может занимать 2 байта (16 бит) или 4 байта (32 бита). Диапазон предельных значений соответственно также может варьироваться от –32768 до 32767 (при 2 байтах) или от −2 147 483 648 до 2 147 483 647 (при 4 байтах).
Может, в этом дело?
Алгоритм работает. Ответ у обеих программ (на С++ и Pyton) получается одинаковый.
Нашел только 1 ошибку:
3 раза получается остаток от деления res % p - в функции f() и 2 раза в main(). Причем в коде питона это делается 1 раз в конце. Не влияет на результат, пока числа в массиве меньше p, но при больших значениях может быть ошибка в вычислении, т.к. в массив заносится количество чисел, а в конце программы вычисляется разница между двумя количествами. И если делать разницу между остатками от деления, то может получиться даже отрицательное число.
long long f(string n, vector<vector<long long>> a)
{
...
res = (res + accumulate(tmp.begin(), tmp.end(), 0)) % p;
return res + 1;
}
int main()
{
for (int i = 0; i < 10; i++)
{
a[k][i] = accumulate(tmp.begin(), tmp.end(), 0) % p;
}
cout << (f(r, a) - f(decrease(l), a)) % p;
}
Ну и небольшие замечания по ходу программы:
В циклах в main() и f() при подсчете не нужно создавать временный вектор, добавлять в него что-то а потом суммировать. Можно сразу суммировать.
long long f(string n, const vector<vector<long long>>& a)
{
if (j >= min_num)
{
/* vector<long long> tmp (0); // вместо этого
for (int x = min_num; x < j; x++)
tmp.push_back(a[len - i][9 - x]);
res = (res + accumulate(tmp.begin(), tmp.end(), 0)) % p;
*/
for (int x = min_num; x < j; x++) // написать вот так
res += a[len - i][8 - x];
min_num = j;
}
}
В функцию параметры лучше передавать по константным ссылкам
long long f(const string& n, const vector<vector<long long>> &a)
В функции f() значение min_num лучше сделать int, т.к. это индекс в массиве и его значения меняются от 0 до 9
long long f(string n, vector<vector<long long>> a)
{
long long min_num = 0; // это индекс, он изменяется от 0 до 9
Интересные числа начинаются от чисел, состоящих как минимум из 1 цифры. Поэтому количество строк можно уменьшить. Нулевая строка - количество интересных чисел для одноцифровых чисел. Но с другой стороны - работает и ладно!
Если убрать в циклах промежуточные вектора, то дает одинаковые результаты с питоном.
Есть подозрение, что функция accumulate() отрабатывает некорректно.
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <numeric>
using namespace std;
const long long p = pow(10, 9) + 7;
long long f(string n, vector<vector<long long>> &a)
{
long long res = 0;
int min_num = 0;
for (int i = 0; i < n.length(); i++)
{
int j = n[i] - '0';
if (j < min_num)
return res;
else if (j > min_num)
{
for (int x = min_num; x < j; x++)
res += a[n.length() - i][9 - x];
min_num = j;
}
}
return res + 1;
}
int main()
{
string l = "91111111119111111111911111111191111111119111111111";
string r = "9111111111911111111191111111119111111111911111111191111111119111111111";
int s = r.length();
cout << s << "\n";
cout << decrease(l) << "\n";
vector<long long> tmp (10, 0);
vector<vector<long long>> a (s + 1, tmp);
a[0][0] = 1;
for (int k = 1; k <= s; k++)
{
for (int i = 0; i < 10; i++)
{
for (int j = 0; j <= i; j++)
a[k][i] += a[k - 1][j];
}
}
long long rv = f(r, a);
long long lv = f(decrease(l), a);
cout << rv << "\n";
cout << lv << "\n";
cout << rv - lv << "\n";
cout << (rv - lv) % p;
}