Valera and Tubes · Interview Problem

Back to problems

Codeforces

Medium

Arrays

Matrices

Simulation

Valera and Tubes

Construct a traversal of a grid by splitting its cells into a fixed number of non-empty contiguous groups.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Codeforces 441C

gfg

Problem Statement

Problem

You are given an $n \times m$ grid of cells. Your task is to output a traversal of all cells such that the cells are divided into exactly $k$ consecutive groups in the order they are visited.

Each group must contain at least one cell, and the groups should be as balanced as possible except that the last group may contain the remaining cells. The goal is to produce any valid traversal that visits every cell exactly once and respects the group boundaries.

A common way to think about the problem is to walk through the grid in a snake-like order and then split the visited sequence into chunks.

Input Format

Input

A single line contains three integers $n$ , $m$ , and $k$ .

Interpretation

$n$ is the number of rows.
$m$ is the number of columns.
$k$ is the number of groups to form while traversing the grid.

Output Format

Output

Print a valid traversal of the $n \times m$ grid split into $k$ consecutive groups.

The exact formatting depends on the chosen representation, but the output should describe each group and the cells it contains in visitation order.

Constraints

$1 \le n, m$
$1 \le k \le n \cdot m$
Every cell must be visited exactly once
Every group must be non-empty

Examples

Sample cases returned by the problem API.

Example 1

Input

2 3 4

Output

Group 1: (1,1) (1,2)
Group 2: (1,3)
Group 3: (2,3)
Group 4: (2,2) (2,1)

Explanation

One valid snake-like traversal of the 2x3 grid is split into 4 consecutive non-empty groups.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress