| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 512 MB | 17 | 11 | 11 | 64.706% |
冒険家のパスカルは古代文明が残した宇宙人との通信装置を発見し使用方法を解明した。装置のアンテナは K 本のエレメントと呼ばれる特殊物質でできた直線状の棒で構成される。各エレメントの一端は + 極と呼ばれ、もう一端は - 極と呼ばれる。エレメントには 1 から K までの番号が振られている。
アンテナを動作させるには以下の4つの条件を満たすように組み立てなければならない。
隣り合うエレメントの - 極の位置 2 点と接続点で作られる三角形の面積を隣り合うエレメントの組み合わせすべてについて足しあわせた値がアンテナの強度となる。
アンテナの強度を最大化する並べ方を計算し、その強度を出力せよ。
エレメントの太さは無視できるほど細いものとする。エレメントを切断したり、複数のエレメントをつなぎあわせて1本のエレメントとして使うことはできない。
最初の行はテストケースの個数 T を表す正の整数である。各テストケースは以下のようなフォーマットで表される。
K E1 E2 ... EK
ここで K はエレメントの数である。Ei は正の整数で、i 番目のエレメントの長さを表している。
各テストケースに対し、
Case #X: P
という内容を1行出力せよ。X は 1 から始まるテストケース番号、P は最大化された強度を表す。
3 3 1 1 1 4 1 1 1 1 4 1 1 2 2
Case #1: 1.299038106 Case #2: 2 Case #3: 4.5
Contest > Google > Google's Coding Competitions > Google Code Jam Japan 2011 > Code Jam Japan 2011 決勝 A1번