Codeforces Round #741 (Div. 2)-A. The Miracle and the Sleeper

문제 설명

두 정수 $l$, $r$이 주어진다.$(l\le r)$ $r\ge a\ge b\ge l$ 을 만족하는 $(a,b)$쌍 중에서 $amodb$의 값이 최대가 되는 쌍을 찾아라.

Input
첫번째 줄에는 테스트 케이스의 수 $t(1\le t\le {10}^4)$이 주어진다.

각 테스트 케이스는 두 정수 $l,r(1\le l\le r\le {10}^9)$ 가 주어진다.

Output
각 테스트케이스마다 문제에 맞는 답을 출력한다.

Example
input
4
1 1
999999999 1000000000
8 26
1 999999999

output
0
1
12
499999999

문제 접근

사용한 알고리즘: 구현, 수학, 정수론
걸린 시간 : 00:04
A번 답게 조금만 생각하면 풀 수 있는 문제지만 이 문제에 놀라운 정수론이 숨어 있었고, 그 사실을 editorial을 보면서 알게됐다. 이게 업솔빙의 중요성이라는 사실을 다시금 깨닫게 한다.

$a;mod;b$는 이 식을 반드시 만족한다. $a;mod;b\le [\frac{n-1}{2}]$ 그리고 이 최대값을 만족하는 $b$값은 $b=[\frac{n}{2}]+1$ 이다.

따라서 $l$이 $b$보다 작거나 같으면 $b$를 $[\frac{n}{2}]+1$로 선택할 수 있기 때문에 최대값은 $[\frac{n-1}{2}]$이다.

만약 $l$이 $b$보다 크다면 최대값을 만족하는 $b$값을 선택할 수 없다. 그러면 $a;mod;b$는 $a-b$를 항상 만족한다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    int t; cin >> t;
    while(t--){
        int l, r; cin >> l >> r;
        cout << (r / 2 + 1 < l ? r - l : (r - 1) / 2) << "\n";
    } 
    return 0;
}