結果

問題 No.1803 Remainder of Sum
ユーザー 👑 SPD_9X2
提出日時 2022-01-08 15:59:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 95 ms / 2,000 ms
コード長 1,508 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,156 KB
実行使用メモリ 83,720 KB
最終ジャッジ日時 2024-11-14 09:27:20
合計ジャッジ時間 2,151 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

"""
https://yukicoder.me/problems/no/1803
お互い消す数字間に辺を貼る
すると、サイクルがあってはいけない。
また、全体は連結である必要がある。
よって、木になる！！
mod Mで最小全域木を求めればよい。
1～Nなので…
M <= N
の場合、
全て、以下のようにペアになる。
1,M-1
2,M-2
...
...
M-1,1
連結成分の個数は,
M=1 -> 0
M=2 -> 0,1
M=3 -> 0,1
M=4 -> 0,1,2
M=5 -> 0,1,2
なので、 M//2 + 1
あとは、連結成分をコスト1で減らせるのでやって終わり
そうでない場合…？
コスト1では連結できない
1234
8765
の場合 2-8 3-7 4-6 でコスト1を達成できる
12345
  76
1-2 -> 3
1-3 -> 4
7-4 -> 1
6-5 -> 1
  
みたいな場合も、5-6で行けるので無問題
 
123456
   987
これは、13がmodの場合
1,2,3に関してはどう頑張っても 13を超えられない
なので、
1-2
1-3
1-4 が一番安い
1234
  5
5-4 -> 1
1-3 -> 4
1-2 -> 3
"""
import sys
from sys import stdin
TT = int(stdin.readline())
ANS = []
for loop in range(TT):
    N,M = map(int,stdin.readline().split())
    if M <= N:
        parts = (M//2) + 1
        ans = parts-1
    else:
        A = M - N
        if A < N:
            #1-2,1-3, ... , 1-A をリンク
            ans = 1*(A-1) + (2+A)*(A-1)//2
            B = (N-(A-1)+1)//2
            ans += B-1
        else:
            ans = 1*(N-1) + (2+N)*(N-1)//2
    ANS.append(ans)
print ("\n".join(map(str,ANS)))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0