시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 192 | 54 | 44 | 33.083% |
2011년 행정안전부에서는 도로명에 일련번호를 붙인 도로명 주소(새 주소) 제도를 시행하였다. 그로부터 수십년이 지났고, 한강의 물줄기를 따라서 물 위에 집을 짓는 것이 유행하였다. 이 새로운 유행에서는 다음과 같이 일렬로 집들이 만들어졌다. (주소 번호만 표시)
북쪽 강변
---------------------------------------------------------------
(하류) 2 3 4 5 6 7 8 9 10 11 12 13 ... N (상류)
---------------------------------------------------------------
남쪽 강변
주소는 2번지부터 매겨지고, 한강변을 거슬러 올라가면서 다음 집들에 3, 4, 5... 번지로 주소가 매겨진다.
이 집들에 사는 사람들끼리 공유하는 특이한 풍습이 하나 있었는데, 한 집의 주소 번호가 다른 집의 주소 번호의 배수가 되는 경우, 두 집은 서로 '형제 관계' 라고 불렀고, 번호가 큰 쪽이 '형', 작은 쪽이 '남동생' 이 되었다. 예를 들어서 6번 집은 2, 3번 집에게 '형'이 되고, 2, 3번 집은 6번 집에게 '남동생' 이 된다. 또한 남동생 중 번호가 가장 작은 집이 ‘막내' 가 되어, 이 경우 2번 집은 6번 집의 ‘막내' 가 된다.
'남동생'의 수가 같은 집들끼리는 또한 친목 관계가 있었는데, 이것을 '자매 관계' 라 불렀다. 예를 들어서 6번 집은 2, 3번 집의 두 '남동생' 이 있고, 8번 집은 2, 4번 집의 두 '남동생' 이 있으므로, 두 집은 '자매' 관계가 된다. 이때 번호가 큰 8번 집을 '언니', 번호가 작은 6번 집을 '여동생' 이라고 불렀다.
N번 집에는 오랜 과거에 새주소 시스템을 인터넷 지도 서비스에 적용시킨 노 프로그래머가 살고 있었다. 그는 자신의 집의 '여동생' 인 집들에게 그 동안의 '자매' 관계에 대한 감사의 뜻으로 선물 상자를 보내기로 했다. 특히 그 선물 상자를 받는 집이 '남동생' 관계의 집들을 가지고 있고 그 중 '막내'의 집 번호가 M 이상일 경우에는, 어떤 특별한 선물을 선물 상자에 하나 넣어서 보내기로 하였다.
이 프로그래머는 특별한 선물을 총 몇 개 준비해야 할까?
입력의 첫 줄에는 테스트 케이스의 숫자 T가 주어진다. 아래로 T 줄의 입력이 주어지며 각 줄은 하나의 테스트 케이스에 대한 입력이다. 각 테스트 케이스는 아래와 같이 2개의 자연수로 주어진다.
N M
여기서 N은 장난감의 수를 계산해야 할 집의 주소 번호이고, M은 막내 주소의 최소 제한이다.
각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 각 케이스에 대해서 준비해야 하는 특별한 선물의 개수이다.
4 3 2 8 2 35 2 35 3
Case #1: 0 Case #2: 1 Case #3: 11 Case #4: 4
Contest > Google > Google's Coding Competitions > Google Code Jam Korea 2012 > Code Jam Korea 2012 본선 라운드 D1번