Asia Hong Kong Regional Contest 2016


2016-11-06 02:00 UTC

Asia Hong Kong Regional Contest 2016


2016-11-06 07:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -767 days 6:04:54

Time elapsed


Time remaining


Problem I
Special Tour

Given an grid with $N$ rows and $M$ columns, your task is to find a tour such that:
  1. The tour has length at least two

  2. All squares in the grid are visited exactly once

  3. Let $a_1, \dots , a_{NM}$ be the sequence of visited squares. Then $d(a_ k$, $a_{k+1}) = 2$ or $3$ for every $1 \leq k < NM$. Also, $d(a_{NM}, a_1) = 2$ or $3$.

    Here, $d(p, q)$ denotes the Manhattan distance between $p$ and $q$. More precisely, if $p$ is the square on row $r_ p$ and column $c_ p$ and $q$ is the square on row $r_ q$ and column $c_ q$, then we write $p = (r_ p, c_ p), q = (r_ q, c_ q)$ and $d(p, q) = |r_ p - r_ q| + |c_ p - c_ q|$.


The first and only line of input consists of two integers $N$ and $M$ ($1 \leq N, M \leq 200$).


If there is no such tour, output -1. Otherwise, output $N \times M$ lines. The $i$th line contains two space-separated integers, denoting the row and column numbers of $a_ i$. If there is more than one such tour, any one will be accepted.

Sample Input 1 Sample Output 1
2 3
1 1
2 2
1 3
2 1
1 2
2 3
Sample Input 2 Sample Output 2
1 1