2024年3月2日(土)開催 DDCC2024予選は終了しました。
![title line](../../image/title_line.png)
![Q3](images/q3.png)
点Pをたくさん動かすゲーム
あなたは友人の考案した「点Pをたくさん動かすゲーム」で遊ぶことにしました。このゲームの最高スコアがこの問題の答えです。
2次元座表上に10個の点(点A~点J)があります。
また、あなたの手元に10個のボタン(ボタンA~ボタンJ)があり、それぞれ同じアルファベットの点に対応しています。
ゲーム開始時は、点Aと同じ座標上に点Pが存在し、ボタンAのみが光っています。このゲームでは光っているボタンは押せません。また、点Pの移動中もボタンを押すことはできません。
ボタンX (XはB~Jのいずれか)を押すと、点Pは点Pと点Xを結ぶ線分上を直進し、点Xの位置で止まります。そして、点Pが止まると同時に押されたボタンXは光ります。
ただし、このときの線分上の両端以外に点A~点Jが含まれる場合はゲームオーバーとなり、スコアは0です。また、このときの線分の長さが整数でないときもゲームオーバーとなり、スコアは0です。
ボタンを9回押して全てのボタンが光ったらゲームクリアです。点Pが移動した線分の長さの合計がスコアとなります。ゲームクリアできなかった場合のスコアは0です。つまり、1以上のスコアを得るにはすべてのボタンを光らせる必要があります。
10個の点の座標は、{X1,Y1,X2,Y2,......,X10,Y10}という形式で与えられます。
点A(X1, Y1), 点B(X2, Y2), ......, 点J(X10, Y10) です。
各点のX座標, Y座標の値は全て0以上100以下の整数であり、各点の座標は互いに異なります。
例えば、{1,0,0,0,2,0,4,0,4,1,4,3,2,3,1,3,0,3,0,1}という入力データは下図と対応します。
上図の場合、ボタンB、ボタンCの順にボタンを押すと、点Bと点Cを結ぶ線分上に点Aが存在するためゲームオーバーです。
また、上図の場合、ゲーム開始直後にボタンFを押すと、線分AFの長さが整数でないためゲームオーバーです。
スコアを1以上にできない入力データが与えられることはありません。
3パターンの入力データがあります。それぞれに対する答えを求め、カンマ区切りで答えてください。
- 例題
-
{0,0,1,0,2,0,3,0,4,0,0,1,0,2,1,2,2,2,4,2},
{1,0,0,0,2,0,4,0,4,1,4,3,2,3,1,3,0,3,0,1},
{4,1,1,0,6,4,0,0,12,0,1,5,12,5,13,5,10,1,0,5} - 例題の解答
- 13,27,81
- 例題の解説
- 各入力データに対する最高スコアを達成するときの点Pの軌跡を赤色の線で示します。
![](images/question/q3_2.png)
![](images/question/q3_3.png)
![](images/question/q3_4.png)
※以下の入力データをコピーして解答してください。
{0,0,30,0,60,0,90,0,96,0,0,40,30,40,60,40,90,40,96,40},
{100,20,65,18,1,0,86,90,0,90,92,60,86,23,80,51,50,100,2,10}
配点:300点