SRM 606 div2 500 EllysNumberGuessing

2023-12-16 08:27:21

猜数字。。。判断什么时候是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

0)  
  
{600, 594}
 
{6, 12}
 
Returns: 606
Apparently Kristina has thought of the number of this SRM.
1)  
  
{100, 50, 34, 40}
 
{58, 8, 8, 2}
 
Returns: 42
It is not guaranteed that Elly has used a perfect strategy so far.
2)  
  
{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.
3)  
  
{500000000}
 
{133742666}
 
Returns: -1
There are multiple possibilities here, thus you should return -1.
4)  
  
{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
5)  
  
{42}
 
{42}
 
Returns: 84
Don‘t forget that the number Kris has thought of must be between 1 and 1,000,000,000.
6)  
  
{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

上一篇：<算法导论>学习笔记(3)--递归树求递归算法时间复杂度


下一篇：UVA - 1443 Garlands （二分+DP）