CF1646F.Playing Around the Table

省选/NOI-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are nn players, numbered from 11 to nn sitting around a round table. The (i+1)(i+1)-th player sits to the right of the ii-th player for 1≤i<n1 \le i \lt n, and the 11-st player sits to the right of the nn-th player.

There are n2n^2 cards, each of which has an integer between 11 and nn written on it. For each integer from 11 to nn, there are exactly nn cards having this number.

Initially, all these cards are distributed among all the players, in such a way that each of them has exactly nn cards. In one operation, each player chooses one of his cards and passes it to the player to his right. All these actions are performed simultaneously.

Player ii is called solid if all his cards have the integer ii written on them. Their objective is to reach a configuration in which everyone is solid. Find a way to do it using at most (n2−n)(n^2-n) operations. You do not need to minimize the number of operations.

有 nn 名玩家,编号从 11 到 nn,围坐在一张圆桌旁。对 1≤i<n1 \le i < n,第 (i+1)(i+1) 号玩家坐在第 ii 号玩家的右侧;而第 11 号玩家坐在第 nn 号玩家的右侧。

共有 n2n^2 张卡片,每张卡片上写有一个介于 11 到 nn 之间的整数。对每个从 11 到 nn 的整数,恰好有 nn 张卡片写有该数。

初始时,所有这些卡片被分发给全部玩家,使得每位玩家恰好持有 nn 张卡片。在一次操作中,每位玩家从自己手中的卡片中选择一张,并将其传递给其右侧的玩家。所有这些操作同时进行。

若玩家 ii 手中所有卡片上写的数均为 ii,则称该玩家为“稳固的”(solid)。他们的目标是达到一种局面,使得所有玩家均为稳固的。请设计一种方法,在至多 (n2−n)(n^2 - n) 次操作内达成该目标。你无需最小化操作次数。

输入格式

The first line contains a single integer nn (2≤n≤1002\le n\le 100).

Then nn lines follow. The ii-th of them contains nn integers c1,c2,…,cnc_1, c_2, \ldots, c_n (1≤cj≤n1\le c_j\le n) — the initial cards of the ii-th player.

It is guaranteed that for each integer ii from 11 to nn, there are exactly nn cards having the number ii.

第一行包含一个整数 nn(2≤n≤1002\le n\le 100)。

接下来是 nn 行。其中第 ii 行包含 nn 个整数 c1,c2,…,cnc_1, c_2, \ldots, c_n(1≤cj≤n1\le c_j\le n),表示第 ii 位玩家初始持有的牌。

保证对于每个从 11 到 nn 的整数 ii,恰好有 nn 张牌的数字为 ii。

输出格式

In the first line print an integer kk (0≤k≤(n2−n)0\le k\le (n^2-n)) — the numbers of operations you want to make.

Then kk lines should follow. In the ii-th of them print nn integers d1,d2,…,dnd_1, d_2, \ldots, d_n (1≤dj≤n1\le d_j\le n) where djd_j is the number written on the card which jj-th player passes to the player to his right in the ii-th operation.

We can show that an answer always exists under the given constraints. If there are multiple answers, print any.

第一行输出一个整数 kk(0≤k≤(n2−n)0\le k\le (n^2-n))—— 表示你希望执行的操作次数。

接下来输出 kk 行。在第 ii 行中,输出 nn 个整数 d1,d2,…,dnd_1, d_2, \ldots, d_n(1≤dj≤n1\le d_j\le n),其中 djd_j 表示在第 ii 次操作中,第 jj 位玩家传递给其右侧玩家的卡片上的数字。

在给定约束下,可以证明答案一定存在。若存在多个答案,输出任意一个即可。

输入输出样例

  • 输入#1

    2
    2 1
    1 2

    输出#1

    1
    2 1
  • 输入#2

    3
    1 1 1
    2 2 2
    3 3 3

    输出#2

    6
    1 2 3
    3 1 2
    2 3 1
    1 2 3
    3 1 2
    2 3 1

说明/提示

In the first test case, if the first player passes a card with number 22 and the second player passes a card with number 11, then the first player has two cards with number 11 and the second player has two cards with number 22. Then, after making this operation, both players are solid.

In the second test case, 00 operations would be enough too. Note that you do not need to minimize the number of operations.

在第一个测试用例中,若第一位玩家传递一张数字为 22 的卡片,第二位玩家传递一张数字为 11 的卡片,则第一位玩家将拥有两张数字为 11 的卡片,第二位玩家将拥有两张数字为 22 的卡片。执行此操作后,两位玩家均变为“稳固的”。

在第二个测试用例中,00 次操作也已足够。注意:你无需最小化操作次数。

输入解题思路,AI测评打分。不知道怎么写?

首页