ACAC 题库 ac.isam.top
GitHub
AtCoder Regular Contest-- 219
A
相似性
Similarity
AtCoder
⌀ 557
原题
←B →

相似性AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

You are given $N$ distinct strings $S_1, \dots, S_N$. Each of these strings is a string of length $M$ consisting of 0 and 1.

给定 $N$ 个互不相同的字符串 $S_1, \dots, S_N$。这些字符串的长度均为 $M$，且仅由 0 和 1 组成。AI (CI翻译)

Determine whether there exists a string $T$ of length $M$ consisting of 0 and 1 satisfying the following condition, and if so, construct one example.

请判断是否存在一个长度为 $M$、仅由 0 和 1 组成的字符串 $T$，满足以下条件；如果存在，请构造出一个示例。AI (CI翻译)

  • Every string $S_i$ matches $T$ in at least one position.
  • More formally, for every integer $i$ ($1 \le i \le N$), there exists an integer $x_i$ ($1 \le x_i \le M$) such that the $x_i$-th character of $S_i$ and the $x_i$-th character of $T$ are the same.
  • 对于每个字符串 $S_i$，$S_i$ 与 $T$ 至少有一个位置上的字符相同。
  • 更形式化地，对于每个整数 $i$（$1 \le i \le N$），存在一个整数 $x_i$（$1 \le x_i \le M$），使得 $S_i$ 的第 $x_i$ 个字符与 $T$ 的第 $x_i$ 个字符相同。
AI (CI翻译)

Constraints

约束条件

AI (CI翻译)
  • $N$ and $M$ are integers.
  • $1 \leq N \leq 2 \times 10^4$
  • $1 \leq M \leq 100$
  • $S_i$ is a string of length $M$ consisting of 0 and 1.
  • $S_1, \dots, S_N$ are distinct.
  • $N$ 和 $M$ 是整数。
  • $1 \leq N \leq 2 \times 10^4$
  • $1 \leq M \leq 100$
  • $S_i$ 是一个长度为 $M$、仅由 0 和 1 组成的字符串。
  • $S_1, \dots, S_N$ 互不相同。
AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

N M
S_1
\vdots
S_N

N M
S_1
\vdots
S_N
AI (CI翻译)

Output

输出格式

AI (CI翻译)

If no $T$ satisfying the condition in the problem statement exists, output No.

如果不存在满足题目描述中条件的 $T$，输出 No。AI (CI翻译)

If a $T$ satisfying the condition in the problem statement exists, output in the following format:

如果存在满足题目描述中条件的 $T$，请按以下格式输出：AI (CI翻译)

Yes
T

Yes
T
AI (CI翻译)

If multiple $T$ satisfying the condition exist, any of them will be accepted.

如果存在多个满足条件的 $T$，输出其中任意一个即可。AI (CI翻译)

样例

Input #1
5 3
000
111
110
100
011
Output #1
Yes
101
If we set $T$ to `101`, the following holds: - The $2$nd character of $S_1$ and the $2$nd character of $T$ are the same. - The $1$st character of $S_2$ and the $1$st character of $T$ are the same. - The $1$st character of $S_3$ and the $1$st character of $T$ are the same. - The $2$nd character of $S_4$ and the $2$nd character of $T$ are the same. - The $3$rd character of $S_5$ and the $3$rd character of $T$ are the same.
Input #2
4 2
00
01
10
11
Output #2
No
No $T$ satisfies the condition.
Input #3
9 50
00001000011111100011111000011111000001000001111100
00010100010000010100000100100000100011000010000010
00100010010000010100000000000000100101000010000010
01000001011111100100000000011111000001000001111110
01111111010001000100000000100000000001000000000010
01000001010000100100000100100000000001000010000010
01000001010000010011111000111111100111110001111100
00000000000000000000000000000000000000000000000000
11111111111111111111111111111111111111111111111111
Output #3
Yes
10101010101010101010101011010101011010101101010101
题目信息
题号
arc219_a
所属比赛
AtCoder Regular Contest-- 219
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。