Brakujące cyfry (omówienie)

30.11.2011

Zadanie składa się z szeregu zapytań o to jaką najmniejszą cyfrę należy wstawić w miejsce 'x', aby A dzieliło się przez B. Ponieważ jest tylko 10 cyfr, możemy sobie pozwolić na przejrzenie kolejno ich wszystkich. Zaczynając od 0 i idąc w kierunku 9 jeśli jakaś cyfra wstawiona w miejsce 'x' spełni podzielność, to mamy gotowy wynik. Jedynym problemem może być samo wstawienie cyfry w miejsce 'x'.

To jednak jest realizowane przez poniższy kod (a to potęga dziesiątki będąca wagą 'x' w liczbie A, zaś b to potęga dziesiątki będąca wagą 'x' w liczbie B; jeśli w danej liczbie nie ma 'x', to odpowiednia potęga dziesiątki jest równa 0):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
if(a == 0)
{
        int beg = (b > B) ? 1 : 0;
        for(int i=beg; i < 10; ++i)
        {
                if(A % (B + b * i) == 0)
                {
                        printf("%d", i);
                        break;
                }
        }
}
else if(b == 0)
{
        int beg = (a > A) ? 1 : 0;
        for(int i=beg; i < 10; ++i)
        {
                if((A + a * i) % B == 0)
                {
                        printf("%d", i);
                        break;
                }
        }
}


Same wartości liczb A, B, a, b znajdowane są następująco:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
scanf("%s%s", sA, sB);
A = B = a = b = 0;
for(int i=0; sA[i] != '\0'; ++i)
{
        if(sA[i] == 'x')
        {
                a = 1;
                A *= 10;
        }
        else
        {
                a *= 10;
                A = 10 * A + (sA[i] - '0');
        }
}
for(int i=0; sB[i] != '\0'; ++i)
{
        if(sB[i] == 'x')
        {
                b = 1;
                B *= 10;
        }
        else
        {
                b *= 10;
                B = 10 * B + (sB[i] - '0');
        }
}

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com