# Internet Problem Solving Contest

## Solution to Problem A – Andrew's Exams II

Let's go straight to the solutions. The easier one first.

```#include <stdio.h>

int A, B;
int i,j,k,l,m;

int main(void) {
for (i=0;i<4000;i++) { A[i]=B[i]=0; } k=-1; m=0;
while (!A) {
A++; B++;
for (j=0;j<3999;j++) { B[j+1]+=B[j]/13; B[j]%=13; }
for (j=0,l=-1;j<3999;j++) {
if ((A[j]>0) && (k<j)) { k=l=j; }
A[j+1]+=A[j]/(j+2); A[j]%=(j+2);
}
if (l>-1) m+=B;
}
printf("%d\n",m);
return 0;
}
```

Initially, all elements in both arrays are set to 0. In each pass through the while cycle, we add 1 to both A and B. What happens with the array B? If B is less than 13, nothing. If it is now equal to 13, we set B to 0, increase B and continue with B in the same way. It is quite easy to find out, that after N passes through the cycle the numbers B[i] will be the digits of N in base 13. (The process done with this array corresponds to adding 1.) And what about array A? The element A[i] can only have values from 0 to i+1. If we look at this array in the same way, it makes us realize, that this process also corresponds to "adding 1" in some way. Exactly said, the sum A.(0+1)! + A.(1+1)! + ... + A[i].(i+1)! + ... + A.(1000+1)! always increases by 1. The last question to answer: when is l>-1 (and the value of m altered)? It happens, when a non-zero element with the index greater than ever before occurs in the array A. This means, that it's the moment, when all elements of A but one are zero and that one element is 1. But this means, that if the index of the non-zero element is j, there were exactly (j+1)! passes through the cycle so far. And so B (the last digit of (j+1)! in base 13) is (j+1)! mod 13.

It is already possible to solve this task by simply summing up all values of n! mod 13 for n from 1 to 1001, but we can make yet one simple observation. For n greater than 12, n! is divisible by 13. So it suffices to count the sum for n 1 to 12.

We have to apologize, because (despite our efforts) there was a small bug in the Pascal version of this problem -- the line writeln(m); at the end was missing. Some of you have notified us about this problem during the contest, but we decided that it is just a small bug that can easily be corrected by looking at the C version of this problem, and so we won't send you more than 500 emails with the correct input... We hope, that this small flaw didn't cause you any inconvenience.

And now the more difficult one:

```#include <stdio.h>

int foo(int a, int b)
{
return a<b?0:a-b;
}

int goo(int a, int b)
{
return a+foo(b,a);
}

int boo(int a, int b)
{
return a+b-goo(b,a);
}

int moo(int a, int b)
{
int i,j,r;
r = 0;
for (i=b+boo(a,b)-goo(b,a); i<=b+foo(a,b)+foo(b,a)+7; i++) {
if (i<=0) continue;
j = foo(a%i, b%i) + foo(goo(a%i, 0), boo(b%i, 0));
j += foo(b%i, a%i) + foo(boo(0, b%i), goo(0, a%i));
if (!j) r=i;
}
return ( boo(r,b)==(a-foo(a,b)) );
}

int soo(int a)
{
int i,s;
s = 0;
for (i=1; i<=goo(a,7)+boo(7,a)-7; i++)
if (moo(a,i)) s++;
return s;
}

int main(void){
int i;
i = 0;
while(soo(i)!=7777)
i++;
printf("%d\n",i);
return 0;
}
```

So, let's find out, what do the various functions do.

foo is fairly simple, it returns max(a-b,0). We may also note, that foo(a,b)+foo(b,a)=abs(a-b), it will be useful later.
if a>=b, goo returns a+max(b-a,0)=a+0=a.
if a<b, goo returns a+max(b-a,0)=a+(b-a)=b.
From these observations easily follows, that goo(a,b)=max(a,b)
And if goo(a,b)=max(a,b), then boo(a,b)=a+b-max(a,b)=min(a,b)