[UVA] 927 - Integer Sequences from Addition of Terms＠Morris' Blog｜PChome Online 人新台
24h物| | PChome| 登入
2012-09-02 12:31:40| 人1,508| 回0 | 上一篇 | 下一篇

[UVA] 927 - Integer Sequences from Addition of Terms

推 0 收藏 0 0 站台

Problem H

Integer Sequences from Addition of Terms

We consider sequences formed from the addition of terms of a given sequence. Let $ {a_n}$, $ n = 1,2,3,ldots$, be an arbitrary sequence of integer numbers; $ d$ a positive integer. We construct another sequence $ {b_m}$, $ m = 1,2,3,ldots$, by defining $ b_m$ as consisting of $ n times d$ occurrences of the term $ a_n$:
$displaystyle b_1 = underbrace{a_1, ldots, a_1}_{d text{ occurrences of } a_... ...underbrace{a_3, ldots, a_3}_{3d text{ occurrences of } a_3} , , quad cdots$    

For example, if $ a_n = n$, and $ d = 1$, then the resulting sequence $ {b_m}$ is:
$displaystyle underbrace{1}_{b_1},underbrace{2,2}_{b_2},underbrace{3,3,3}_{b_3}, underbrace{4,4,4,4}_{b_4},cdots$    

Problem

Given $ a_n$ and $ d$ we want to obtain the corresponding $ k$th integer in the sequence $ {b_m}$. For example, with $ a_n = n$ and $ d = 1$ we have 3 for $ k = 6$; we have 4 for $ k=7$. With $ a_n = n$ and $ d = 2$, we have 2 for $ k = 6$; we have 3 for $ k=7$.

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:

  1. The first line represents $ a_n$ - a polynomial in $ n$ of degree $ i$ with non-negative integer coefficients in increasing order of the power:
    $displaystyle a_n = c_0+c_1 n +c_2 n^2+c_3 n^3+cdots + c_i n^i , , $
    where $ c_j in mathbb{N}_0$, $ j = 0,ldots,i$. This polynomial $ a_n$ is codified by its degree $ i$ followed by the coefficients $ c_j$, $ j = 0,ldots,i$. All the numbers are separated by a single space.
  2. The second line is the positive integer $ d$.
  3. The third line is the positive integer $ k$.

It is assumed that the polynomial $ a_n$ is a polynomial of degree less or equal than 20 ( $ 1 le i le 20$) with non-negative integer coefficients less or equal than 10000 ( $ 0 le c_j le 10000$, $ j = 0,ldots,i$); $ 1 le d le 100000$; $ 1 le k le 1000000$.

Output

The output is a sequence of lines, one for each test case. Each of these lines contains the $ k$th integer in the sequence $ {b_m}$ for the corresponding test case. This value is less or equal than $ 2^{63}-1$.

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;
}
 

我要
#927#Integer Sequences#from Addition of Terms
台： Morris

您可能以下文章有趣

人(1,508) | 回(0)| 推 (0)| 收藏 (0)| 寄
全站分: 不分 | 人分: UVA |
此分下一篇:[UVA] 626 - Ecosystem
此分上一篇:[UVA] 1237 - Expert Enough?

我要回
否 是 (若未登入"人新台"看不到回覆唷!)
* 入：
入片中算式的果(可能0) 
(有*必填)
TOP
全文
ubao snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86