24h購物| | PChome| 登入
2012-09-02 12:31:40| 人氣1,456| 回應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,456) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 626 - Ecosystem
此分類上一篇:[UVA] 1237 - Expert Enough?

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文