Process

This one gave me a lot of problems. The concept itself was difficult to understand at first. A sequence a_n consists of groups of size d * n. For example, 1 2 2 3 3 3 4 4 4 4… where d = 1 or 1 1 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4… where d = 2. Given this sequence, we’re given a polynomial function and asked to find the value outputted from this function whose input we calculate given an index k and d for the sequence a_n. Therefore, we must pregenerate the a_n sequence and calculate the value of the group the index belongs to. I preprocessed a few thousand values in the sequence a_n where d = 1. The values where d = 2, 3… can be calculated by the formula k / d. I used (k – 1) / d because I shifted to zero index. The most painful part was that I glanced over the bit that said, output is “less or equal than 2^63 – 1”. This is a long long value and must be incorporated in your evaluation function and print statement, or you will certainly get WA.

/*
* Sai Cheemalapati
* UVA 927: Integer sequences from addition of terms
*
*/
#include<cmath>
#include<cstdio>
using namespace std;
int C, T, coefs[30], d, k;
int seq[1000000];
int prep() {
int sum = 0;
seq[0] = sum;
for(int i = 0;; i++) {
sum = sum + i;
if(sum >= 1000000) break;
seq[sum] = i + 1;
}
}
unsigned long long eval(int n, int i) {
if(i == T) return 0;
return coefs[i] * pow(n, i) + eval(n, i + 1);
}
int main() {
prep();
scanf("%d", &C);
while(C--) {
scanf("%d", &T);
T++;
for(int i = 0; i < T; i++)
scanf("%d", &coefs[i]);
scanf("%d\n%d", &d, &k);
int ind = (k - 1) / d;
while(ind > 0 && seq[ind] == 0) ind--;
printf("%llu\n", eval(seq[ind], 0));
}
}

12
4 3 0 0 0 23
25
100
1 0 1
1
6
3 0 1 5 7
7
43
3 0 1 5 7
7
1
3 0 1 5 7
7
16
3 0 1 5 7
7
42
3 0 1 5 7
7
7
3 0 1 5 7
7
1000000
5 1 1 1 1 1 1
1
1000000
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100000
1000000
1 1 1
2
1000000
20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1
21

1866
3
532
13
78
237
13
1073344285
5656584705361395
1466015503701
1001
3656158440062976

### Like this:

Like Loading...

*Related*