特許の出願を行いました。

18-1. 第1回ビネクラ杯(問題編)

ストーリー

ビネクラ社はお金がないので、無人島に本社ビルを建てました。

無人島には電気が来ていませんので、発電機の力でいろいろな装置を動かさなければなりません。当初は「1つの大きな発電機にいろいろな装置をつないで動かそう」という構想がありましたが、ベンダーに包括的なシステム開発の見積りをとったところ、とんでもない金額になり驚いてしまいました。

そこで、ひとつひとつのシステム開発を、安価なフリーランスエンジニアたちに委託しようと考えました。こうすると、「装置Aには発電機A」「装置Bには発電機B」というように専用設計にはなってしまいますが、全体としてコストを抑えることができます。

ところで、ビネクラ本社ビルの内部は、工賃をケチったために、(たて×よこ×高さ)が(20×20×20)のグリッド状に小部屋が並んだ構造になっています。全8000個の小部屋には、発電機、装置、ケーブルのいずれか1つを置くことができます。1つの小部屋に発電機と装置の両方を置くことはできませんし、ケーブルが通る部屋に発電機や装置を置くこともできません。

ビネクラ社は早速8000人のフリーランスを集めて、発電機(No.1~No.4000)の設置と、装置(No.1~No.4000)の設置の見積りをとりました。集まった8000枚の見積書によれば、すべての発電機と装置はまったくバラバラな場所に設置されることになるようです。

新入社員「え、なんで対応する発電機と装置を隣同士にしなかったんですか。ケーブルを通す部屋もありますし、さすがに4000システム全部は稼働できないんじゃないでしょうか。」

社長「新米のくせに生意気だな!いまある見積りの中で、うまくケーブルを通してできるだけ多くのシステムを稼働させろ!」

新入社員「ひえ~」

問題

発電機と装置の座標がそれぞれ4000個与えられます。対応する発電機と装置をできるだけ多くケーブルでつないでください。どのシステムを、どのような経路でつなげばよいでしょうか?

発電機と装置の座標

2つのテキストファイルをダウンロードして用いてください。

「generators.txt」は、発電機の(x, y, z)座標がスペース区切りで並んだ4000行のファイルです。

7 13 9
4 3 15
15 19 5
...
12 8 2
10 2 15
15 10 12

「equipments.txt」は装置の(x, y, z)座標がスペース区切りで並んだ4000行のファイルです。

17 18 2
5 4 14
16 19 16
...
4 2 13
6 10 7
6 16 12

発電機と装置は上から順にNo.1~No.4000ですので、対応する物同士でしかつなぐことができません。各座標は、0≦x≦19、0≦y≦19、0≦z≦19 を満たします。

期待される解答

次のフォーマットにしたがって、接続順を記入したテキストファイル(あなたのニックネーム.txt)を提出してください。

n
k_1
1番目のシステムのケーブル接続順(k_1行)
k_2
2番目のシステムのケーブル接続順(k_2行)
...
k_n
n番目のシステムのケーブル接続順(k_n行)

n : つないだシステムの数
k : あるシステムをつなぐための座標数(発電機と装置の座標を含む)

ただし、各接続順は発電機の座標から始まり、装置の座標で終わるようにしてください。システムNo.順に並べる必要はありません。ケーブル同士がぶつかったり、1つの座標(小部屋)にケーブルと発電機/装置が混在してしまうような解答はエラーとなります。

ケーブルは軸に平行な向きにしか伸ばすことができません(斜めは禁止)。また、長く直線的な接続であっても、途中の座標を省略して解答することはできません。

解答例1

システムNo.2は、発電機(4, 3, 15)と装置(5, 4, 14)がとても近いので、簡単につなぐことができます。

1
4
4 3 15
4 3 14
4 4 14
5 4 14

ケーブルの経路を表示すると次のようになります。

解答例2

システムNo.1~3の発電機と装置をつないだ例です。

3
23
7 13 9
7 13 8
7 13 7
7 13 6
7 13 5
7 13 4
7 13 3
7 13 2
7 14 2
7 15 2
7 16 2
7 17 2
7 18 2
8 18 2
9 18 2
10 18 2
11 18 2
12 18 2
13 18 2
14 18 2
15 18 2
16 18 2
17 18 2
4
4 3 15
4 3 14
4 4 14
5 4 14
13
15 19 5
15 19 6
15 19 7
15 19 8
15 19 9
15 19 10
15 19 11
15 19 12
15 19 13
15 19 14
15 19 15
15 19 16
16 19 16

ケーブルの経路を表示すると次のようになります。(No.1=青、No.2=水、No.3=橙)

達成目標

レベル目標
初学者1システム以上
有識者4システム以上
黒帯18システム以上
政府筋33システム以上
事務次官49システム以上
瑞宝重光章73システム以上
元帥106システム以上
総書記151システム以上
ドラゴン311システム以上
485システム以上

提出

2019年8月31日23時59分までに、次のフォームから提出を行ってください。ファイル名は「あなたのニックネーム.txt」としてください。複数回の提出があった場合は最大スコアのものが採用されます。

※100KBまでの.txtファイルのみ受け付けます

ランキングと賞品

提出してくださった方全員のニックネームとスコアを、次のページに随時ランキング形式で掲示いたします。提出の早さは考慮しませんので、焦る必要はありません。

また、ビネクラ社はお金がありませんので、賞品はありません。お金持ちの方からの賞品の提供を歓迎しております

タイトルとURLをコピーしました