점진적으로 주문받는 팬케이크 집
시간 제한20초메모리 제한1024 MB
두 더미에서 i번째 손님이 i개를 큰 더미에서 가져갈 때, 몇 명이 주문을 받는지와 남은 팬케이크 수를 구합니다.
문제
매일 아침 점진적으로 주문받는 팬케이크 집의 주방 직원은 그날 쓸 팬케이크를 모두 만들어 두 개의 더미로 나눕니다. 처음에 왼쪽 더미에는 L개, 오른쪽 더미에는 R개가 있습니다.
이 식당의 손님들은 매우 일정하게 주문합니다. 도착한 i번째 손님(1부터 셈)은 항상 i개를 주문합니다. i번째 손님이 i개를 주문하면, 남은 팬케이크가 가장 많은 더미에서 i개를 가져옵니다(두 더미의 개수가 같으면 왼쪽 더미에서 가져옵니다). 두 더미 모두 i개 이상이 없으면 식당 문을 닫고, i번째 손님은 아무것도 받지 못합니다. 한 주문을 두 더미의 팬케이크로 채우는 일은 없습니다.
각 더미의 초기 개수가 주어졌을 때, 몇 명의 손님이 주문을 받는지, 그리고 식당이 문을 닫을 때 각 더미에 몇 개가 남는지 구해야 합니다.
입력
첫 줄에 테스트 케이스의 개수 T가 주어집니다. 이어서 T개의 테스트 케이스가 주어집니다. 각 테스트 케이스는 한 줄로 이루어지며, 위에서 설명한 왼쪽 더미와 오른쪽 더미의 초기 개수 L과 R이 차례로 주어집니다.
출력
각 테스트 케이스마다 Case #x: n l r 형식으로 한 줄을 출력합니다. 여기서 x는 테스트 케이스 번호(1부터 시작), n은 주문을 받은 손님 수, l과 r은 식당이 문을 닫을 때 왼쪽 더미와 오른쪽 더미에 남은 팬케이크 개수입니다.
제한
- 1 ≤ T ≤ 1000.
힌트
예제 1에서 1번째 손님은 오른쪽 더미에서 1개를 받아 각 더미에 1개씩 남습니다. 2번째 손님은 2개를 원하지만, 두 더미에 전체 합으로는 2개가 있어도 어느 더미에도 2개가 없습니다.
예제 2에서 두 더미의 개수가 같으므로 1번째 손님은 왼쪽 더미에서 1개를 받습니다. 왼쪽 더미에 1개, 오른쪽 더미에 2개가 남습니다. 2번째 손님은 2개를 원하며, 오른쪽 더미에서 2개를 내어 오른쪽 더미를 비웁니다. 3번째 손님이 도착했을 때 어느 더미에도 3개가 없으므로 더 이상 주문을 처리하지 않습니다.
예제 3에서 1번째 손님은 오른쪽 더미에서 받아 왼쪽에 8개, 오른쪽에 10개가 남습니다. 2번째 손님도 오른쪽 더미에서 받아 두 더미에 8개씩 남습니다. 3번째 손님은 왼쪽 더미에서 받아 왼쪽에 5개, 오른쪽에 8개가 남습니다. 4번째 손님은 오른쪽 더미에서 받아 오른쪽에 4개가 남습니다. 5번째 손님에게 주문을 내어 주면 왼쪽 더미가 비고, 두 더미 어디에도 6번째 손님에게 줄 만큼의 팬케이크가 남지 않습니다.