50009. Snake Order

I'm a slow walker, but I never walk backwards.

Problem description

We define a snake-order of a matrix as follows. We first traverse the first row from left to right, then the second row from right to left, and so on. For example, if a matrix has $R = 3$ rows and $C = 2$ columns, then we will traverse (0, 0), (0, 1), (1, 1), (1, 0), (2, 0), and (2, 1). If we place $r \times C + c$ into the elment in the r-th row and c-th column, we will have 0, 1, 3, 2, 4, 5. For ease of indentification we assume that this traversal always ends in 0, so we will see 0, 1, 3, 2, 4, 5, 0.

+---+---+   +---+---+
| 0 | 1 |   | > | V |
+-------+   +-------+
| 2 | 3 |   | V | < |
+-------+   +-------+
| 4 | 5 |   | > | > |
+---+---+   +---+---+

Now suppose we look into the memory and see 0, 1, 3, 2, 4, 5, and 0, we want to determine the number of rows and columns of the original matrix. We assume that the number columns is at least 2 in all subtasks.

If the data are all correct please compute the number of rows and columns, and return 1. However, the data could be incorrect. In thast case output the row and column indices of the first incorrect data, and return 0.

The prototype of the function you need to implement is as follows.

1
int snake(int *ptr, int *row, int *column);

Subtask

In all subtask the second 0 you see always means the end of data.

  • 20pt. The matrix has only one row, and the input is always correct.
  • 50pt. The matrix has multiple rows, and the input is always correct.
  • 30pt. The matrix has multiple rows, and the input may be incorrect. However, we assume that the first c + 1 data are always correct. That is, the first row of the data, plus the data in the last column of the second row, are always correct.

Main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#include "snake.h"
int main(void)
{
    int trav[1024] = {0}, row = 0, column = 0, res = 0;
    scanf("%d %d", &trav[0], &trav[1]);
    for(int i = 1; trav[i]; i++)
      scanf("%d", &trav[i + 1]);
    res = snake(trav, &row, &column);
    if(res) printf("%d %d\n", row, column);
    else printf("err %d %d\n", row, column);
    return 0;
}

snake.h

1
int snake(int *ptr, int *row, int *column);

snake.c

1
2
3
4
5
#include "snake.h"
 
int snake(int *ptr, int *row, int *column) {
    // add your code
}

Sample Input 1

0 1 2 3 4 0

Sample Output 1

1 5

Sample Input 2

0 1 2 5 4 3 6 7 8 0

Sample Output 2

3 3

Sample Input 3

0 1 2 5 4 9 6 7 8 0

Sample Output 3

err 1 0

Discussion