{"problem":{"name":"[ROI 2018] Addition without carry","description":{"content":"对于一个只含自然数的集合，如果集合中所有数之和 = 集合中所有数的 $\\mathtt{OR}$ 和，那么我们称之为「美丽的集合」。 给出 $a_1\\ldots a_n$, 存在一个由数列 $b_1\\ldots b_n$ 组成的「美丽的集合」，且满足： $\\forall i=1\\ldots n$， $b_i\\geq a_i$, 且 $\\sum b_i$ 最小。 试求出新数列的 $\\sum b_","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9293"},"statements":[{"statement_type":"Markdown","content":"对于一个只含自然数的集合，如果集合中所有数之和 = 集合中所有数的 $\\mathtt{OR}$ 和，那么我们称之为「美丽的集合」。\n\n给出 $a_1\\ldots a_n$, 存在一个由数列 $b_1\\ldots b_n$ 组成的「美丽的集合」，且满足：\n\n$\\forall i=1\\ldots n$， $b_i\\geq a_i$, 且\n$\\sum b_i$ 最小。\n\n试求出新数列的 $\\sum b_i$。\n\n为了简便起见，我们给出的 $a_i$ 均为二进制形式，你的答案也应是二进制形式。\n\n## Input\n\n第一行一个整数 $n$。\n\n接下来 $n$ 行，一行一个二进制数 $a_i$。\n\n## Output\n\n输出得出的二进制的 $\\sum b_i$。\n\n[samples]\n\n## Background\n\n译自 [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T4. [Сложение без переносов ](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf)([Addition without carry](https://codeforces.com/gym/102154/problem/A))。\n\n## Note\n\n对于所有的数据，$1 \\leq n \\leq 3 \\times 10^5$。\n\n（在二进制下）$a_i$ 的位数不超过 $3 \\times 10^5$，并且所有 $a_i$ 的位数之和不超过 $3\\times 10^5$。\n\n子任务依赖仅供参考，洛谷评测时无子任务依赖。\n\n| 子任务 | 分值 | $n$ | $\\max L$ | 必须通过的子任务 |\n|:------:|:----:|:---:|:--------:|:----------------:|\n| 1      | 4    | $n=2$ | $\\max L \\le 10$ |    |\n| 2      | 2    | $n=2$ | $\\max L \\le 20$ | 1  |\n| 3      | 2    | $n=2$ | $\\max L \\le 100$ | 1,2 |\n| 4      | 2    | $n=2$ | $\\max L \\le 1000$ | 1--3 |\n| 5      | 2    | $n=2$ | $\\max L \\le 300\\,000$ | 1--4 |\n| 6      | 4    | $n \\le 100$ | $\\max L \\le 100$ |    |\n| 7      | 4    | $n \\le 1000$ | $\\max L \\le 1000$ | 6  |\n| 8      | 4    | $n \\le 300\\,000$ | $\\max L \\le 300\\,000$ | 6,7 |\n| 9      | 4    | $n \\le 5$ | $\\max L \\le 5$ | U  |\n| 10     | 4    | $n \\le 5$ | $\\max L \\le 1\\,000$ | U,1--4,9 |\n| 11     | 4    | $n \\le 1\\,000$ | $\\max L \\le 5$ | U,9 |\n| 12     | 4    | $n \\le 10$ | $\\max L \\le 10$ | U,1,9 |\n| 13     | 4    | $n \\le 50$ | $\\max L \\le 50$ | U,1,2,9,12 |\n| 14     | 7    | $n \\le 100$ | $\\max L \\le 100$ | U,1--3,6,9,12,13 |\n| 15     | 7    | $n \\le 300$ | $\\max L \\le 300$ | U,1--3,6,9,12--14 |\n| 16     | 8    | $n \\le 1000$ | $\\max L \\le 1000$ | U,1--4,6,7,9--15 |\n| 17     | 8    | $n \\le 3000$ | $\\max L \\le 3000$ | U,1--4,6,7,9--16 |\n| 18     | 6    | $n \\le 10\\,000$ | $\\max L \\le 10\\,000$ | U,1--4,6,7,9--17 |\n| 19     | 7    | $n \\le 30\\,000$ | $\\max L \\le 30\\,000$ | U,1--4,6,7,9--18 |\n| 20     | 7    | $n \\le 100\\,000$ | $\\max L \\le 100\\,000$ | U,1--4,6,7,9--19 |\n| 21     | 6    | $n \\le 300\\,000$ | $\\max L \\le 300\\,000$ | U,1--20 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9293","tags":["2018","ROI（俄罗斯）"],"sample_group":[["2\n10\n10","110"],["2\n10100\n1001","11101"],["3\n1\n1\n110","1011"]],"created_at":"2026-03-03 11:09:25"}}