UVA 10202+HDU 1270小希の数表
KIDxの解題報告
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1270
題意:n(n-1)/2個の和数(元のn個の数の2つの和)を与え、元のn個の数を求める
黒書『アルゴリズム芸術と情報学コンテスト』30ページにも例題解析があります~~
解析:研究の便宜上、このn個の整数を小さいから大きい順にA 1,A 2,A 3,...,n(n−1)/2個の和数も小さいものから大きいものまで順にK 1,K 2,K 3,...とする.
①A 1+A 2は常に最小で、A 1+A 3は2番目に小さい(なぜか考えてみましょうか?)
方程式があります.
A1+A2 = K1;
A1+A3 = K2;
②A 2+A 3はわかりませんが、A 1+A 4などは彼と大きさを比較できないので、未知数A 1,A 2,A 3が3つあるので、A 1,A 2,A 3を解くには方程式を1つ多くしなければならないので、A 2+A 3の和Ki(i>2)を列挙します
③A 1+A 4④检查方法：利用和K-A 1生成新的数Aj,回到A 2,A 3.Aj-1页,有没有对应的和数,比如A 1+Aj有,A 2+Aj…,但是只能用1次和1次,所以需要标志,以下是UVA 10202的コード,同理HDU 1270也解决了~#include<iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> using namespace std; #define M 105 int main() { int n, m, i, j, k, sum[M], a[15], has[M], s, x; while (~scanf ("%d", &n)) { m = n*(n-1) / 2; for (i = 0; i < m; i++) scanf ("%d", sum+i); sort (sum, sum+m); bool flg; for (i = 2; i < m; i++) //列挙sum[i],令a[2]+a[3]=sum[i] { /****************解方程式****************/ a[2] = (sum[0] - sum[1] + sum[i])/2; a[1] = sum[0] - a[2]; a[3] = sum[1] - a[1]; if (a[2] + a[3] != sum[i]) continue; /****************解方程式****************/ //マークと、0:まだ占有されていません。1:占有されています。 memset (has, 0, sizeof(has)); has[i] = 1; s = 2; flg = true; for (j = 4; j <= n && flg; j++) //繰返し生成後の数 { while (has[s]) s++; //占有されていない和は、新数a[j]を生成する a[j] = sum[s] - a[1]; has[s] = 1; //a[1]+a[j]がsum[s]を占有 for (k = 2; k < j && flg; k++) //a[j]+a[k]の和が存在するかどうかを確認する { for (x = s+1; x < m; x++) { if (!has[x] && a[j]+a[k] == sum[x]) { has[x] = 1; //およびsum[x]が占有される break; //a[j]検査合格 } } //a[j]+a[k]=Sに使用可能な和Sが存在しないことを示す if (x >= m) flg = false; } } if (flg) break; //すべての検査によりn個の数の生成に成功した } if (i < m) { printf ("%d", a[1]); for (i = 2; i <= n; i++) printf (" %d", a[i]); printf (""); } else puts ("Impossible"); } return 0; }
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1270
題意:n(n-1)/2個の和数(元のn個の数の2つの和)を与え、元のn個の数を求める
黒書『アルゴリズム芸術と情報学コンテスト』30ページにも例題解析があります~~
解析:研究の便宜上、このn個の整数を小さいから大きい順にA 1,A 2,A 3,...,n(n−1)/2個の和数も小さいものから大きいものまで順にK 1,K 2,K 3,...とする.
①A 1+A 2は常に最小で、A 1+A 3は2番目に小さい(なぜか考えてみましょうか?)
方程式があります.
A1+A2 = K1;
A1+A3 = K2;
②A 2+A 3はわかりませんが、A 1+A 4などは彼と大きさを比較できないので、未知数A 1,A 2,A 3が3つあるので、A 1,A 2,A 3を解くには方程式を1つ多くしなければならないので、A 2+A 3の和Ki(i>2)を列挙します
③A 1+A 4④检查方法：利用和K-A 1生成新的数Aj,回到A 2,A 3.Aj-1页,有没有对应的和数,比如A 1+Aj有,A 2+Aj…,但是只能用1次和1次,所以需要标志,以下是UVA 10202的コード,同理HDU 1270也解决了~#include<iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> using namespace std; #define M 105 int main() { int n, m, i, j, k, sum[M], a[15], has[M], s, x; while (~scanf ("%d", &n)) { m = n*(n-1) / 2; for (i = 0; i < m; i++) scanf ("%d", sum+i); sort (sum, sum+m); bool flg; for (i = 2; i < m; i++) //列挙sum[i],令a[2]+a[3]=sum[i] { /****************解方程式****************/ a[2] = (sum[0] - sum[1] + sum[i])/2; a[1] = sum[0] - a[2]; a[3] = sum[1] - a[1]; if (a[2] + a[3] != sum[i]) continue; /****************解方程式****************/ //マークと、0:まだ占有されていません。1:占有されています。 memset (has, 0, sizeof(has)); has[i] = 1; s = 2; flg = true; for (j = 4; j <= n && flg; j++) //繰返し生成後の数 { while (has[s]) s++; //占有されていない和は、新数a[j]を生成する a[j] = sum[s] - a[1]; has[s] = 1; //a[1]+a[j]がsum[s]を占有 for (k = 2; k < j && flg; k++) //a[j]+a[k]の和が存在するかどうかを確認する { for (x = s+1; x < m; x++) { if (!has[x] && a[j]+a[k] == sum[x]) { has[x] = 1; //およびsum[x]が占有される break; //a[j]検査合格 } } //a[j]+a[k]=Sに使用可能な和Sが存在しないことを示す if (x >= m) flg = false; } } if (flg) break; //すべての検査によりn個の数の生成に成功した } if (i < m) { printf ("%d", a[1]); for (i = 2; i <= n; i++) printf (" %d", a[i]); printf (""); } else puts ("Impossible"); } return 0; }