2 shunfurh shunfurh 于 2017.09.05 22:24 提问

Computer Dialogue

There are three computers connected by a network. One of them is a server and the other two are clients. The server has some files, each with a different name. The full name of each file consists of two parts, a name and an extension. Both clients know the full names of all of the files stored on the server. From among its files, the server chooses a single file and sends the name part of that file's full name to one of the clients and the extension part of the full name to the other client.
The clients then begin communicating in an effort to determine which file was selected by the server (they want to learn the file's full name). However, the clients have to communicate in a very restricted manner. Clients take turns sending messages to each other, but they can only say when they don't know the full name of the file. If one client does not know the full name of the chosen file, that client may send a message saying "I don't know the full file name" to the other client. The two clients alternate, sending only this message back and forth. This continues until either one of the clients knows the full file name or they decide to quit. The client that received the name part of the full file name always waits for the other client to send the first message.

Pretend that you know all the full file names that reside on the server (both the name and the extension part) and you are listening to the conversation between the clients. Based on this conversation, you should determine the set of files that might have been chosen by the server. Files in this set are called candidate files.

Input

The first line of the input contains two integers N and M, separated by a space. N (1 <= N <= 1000) is the number of files of the server, and M (1 <= M <= 100) is the number of messages exchanged between the clients in their effort to determine the full file name.

Each of the next N lines contain one full file name. Full file names are given in a manner similar to MS-DOS 8.3 format. Each full file name is represented in name.extension form, where both the name and the extension consist of only capital, alphabetic characters and decimal digits. The name part will have at least one character and at most eight. The extension part will have at most three characters and may be empty. If extension is empty then separating dot may be omitted.

Each full file name appears in the input no more than once.

Output

Write on the first line of the output the number of candidate files based on the given set of files and the number of messages exchanged between the clients. Write zero if there are no candidate files.

On the following lines, write the full names of all candidate files. Each of these names should be written on a separate line. They should appear in the same order and with exactly the same spelling as in the input. That means that if the separating dot was omitted in the input for a particular file then it should also be omitted for this file in the output and vice versa. No file may be listed more than once.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Sample Input

19 2
LICENCE.TMP
WIN32.LOG
FILEID.
PSTOTEXT.TXT
GSVIEW32.EXE
GSVIEW32.ICO
GSVIEWDE.HLP
LICENCE
GSVIEWEN.HLP
GSVW32DE.DLL
FILEID.TMP
GSVW32EN.DLL
PSTOTXT3.DLL
PSTOTXT3.EXE
GSV16SPL.EXE
GVWGS32.EXE
ZLIB32.DLL
PRINTER.INI
README.TXT

Sample Output

6
LICENCE.TMP
FILEID.
LICENCE
FILEID.TMP
PSTOTXT3.DLL
PSTOTXT3.EXE

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.20 08:50
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Dialogue System for Unity文档中文对照版(简雨原创翻译)第二篇(我们开始仙剑demo的剧情)
DialogueDatabase To usethe Dialogue System, you need to create a dialogue database containing lines ofdialogue (conversations) and related information. A dialogue database contains: ProjectInfo: Des
[插件资源] Dialogue System for Unity 1.7.0 - 创建对话系统的专用插件
[插件资源] Dialogue System for Unity 1.7.0 - 创建对话系统的专用插件
[插件资源] Dialogue System for Unity 1.7.2 - 创建对话系统的专用插件
[插件资源] Dialogue System for Unity 1.7.2 - 创建对话系统的专用插件
Dialogue System for Unity制作剧情,我们需要一个什么样的需求
我们先看下改版的Dialogue System for Unity要完成我们仙剑demo的效果。
Dialogue System for Unity文档中文对照版(简雨原创翻译)第一篇(我们开始仙剑demo的剧情)
这篇文档本身有快300页,因为实在太多,所以不像前面的插件那样翻译的,很多地方直接用了机翻,因为文字量实在太大,如果翻译完全套,再加上讲解的话,估计要花几个月的时间,对于普通的程序来说,其实机翻对照上下文完全可以掌握该插件的用法,在这个的最后我会提供chm版的DialogueSystem for Unity 本地API和整个机翻的原文和翻译以后文章word版本对照,有兴趣的朋友可以在word版里面
Dialogue between Jack and Rose
[Rose is on top of a door in the water and Jack is hanging off the side, shivering]Rose : It's getting quiet.Jack : It's gonna take a couple of minutes to get the boats organized. I don't know about y...
Building task-oriented dialogue systems for online shopping 论文笔记
Building task-oriented dialogue systems for online shopping 论文笔记 1. 摘要 该文给出了针对用于线上购物的面向任务的对话系统的一个一般的解决方案, 目标是协助用户完成多样化的购买相关任务, 比如搜索商品和回答问题, 如同正常人之间的对话. 作为一个创始工作, 我们会展现NLP的技术, 数据源以及可以利用的众包来建立这样一个关于...
Dialogue System for Unity文档中英对照版(简雨原创翻译)完结篇(内置脚本使用,脚本API)
这一篇是Dialogue System for Unity翻译的最后一篇了,本来这一篇是夹在前六篇里面的一个章节,之所以提出来是因为是我认为这一篇是整个Dialogue System for Unity使用的核心,只有学好这一篇的内容,Dialogue System for Unity才可以得心用手的使用,这一篇的翻译也与其他前几篇不同,前几篇大量使用机翻,之后只是把一些翻译特别别扭的才改了一下,
Neural Dialogue Generation
构造 chatbot 的难点: 1. 计算机需要理解你所问的内容 2. 计算机需要对你的问题生成有意义的序列,这需要领域知识、对话上下文、世界知识背景知识一开始利用 SMT 来生成响应,利用 phrase-base MT 抽取高频模式:后来用神经网络 encoder-decoder 架构来做:Mutual Information for Response Generation一般的 seq2se
Deep Reinforcement Learning for Dialogue Generation
关键词reinforcement learing,seq2seq来源EMNLP 2016.06.05问题目前的 seq2seq 模型做对话生成存在两个问题: 当前的 seq2seq 模型是这么去训练的,在给定对话上下文后,用最大似然估计作为目标函数,预测下一轮对话。但是 MLE 训练出来的模型并不能够产生有趣、多样、有信息量的反馈。 另一方面基于 MLE 的 seq2seq 模型不能够排除重复回复,