Hexagonal Pasture Network

Interview

Time limit1sMemory limit128 MB

Summary

Given a hexagon-shaped grid of pastures, count and list all pastures at exact distance L from start H using BFS.

Level: Medium5 of 10
Topics: Graph, BFS, Implementation
Solved: No attempts yet

Problem

Farmer John recently acquired some new land to expand his farm. His cows have taken a liking to the hexagonal structure of bee honeycombs, so Farmer John has laid out a new system of pastures and cowpaths in that shape.

The whole plot of pastures and cowpaths forms a hexagon with side length $K$ ( $2 \le K \le 50$ ). The pastures are numbered $1 \ldots 3K(K-1)+1$ .

Think of the hexagon as a set of vertical columns. From left to right the columns contain $K, K+1, \ldots, 2K-1, \ldots, K+1, K$ pastures (the middle column is the tallest, with $2K-1$ pastures). Pastures are numbered consecutively starting from $1$ : column by column from left to right, and within each column from bottom to top. So pasture $1$ sits at the bottom of the leftmost column, and the last pasture $3K(K-1)+1$ sits at the top of the rightmost column.

Each pasture is connected by a cowpath to every one of its immediate neighbors. A pasture in the interior of the hexagon is adjacent to exactly six others; for example, when $K = 3$ , pasture $10$ is adjacent to pastures $5$ , $6$ , $9$ , $11$ , $14$ , and $15$ . A pasture on an edge (but not a corner) is adjacent to exactly four others (e.g. pasture $4$ is adjacent to $1$ , $5$ , $8$ , and $9$ ), and a pasture at a corner is adjacent to only three (e.g. pasture $1$ is adjacent to $2$ , $4$ , and $5$ ). Every cowpath has length $1$ , and the distance between two pastures is the length of the shortest route between them.

Farmer John's Holstein cows have been grazing in pasture $H$ ( $1 \le H \le 3K(K-1)+1$ ) for several days and have grown fat and lazy. To make them exercise, Farmer John places tasty treats in every pasture that is exactly at distance $L$ ( $1 \le L \le 2K-2$ ) from the cows. He promises that at least one treat has been placed, but he does not reveal which pastures hold them.

Help the cows avoid unnecessary walking: determine how many pastures could hold a treat, and list them in ascending order.

Input

The first line contains three space-separated integers $K$ , $H$ , and $L$ .

Output

On the first line, print a single integer: the number of pastures that are exactly at distance $L$ from pasture $H$ .

On each of the following lines, print one such pasture number, in ascending order.

Examples3

Example 1
Input
```
3 1 2
```
Expected output
```
5
3
6
8
9
10
```
Example 2
Input
```
2 1 1
```
Expected output
```
3
2
3
4
```
Example 3
Input
```
3 10 1
```
Expected output
```
6
5
6
9
11
14
15
```