CF549B.Looksery Party
提高+/省选-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The Looksery company, consisting of n staff members, is planning another big party. Every employee has his phone number and the phone numbers of his friends in the phone book. Everyone who comes to the party, sends messages to his contacts about how cool it is. At the same time everyone is trying to spend as much time on the fun as possible, so they send messages to everyone without special thinking, moreover, each person even sends a message to himself or herself.
Igor and Max, Looksery developers, started a dispute on how many messages each person gets. Igor indicates n numbers, the i-th of which indicates how many messages, in his view, the i-th employee is going to take. If Igor guesses correctly at least one of these numbers, he wins, otherwise Max wins.
You support Max in this debate, so you need, given the contact lists of the employees, to determine whether there is a situation where Igor loses. Specifically, you need to determine which employees should come to the party, and which should not, so after all the visitors send messages to their contacts, each employee received a number of messages that is different from what Igor stated.
Looksery 公司共有 n 名员工,正计划举办另一场大型派对。每位员工的手机通讯录中都存有自己的电话号码以及自己朋友们的电话号码。所有出席派对的员工都会向自己的全部联系人发送消息,宣传派对有多么精彩。与此同时,每个人都想尽可能多地享受派对乐趣,因此他们不加甄别地向所有联系人发送消息;更进一步地,每个人甚至还会给自己发送一条消息。
Looksery 公司的开发者 Igor 和 Max 就每位员工最终会收到多少条消息展开了争论。Igor 给出了 n 个数字,其中第 i 个数字表示他预测第 i 位员工将收到的消息数量。如果 Igor 至少猜对了其中一个数字,则 Igor 获胜;否则 Max 获胜。
你支持 Max,因此你需要根据员工们的联系人列表,判断是否存在一种情况使得 Igor 输掉这场争论。具体而言,你需要确定哪些员工应该出席派对、哪些员工不应出席,使得在所有出席者向其全部联系人发送完消息后,每位员工实际收到的消息数量均与 Igor 所声称的数量不同。
输入格式
The first line contains a single integer n (1 ≤ n ≤ 100) — the number of employees of company Looksery.
Next n lines contain the description of the contact lists of the employees. The i-th of these lines contains a string of length n, consisting of digits zero and one, specifying the contact list of the i-th employee. If the j-th character of the i-th string equals 1, then the j-th employee is in the i-th employee's contact list, otherwise he isn't. It is guaranteed that the i-th character of the i-th line is always equal to 1.
The last line contains n space-separated integers: _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ n), where a__i represents the number of messages that the i-th employee should get according to Igor.
第一行包含一个整数 n(1≤n≤100)—— 表示 Looksery 公司的员工人数。
接下来的 n 行描述了每位员工的联系人列表。其中第 i 行是一个长度为 n 的字符串,仅由数字 0 和 1 组成,表示第 i 位员工的联系人列表。若第 i 行中第 j 个字符为 1,则表示第 j 位员工在第 i 位员工的联系人列表中;否则不在。保证对于任意 i,第 i 行的第 i 个字符恒为 1。
最后一行包含 n 个以空格分隔的整数:a1,a2,…,an(0≤ai≤n),其中 ai 表示 Igor 希望第 i 位员工收到的消息数量。
输出格式
In the first line print a single integer m — the number of employees who should come to the party so that Igor loses the dispute.
In the second line print m space-separated integers — the numbers of these employees in an arbitrary order.
If Igor wins the dispute in any case, print -1.
If there are multiple possible solutions, print any of them.
第一行输出一个整数 m —— 应参加聚会的员工人数,使得 Igor 输掉这场争论。
第二行输出 m 个用空格分隔的整数 —— 这些员工的编号(顺序任意)。
如果 Igor 在任何情况下都会赢得这场争论,则输出 −1。
如果存在多种可能的解,输出任意一种即可。
输入输出样例
输入#1
3 101 010 001 0 1 2
输出#1
1 1
输入#2
1 1 1
输出#2
0
输入#3
4 1111 0101 1110 0001 1 0 1 0
输出#3
4 1 2 3 4
说明/提示
In the first sample Igor supposes that the first employee will receive 0 messages. Since he isn't contained in any other contact list he must come to the party in order to receive one message from himself. If he is the only who come to the party then he will receive 1 message, the second employee will receive 0 messages and the third will also receive 1 message. Thereby Igor won't guess any number.
In the second sample if the single employee comes to the party he receives 1 message and Igor wins, so he shouldn't do it.
In the third sample the first employee will receive 2 messages, the second — 3, the third — 2, the fourth — 3.
在第一个样例中,Igor 假设第一位员工将收到 0 条消息。由于他未被包含在任何其他人的联系人列表中,因此他必须出席聚会,才能从自己那里收到 1 条消息。如果只有他一人出席聚会,则他将收到 1 条消息,第二位员工将收到 0 条消息,第三位员工也将收到 1 条消息。因此 Igor 将无法猜中任何一个数字。
在第二个样例中,若唯一的一位员工出席聚会,则他将收到 1 条消息,Igor 获胜,因此他不应这样做。
在第三个样例中,第一位员工将收到 2 条消息,第二位员工收到 3 条,第三位员工收到 2 条,第四位员工收到 3 条。
输入解题思路,AI测评打分。不知道怎么写?