結果

問題 No.2368 I love a square root of 2
ユーザー navel_tos
提出日時 2024-02-17 16:52:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 774 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 82,536 KB
実行使用メモリ 281,576 KB
最終ジャッジ日時 2024-09-28 23:49:34
合計ジャッジ時間 4,018 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder 2368 I love a square root of 2

from collections import deque

#入力受取
N = int(input())

#比較関数を定義  (x, y) = x + y√2 として、前者のほうが小さいか判定する
def compare(P1, P2):
    x1, y1 = P1
    x2, y2 = P2
    return (x1 - x2) ** 2 <= 2 * (y1 - y2) ** 2

#2つの筒を用意  Q[0]は長さ1, Q[1]は長さ√2
Q = [deque([(1, 0)]), deque([(0, 1)])]

#1個目の処理を終えた状態から始める
x = y = 0
for _ in range(N - 1):
    i = 0 if compare(Q[0][0], Q[1][0]) else 1
    #Q[i]の先頭要素を取り出す
    x,y = Q[i].popleft()

    #次の値に遷移  y == 0の時に限り長さ1の筒に入れる
    if y == 0:
        Q[0].append((x + 1, y))
    Q[1].append((x, y + 1))

#答えを出力
print(x,y)
0