首页 > 试题广场 >

连线游戏

[编程题]连线游戏

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

某一天，Alice 比较无聊，于是她为自己发明了一个游戏玩。首先她在纸上画了一个圆，然后从这个圆的圆弧上均匀地取出 n 个点，这 n 个点将圆 n 等分。接下来，Alice 每次从这 n 个点中选取两个点，在这两个点之间画一条线段，但是要求这条线段不能与已有的线段相交 (允许在端点处相交)。为了能打发更多的时间，Alice 希望能画尽量多的线段，请你告诉她最多她能画出几条线段?

数据范围： $2 \le n \le 10^9 \$

输入描述:

第一行包含一个整数𝑛，表示从圆弧上取出的点数。

输出描述:

输出对应的答案。

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

牛客735570582号

#include <stdio.h>
#include <stdlib.h>
int func(int x)
{
    if(x<4)
        return 0;
    else if(x==4)
        return 1;
    else
        return x/2+func(x/2+x%2);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n<2)
            printf("0\n");
        else if(n==2)
            printf("1\n");
        else
        {
            printf("%d\n",n+func(n));
        }
    }
    return 0;
}

发表于 2021-08-20 21:57:30 回复(0)