Cod sursa(job #6533)

Utilizator filipbFilip Cristian Buruiana filipb Data 19 ianuarie 2007 23:11:07
Problema Diviz Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define aduna(a, b) ( ((a += b) >= MOD) ? (a -= MOD) : 0 )
#define INF 900000000
#define MOD 30103

int N, K, A, B;
char s[205];

int nou[205][205], vechi[205][205], fst[10][205], S[10][205], cnt = 0;
int rst[4505];

int main(void)
{
    int l, i, r, c, cif, uz[10], x;
    
    freopen("diviz.in", "r", stdin);
    freopen("diviz.out", "w", stdout);
    
    scanf("%d %d %d", &K, &A, &B);
    for (i = 1; i < 4500; i++) rst[i] = i % K;
    
    scanf("%s", &s);
    N = strlen(s);
    for (i = N; i >= 1; i--) s[i] = s[i-1]; s[0] = ' '; s[N+1] = "\n";

    for (cif = 0; cif < 10; cif++)
    {
        fst[cif][N+1] = INF;
        for (i = N; i >= 1; i--)
            if (s[i] - '0' != cif)
                  fst[cif][i] = fst[cif][i+1];
            else  fst[cif][i] = i;
        for (i = 1; i <= N; i++)
            S[cif][i] = S[cif][i-1] + (s[i]-'0' == cif);
    }
            
        
    memset(uz, 0, sizeof(uz));
    for (i = 1; i <= N; i++)
        c = s[i]-'0',
        vechi[i][rst[c]] = (!uz[c] && c),
        uz[c] = 1;

    if (A == 1)
       for (i = 1; i <= N; i++)        
           aduna(cnt, vechi[i][0]);    

    for (l = 2; l <= B; l++)
    {
        memset(nou, 0, sizeof(nou));
        for (i = l-1; i < N; i++)
            for (r = 0; r < K; r++)
                for (cif = 0; cif < 10; cif++)
                {
                       x = fst[cif][i+1];                       
                       if (x == INF) continue;
                       /* daca mai exista o alta cifra egala cu cif
                          intre pozitiile i+1 si x-1 */
                       if (S[cif][x-1] - S[cif][i+1] > 0) continue;
                       
                       aduna(nou[x][rst[r * 10 + cif]], vechi[i][r]);                       
                }

        if (l >= A)
           for (i = 1; i <= N; i++)
               aduna(cnt, nou[i][0]);
                
        memcpy(vechi, nou, sizeof(nou));
    }
    
    printf("%d\n", cnt);

    return 0;    
}