SRM 606 div2 500 EllysNumberGuessing

时间：2014-01-31 14:46:39 阅读：456 评论：0 收藏：0 [点我收藏+]

猜数字。。。判断什么时候是lied情况挺多，写的很麻烦。。。

Problem Statement

Elly and Kris play the following game. In the beginning Kristina thinks of a number between 1 and 1,000,000,000, inclusive. After that Elly starts trying to guess it. In each round she says a number and Kristina says what is the absolute difference between the number she has thought of, and the number Elly guessed. Now Elly wonders if the guesses she has already made are sufficient to uniquely determine Kristina‘s number.

You are given a vector <int> guesses and a vector <int> answers of the same length. For each valid i, in round i of the game (0-based index) Elly guessed the number guesses[i] and Kristina answered answers[i]. If Kristina‘s number can be uniquely determined, return that number. If there are multiple possibilities that are consistent with the current set of guesses and answers, return -1. If it can be shown that at some point Kristina has lied (some of her answers were inconsistent), return -2.

Definition

Class:	EllysNumberGuessing
Method:	getNumber
Parameters:	vector <int>, vector <int>
Returns:	int
Method signature:	int getNumber(vector <int> guesses, vector <int> answers)
(be sure your method is public)

Limits

Time limit (s):	2.000
Memory limit (MB):	256

Constraints

guesses and answers will each contain between 1 and 50 elements, inclusive.

guesses and answers will contain the same number of elements.

Each element of guesses will be between 1 and 1,000,000,000, inclusive.

Each element of answers will be between 1 and 999,999,999, inclusive.

Examples

{600, 594}

{6, 12}

Returns: 606

Apparently Kristina has thought of the number of this SRM.

{100, 50, 34, 40}

{58, 8, 8, 2}

Returns: 42

It is not guaranteed that Elly has used a perfect strategy so far.

{500000, 600000, 700000}

{120013, 220013, 79987}

Returns: -2

The answers here are inconsistent. After the second guess we can conclude that the answer is below 500000. But the third one indicates that it is above 500000. Thus, Kristina is a liar and you should return -2.

{500000000}

{133742666}

Returns: -1

There are multiple possibilities here, thus you should return -1.

{76938260, 523164588, 14196746, 296286419, 535893832,
 41243148, 364561227, 270003278, 472017422, 367932361,
 395758413, 301278456, 186276934, 316343129, 336557549,
 52536121, 98343562, 356769915, 89249181, 335191879}

{466274085, 20047757, 529015599, 246925926, 7318513,
 501969197, 178651118, 273209067, 71194923, 175279984,
 147453932, 241933889, 356935411, 226869216, 206654796,
 490676224, 444868783, 186442430, 453963164, 208020466}

Returns: 543212345

{42}

{42}

Returns: 84

Don‘t forget that the number Kris has thought of must be between 1 and 1,000,000,000.

{999900000}

{100001}

Returns: 999799999

Don‘t forget that the number Kris has thought of must be between 1 and 1,000,000,000.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

class EllysNumberGuessing {
public:
	int getNumber(vector <int> guesses, vector <int> answers)
	{
	    int xy=-1;

        bool okt1=false,okt2=false;

        bool flagbutong=false;

	    for(int i=0;i<guesses.size();i++)
        {
            for(int j=i+1;j<guesses.size();j++)
            {
                if(guesses[i]!=guesses[j])
                {
                    int t1=guesses[i]-answers[i];
                    int t2=guesses[i]+answers[i];

                    if(guesses[j]-answers[j]==t1) okt1=true;
                    if(guesses[j]+answers[j]==t1) okt1=true;
                    if(guesses[j]-answers[j]==t2) okt2=true;
                    if(guesses[j]+answers[j]==t2) okt2=true;

                    if(okt1) xy=t1;
                    else if(okt2) xy=t2;

                    flagbutong=true;
                    break;
                }
            }
            if(flagbutong) break;
        }
        if(flagbutong==false)
        {
            int t1=guesses[0]-answers[0];
            int t2=guesses[0]+answers[0];
            if(((t1>=1&&t1<=1000000000)+(t2>=1&&t2<=1000000000))==1)
            {
                int temp=(t1>=1&&t1<=1000000000)?t1:t2;
                for(int i=0;i<guesses.size();i++)
                {
                    int t1=guesses[i]-answers[i];
                    int t2=guesses[i]+answers[i];

                    if(t1==temp||t2==temp) continue;
                    else return -2;
                }
                return temp;
            }
            else if(((t1>=1&&t1<=1000000000)+(t2>=1&&t2<=1000000000))==2)
            {
                for(int i=0;i<guesses.size();i++)
                {
                    if(answers[i]!=answers[0]) return -2;
                }
                return -1;
            }
            else if(((t1>=1&&t1<=1000000000)+(t2>=1&&t2<=1000000000))==0)
                return -2;
        }

        if((xy>=1&&xy<=1000000000)==false) return -2;

        for(int i=0;i<guesses.size();i++)
        {
            int t1=guesses[i]-answers[i];
            int t2=guesses[i]+answers[i];

            if(t1==xy||t2==xy) continue;
            else return -2;
        }

        return xy;
	}
};

SRM 606 div2 500 EllysNumberGuessing

原文：http://blog.csdn.net/u012797220/article/details/18882859

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)