군 복무
시간 제한2초메모리 제한512 MB
각 병사는 최대 K개월 연속 근무 후 한 달 휴식을 취할 때, 매달 보장할 수 있는 근무 병사 수의 최댓값을 구한다.
문제
국경 수비대에서 군 복무를 막 시작했다. 컴퓨터공학을 전공했기 때문에 병사들의 근무 일정을 구현해 달라는 요청을 받았다. 처음에는 아무 병사도 근무하지 않으며, 일정은 다음 두 조건을 만족해야 한다.
- 병사는 N명이고, 각 병사는 최대 K개월 연속으로 근무할 수 있으며 그 뒤에는 한 달간 휴가를 받아야 한다.
- 어느 시점에든 근무 중인 병사 수의 보장된 최솟값이 최대가 되도록 일정을 짜야 한다.
N과 K가 주어지면, 어느 시점에든 근무 중인 병사 수의 보장된 최댓값을 계산한다.
입력
프로그램은 하나 이상의 테스트 케이스에 대해 채점된다. 입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 100)
각 테스트 케이스는 공백으로 구분된 정수 2개가 있는 한 줄로 이루어진다.
- N: 병사의 수 (0 ≤ N ≤ 10, 000, 000)
- K: 병사가 한 달간 휴가를 받기 전까지 연속으로 근무할 수 있는 개월 수 (0 ≤ K ≤ 10, 000, 000)
출력
각 테스트 케이스마다 어느 시점에든 근무 중인 병사 수의 보장된 최댓값을 한 줄에 출력한다.