#P18188. New School Term
New School Term
New School Term
题目描述
NPCA 学校有 名学生,编号为 到 。老师 Napuka 需要将他们分成两个班,每个班恰好有 名学生。
给定 对学生 ,其中 。如果第 对中的两名学生被分到同一个班,则产生 的不满意度;否则这一对不产生不满意度。
总不满意度为所有这些值之和。请构造一种分班方案,使总不满意度最小。
注意,权值由学生对在输入中的下标决定:第一对的权值是 ,第二对的权值是 ,以此类推。
输入格式
第一行包含两个整数 。
接下来 行,第 行包含两个整数 ,表示第 对学生。
输出格式
输出一个长度为 的字符串 ,其中每个字符均为 或 。
表示第 名学生所在的班。字符串中必须恰好有 个 和 个 ,且对应方案的总不满意度必须最小。
如果存在多种最优方案,输出任意一种。
数据范围
- ;
- ;
- ;
- 任意两对学生均不同,即 时 ;
- 所有输入值均为整数。
输入只有一组数据,允许 。
样例 1
输入:
2 4
1 3
2 4
1 4
1 2
输出:
0101
样例 1 解释
学生 在一个班,学生 在另一个班。因此前两对学生各自同班,后两对学生各自异班,总不满意度为
这是最小值。也可以输出 1010。
虽然 0111 对应的不满意度是 ,但两个班的人数分别为 和 ,不满足每班恰好 人的要求,因此不是合法答案。
样例 2
输入:
3 7
2 5
1 3
4 6
2 6
4 5
2 4
5 6
输出:
001101