6064 카잉 달력

https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

카잉 달력 성공

한국어   

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

31171

6645

5044

22.832%

문제

최근에 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>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력

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

예제 입력 1 복사

3 10 12 3 9 10 12 7 2 13 11 5 6

예제 출력 1 복사

33 -1 83

출처

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2013 B번

• 문제의 오타를 찾은 사람: 2e718 apjw6112 roeniss
• 데이터를 만든 사람: baekjoon

 

<개인 풀이>

1. 문제 조건의 N , M 의 범위는 (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N)

 일반적으로 숫자 1개씩 카운팅할 수 있는 방법이 있지만, 이 문제에서는

O(N*M)의 최대는 16억으로 보통 1억을 1초로 계산했을때 1초를 넘게 되므로 시간초과가 됨.

 

2. 풀이 방법의 예

 N : 10 ,M : 12 ,  x=3 , y=9 

 

나머지 (mod) 연산을 통해 N과 M으로 나눈 나머지가 0인 값들을 적용시키기 위해 
x 에 1을 빼주고, y에 1을 빼준값을 찾는다.

 

찾고자 하는 답,

x=2, y=8

 

x의 인덱스는 해당 인덱스에서 N(10)만큼 주기로

y의 인덱스는 y값의 인덱스에서 다음 인덱스까지 M(12) 만큼 주기로

바뀌는것을 볼 수 있다.

0, <0,0>     21  <1,9>

1, <1,1>     22  <2,10>    

2, <2,2>    23  <3,11>

3, <3,3>     24  <4,0>

4, <4,4>     25  <5,1>

5, <5,5>     26  <6,2>

6, <6,6>     27  <7,3>

7, <7,7>     28  <8,4>

8, <8,8>     29  <9,5>

9, <9,9>     30  <0,6>

10, <0,10>  31  <1,7>

11 <1,11>   32 <2,8> <정답

12 <2,0>    33 <3,9>

13 <3,1>    34  <4,10>

14 <4,2>     35 <5,11>

15 <5,3>     36 <6,0>

16 <6,4>     37 <7,1>

17 <7,5>     38 <8,2>

18 <8,6>     39 <9,3>

19 <9,7>     40 <0,4>

20 <0,8>     41 <1,5>

 

#include<iostream>

using namespace std;
int main(void)
{
	int T; // test case 수 ;
	int M, N, x, y;

	cin >> T;
	bool isfind = false;
	bool isfind_x[2] = { false, false };
	while (T--)
	{
		cin >> M >> N >> x >> y;

		int tx = x, ty = y;

		tx = tx - 1, ty = ty - 1; // <3,9> -> <2,8>

		int a = 0,b = 0;
		for (long long i = 0; i <= M * N; ++i)
		{
			a = i % M;
			b = i % N;

			if (a == tx && b == ty)
			{
				cout << i + 1 << '\n';
				isfind = true;
				break;
			}
			else isfind = false;

			if (M > N)
			{
				if (a == tx)
					isfind_x[0] = true;
			}
			else
			{
				if (b == ty)
					isfind_x[1] = true;
			}

			if (isfind_x[0])
			{
				i = i + M - 1;
			}
			if (isfind_x[1])
			{
				i = i + N - 1;
			}
			
		}

		if (!isfind) 
			cout << -1 << '\n';

		isfind = false;
		isfind_x[0] = false;
		isfind_x[1] = false;
	}

	return 0;
}