2013-05-11 15:00:24| 人氣1,194| 回應0 | 上一篇 | 下一篇

[UVA][ad-hoc] 11319 - Stupid Sequence

A stupid sequence is a sequence generated by a function defined by a polynomial as shown below:

So the stupid sequence is actually f(1), f(2), f(3), f(4)…

You can assume that for all i (), .

In this problem you will be given the first 1500 terms of stupid sequence, and you will have to find the values of .

Input

First line of the input file contains an integer N (0<N<101) which denotes the total number of input set. The description of each set is given below:

Each set contains 1500 lines of inputs. Each line contains a single integer. The i-th line of a set denotes the i-th element of a stupid sequence. All these integers fit in 64-bit unsigned integer. There is a blank line after the input of each set.

Output

For each set of input produce one line of output. This line contains the values of . All these values are non-negative and less than 1001. If such values are not found print a line “This is a smart sequence!” instead.

Sample Input Output for Sample Input

sample.in

//Too large to paste here so //download from the link above

1 0 0 0 0 0 0

0 1 1 0 0 0 0

This is a smart sequence!

Problemsetter: Shahriar Manzoor

Special Thanks: Abdullah al Mahmud

看了網路上的解說後，真的是該死的方程式求解。
利用特別的規範條件，a[i] <= 1000。

f(1001) = a0 + a1*1001 + a2*1001*1001 + ... + a6*pow(1001,6)
得 f(1001) ≡ a0 (mod 1001) 可得 a0

(f(1001) - a0)/1001 = a1 + a2*1001 + ... + a6 * pow(1001,5)
得 (f(1001) - a0)/1001 ≡ a1 (mod 1001) 可得 a1

... 類推得全部 a0 ~ a6，然後檢查所有 function 就可以了。
當然不見得要抓 1001, 不過比較方便, 這樣就不用判斷範圍(0~1000)。
也可以抓 1500 的，這題真是讓我見識了一番方程式的奧妙。

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
using namespace std;
unsigned long long s[1505];
unsigned long long o[1505];
#define eps 1e-6
int main() {
    //freopen("in.txt", "r+t", stdin);
    int testcase;
    scanf("%d", &testcase);
    int i, j, k;
    while(testcase--) {
        for(i = 1; i <= 1500; i++) {
            scanf("%llu", &o[i]);
            s[i] = o[i];
        }
        long long sol[10];
        int hasSol = 1;
        for(i = 0; i <= 6; i++) {
            sol[i] = (s[1001]%1001+1001)%1001;
            if(s[1001] < sol[i])
                while(1);
            s[1001] = (s[1001] - sol[i])/1001;
        }
        for(i = 1; i <= 1500 && hasSol; i++) {
            unsigned long long sum = 0, tmp = 1;
            for(j = 0; j <= 6; j++)
                sum += sol[j] * tmp, tmp *= i;
            if(sum != o[i])
                hasSol = 0;
        }
        if(hasSol) {
            printf("%lld", sol[0]);
            for(i = 1; i <= 6; i++)
                printf(" %lld", sol[i]);
            puts("");
        } else
            puts("This is a smart sequence!");
    }
    return 0;
}

高斯消去法，不知道怎麼了一直過不去。

// Wrong Answer !!
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
using namespace std;
double mtx[1505][10];
double o[1505][10];
#define eps 1e-3
int main() {
    //freopen("in.txt", "r+t", stdin);
    int testcase;
    scanf("%d", &testcase);
    int i, j, k;
    while(testcase--) {
        for(i = 1; i <= 1500; i++) {
            scanf("%lf", &mtx[i][8]);
            mtx[i][1] = 1;
            mtx[i][2] = pow(i, 1), mtx[i][3] = pow(i, 2);
            mtx[i][4] = pow(i, 3), mtx[i][5] = pow(i, 4);
            mtx[i][6] = pow(i, 5), mtx[i][7] = pow(i, 6);
        }
        memcpy(o, mtx, sizeof(o));
        for(i = 1; i <= 8; i++) {
            k = i;
            for(j = i+1; j <= 1500; j++)
                if(fabs(mtx[k][i]) < fabs(mtx[j][i]))
                    k = j;
            if(fabs(mtx[k][i]) < eps)
                continue;
            if(k != i) {
                for(j = 1; j <= 7+1; j++)
                    swap(mtx[k][j], mtx[i][j]);
            }
            for(j = 1; j <= 1500; j++) {
                if(i == j) continue;
                for(k = 7+1; k >= i; k--)
                    mtx[j][k] -= mtx[j][i]/mtx[i][i]*mtx[i][k];
            }
        }
        int nosol[10] = {};
        double sol[10] = {};
        for(i = 7; i >= 1; i--) {
            if(fabs(mtx[i][8]) > eps && fabs(mtx[i][i]) < eps)
                nosol[i] = 1;
            else {
                if(fabs(mtx[i][7+1]) < eps)
                    sol[i] = 0;
                else
                    sol[i] = mtx[i][7+1]/mtx[i][i];
            }
            for(j = i+1; j <= 7; j++) {
                if(fabs(mtx[i][j]) > eps && nosol[j])
                    nosol[i] = 1;
            }
        }
        int hasSol = 1;
        for(i = 1; i <= 7; i++) {
            hasSol &= !nosol[i];
            if(round(sol[i]) < 0 || round(sol[i]) > 1000)
                hasSol = 0;
            sol[i] = round(sol[i]);
        }
        if(hasSol) {
            for(i = 1; i <= 1500 && hasSol; i++) {
                double sum = 0;
                for(j = 1; j <= 7; j++)
                    sum += sol[j] * pow(i, j-1);
                if(fabs(sum-o[i][8]) > eps) {
                    hasSol = 0;
                }
            }
        }
        if(hasSol == 0) {
            puts("This is a smart sequence!");
        } else {
            for(i = 1; i <= 7; i++) {
                if(i != 1) putchar(' ');
                printf("%.0lf", sol[i]);
            }
            puts("");
        }
    }
    return 0;
}

我要檢舉

#11319#Stupid Sequence#ad-hoc#方程式求解

台長： Morris

您可能對以下文章有興趣

[UVA] 10672 - Marbles on a tree

[UVA][組合、JAVA大數] 10516 - Another Counting Problem

[UVA] 615 - Is It A Tree?

[UVA][dp] 10898 - Combo Deal

人氣(1,194) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][SlidingWindow] 11536 - Smallest Sub-Array
此分類上一篇:[UVA][3D球面距離] 10316 - Airline Hub

回應(0)