首页 > 试题广场 >

冰冻青蛙

[编程题]冰冻青蛙
  • 热度指数：442 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}在女仆长紧张修建红魔馆的同时，雾之湖附近却也不安宁。
\hspace{15pt}在雾之湖的岸边，有 n 只青蛙排成一排，编号依次为 1 到 n。冰之妖精琪露诺（⑨）和她的好朋友大妖精正在练习冰冻魔法！每一轮施展魔法的规则如下：
\hspace{23pt}\bullet\,如果一个青蛙的编号为 x，满足 \gcd(x,\underbrace{999\,999\,999}_{9 \text { 个 } 9})\neq 1，则可以一次性冻结它以及它左右相邻的青蛙（如果存在）；
\hspace{23pt}\bullet\,被冻结的青蛙可以再次被选中并冻结。
\hspace{15pt}现在，你作为琪露诺的好朋友大妖精，可以提前帮助琪露诺，将这些青蛙进行重新排序。如果排序后可以使得琪露诺通过施展任意多次魔法、最终冻结所有的青蛙，她会夸你和她一样聪明。否则，琪露诺会气呼呼的说你是 \textrm{Baka!}。当然，你也需要骂回去。

\hspace{15pt}\gcd，即最大公约数，指两个整数共有约数中最大的一个。例如，12 和 30 的公约数有 1,2,3,6，其中最大的约数是 6，因此 \gcd(12,30)=6。‌

输入描述:
\hspace{15pt}在一行上输入一个整数 n \left(3 \le n \le 10^5\right) 代表青蛙数量。


输出描述:
\hspace{15pt}如果不存在任何一种排序，使得琪露诺可以冻结所有青蛙，直接输出 \textrm{Baka!}。否则，在一行上输出 n 个不同的整数 a_1,a_2,\dots,a_n \left(1\leq a_i \leq n\right)，代表重新排序后的青蛙编号。

\hspace{15pt}如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
示例1

输入

3

输出

1 3 2

说明

\hspace{15pt}在这个样例中，\gcd(3,999\,999\,999)=3，所以琪露诺可以冻结第二只青蛙，这会一并使得第一只和第三只青蛙被冻结。因此，琪露诺可以冻结所有青蛙。
示例2

输入

4

输出

Baka!
算法知识视频讲解
添加回答
C++
Minajka头像 Minajka
#include <iostream>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
    while (b != 0) {
        ll temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main()
{
    int n;cin >> n;
    if(n % 3 == 0)
    {
        for(int i = 2;i <= n;i++) cout << i << " ";
        cout << 1;
    }
    else
    {
        if(n < 37) cout << "Baka!";
        else
        {
            for(int i = 2;i <= 36;i++)
            {
                cout << i << " ";
            }
            cout << 1 << " ";
            for(int i = 38;i <= n;i++) cout << i << " ";
            cout << 37;
        }
    }
}
发表于 2026-01-20 10:54:03 回复(0)
提交观点

问题信息

难度：
1条回答 61浏览

热门推荐

相关试题

冰冻青蛙

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号