Cod sursa(job #1967802)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 17 aprilie 2017 03:30:49
Problema Koba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;

long long sum_here[1000][32] = {}, goes_to[1000][32];
// sum_here[ijk][x] = 
// suma daca incepe la (i, j, k) si avem 2^x elemente

int next(const int x){
    return ((x/100) * (x/10) + x)%10; }

int composite(const int x, const int y){
    return (10*x+y) % 1000; }

int main(){
    for(int i = 0; i < 1000; ++i)
        goes_to[i][0] = composite(i, next(i));
    for(int x = 1; x < 32; ++x)
        for(int i = 0; i < 1000; ++i)
            goes_to[i][x] = goes_to[goes_to[i][x-1]][x-1];

    for(int i = 0; i < 1000; ++i){
        sum_here[i][0] = i/100;
        sum_here[i][1] = i/100 + (i/10)%10;
        sum_here[i][2] =(i/100) + (i/10)%10 + i%10 + next(i); }

    for(int x = 3; x < 32; ++x)
        for(int i = 0; i < 1000; ++i)
            sum_here[i][x] = sum_here[i][x-1] + sum_here[goes_to[i][x-1]][x-1];
    
    ifstream f("koba.in");
    ofstream g("koba.out");
    int x, y, z, n;
    f >> n >>  x >> y >> z;
    int stare = 100 * (x%10) + 10 * (y%10) + z%10;

    long long sum = 0;
    for(int i = 0; n; ++i){
        if((n>>i)&1){
            sum += sum_here[stare][i];
            stare = goes_to[stare][i];
            n ^= 1<<i; } }
    g << sum << endl;
    return 0; }