首页 > 试题广场 >

猜数

[编程题]猜数

热度指数：3990 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛和妞妞正在玩一个猜数游戏，妞妞心里想两个不相等的正数，把这两个正数的和y告诉牛牛。

妞妞声称这两个数都不超过x，让牛牛猜这两个数是多少。

牛牛每猜一次，妞妞会告诉他猜对了还是猜错了，猜对了就停止游戏，猜错了就直到牛牛猜对为止。
妞妞为了加大难度，有时会误报x的大小，如果牛牛可以判断出了这个x是错误的，就会直接询问妞妞答案。
牛牛最坏情况下要猜多少次才能猜到妞妞想的数呢？

输入描述:

两个整数x，y。1<=x,y<=10¹⁴。

输出描述:

一个数n，表示牛牛在最坏情况下猜测的次数。

示例1

输入

7 10

输出

示例2

输入

4 10

输出

算法知识视频讲解

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    long x,y;
    cin>>x>>y;
    if(x>=y)
        cout<<((y-1)>>1)<<endl;
    else{
        if((x<<1)<y)
            cout<<0<<endl;
        else
            cout<<x-(y>>1)<<endl;
    }
    return 0;
}

发表于 2019-08-19 23:04:22 回复(0)

pein531

有如下两种情况：

1.x有误的情况：如果2x<=y，则x肯定有误，因为两个不超过x的数相加是不可能等于y的。

2.其他情况又分为两种：

(1) x < y：如题中所给示例(7,10)，从x开始入手，尝试顺序为(7,3)->(6,4)->(5,5)->(4,6)->(3,7)，5个数对中有2个数对其实是重复的，排除相等的(5,5)，其实一共只需要尝试2次，2=5/2；如果将y改成11的话很明显就会多一次，因为奇数不存在两个相等数的情况。所以在这种情况下尝试的最多次数由x和y-x的差距决定（因为根据x入手拼凑数对时，一个数为x，另一个数为y-x），为[x-(y-x)+1]/2=(2x-y+1)/2。

(2) x > y：如果是这种情况，如(8,5)，就直接从y入手，尝试顺序为(4,1)->(3,2)->(2,3)->(1,4)，有2个数对是重复的，只需要猜2次，2=5/2，而将y改为6，偶数会有一次是两数相等的情况，应该排除，所以仍然是2次。在这种情况下尝试的最多次数由y决定，为y/2。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        long x = Long.parseLong(params[0]);
        long y = Long.parseLong(params[1]);
        if(2*x <= y){
            // 两个数都不超过x，加起来是不可能为y的
            System.out.println(0);
        }else{
            if(x < y){
                if(y % 2 == 0)
                    System.out.println((2*x - y) / 2);
                else
                    System.out.println((2*x - y) / 2 + 1);
            }else{
                System.out.println(y / 2);
            }
        }
    }
}

发表于 2021-02-25 20:53:18 回复(0)

Python

LitterF

想了半天没明白为啥 7 10 答案是2 而不是5。

最后终于看见了题干要求不相等的两个正数。。。

算一下上下边界就行了。

可能性就是

1 9

2 8

3 7

4 6

5 5

……

可行域范围满足a,b<=7。直接数a，从1数到x。

那就是左边的数字a从1数但要满足b = y-a<=x.

则a的下界为max(1,y-x)。

最多数到x，此时得到上界，为x，但不能超过y，因此是min(x,y)

还要把存在相等情况去了，比如a=b的情况。

去完后还要除以2，我佛了。因为这里不要求顺序，1 9和9 1是一种情况，搞笑。

x,y = [int(x) for x in input().split()]
left = max(1,y-x)
right = min(x,y)
times = right - left + 1
if y%2==0:
    times-=1
times = (times)//2
if times<0:
    times = 0
print(times)

发表于 2019-11-30 21:20:27 回复(0)

C/C++

昔遥暮云

#include <bits/stdc++.h>
using namespace std;
int main(){
    long x,y;
    cin>>x>>y;
    if((x<<1)<=y)
        cout<<0;
    else {
        long t = x>=y ? 1:y-x;
        cout<<((y+1)>>1)-t;
    }
    return 0;
}

发表于 2019-11-15 17:14:53 回复(0)

。。。。201904011633820

var arr = readline().split(' ');

var x = parseInt(arr[0]);

var y = parseInt(arr[1]);

var i = 0;

if(x >= y/2){

if(x >= y){

x = y - 1;

}

i = x - Math.floor(y/2);

}

print(i);

发表于 2019-09-03 19:16:36 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long x,y;
    cin>>x>>y;
    if(x*2<y)
    {
        cout<<0<<endl;
        return 0;
    }
    long long high, middle, num = 0;
    if(x>=y)
    {
        high = y - 1;
        middle = y/2;
        num = high - middle;
        if(y%2==0)
            num = num + 1;
    }
    else
    {
        high = x;
        middle = y/2;
        num = high - middle;
        if(y%2==0)
            num = num + 1;
    }
    cout<<num<<endl;
    return 0;
}

发表于 2019-07-17 18:44:14 回复(0)

Java

lmz9509

/*
假设两个数时a,b
想法：首先当2*x<y的时候，这个x就是错的，直接输出0
然后判断x与y的大小关系，当x<Y时，这时候a,b，就是根据x来变化的，a取值最大为x，b起始位y-x,递减，b递增
当y<x的时候，a,b就是依据y来决定，a最大为y，b起始位0

示例： 7 10
a    b
7    3
6    4
5    5
后面是重复的

示例：8    5
a    b
5    0
4    1
3    2
后面是重复的

这个规律我们发现只需要用(x-(y-x)+1)/2或者y/2就可以得到最坏的次数

*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        long x = Long.parseLong(str[0]);
        long y = Long.parseLong(str[1]);
        if(x*2<y){
            System.out.println(0);
            return;
        }
        if(x<y)
            System.out.print((x-(y-x)+1)/2);
        if(y<=x)
            System.out.print(y/2);
    }
}

发表于 2020-05-07 12:43:41 回复(1)

呼延棋大宝

x , y = map(int,input().split())

if y > x:
    if x <= y//2:
        print(0)
    else:
        print( x - (y//2) )
else:
    print(y//2)

发表于 2023-04-15 17:34:51 回复(0)

Php

牛客84670037号

<?php
/*
 *n1+n2 = $y
 *n1|n2 <= $x
 *n1!=n2
*/
function a($x, $y){
	// 判断x是错误的
	if ((2*$x-1) < $y) {
		return 0;
	}
    
    // 如果x > y 则重置x为y-1
    if($x>$y){
        $x = $y-1;
    }
    
	$a1 = $y/2; // 取中间值
	$a2 = $y%2; // 取余

    return $a2 ==0 ? $x-$a1: ($x-$a1)+0.5;
}
if(fscanf(STDIN, "%d %d", $a, $b) == 2){
    echo a($a,$b);
}

发表于 2022-05-24 18:00:06 回复(0)

C++

桃椰鲜奶冻

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long x, y;
    cin >>x>>y;
    if(x>=y) cout<<(y-1)/2<<endl;
    else
    {
        if(x<y/2) cout <<0<<endl;
        else cout <<x-y/2<<endl;
    }
    return 0;
}

发表于 2021-07-17 09:14:28 回复(0)

爆炸玉米花

x,y=map(int,input().split())
if 2*x<y:
    print(0)
