시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 310 147 129 51.190%

문제

모래두지는 어디를 가나 $R \times C$장의 카드를 들고 다닌다. 이 카드들에는, 같은 무늬가 그려진 카드가 정확히 두 장 씩 있다.  카드를 들고 다니는 이유는, 혼자 있을 때 짝 맞추기 게임을 하기 위해서이다. 게임은 다음과 같은 방법으로 진행된다.

  1. 처음에 카드를 잘 섞은 후 가로 $R$행, 세로 $C$열로 카드들을 무늬가 보이지 않게 뒷면으로 잘 배치한다.
  2. 다음의 행동을 카드가 모두 없어질 때 까지 반복한다.
    1. 카드를 한 장 정해 뒤집어서 무늬를 본다.
    2. 나머지 카드를 한 장 정해 뒤집어서 무늬를 본다.
    3. 두 카드에 그려진 무늬가 같으면, 카드를 두 장 모두 게임에서 제외시킨다. 아니면, 다시 원래대로 뒷면으로 뒤집어 놓는다.
  3. 게임에서 승리한다!

모래두지는, 행동을 될 수 있는 한 적게 사용해서 게임에서 승리하려고 한다. 그는 행동의 수를 줄이기 위해 최적의 전략을 쓸 것이다. 이때, 게임에서 승리하기 위한 최소의 행동 횟수와, 최대의 행동 횟수를 구하여라. 

입력

첫째 줄에 정수 $R, C$가 공백으로 구분되어 들어온다. ($1 \le R, C \le 10$, $R \times C$ 는 2의 배수.)

출력

게임에서 승리하기 위한 최소의 행동 횟수와, 최대의 행동 횟수를 공백으로 구분하여 출력하여라.

예제 입력 1

1 2

예제 출력 1

1 1

예제 입력 2

2 2

예제 출력 2

2 3

힌트

두 번째 게임에는, 총 4장의 카드가 있다. 처음 행동 때, 같은 무늬가 나왔으면, 카드를 두 장 모두 게임에서 제외하고, 나머지 카드를 뒤집어 게임에서 제외시키면 된다. 처음 행동 때, 다른 무늬가 나왔으면, 두 번째 행동때는, 첫 번째 행동때 뒤집지 않은 카드의 무늬를 확인하여, 첫 번째 행동때 뒤집어서 확인한 카드중 같은 무늬의 카드도 뒤집어, 제외시키고, 나머지 카드 두개를 제외시키면 된다. 그러므로 최소의 행동은 2번, 최대의 행동은 3번이 든다.