結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー LyricalMaestro
提出日時 2024-02-25 22:03:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 40 ms / 1,000 ms
コード長 2,071 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 53,588 KB
スコア 1,221,702
最終ジャッジ日時 2024-02-25 22:03:24
合計ジャッジ時間 3,041 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import sys

ALPHA = 5

class Result:
    def __init__(self, stations, travel_seq):
        self.stations = []
        for x, y in stations:
            self.stations.append(f"{x} {y}")
        self.travel_seq = []
        for t, r in travel_seq:
            self.travel_seq.append(f"{t} {r}")


def solve(N, M, planets):
    # stationの情報の格納
    stations = []
    for i in range(M):
        stations.append(planets[i])

    # 旅行の順番の格納
    travel_seq = []
    for i in range(N):
        travel_seq.append((1, i + 1))
    travel_seq.append((1, 1))

    # スコア計算
    S = 0
    for i in range(len(travel_seq) - 1):
        t1, r1 = travel_seq[i]
        t2, r2 = travel_seq[i + 1]
        if t1 == 2 and t2 == 2:
            x1, y1 = stations[r1 - 1]
            x2, y2 = stations[r2 - 1]
            S += ((x1 - x2) ** 2 + (y1 - y2) ** 2)
        elif t1 == 2 and t2 == 1:
            x1, y1 = stations[r1 - 1]
            x2, y2 = planets[r2 - 1]
            S += ALPHA * ((x1 - x2) ** 2 + (y1 - y2) ** 2)
        elif t1 == 1 and t2 == 2:
            x1, y1 = planets[r1 - 1]
            x2, y2 = stations[r2 - 1]
            S += ALPHA * ((x1 - x2) ** 2 + (y1 - y2) ** 2)
        else:
            # t1 == 1 and t2 == 1
            alpha2 = ALPHA ** 2
            x1, y1 = planets[r1 - 1]
            x2, y2 = planets[r2 - 1]
            S += alpha2 * ((x1 - x2) ** 2 + (y1 - y2) ** 2)
    print(f"S = {S}", file=sys.stderr, flush=True)

    score = (10 ** 9) / (1000 + math.sqrt(S))
    score = int(score)
    print(f"score = {score}", file=sys.stderr, flush=True)

    return Result(stations, travel_seq)

def main():
    N, M = map(int, input().split())
    planets = []
    for _ in range(N):
        a, b = map(int, input().split())
        planets.append((a, b))
    
    result = solve(N, M, planets)

    for i in range(M):    
        print(result.stations[i])
    print(len(result.travel_seq))
    for i in range(len(result.travel_seq)):
        print(result.travel_seq[i])


if __name__ == "__main__":
    main()
0