[UVA][ad-hoc] 11319 - Stupid Sequence
Problem E
Stupid Sequence
Input: Standard Input
Output: Standard Output
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
|
//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 <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;
}