G. University Classes

Codeforces

IDCF847G

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

There are _n_ student groups at the university. During the study day, each group can take no more than 7 classes. Seven time slots numbered from 1 to 7 are allocated for the classes. The schedule on Monday is known for each group, i. e. time slots when group will have classes are known. Your task is to determine the minimum number of rooms needed to hold classes for all groups on Monday. Note that one room can hold at most one group class in a single time slot. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 1000) — the number of groups. Each of the following _n_ lines contains a sequence consisting of 7 zeroes and ones — the schedule of classes on Monday for a group. If the symbol in a position equals to 1 then the group has class in the corresponding time slot. In the other case, the group has no class in the corresponding time slot. ## Output Print minimum number of rooms needed to hold all groups classes on Monday. [samples] ## Note In the first example one room is enough. It will be occupied in each of the seven time slot by the first group or by the second group. In the second example three rooms is enough, because in the seventh time slot all three groups have classes.

大学里有 #cf_span[n] 个学生小组。在学习日，每个小组最多可以上 #cf_span[7] 节课。为课程分配了七个时间槽，编号从 #cf_span[1] 到 #cf_span[7]。已知每个小组周一的课程安排，即已知每个小组上课的时间槽。你的任务是确定周一容纳所有小组课程所需的最少房间数。注意，一个房间在单个时间槽内最多只能容纳一个小组的课程。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1000]) —— 小组的数量。接下来的 #cf_span[n] 行，每行包含一个由 #cf_span[7] 个零和一组成的序列——表示一个小组周一的课程安排。如果某位置的符号等于 #cf_span[1]，则该小组在对应的时间槽有课；否则，该小组在该时间槽没有课。请输出周一容纳所有小组课程所需的最少房间数。在第一个例子中，一个房间就足够了。在七个时间槽中的每一个，都由第一个小组或第二个小组占用。在第二个例子中，三个房间就足够了，因为在第七个时间槽，三个小组都有课。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1000]) —— 小组的数量。接下来的 #cf_span[n] 行，每行包含一个由 #cf_span[7] 个零和一组成的序列——表示一个小组周一的课程安排。如果某位置的符号等于 #cf_span[1]，则该小组在对应的时间槽有课；否则，该小组在该时间槽没有课。 ## Output 请输出周一容纳所有小组课程所需的最少房间数。 [samples] ## Note 在第一个例子中，一个房间就足够了。在七个时间槽中的每一个，都由第一个小组或第二个小组占用。在第二个例子中，三个房间就足够了，因为在第七个时间槽，三个小组都有课。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of student groups. Let $ S_i = (s_{i,1}, s_{i,2}, \dots, s_{i,7}) \in \{0,1\}^7 $ be the schedule of group $ i $, where $ s_{i,j} = 1 $ if group $ i $ has a class in time slot $ j $, and $ 0 $ otherwise, for $ i \in \{1, \dots, n\} $, $ j \in \{1, \dots, 7\} $. **Constraints** 1. $ 1 \leq n \leq 1000 $ 2. $ s_{i,j} \in \{0,1\} $ for all $ i,j $ **Objective** Compute the minimum number of rooms required, which equals the maximum number of overlapping classes in any single time slot: $$ \max_{j \in \{1, \dots, 7\}} \sum_{i=1}^{n} s_{i,j} $$

Samples

Input #1

2
0101010
1010101

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "G. University Classes",
    "description": {
      "content": "There are _n_ student groups at the university. During the study day, each group can take no more than 7 classes. Seven time slots numbered from 1 to 7 are allocated for the classes. The schedule on ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF847G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are _n_ student groups at the university. During the study day, each group can take no more than 7 classes. Seven time slots numbered from 1 to 7 are allocated for the classes.\n\nThe schedule on ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "大学里有 #cf_span[n] 个学生小组。在学习日，每个小组最多可以上 #cf_span[7] 节课。为课程分配了七个时间槽，编号从 #cf_span[1] 到 #cf_span[7]。\n\n已知每个小组周一的课程安排，即已知每个小组上课的时间槽。\n\n你的任务是确定周一容纳所有小组课程所需的最少房间数。注意，一个房间在单个时间槽内最多只能容纳一个小组的课程。\n\n第一行包含一个整数 #cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of student groups.  \nLet $ S_i = (s_{i,1}, s_{i,2}, \\dots, s_{i,7}) \\in \\{0,1\\}^7 $ be the schedule of group $ i $, where $ s_{i,j} = 1 $ if gr...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments