📄 filling the gaps(nwec89c).htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0072)http://www.acm.inf.ethz.ch/ProblemSetArchive/B_EU_NWRC/1989/nwec89c.html -->
<!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds --><HTML><HEAD><TITLE>Filling the Gaps</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="Filling the Gaps" name=description>
<META content=htmlatex name=keywords>
<META content=document name=resource-type>
<META content=global name=distribution>
<META content="MSHTML 6.00.2800.1491" name=GENERATOR></HEAD>
<BODY lang=EN bgColor=#ffffff>
<CENTER>
<H5>ACM International Collegiate Programming Contest 1989</H5>
<H5>Northwestern European Regionals</H5>
<P>
<P>
<H1>Problem C</H1></CENTER>
<H1><BR clear=all>
<CENTER>
<TABLE bgColor=#0060f0>
<TBODY>
<TR>
<TD><B><FONT color=#c0ffff size=5> <A
name=SECTION0001000000000000000000>Filling the
Gaps</A></FONT> </B></TR></TBODY></TABLE></CENTER></H1>
<P>At the largest conference on coding and cryptography the following theorem
needed a proof or a counterexample: Suppose you are given a set of words of
equal length; each word consisting of <TT>0</TT>'s, <TT>1</TT>'s and/or
<TT>*</TT>'s. Furthermore suppose the pattern of <TT>*</TT>'s is different for
all words in the set. By this we mean: if you replace all <TT>0</TT>'s and
<TT>1</TT>'s by say <TT>$</TT> you obtain different words.
<P>The claim is: if you replace the <TT>*</TT>'s by <TT>0</TT>'s and
<TT>1</TT>'s in all possible ways, then you obtain a set that is at least as big
as the set you started with.
<P>Example:
<P><TT>{ 10*, *0*, *00 }</TT> produces <TT>{ 100, 101, 000, 001 }</TT>
<P><TT>{ 100, 101, 10* }</TT> produces <TT>{ 100, 101 }</TT>
<P>Notice that the set in the latter example does not satisfy the condidtion
mentioned above, so it does not provide a counterexample.
<P>You program has to check for a number of cases:
<OL>
<LI>Whether the pattern of <TT>*</TT>'s is different for all words in the set
and:
<LI>Compute the number of words obtained by replacing the <TT>*</TT>'s by
<TT>0</TT>'s and <TT>1</TT>'s. </LI></OL>The words will not be longer than 15
symbols.
<H2><FONT color=#0070e8><A
name=SECTION0001001000000000000000>Input</A></FONT></H2>
<P>The input is a text-file that presents a sequence of sets. Each set is
described as follows. The first line gives two integers: the length of the words
and the number of the words. Then follow the words, each on a separate line. The
end of the sequence of sets is indicated by a set with wordlength 0 and number
of words equal to 0.
<P>
<H2><FONT color=#0070e8><A
name=SECTION0001002000000000000000>Output</A></FONT></H2>
<P>The output is a textfile that contains one line for each set. if the pattern
of <TT>*</TT>'s is different for all the words in this set this line should
contain <TT>YES</TT> (in uppercase), followed by a space and the number of
obtained words, otherwise it should contain <TT>NO</TT> (uppercase) only.
<P>
<H2><FONT color=#0070e8><A name=SECTION0001003000000000000000>Sample
Input</A></FONT></H2>
<P><PRE>3 3
10*
*0*
*00
4 3
1100
1101
110*
0 0
</PRE>
<P>
<H2><FONT color=#0070e8><A name=SECTION0001004000000000000000>Sample
Output</A></FONT></H2>
<P><PRE>YES 4
NO
YES 0</PRE>
<P></P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -