No tags yet

No tag edit access

The problem statement has recently been changed. View the changes.

×
time limit per test: 1 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: standard

output: standard

A Go championship is being set up in Petrozavodsk State University. There are many skilled Go players here, including Qc. But this year he decided to join the organizing committee, and try to create a schedule for the tournament.

The championship will be decided in a round-robin tournament, that is, for every pair of players there will be exactly one match between them. Qc has to split the matches in tours in such a manner that no competitor plays twice or more in the same tour. Moreover, the number of tours should be made minimal possible.

As you have probably expected, Qc asked you to do this.

The championship will be decided in a round-robin tournament, that is, for every pair of players there will be exactly one match between them. Qc has to split the matches in tours in such a manner that no competitor plays twice or more in the same tour. Moreover, the number of tours should be made minimal possible.

As you have probably expected, Qc asked you to do this.

The input contains one integer number N (1 <= N <= 2005) --- the number of participants.

In the first line output an integer number T --- the minimal number of tours. In the following N lines output a NxN matrix containing your schedule. The j-th number in the i-th row of the matrix is the number of the tour for the match between i-th and j-th players, tours being numbered from 1 to T. If i=j, this number should be 0. If there are several optimal solutions, output any.

Input

Test #1

4

Test #2

5

4

Test #2

5

Output

Test #1

3

0 1 2 3

1 0 3 2

2 3 0 1

3 2 1 0

Test #2

5

0 1 5 4 3

1 0 2 3 5

5 2 0 1 4

4 3 1 0 2

3 5 4 2 0

3

0 1 2 3

1 0 3 2

2 3 0 1

3 2 1 0

Test #2

5

0 1 5 4 3

1 0 2 3 5

5 2 0 1 4

4 3 1 0 2

3 5 4 2 0

Author: | Anton Golubev, Petrazavodsk SU |

Resource: | Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University |

Date: | August 26, 2005 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/13/2021 10:17:51 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|