A. Toda 2

Codeforces

IDCF730A

Time2000ms

Memory512MB

Difficulty—

greedyimplementation

English · Original

Chinese · Translation

Formal · Original

A group of _n_ friends enjoys playing popular video game Toda 2. There is a rating system describing skill level of each player, initially the rating of the _i_\-th friend is _r__i_. The friends decided to take part in the championship as a team. But they should have equal ratings to be allowed to compose a single team consisting of all _n_ friends. So the friends are faced with the problem: how to make all their ratings equal. One way to change ratings is to willingly lose in some matches. Friends can form a party consisting of **two** to **five** (but not more than _n_) friends and play a match in the game. When the party loses, the rating of each of its members decreases by 1. A rating can't become negative, so _r__i_ = 0 doesn't change after losing. The friends can take part in multiple matches, each time making a party from any subset of friends (but remember about constraints on party size: from 2 to 5 members). The friends want to make their ratings equal but as high as possible. Help the friends develop a strategy of losing the matches so that all their ratings become equal and the resulting rating is maximum possible. ## Input The first line contains a single integer _n_ (2 ≤ _n_ ≤ 100) — the number of friends. The second line contains _n_ non-negative integers _r_1, _r_2, ..., _r__n_ (0 ≤ _r__i_ ≤ 100), where _r__i_ is the initial rating of the _i_\-th friend. ## Output In the first line, print a single integer _R_ — the final rating of each of the friends. In the second line, print integer _t_ — the number of matches the friends have to play. Each of the following _t_ lines should contain _n_ characters '_0_' or '_1_', where the _j_\-th character of the _i_\-th line is equal to: * '_0_', if friend _j_ should not play in match _i_, * '_1_', if friend _j_ should play in match _i_. Each line should contain between two and five characters '_1_', inclusive. The value _t_ should not exceed 104, it is guaranteed that such solution exists. Remember that you shouldn't minimize the value _t_, but you should maximize _R_. If there are multiple solutions, print any of them. [samples]

一组 #cf_span[n] 位朋友喜欢玩流行视频游戏 Toda 2。游戏中有一个描述每位玩家技术水平的评分系统，初始时第 #cf_span[i] 位朋友的评分为 #cf_span[ri]。朋友们决定组队参加锦标赛。但为了被允许组成一个包含全部 #cf_span[n] 位朋友的队伍，他们的评分必须相等。因此，朋友们面临一个问题：如何使他们的评分全部相等。改变评分的一种方式是主动输掉一些比赛。朋友们可以组成一个由 *两* 到 *五* 名（但不超过 #cf_span[n]）朋友组成的队伍参加一场比赛。当队伍输掉比赛时，队伍中每位成员的评分减少 #cf_span[1]。评分不能变为负数，因此当 #cf_span[ri = 0] 时，输掉比赛后评分不会改变。朋友们可以参加多场比赛，每次从任意子集的朋友中组建队伍（但需遵守队伍规模限制：由 #cf_span[2] 到 #cf_span[5] 名成员组成）。朋友们希望使他们的评分相等，且尽可能高。请帮助朋友们制定一个输掉比赛的策略，使得所有人的评分最终相等，且最终评分尽可能大。第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 100]) —— 朋友的数量。第二行包含 #cf_span[n] 个非负整数 #cf_span[r1, r2, ..., rn] (#cf_span[0 ≤ ri ≤ 100])，其中 #cf_span[ri] 是第 #cf_span[i] 位朋友的初始评分。第一行输出一个整数 #cf_span[R] —— 每位朋友的最终评分。第二行输出整数 #cf_span[t] —— 朋友们需要进行的比赛场数。接下来的 #cf_span[t] 行每行包含 #cf_span[n] 个字符 '_0_' 或 '_1_'，其中第 #cf_span[i] 行的第 #cf_span[j] 个字符表示：每行应包含两到五个（含） '_1_' 字符。 #cf_span[t] 的值不应超过 #cf_span[104]，保证存在这样的解。请注意，你无需最小化 #cf_span[t] 的值，但应最大化 #cf_span[R]。如果存在多个解，输出任意一个即可。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 100]) —— 朋友的数量。第二行包含 #cf_span[n] 个非负整数 #cf_span[r1, r2, ..., rn] (#cf_span[0 ≤ ri ≤ 100])，其中 #cf_span[ri] 是第 #cf_span[i] 位朋友的初始评分。 ## Output 第一行输出一个整数 #cf_span[R] —— 每位朋友的最终评分。第二行输出整数 #cf_span[t] —— 朋友们需要进行的比赛场数。接下来的 #cf_span[t] 行每行包含 #cf_span[n] 个字符 '_0_' 或 '_1_'，其中第 #cf_span[i] 行的第 #cf_span[j] 个字符表示：'_0_'，表示朋友 #cf_span[j] 不参加第 #cf_span[i] 场比赛；'_1_'，表示朋友 #cf_span[j] 参加第 #cf_span[i] 场比赛。每行应包含两到五个（含） '_1_' 字符。#cf_span[t] 的值不应超过 #cf_span[104]，保证存在这样的解。请注意，你无需最小化 #cf_span[t] 的值，但应最大化 #cf_span[R]。如果存在多个解，输出任意一个即可。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of friends, with $ 2 \leq n \leq 100 $. Let $ R = (r_1, r_2, \dots, r_n) $ be the initial rating vector, where $ r_i \in \mathbb{Z}_{\geq 0} $ and $ r_i \leq 100 $. **Constraints** 1. In each match, a party of size $ k $ is formed, where $ 2 \leq k \leq \min(5, n) $. 2. When a party loses, each member’s rating decreases by 1, but cannot go below 0. 3. After all matches, all ratings must be equal to some value $ R^* \in \mathbb{Z}_{\geq 0} $. 4. The total number of matches $ t \leq 10^4 $. **Objective** Maximize $ R^* $ such that there exists a sequence of valid matches reducing the ratings of selected subsets (of size 2 to 5) to make all final ratings equal to $ R^* $. **Output Requirements** - Print $ R^* $, the maximum achievable equal rating. - Print $ t $, the number of matches. - For each match, output a binary string of length $ n $ with exactly $ k \in \{2,3,4,5\} $ ones, indicating which friends participated in that match.

Samples

Input #1

5
4 5 1 7 4

Output #1

Input #2

2
1 2

Output #2

Input #3

3
1 1 1

Output #3

1
0

API Response (JSON)

{
  "problem": {
    "name": "A. Toda 2",
    "description": {
      "content": "A group of _n_ friends enjoys playing popular video game Toda 2. There is a rating system describing skill level of each player, initially the rating of the _i_\\-th friend is _r__i_. The friends deci",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF730A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A group of _n_ friends enjoys playing popular video game Toda 2. There is a rating system describing skill level of each player, initially the rating of the _i_\\-th friend is _r__i_.\n\nThe friends deci...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一组 #cf_span[n] 位朋友喜欢玩流行视频游戏 Toda 2。游戏中有一个描述每位玩家技术水平的评分系统，初始时第 #cf_span[i] 位朋友的评分为 #cf_span[ri]。\n\n朋友们决定组队参加锦标赛。但为了被允许组成一个包含全部 #cf_span[n] 位朋友的队伍，他们的评分必须相等。因此，朋友们面临一个问题：如何使他们的评分全部相等。\n\n改变评分的一种方式是主动输掉一些比赛...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of friends, with $ 2 \\leq n \\leq 100 $.  \nLet $ R = (r_1, r_2, \\dots, r_n) $ be the initial rating vector, where $ r_i \\in \\mathbb{Z}_{\\geq 0} ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments