全国高等学校パソコンコンクール
プログラミング部門 本選問題
２０２３年１１月１１日(土)１３時４５分～１７時４５分

全国高等学校パソコンコンクール実行委員会

問題１ 穴あきワッフル（２点）

穴あきワッフルは、生地が格子状になっている。生地の線が縦に𝑁本、横に𝑁本あるワッフルを、レベル𝑁の穴あきワッフルと呼ぶ。線の太さは１ｃｍであり、同方向の線は 1ｃｍ間隔で並んでいる。また、生地の線とその交点以外の部分は穴であり、ワッフル全体の四隅は穴である。たとえば、レベル３の穴あきワッフルは、生地を黒色、穴を白色で表すと、右のように描ける。

課題
与えられたレベルの穴あきワッフルを描くプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁
１行に穴あきワッフルのレベル𝑁(1 ≤ 𝑁 ≤ 100)が与えられる。

出力
1ｃｍ×1ｃｍの領域を 1 文字とし、生地には「#」、穴には「.」を使い、レベル𝑁の穴あきワッフルを出力する。

入出力例
入力例１3出力例１.#.#.#.
#######.#.#.#.
#######.#.#.#.
#######.#.#.#.

入力例２
1

出力例２.#.
###.#.

問題２ サバを読む（３点）

キヨシさんはネットで𝑛進法に関する記事を読んだ。そこには以下のように書かれていた。
くらい

くらい

我々は数値を表現する際に、10 進 位 取り記数法を使用している。10 進 位 取り記数法は 10 進法とも呼び、この表現で示された数値を 10 進数と呼ぶ。10 進法は以下のルールで数値を数字の列で表現する。


0,1,2,3,4,5,6,7,8,9 の 10 種類の数字を使う。
数字をいくつか並べて列を作る。数字の位置を桁と呼び、いちばん右の数字を 1 桁目とする。
𝑖桁目の数字に10 を掛けた数値をもとめ、それらをすべて足したものが、その数字の列が示す数値となる。ただし、10 = 1とする。

同様に、𝑛進法 (𝑛 ≥ 2, 𝑛は整数)は、以下のルールで数値を数字の列で表現する。
0 から𝑛 − 1までの数字を使う。ただし、𝑛が 10 より大きいときは、10 以上の数字を表すときに文字を使う。たとえば、𝑛が 16 までのときは数が小さい方から順番に、0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F を使うことが多い。A=10, B=11, …, F=15 を示す。
数字をいくつか並べて列を作る。数字の位置を桁と呼び、いちばん右の数字を 1 桁目とする。
𝑖桁目の数字に𝑛 を掛けた数値をもとめ、それらをすべて足したものが、その数字の列が示す数値となる。ただし、𝑛 = 1とする。



𝑛進法について学習したキヨシさんは、10 進数𝑋を𝑛進数(𝑛 ≠ 10)として読み取ると、𝑋より小さな数として読み取れる場合があることに気付いた。さらに 10 進数を𝑛進数(𝑛 ≠ 10)として読み取ることができるような𝑛とできない𝑛があることに気付いた。たとえば、10 進数 237 は 8 進数として読み取ることができるが、7 進数として読み取ることはできない。
キヨシさんは自分の年齢𝑋を 10 進法で表した数字の列を、𝑛 ≠ 10を満たす𝑛進数として読み取ることで、自分が𝑋歳より若いと言い張れるかどうかを考えることにした。

課題
キヨシさんの年齢𝑋が 10 進数で与えられる。これを 10 進数以外の数として読み取ったときに、𝑋未満の数として読み取れるかどうかを判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑋

1 行目にキヨシさんの年齢𝑋(1 ≦ 𝑋 ≦ 1,000,000,000 = 10 )が 10 進数で与えられる。

出力
キヨシさんの年齢𝑋を 10 進数以外の数として読み取ったときに、𝑋未満の数として読み取れる場合は「Yes」、そうでないならば「No」を出力せよ。

入出力例
入力例１30029

出力例１No

入力例２8264

出力例２
Yes

入力例３5出力例３
No問題３ 村を整える（４点）

イヅア村には畑 1 から畑𝑁までの𝑁区画の畑がある。この村では、それぞれの畑に植えなければならない作物の数が畑ごとに決まっている。その決まりに従った数の作物がすべての畑に植えられると、村人たちは村が整ったと言って、その年の豊作を確信する。
今年は、その決まりを知らない人がすべての畑に適当に作物を植えてしまった。村長であるあなたは、それぞれの畑について作物の数が決められた数になるようにして、村を整えなければならない。しかし、イヅア村では畑𝑖に植えられている作物の数（𝑥本とする）を変更したいときは、以下のような手順に従わなければならない。
1.
2.

作物の数が𝑥本より多い畑𝑘を選ぶ。
畑𝑘の作物の数を𝑦本とするとき、𝑦 − 𝑥本の作物を畑𝑖に加えることで畑𝑖の作物の数を𝑦本にする。

この手順を何回か行うことで村を整えることができるなら、そのために必要な最少の回数を知りたいとあなたは思っている。

課題
畑の区画の数𝑁とそれぞれの畑に植えなければならない作物の数、決まりを知らない人が植えた作物の数が与えられたとき、村を整えるために行う手順の最少の回数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑟 𝑟 ⋯𝑟𝑐 𝑐 ⋯𝑐

1 行目に畑の区画の数𝑁(1 ≤ 𝑁 ≤ 1,000)が与えられる。続く１行に、畑𝑖に植えなければならない作物の数𝑟 (1 ≤ 𝑟 ≤ 1,000)が与えられる。
続く 1 行に、決まりを知らない人が畑𝑖に植えた作物の数𝑐 (1 ≤ 𝑐 ≤ 1,000)が与えられる。

出力
村を整えることができるなら、そのために必要な最少の回数を１行に出力する。村を整えることができないなら、「-1」を１行に出力する。

入出力例
入力例１33 3 23 2 1

出力例１2

入力例２34 3 24 2 1

出力例２-1

問題４ ロールケーキ（５点）

イヅア菓子店の目玉商品は、イチゴが乗ったロールケーキである。
ロールケーキは長さ𝑁cm で、右の図のように、𝑁 − 1本の線によって長さ 1cm の𝑁個の区間に分かれている。各区間にはイチゴが１個乗っているか１個もないかのいずれかである。どの区間にイチゴが乗るかは店主のその日の気分で変わる。
イヅア菓子店のロールケーキを買ったあなたは、何本かの線に沿ってロールケーキを切り、ケーキのピースを作る。できたピースのうち、長さが同じ（ただし 2cm 以上）で、イチゴの数が等しいピースだけを選んでみんなに配ろうとしている。できるだけ多くのピースを配れるようにロールケーキを切りたい。
あなたは、最大でいくつのピースを配ることができるだろうか？

課題
ロールケーキの情報が与えられたとき、配ることができるピースの最大の数を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑆

1 行目にケーキの情報を示す文字列𝑆（長さ2以上100,000 = 10 以下）が与えられる。文字列𝑆は文字 x（小文字のエックス）と文字 o（小文字のオー）のみから構成されており、1 文字が１つの区間に対応する。文字x は区間にイチゴが乗っていないことを、o は区間にイチゴが乗っていることを表す。

出力
配ることができるピースの最大の数を 1 行に出力する。

入出力例
入力例１ooxoxooxoo

出力例１3

たとえば、ooxとoxoとxooを配ることができる。
入力例２xxxxoxxxoxxxx

出力例２5

この例では、xxを５ピース配ることができる。
入力例３xo

出力例３1

問題５ ９つの数字（６点）

PCK 君の家の入口には特殊な電子錠がついている。この電子錠には１から９までの数字が、右の図のように縦３行、横３列に配置されている。この電子錠には数字を指し示すカーソルが１つあり、カーソルによって常にどれか１つの数字が指し示されている。

789456123

電子錠を開錠するために、所定の数字列が暗証番号として設定されている。暗証番号に含まれる数字を左から順番に入力していくことで開錠することができる。入力するときには、以下のどちらも１回の操作と考える。


隣接する上下左右のどれかの数字へカーソルを移動する。
カーソルが指し示す数字を入力する。

暗証番号の入力開始時には、図のように矢印で表されるカーソルが右下の数字を指している。１から９までの数字は、操作開始前に自由に並べ替えることができる。PCK 君は、数字を並べ替えることによって、暗証番号を入力するために必要な操作回数がどれだけ少なくできるかを知りたい。

課題
暗証番号が与えられたとき、暗証番号を入力するために必要な操作回数の最小値を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁
１行に暗証番号を表す整数𝑁(1 ≤ 𝑁 < 10)が与えられる。ただし、𝑁の各桁に0は含まれない。

出力
操作回数の最小値を出力する。

入出力例
入力例１123456789

出力例１17

入力例２325821642813

出力例２26

たとえば、以下のように数字を並べ替えれば、26回の操作で暗証番号を入力できる。

789975456482123613

変更前

変更後

問題６ PCK 君のひそかな楽しみ（６点）

PCK 君の楽しみは、目にした文字列の中から自分の名前 PCK を見つけることである。文字 P、C、K は左から順番に現れてさえいれば連続していなくてもよい。PCK を文字列の中に見つけられれば彼は満足する。
自分の名前を見つけるだけでは物足りなくなってきた PCK 君は、文字列の中から、自分のラッキーナンバー以上の数だけ PCK が現れる文字列の範囲がいくつあるか探すことにした。たとえば、ラッキーナン
バーが 2 で文字列が PCCKA とする。この文字列の中には 1,2,4 文字目と 1,3,4 文字目からなる２つのPCK があるので、PCK が２つ以上現れる文字列の範囲は 1 文字目から 4 文字目までと 1 文字目から 5 文字目までの２つである。

課題
ラッキーナンバー𝐿と文字列が与えられたとき、PCK が𝐿個以上現れる文字列の範囲の個数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝐿𝑆

1 行 目 に 文 字 列 の 長 さ 𝑁(3 ≤ 𝑁 ≤ 200,000 = 2 × 10 ) と 、 そ の 日 の ラ ッ キ ー ナ ン バ ー 𝐿(1 ≤ 𝐿 ≤1,000,000,000,000,000 = 10 )が与えられる。続く 1 行に、英大文字からなる長さ𝑁の文字列𝑆が与えられる。

出力
文字列 PCK が𝐿個以上現れる範囲の数を 1 行に出力する。

入出力例
入力例１5 2
PCCKA

出力例１2

入力例２8 2
BPCKQPCK

出力例２2

入力例３9 3
PPCPKPCKK

出力例３6

入力例４6 2PKCPKC

出力例４0

問題７ 順位の予測（９点）

白虎大学が主催するプログラミングコンテストには、それぞれ 1 から𝑀の番号が付けられた𝑀組のチームが参加している。コンテストでは難易度に応じた得点がそれぞれ割り当てられたいくつかの問題が出題され、以下の基準で参加チームの順位付けが行われる。



ある２つのチームについて、正答した問題の得点の合計が大きい方が良い成績となる得点の合計が等しい場合は、その得点の合計に到達した時刻が早い方が良い成績となる
各チームの順位を「そのチームよりも良い成績であるチームの数」＋１とする

このコンテストでは、表彰式を盛り上げるために特殊なスコアボードを採用しており、以下の情報が開示される。


問題𝑖の得点は𝑆 である
問題𝑖に正答したチームの数は𝐾 である
問題𝑖を𝑗番目に正答したチームは𝑃 , である

あなたは、コンテスト終了時点でのスコアボードの情報から、各チームの最終結果について最も良い順位と最も悪い順位を推測することにした。

課題
問題の数、コンテストに参加したチームの数、各問題の得点、各問題を解いたチームとその順番の情報が与えられる。各チームについて、取りうる順位の最小値と最大値を求めるプログラムを作成せよ。ただし、各チームがいずれかの問題を正答した時刻は全て異なるものとする。

入力
入力は以下の形式で与えられる。
𝑁𝑀𝑆𝐾 𝑃, 𝑃, … 𝑃,
𝑆𝐾 𝑃, 𝑃, …𝑃,⋮𝑆𝐾 𝑃 , 𝑃 , …𝑃 ,１行目に問題の数𝑁(1 ≤ 𝑁 ≤ 200,000 = 2 × 10 )とチームの数𝑀 (1 ≤ 𝑀 ≤ 300)が与えられる。
続く2𝑁行に、各問題に関する情報がそれぞれ２行で与えられる。１行目に問題𝑖の得点𝑆 (1 ≤ 𝑆 ≤1,000,000,000 = 10 )が与えられる。２行目に、問題𝑖を正答したチームの数𝐾 (0 ≤ 𝐾 ≤ 𝑀)と、問題𝑖を𝑗番目に正答したチームの番号𝑃 , (1 ≤ 𝑃 , ≤ 𝑀)が与えられる。ただし、𝐾 + 𝐾 + ⋯ + 𝐾 ≤200,000 = 2 × 10 、かつ、𝑃 , ≠ 𝑃 , (𝑗 ≠ 𝑙)である。

出力
出力は𝑀行である。チーム𝑖の順位の最小値と最大値を空白区切りで𝑖行目に出力する。

入出力例
入力例１3 3100
1 22002 3 2300
2 1 3出力例１2 32 31 1

入力例２4 310101010

出力例２1 1
1 11 1

問題８ 条坊制都市（９点）

アイヅ京は、その領域が𝐻 × 𝑊個の区画からなる碁盤目状に区画された条坊制都市である。上から𝑖行目、左から𝑗列目の区画には番号(𝑖, 𝑗)がつけられており、各区画(𝑖, 𝑗)には高さ𝐴 , の建物が建っている。
みかど

アイヅ京の 帝 であるあなたは、都市改革の一環として領域の１行分のどこかと１列分のどこかの建物をすべて取り壊して大通りを作ろうとしている。そこで、住民を説得するために以下の要領で京の景観の良さを定義し、それらを基準に大通りの場所を決めることにした。


京の全領域𝑇から𝑟行目と𝑐列目を取り除き、残った領域を𝑇’とする。
𝑇’内のどの建物の高さとも異なる非負整数のうち最小の値を、𝑇’の景観の良さとする。

課題
京の領域の大きさと建物の高さが与えられる。大通りを作る場所の候補それぞれにおける景観の良さを求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝐻𝑊
𝐴 , 𝐴 , . .. 𝐴 ,𝐴 , 𝐴 , . .. 𝐴 ,⋮𝐴 , 𝐴 , . .. 𝐴 ,1 行目に、領域の縦方向の区画の数𝐻(2 ≤ 𝐻 ≤ 1,500)と横方向の区画の数𝑊(2 ≤ 𝑊 ≤ 1,500)が与えられる。続く𝐻行に、𝑖行目に並ぶ区画に建てられた建物の高さ𝐴 , (0 ≤ 𝐴 , ≤ 𝐻 × 𝑊 − 1)が与えられる。

時間制限
入力に対して、実行時間が２秒を超えてはならない。

出力領域の𝑟行目と𝑐列目を取り除いたときの景観の良さを𝑃 , としたとき、大通りを作る場所の候補それぞれにおける景観の良さを、以下の形式で出力する。
𝑃 , 𝑃 , . .. 𝑃 ,𝑃 , 𝑃 , . .. 𝑃 ,⋮𝑃 , 𝑃 , ... 𝑃 ,入出力例
入力例１2 20 11 2

出力例１0 00 1

入力例２3 30 1 2
1 0 22 4 2

出力例２1 0 30 1 3
3 3 2

問題９ 連環迷路（１０点）

PCK 君は連環迷路で遊んでいる。連環迷路は、座標平面上にある𝑁個の円から成り、1 つ以上の円の周は原点を通っている。この迷路では、原点をスタート地点として、円の周上だけをたどって移動する。もし、現在たどっている円𝐴と別の円𝐵が共有点を持てば、円𝐴の周上でその共有点まで移動することで円𝐵の周上に移ることができる。
連環迷路のゴール地点は、𝑁個の円の周上のうち、スタート地点からの周上に沿った最短の移動距離が最も大きい点である。たとえば、右図のように、中心が(0, 1)にあり半径が 1 である円𝐴と、中心が(0, 2)にあり半径が 1 である円𝐵があるとき、スタート地点は円𝐴の円周上にある。図に示す通り、円𝐴と円𝐵の交点は二つある。図中の★印以外で、円周上にあるどの点も、スタート地点からの最短の経路に沿った移動距離は★印よりも近いので、この場合のゴール地点は★印で示した点である。PCK 君は、スタート地点からゴール地点までの経路の最短距離を求めたい。

(0, 2)交点１交点２(0, 1)
スタート地点課題
𝑁個の円の情報が与えられたとき、スタート地点からゴール地点までの最短距離を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑥 𝑦 𝑟𝑥 𝑦 𝑟⋮
𝑥 𝑦 𝑟
１行目に円の数𝑁(1 ≤ 𝑁 ≤ 100)が与えられる。続くN行に、各円の中心の𝑥座標と𝑦座標𝑥 , 𝑦 (−10,000 ≤ 𝑥 , 𝑦 ≤ 10,000)と半径𝑟 (1 ≤ 𝑟 ≤ 10,000)が、整数で与えられる。ただし、中心の座標と半径が同じ円は与えられない(𝑖 ≠ 𝑗なら、𝑥 ≠ 𝑥 または𝑦 ≠ 𝑦 または𝑟 ≠ 𝑟 )。スタート地点がある円から、いくつかの円をたどることで、どの円の周上にも到達できる。また、円同士が共有点を持たない場合、それら２つの円の周上の最近接点同士は、0.0001以上離れているとする。

時間制限
入力に対して、実行時間が３秒を超えてはならない。

出力
最短距離を実数で１行に出力する。ただし、誤差がプラスマイナス 0.0001 を超えてはならない。この条件を満たせば小数点以下は何桁表示してもよい。

入出力例
入力例１21 0 1
3 0 1

出力例１6.28318531

入力例２41 0 1
3 0 12 2 14 2 2

出力例２10.35207318

入力例３20 1 10 2 1

出力例３4.1887902

問題１０ 投網（１０点）

イワシロ湖には魚が取れるポイントが𝑁箇所ある。湖の上に座標平面を取ると、これらのポイントはすべて格子点、つまり、𝑥座標と𝑦座標がどちらも整数である点である。各ポイントに魚が何匹いるか漁師たちは把握している。
漁師のケンジロウ君は、イワシロ湖に正方形の網を投げて魚を捕る。
網の一辺の長さは整数である。ケンジロウ君は、網の頂点が湖上の座標平面の格子点上に乗り、かつ、網の対角線の一本が直線𝑦 = 𝑥の上にO乗るように網を投げなければならない。たとえば、右の図の A のように網を投げることはできるが、B や C のように投げることはできない。

ABC

ケンジロウ君は、辺も含めて網に覆われたポイントにいるすべての魚を捕ることができ、捕れた魚の数に応じた売り上げが得られる。しかし、網を作るコストは網の周の長さだけかかるため、ケンジロウ君が得られる利益は、捕れた魚の数から網の周の長さ（網の一辺の長さの４倍）を引いた値になる。
ケンジロウ君は、網の大きさと網を投げる位置をうまく決めて、網を 1 回だけ投げたときの利益が最大になるようにしたい。

