Cod sursă (job #131468)

#include <bits/stdc++.h>

using namespace std;

const int MOD = 100003;

void nextT( int &t1, int &t2, int &t3 ){

    int aux = (t1 + t2 + t3) % MOD;
    t1 = t2;
    t2 = t3;
    t3 = aux;
}

int exp3( int n ){
    long long e = 3;
    long long k = 1;

    while( n ){
        if( n & 1 )
            k = ( k * e ) % MOD;

        e = ( e * e ) % MOD;
        n = ( n >> 1 );
    }

    return k;
}

int main()
{
    ifstream f("2sah.in");
    ofstream g("2sah.out");

    int p;
    int n, k;

    f >> p >> n >> k;

    int t1 = 1;
    int t2 = 1;
    int t3 = 2;

    nextT( t1, t2, t3 );

    if( p == 1 ){
        g << exp3( k - 1 ) << endl;
    }
    else
    {
        int k2 = n - k;

        if( k2 == 0 )
            g << t1 << endl;
        else if( k2 == 1 )
            g << t2 << endl;
        else if( k2 == 2 )
            g << t3 << endl;
        else{
            for( int i = 2 ; i <= k2 ; i++ )
                nextT( t1, t2, t3 );

            g << t3 << endl;
        }
    }

    return 0;
}