817C - Really Big Numbers - CodeForces Solution


binary search brute force dp math *1600

Please click on ads to support us..

Python Code:

n, s = map(int, input().split())
dem = max(0, n - (s + 162) + 1)
for x in range(s, min(n, s+161) + 1):
    if x - sum([int(u) for u in str(x)]) >= s:
        dem += 1
print(dem)

C++ Code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int sumOfDig(ll num)
{
    int sum = 0;
    while (num)
    {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}
ll diff(ll num)
{
    return num - sumOfDig(num);
}
bool isValid(ll num, ll s)
{
    return s <= diff(num);
}
int main()
{
    ll n, s;
    cin >> n >> s;

    ll l, r, m;
    l = 0;
    r = n;
    ll ans = -1;
    while (l <= r)
    {
        m = l + (r - l) / 2;

        if (isValid(m, s))
        {
            r = m - 1;
            ans = m;
        }
        else
        {
            l = m + 1;
        }
    }

    printf("%lld", n < n - ans + 1 ? 0 : n - ans + 1);

    return 0;
}


Comments

Submit
0 Comments
More Questions

688B - Lovely Palindromes
66B - Petya and Countryside
1557B - Moamen and k-subarrays
540A - Combination Lock
1553C - Penalty
1474E - What Is It
1335B - Construct the String
1004B - Sonya and Exhibition
1397A - Juggling Letters
985C - Liebig's Barrels
115A - Party
746B - Decoding
1424G - Years
1663A - Who Tested
1073B - Vasya and Books
195B - After Training
455A - Boredom
1099A - Snowball
1651D - Nearest Excluded Points
599A - Patrick and Shopping
237A - Free Cash
1615B - And It's Non-Zero
1619E - MEX and Increments
34B - Sale
1436A - Reorder
1363C - Game On Leaves
1373C - Pluses and Minuses
1173B - Nauuo and Chess
318B - Strings of Power
1625A - Ancient Civilization