課題
魚がいるポイントの数と、各ポイントの位置とそこにいる魚の数が与えられたとき、網を 1 回だけ投げたときにケンジロウ君が得られる最大の利益を求めるプログラムを作成せよ。ただし、網の一辺の長さの最小値は 1 とする。

入力
入力は以下の形式で与えられる。
𝑁𝑥 𝑦 𝑓𝑥 𝑦 𝑓

⋮
𝑥 𝑦 𝑓

1 行目に魚がいるポイントの数𝑁(1 ≤ 𝑁 ≤ 200,000 = 2 × 105 )が与えられる。続く𝑁行に、魚がいる𝑖番目のポ イ ン ト の 𝑥 座 標 𝑥 と 𝑦 座 標 𝑦 (0 ≤ 𝑥 , 𝑦 ≤ 200,000 = 2 × 10 ) と そ こ に い る 魚 の 数 𝑓 (1 ≤ 𝑓 ≤1,000,000,000 = 10 )が与えられる。ただし、同じ座標をもつポイントは与えられない(𝑖 ≠ 𝑗について、𝑥 ≠ 𝑥 または𝑦 ≠ 𝑦 ）。

時間制限
入力に対して、実行時間が３秒を超えてはならない。

出力
ケンジロウ君が得られる最大の利益を１行に出力する。

入出力例
入力例１33 2 14 5 15 3 9

出力例１2

入力例２10 0 1

出力例２-3

問題１１ 串団子

（１０点）

様々な大きさの団子が𝑁個あり、𝑖番目の団子の大きさは𝑎 である。ここから𝐾個の団子を選ぶ。𝐾個の団子をあらゆる順番で串に刺して作ることができる、すべての串団子について考える。ただし、２つの串団子について、同じ位置にある団子の大きさがすべて同じ場合は同じものと考える。このようにして作ることができるすべての串団子について、一番大きな団子が存在する位置の和を求めて、それらの総和を求めよ。
たとえば、𝑁 = 4個の団子それぞれの大きさが、𝑎 = 6, 𝑎 = 6, 𝑎 = 7, 𝑎 = 7であり、𝐾 = 2とする。このとき、串団子として(6, 6)、(6, 7)、(7, 6)、(7, 7)の４種類を作ることができる。団子の大きさの最大値が存在する位置について考えると、串団子(6, 6)については一番大きな団子の大きさは 6 で、その団子がある位置は 1 番目と 2 番目なので、位置の和は1 + 2 = 3である。串団子(6, 7)については一番大きな団子の大きさは 7 で、その位置は 2 番目なので、位置の和は2である。串団子(7, 6)については一番大きな団子の大きさは 7 で、その位置は 1 番目なので、位置の和は1である。串団子(7, 7)については一番大きな団子の大きさは 7 で、その位置は 1 番目と 2 番目なので、位置の和は1 + 2 = 3である。よって、全ての串団子の一番大きな団子が存在する位置の和の総和は、3 + 2 + 1 + 3 = 9である。

課題
団子の情報と正の整数𝐾が与えられたとき、上述の一番大きな団子が存在する位置の和の総和を計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝐾𝑎 𝑎 ⋯𝑎
１行目に団子の数𝑁(1 ≤ 𝑁 ≤ 5000)と取り出す団子の数𝐾(1 ≤ 𝐾 ≤ 𝑁)が整数で与えられる。２行目に、各団子の大きさ𝑎 (1 ≤ 𝑎 ≤ 1,000,000,000 = 10 )が与えられる。

時間制限
入力に対して、実行時間が３秒を超えてはならない。

出力一番大きな団子が存在する位置の和の総和を 998,244,353 で割った余りを１行に出力する。

入出力例
入力例１4 26 6 7 7

出力例１9入力例２4 3
1 1 2 2

出力例２18

問題１２ 星座を探して（１３点）

ニッシンカン天文台では、イヅア地方で観測できる星座を分類することにした。それぞれの星座は、星座を構成する星を表す座標平面上の点の集合で表されている。これらの星座のうち、以下の３種類の操作を、それぞれ任意の回数組み合わせて行うことで一致させることができる星座は、同じ種類の星座と考えることにした。
平行移動

原点を中心とした回転
原点を中心として、正の係数を倍率とした拡大・縮小
ニッシンカン天文台の分類業務のために、あなたはそれぞれの星座について、同じ種類の星座がどのくらいあるのかをリストにまとめることにした。

課題
星座の情報が与えられたとき、各星座について同じ種類の星座がいくつあり、何番目の星座が同じ種類の星座かを求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑀
𝑐𝑜𝑛
𝑐𝑜𝑛
⋮𝑐𝑜𝑛
１行目に星座の数𝑁(1 ≤ 𝑁 ≤ 1,000)と各星座を構成する点の数𝑀(1 ≤ 𝑀 ≤ 1,000)が与えられる。続く𝑁行に、各星座の情報𝑐𝑜𝑛 が、以下の形式で与えられる。
𝑥 𝑦 𝑥 𝑦 ⋯𝑥 𝑦𝑥 , 𝑦 (−1,000 ≤ 𝑥 , 𝑦 ≤ 1,000)は、この星座を構成する𝑖番目の点の𝑥, 𝑦座標である。ただし、各星座について、同じ座標をもつ点は与えられない(𝑖 ≠ 𝑗について、𝑥 ≠ 𝑥 または𝑦 ≠ 𝑦 ）。

時間制限
入力に対して、実行時間が５秒を超えてはならない。

出力
出力は𝑁行である。星座𝑖について、同じ種類の星座の数と、同じ種類の星座の番号を𝑖行目に出力する。ただし、同じ種類の星座が複数ある場合、番号は昇順で出力する。

入出力例
入力例
4 30 0 1 1 0 1-1 1 -2 -2 2 20 0 0 -2 2 0-2 -2 2 -2 2 2

出力例
2 3 402 1 42 1 3

問題１３ 点の削除

（１３点）

イヅア大学は今年もプログラミングコンテストを開催する。問題作成チームの一員であるあなたは、座標平面上に十分に散らばった複数の点を配置した入力データを生成する必要がある。ところが、実際に生成してみると、点の集まりが十分に散らばらないことがあった。あなたは、生成した点の集まりが十分に散らばるように入力データを修正することにした。
点の集まりの中で最も距離が近い二点間の距離を、その点の集まりの散らばり方の尺度とする。あなたは、点の集まりからいくつかの点を削除することで、この尺度を最大にしたい。

課題
座標平面上の各点の座標と削除する点の数𝐾が与えられたとき、点を𝐾個削除したときの散らばり方の尺度の最大値の二乗を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝐾𝑥 𝑦𝑥 𝑦⋮
𝑥 𝑦
１行目に座標平面上の点の数𝑁(3 ≤ 𝑁 ≤ 1,000)と整数𝐾(0 ≤ 𝐾 ≤ 𝑁 − 2 かつ 𝐾 ≤ 30)が与えられる。続く𝑁行に、点の座標𝑥 , 𝑦 (0 ≤ 𝑥 , 𝑦 ≤ 10,000)が整数で与えられる。ただし、同じ座標をもつ点は与えられない(𝑖 ≠ 𝑗について、𝑥 ≠ 𝑥 または𝑦 ≠ 𝑦 ）。

時間制限
入力に対して、実行時間が１０秒を超えてはならない。

出力散らばり方の尺度の最大値の二乗を整数で 1 行に出力する。

入出力例
入力例
5 20 02 24 14 27 0

出力例13