CodeDrive

문제:

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세우졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x,y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x<M이면 x'=x+1이고, 그렇지 않으면 x'=1이다. 같은 방식으로 만일 y<N이면 y'=y+1이고, 그렇지 않으면 y'=1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M=10 이고 N=12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M,N,x와 y가 주어질 때 <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

입력:

출력:

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

풀이 방법:

최소공배수를 사용해서 푸는 방법도 있다고 하지만 규칙을 찾아서 풀어보려고 했다. 10 12의 케이스에 대해서 순서대로 해를 나열해보고 재배열 해보니 다음과 같이 표를 얻을 수 있었다.

지금은 x좌표를 고정으로 잡고 재배열을 한 경우이다. 테스트 케이스 중 3,9를 찾아야 하는 경우라면 3을 고정시키고 y좌표만 변경시키며 3,9가 존재하는지 찾아보면 된다. y좌표도 변하는 규칙을 찾을 수가 있는데 지금은 10,12인 경우이므로 한 줄이 넘어갈 때마다 (n-m)=-2씩 더해주면 된다. 그러면 3,9는 위 표에서 3,11 밑 행에 있음을 알 수 있다. 또한 이렇게 규칙적으로 y좌표가 변하기 때문에 while문을 사용해 y좌표를 바뀌어주다가 다시 원래의 수가 돌아온다면 존재하지 않는 케이스임을 알 수 있으므로 -1을 반환하면 된다.

다음은 위의 규칙에 따라 구하는 코드이다.