結果

問題 No.1803 Remainder of Sum
ユーザー 👑 SPD_9X2SPD_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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,196 KB
testcase_01 AC 92 ms
82,060 KB
testcase_02 AC 93 ms
82,208 KB
testcase_03 AC 94 ms
82,348 KB
testcase_04 AC 94 ms
82,100 KB
testcase_05 AC 95 ms
82,232 KB
testcase_06 AC 94 ms
83,720 KB
testcase_07 AC 86 ms
81,328 KB
testcase_08 AC 84 ms
79,768 KB
権限があれば一括ダウンロードができます

ソースコード

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)))
0