洛谷 P2765 魔术球问题

简介: 题目描述 «问题描述: 假设有n根柱子,现要按下述规则在这n根柱子中依次放入编号为1,2,3,...的球。 (1)每次只能在某根柱子的最上面放球。 (2)在同一根柱子中,任何2个相邻球的编号之和为完全平方数。

题目描述

«问题描述:

假设有n根柱子,现要按下述规则在这n根柱子中依次放入编号为1,2,3,...的球。

(1)每次只能在某根柱子的最上面放球。

(2)在同一根柱子中,任何2个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在n根柱子上最多能放多少个球。例如,在4 根柱子上最多可放11 个球。

«编程任务:

对于给定的n,计算在n根柱子上最多能放多少个球。

输入输出格式

输入格式:

 

第1 行有1个正整数n,表示柱子数。

 

输出格式:

 

程序运行结束时,将n 根柱子上最多能放的球数以及相应的放置方案输出。文件的第一行是球数。接下来的n行,每行是一根柱子上的球的编号。

 

输入输出样例

输入样例#1:
4
输出样例#1:
11
1 8
2 7 9
3 6 10
4 5 11

说明

感谢 @PhoenixEclipse 提供spj

解题思路

  贪心明明可以,非要搞网络流……http://hzwer.com/1878.html

源代码

#include<stdio.h>
#include<math.h>
int n,i;
int a[100][100]={0},num=0;
inline bool judge(int x)
{
    int s=sqrt(x);
    return s*s==x;
}
int main()
{
    scanf("%d",&n);
    for(i=1;;i++)
    {
        bool flag=1;
        for(int pos=1;pos<=num;pos++)
        {
            if(judge(i+a[pos][a[pos][0]]))
            {
                a[pos][++a[pos][0]]=i;
                flag=0;
                break;
            }
        }
        if(flag)
        a[++num][1]=i,a[num][0]=1;
        if(num>n) break;
    }
    printf("%d\n",i-1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=a[i][0];j++) printf("%d ",a[i][j]);
        printf("\n");
    }
    return 0;
}

 

目录
相关文章
|
6月前
|
C语言
c语言编程练习题:7-22 用天平找小球
c语言编程练习题:7-22 用天平找小球
69 0
|
6月前
|
算法
算法刷题(二十二):宝石与石头
算法刷题(二十二):宝石与石头
64 0
蓝桥杯:2021省赛 例题:直线
蓝桥杯:2021省赛 例题:直线
50 0
|
21天前
|
存储 算法 C++
Leetcode第三十六题(有效的数独)
这篇文章介绍了如何使用C++编写一个算法来验证一个9x9数独是否有效,遵循数独的规则,即数字1-9在每一行、每一列和每个3x3宫内只能出现一次。
34 0
|
5月前
|
C语言
C语言----要喝10升水才能解渴,但现在只有一个深 h 厘米,底面半径是 r 厘米的水杯,牛牛最少要喝多少杯水才能解渴
C语言----要喝10升水才能解渴,但现在只有一个深 h 厘米,底面半径是 r 厘米的水杯,牛牛最少要喝多少杯水才能解渴
|
5月前
|
人工智能 程序员 定位技术
老程序员分享:NOIP2016天天爱跑步(树上差分)
老程序员分享:NOIP2016天天爱跑步(树上差分)
24 0
|
5月前
|
C++
【洛谷 P1428】小鱼比可爱 题解(循环)
这是一个编程竞赛问题,题目要求编写一个程序来计算每只鱼在其视野内看到的更不可爱的鱼的数量。给定鱼的总数`n`和每只鱼的可爱程度数组`a[]`,输出每个位置的鱼能看到的更不可爱的鱼的数量。 **摘要:** ```markdown 解决一个编程挑战,计算鱼在“比可爱”比赛中左边有多少条更不可爱的鱼。输入包含鱼的总数`n`和每条鱼的可爱度,输出每条鱼眼中更不可爱的鱼数。提供的C++代码通过遍历数组,比较每只鱼的可爱度并累计小于它的数量,然后输出结果。 ``` 这个摘要在240个字符以内,简要概述了问题的背景、任务和解决方案的概要。
50 0
|
6月前
【编程题-错题集】kotori和气球(组合数学)
【编程题-错题集】kotori和气球(组合数学)
|
12月前
|
Java
hdu1181 变形课(暴力搜索法)
hdu1181 变形课(暴力搜索法)
40 0