Submission #974605

#	Time	Username	Problem	Language	Result	Execution time	Memory
974605		sleepntsheep	Trol (COCI19_trol)	C11	30 / 50	8 ms	444 KiB

trol

#include<stdio.h>
#include<string.h>

#define S 181

int q, A[S];
unsigned 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];
unsigned 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];

    unsigned 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;
}

unsigned long long count_bounded(unsigned long long x)
{
    long long z = 0;
    sprintf(s, "%018llu", x);
    for (int wa, l = 0, r = 17; l < r; ++l, --r)
        wa = s[l], s[l] = s[r], s[r] = wa;

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

int main()
{
    init();

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

Compilation message (stderr)

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("%llu%llu", &l, &r),
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 50