結果

問題 No.1803 Remainder of Sum
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2022-01-08 15:54:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,468 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 83,584 KB
最終ジャッジ日時 2024-11-14 09:27:18
合計ジャッジ時間 1,828 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
53,096 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 86 ms
81,448 KB
testcase_08 WA -
権限があれば一括ダウンロードができます

ソースコード

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 が一番安い


"""

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))//2
            ans += B-1
        else:
            ans = 1*(N-1) + (2+N)*(N-1)//2

    ANS.append(ans)

print ("\n".join(map(str,ANS)))
0