PTIT136C spoj – Tìm dãy số
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT136C/ 1. Đề bài PTIT136C spoj Cho trước một dãy số dương có N phần tử. Bạn biết trước tổng của bất kì 2 phần tử nào trong dãy số, hãy tìm dãy số ban đầu. Input Dòng đầu tiên là N, số phần tử của dãy số. (2 <= N <= ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT136C/
1. Đề bài PTIT136C spoj
Cho trước một dãy số dương có N phần tử. Bạn biết trước tổng của bất kì 2 phần tử nào trong dãy số, hãy tìm dãy số ban đầu.
Input
Dòng đầu tiên là N, số phần tử của dãy số. (2 <= N <= 1000)
N dòng sau, mỗi dòng gồm N số (mỗi số <= 100 000) mô tả ma trận biểu diễn tổng của 2 phần tử trong dãy.
* S(i,j) = 0 nếu i = j.
* S(i,j) = A[i] + A[j] với i ≠ j, là tổng của phần tử thứ i và thứ j trong dãy số.
Output
In ra trên 1 dòng dãy số cần tìm. Input luôn đảm bảo có 1 đáp số duy nhất.
Example
Input1:
2
0 2
2 0
Ouput1:
1 1
Input2:
4
0 3 6 7
3 0 5 6
6 5 0 9
7 6 9 0
Ouput2:
2 1 4 5
2. Gợi ý PTIT136C spoj
– Bài này nếu bạn để ý bạn sẽ dễ dàng nhận thấy, chỉ cần cộng trừ những ô trên bảng cho trước thì sẽ thu được kết quả cho trước :))…=))
2 code tham khảo dưới đây không dùng chung 1 công thức nhưng có ý tưởng giống nhau là dùng công thức để tính… các bạn có thể tham khảo:
3. Code tham khảo PTIT136C spoj
a. Code pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | const fi='; nmax=1000; type data=longint; var f:text; A:array[1..nmax,1..nmax] of data; B:array[1..nmax] of data; N:data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do for j:=1 to n do read(f,a[i,j]); close(f); end; procedure xuli; var i,j:data; begin B[1]:=(A[1,2]+a[1,3]-a[2,3]) div 2; B[2]:=(a[1,2]-a[1,3]+a[2,3]) div 2; write(b[1],' ',b[2],' '); for i:=3 to n do write((A[1,2]-A[1,i]-a[2,i]) div (-2),' '); end; begin docfile; xuli; end. |
b. Code c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include <iostream> using namespace std; int main() { int n; cin >> n; int a[n+1][n+1],s[n+1][n+1]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin >> a[i][j]; if(n==2) cout << a[1][2]/2 << " " << a[1][2]/2; else { for(int j=2;j<n;j++) { s[j][j+1]=a[1][j]-a[1][j+1]; if(j==2) cout << a[1][2]-(s[j][j+1]+a[j][j+1])/2 << " "; cout << (s[j][j+1]+a[j][j+1])/2 << " "; if(j==n-1) cout << a[j][j+1]- (s[j][j+1]+a[j][j+1])/2; } } } |
