Master-Mind Hints --340

problem description

link:https://vjudge.net/problem/UVA-340

description:
MasterMind is a game for two players. One of them, Designer, selects a secret(秘密的) code. The other, Breaker,
tries to break it. A code is no more than a row of colored dots(圆点) 《no more than 只是,仅仅 | a row of 一排》. At the beginning of a game, the players
agree upon《agree upon对。。。获得一致意见》 the length N that a code must have and upon the colors that may occur in a code.

In order to break the code, Breaker makes a number of guesses, each guess itself being a code. After
each guess Designer gives a hint(暗示,线索), stating to what extent(程度) the guess matches his secret code.

In this problem you will be given a secret code s1 … sn and a guess g1 … gn, and are to determine
the hint. A hint consists of a pair of numbers determined as follows.

A match is a pair (i, j), 1 ≤ i ≤ n and 1 ≤ j ≤ n, such that si = gj . Match (i, j) is called strong
when i = j, and is called weak otherwise. Two matches (i, j) and (p, q) are called independent when
i = p if and only if j = q. A set of matches is called independent when all of its members are pairwise(成对发生的)
independent.

Designer chooses an independent set M of matches for which the total number of matches and the
number of strong matches are both maximal(最大的). The hint then consists of the number of strong followed
by the number of weak matches in M. Note that these numbers are uniquely(独特的) determined by the secret
code and the guess. If the hint turns out to be (n, 0), then the guess is identical(完全相同的) to the secret code.

Input
The input will consist of data for a number of games. The input for each game begins with an integer
specifying N (the length of the code). Following these will be the secret code, represented as(被。。描绘成) N integers,

which we will limit to the range (范围)1 to 9. There will then follow an arbitrary(任意的) number of guesses, each
also represented as N integers, each in the range 1 to 9. Following the last guess in each game will be
N zeroes; these zeroes are not to be considered as a guess.

Following the data for the first game will appear data for the second game (if any) beginning with a
new value for N. The last game in the input will be followed by a single ‘0’ (when a value for N would
normally be specified). The maximum value for N will be 1000

Output
The output for each game should list the hints that would be generated for each guess, in order, one hint
per line. Each hint should be represented as a pair of integers enclosed(装入) in parentheses and separated by
a comma. The entire list of hints for each game should be prefixed(前缀) by a heading indicating the game
number; games are numbered sequentially starting with 1. Look at the samples below for the exact
format.

Sample Input
4
1 3 5 5
1 1 2 3
4 3 3 5
6 5 5 1
6 1 3 5
1 3 5 5
0 0 0 0
10
1 2 2 2 4 5 6 6 6 9
1 2 3 4 5 6 7 8 9 1
1 1 2 2 3 3 4 4 5 5
1 2 1 3 1 5 1 6 1 9
1 2 2 5 5 5 6 6 6 7
0 0 0 0 0 0 0 0 0 0
0

Sample Output
Game 1:
(1,1)
(2,0)
(1,2)
(1,2)
(4,0)
Game 2:
(2,4)
(3,2)
(5,0)
(7,0)


analysis


题目大概意思:给定答案序列和用户猜的序列,统计有多少数字位置正确(A),有多少数字在两个序列都出现过但位置不正确(B)
analysis:
直接统计A,
方法1:求B,对于每个数字(1–9),统计二者出现的次数c1,c2,
则min(c1 , c2)就是该数字对B的贡献。在减去A
方法2:
求B,还可以用一个标记数组,猜中就标记一下,对于两种方法,时间复杂度都是O(n^2)

但是个人觉得,方法1的想法还是很好的


code


#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 1005;
int a[maxn],b[maxn]; //a存答案,b存猜的
int n;
int main()
{
    int Case = 0;
    while(scanf("%d",&n)==1 && n)
    {
        for(int i=0; i<n; ++i)
            cin >> a[i];
        printf("Game %d:\n",++Case);
        for(int k=1;; ++k)
        {
            int A=0,B=0;
            for(int i=0; i<n; ++i)
            {
                cin >> b[i];
                if(a[i]==b[i])
                    A++;
            }
            if(!b[0])
                break;
            for(int i=1; i<=9; ++i)
            {
                int c1=0,c2=0;
                for(int j=0; j<n; ++j)
                {
                    if(a[j]==i)
                        c1++;
                    if(b[j]==i)
                        c2++;
                }
                if(c1<c2)
                    B += c1;
                else
                    B += c2;
            }

            printf(" (%d,%d)\n",A,B-A);
        }
    }
    system("pause");
    return 0;
}


全部评论

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
程序员小白条:找的太晚,别人都是大三实习,然后大四秋招春招的,你大四下了才去实习,晚1年
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
这是什么操作什么意思,这公司我服了...
斯派克spark:意思是有比你更便宜的牛马了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务