else:
    if y%2==0:
        print(min(abs(y//2-x),y//2-1))
    else:
        print(min(abs(y//2-x),y//2))

发表于 2021-03-29 10:05:35 回复(0)

华科菜菜子

#include<iostream>
using namespace std;
int main()
{
    long long x,y;
    while(cin>>x>>y)
    {
        if(x>=y)
            cout<<(y-1)/2<<endl;
        else
        {
            if(x<=y/2)
                cout<<0<<endl;
            else
                cout<<x-y/2<<endl;
        }
    }
    return 0;
}

发表于 2020-11-23 15:05:24 回复(0)

202102

let [x,y] = readline().split(" ")
x=parseInt(x)
y=parseInt(y)
let t=0
if(x>=y){
    x=y-1
}
if(x>=y/2){

    t=x-Math.floor(y/2)
}
print(t)

发表于 2020-09-03 15:09:38 回复(0)

墨凌飞

#include <iostream>
using namespace std;

int main()
{
    long long x;
    long long y;
    long long a;
    long long b;
    cin >> x;
    cin >> y;

    //if x error
    if(y > 2*x || y < 2 || x < 1)
    {
        cout << 0 << endl;
    }
    else
    {
        //x 比 y大也是一种符合要求的情况，即不重复的所有结果
        if(x >= y)
            x = y - 1;
        //所有结果数，去除a == b
        long long totoalReslut = (y - 1) / 2;
        //去除过大或过小的非结果成分
        long long notResult = y - (x + 1);
        //结果
        long long reslut = totoalReslut - notResult;
        cout << reslut << endl;
    }

    return 0;
}

发表于 2020-06-25 14:58:50 回复(0)

夏花爱秋叶

var line=readline().split(' ').map(Number);
var max=line[0];
var sum=line[1];
// 表示较小的x
if(sum>max){
    var left=sum-max;
}else{
    // 给定的不超过的值太大了，和为5，每个数不超过8，这样的话就重设置max
    max=sum-1;
    var left=sum-max;
}

// 表示较大的x
var right=max;
// 此时就是说谎了
// 两个数不能相等
if(left>max||left==right||left>right){
    console.log(0)
}else{
    var tem=Math.ceil((right-left)/2);
    console.log(tem)
}

发表于 2020-04-08 20:23:26 回复(0)

系咁啊啦

#include <stdio.h>
int main() { 
  long long x, y;
  scanf("%ld %ld", &x, &y);

  long long n = y / 2 + 1;
  x = x > y - 1 ? y - 1 : x;
  long long ret = x - n;
  printf("%ld\n", ret < 0 ? 0 : ret + 1);

  return 0;  }

编辑于 2019-08-01 21:52:30 回复(0)

JavaScript

我教枣子简灯笼

while(line=readline()){
  line=line.split(" ")
  let x=parseInt(line[0]);
  let y=parseInt(line[1]);
  
  if(x>=y){
    print(Math.floor((y-1)/2));
  }
  
  else{
    if(y>2*x){
    print(0)
  }
    else{
      let max=Math.max(x,(y-x));
  let min=y-max
  print(Math.floor((max-min)/2)+1);
    }
    
  }
  
}

感觉在写高中数学。。。

以a b为坐标轴建立坐标系直线a+b=y 和 a=x b=x 交于 i j 两点（i<j）

即f(a)=-a+y 在[i,j]上的取值组合为答案的可行解。

分情况讨论：

1. 当x>=y 的时候

因为x>=y 所以x没什么卵用一定可以推出正确答案

i 和 j为a+b=y 与坐标轴的交点此时只需要剔除可行解中a=0 b=0（a b为正数）和a=b的时候的组合然后除以2（部分可行解对称）的情况便可。

2.当y>2x 的时候

明显x是错的输出0

3.当想x<y<2x的时候

剔除可行解中a=0 b=0（a b为正数）和a=b的时候的组合然后除以2（部分可行解对称）的情况便可。

发表于 2019-08-01 18:01:37 回复(0)

提交观点

问题信息

前端工程师穷举 2019 百度数学

上传者：小小

难度：

17条回答 32收藏 5518浏览

通过挑战的用户

查看代码

牛客37643...

2022-09-13 14:04:17
牛客49143...

2022-09-13 00:30:10
越努力越晦气

2022-09-11 10:01:20
牛客63220...

2022-08-30 17:39:58
牛客44030...

2022-08-30 03:05:37

猜数

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题