oj.uz

Submission #974608

# Submission time Handle Problem Language Result Execution time Memory
974608 2024-05-03T14:07:57 Z vjudge1 Trol (COCI19_trol) C
50 / 50
 7 ms 444 KB 
#include<stdio.h>
#include<string.h>

#define S 181

int q, A[S];
long long dp[19][S], l, r;

void init()
{
    for(int k,i=0;i<S;++i)
    {
        A[i]=i;
        while (A[i] > 9)
        {
            k=A[i],A[i]=0;
            while(k)A[i]+=k%10,k/=10;
        }
    }
    memset(dp, -1, sizeof dp);
}

char s[20];
long long calc(int i, int sum, int f)
{
    if(sum < 0) return 0;
    if(i==-1)return sum==0;
    if (f && dp[i][sum] != -1)
        return dp[i][sum];

    long long ans = 0;
    int high = f ? 9 : s[i] - '0';
    for (int j = 0; j <= high; ++j)
        ans += calc(i-1, sum - j, f || (j < high));
    if(f) dp[i][sum] = ans;
    return ans;
}

long long count_bounded(long long x)
{
    long long z = 0;
    sprintf(s, "%019lld", x);
    for (int wa, l = 0, r = 18; l < r; ++l, --r)
        wa = s[l], s[l] = s[r], s[r] = wa;

    for (int i = 0; i < S; ++i) z += calc(18, i, 0) * A[i];
    return z;
}

int main()
{
    init();

    scanf("%d",&q);
    for (long long l, r; q--;)
        scanf("%lld%lld", &l, &r),
        printf("%lld\n",count_bounded(r) - count_bounded(l-1));
}

Compilation message

trol.c: In function 'main':
trol.c:54:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d",&q);
      |     ^~~~~~~~~~~~~~
trol.c:56:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%lld%lld", &l, &r),
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 5 ms 444 KB Output is correct
3 Correct 7 ms 348 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 7 ms 348 KB Output is correct