- プログラミングのお題スレ Part7 [転載禁止]©2ch.net
706 ：デフォルトの名無しさん[sage]：2015/09/05(土) 11:36:50.97 ID:H3Bu+jcQ - 荒れてるところすみませんがお題です
Google Code Jamより
https://code.google.com/codejam/contest/32016/dashboard#s=p0
最小スカラー積
次の2つのベクトルが与えられているとします：v1=(x1,x2,...,xn)とv2=(y1,y2,...,yn)
これらのベクトルのスカラー積は１個の数字で、x1y1+x2y2+...+xnynとして計算されます
各々のベクトルの要素は任意に並べ替えても構わないとします
入力ファイルの最初の行は、テストケース数(整数)Tが含まれています
各テストケースは、最初の行は整数nを含んでいます。次の二行は、v1とv2それぞれの座標が与えられます
出力は、各々のテストケースに対して
Case #X: Y
のようになります
ここでXはテストケース番号、Yは与えられたベクトルの全ての順列の最小スカラー積です
| - プログラミングのお題スレ Part7 [転載禁止]©2ch.net
707 ：デフォルトの名無しさん[sage]：2015/09/05(土) 11:39:13.55 ID:H3Bu+jcQ - 制限
小さなデータセット
T = 1000
1 ≤ n ≤ 8
-1000 ≤ xi, yi ≤ 1000
大きなデータセット
T = 10
100 ≤ n ≤ 800
-100000 ≤ xi, yi ≤ 100000
2種類のデータセットがあるのは、それぞれの得点が異なるからで、どちらを選択されても構いません
例
入力
2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1
出力
Case #1: -25
Case #2: 6
|
|