Cod sursa(job #7068)

Utilizator vlad_DVlad Dumitriu vlad_D Data 21 ianuarie 2007 12:17:07
Problema 1-sir Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasele 11-12 Marime 0.66 kb
#include <stdio.h>
int sol = 0;
int v[1000];
int S = 0, N;
int st =0;
void back(int k = 1) {
     if (k == N) {
     if (S == st) {sol++; sol%=194767;}
        return;
        }
     int i;
     if (v[k] *(N-k) +(N-k)*(N-k+1)/2+st < S) return;
     if (st - v[k] *(N-k) -(N-k)*(N-k+1)/2 > S) return;
     // mai trebuie N - k...total = N-k + v[k]
     for (i=-1; i<=1; i+=2) {
         v[k+1] = v[k] + i;
         st+=v[k+1];
         back(k+1);
         st-=v[k+1];
         }
     }
int main() {
   freopen("1-sir.in", "r", stdin);
   freopen("1-sir.out", "w", stdout);
   scanf("%d %d", &N, &S);
   back(1);
   printf("%d\n", sol);
   return 0;
}