[UVA] 927 - Integer Sequences from Addition of Terms
Problem H
Integer Sequences from Addition of Terms
We consider sequences formed from the addition of terms of a given sequence. Let
,
,
be an arbitrary sequence of integer numbers; 
a positive integer. We construct another sequence 
,
,
by defining 
as consisting of
occurrences of the term 
:
 |
For example, if
,
and 
,
then the resulting sequence
is:
 |
Problem
Given
and
we want to obtain the corresponding 
th
integer in the sequence .
For example, with
and
we have 3 for 
;
we have 4 for 
.
With
and 
,
we have 2 for ;
we have 3 for .
Input
The first line of input contains C (0 < C < 100 ), the number of test cases that follows.
Each of the C test cases consists of three lines:
-
The first line represents
- a polynomial in
of degree 
with non-negative integer coefficients in increasing order of the power:
where
,
.
This polynomial
is codified by its degree
followed by the coefficients 
,
.
All the numbers are separated by a single space.
-
The second line is the positive integer .
-
The third line is the positive integer .
It is assumed that the polynomial
is a polynomial of degree less or equal than 20 (
)
with non-negative integer coefficients less or equal than 10000 (
,
);
;
.
Output
The output is a sequence of lines, one for
each test case. Each of these lines contains
the th
integer in the sequence for
the corresponding test case. This value is less or equal than 
.
Sample Input
2 4 3 0 0 0 23 25 100
1 0 1
1
6
Sample Output
1866
3
#include <stdio.h>
long long mypow(long long x, long long y) {
if(y == 0) return 1;
if(y&1)
return x*mypow(x*x, y/2);
else
return mypow(x*x, y/2);
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n, d, k, i, j;
scanf("%d", &n);
long long c[30];
for(i = 0; i <= n; i++)
scanf("%lld", &c[i]);
scanf("%d %d", &d, &k);
int tk = 0, tb = 0;
for(i = 1; ; i++) {
long long an = 0;
for(j = 0; j <= n; j++)
an += c[j]*mypow(i, j);
tb += d;
tk += tb;
if(tk >= k) {
printf("%lld\n", an);
break;
}
}
}
return 0;
}