洛谷 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
|
5月前
力扣-2029-石子游戏-‘屎山’代码
力扣-2029-石子游戏-‘屎山’代码
42 3
|
6月前
【编程题-错题集】kotori和气球(组合数学)
【编程题-错题集】kotori和气球(组合数学)
|
6月前
|
C语言
|
Java
hdu1181 变形课(暴力搜索法)
hdu1181 变形课(暴力搜索法)
40 0
|
机器学习/深度学习 数据采集 人工智能
【每周一坑】杨辉三角形
了解完背景知识之后,来看看对应的题目,定义一个函数 yanghui() ,传入正整数参数 M、N,分别代表杨辉三角形第 M 行,左起第 N 个数字(M,N 都从 0 开始计算)。入超出范围则返回 invalid query 。
|
算法
算法创作|纸牌三角形
算法创作|纸牌三角形
67 0
|
机器学习/深度学习
剑指offer 13. 剪绳子
剑指offer 13. 剪绳子
73 0
|
小程序
做个经典宝石方块游戏
在做了一个月的进阶课程之后,终于又可以回来做游戏了。不得不说,对于我来讲做课程要比做游戏的难的多。做出来是一回事儿,讲出来又是另一回事儿了。尤其是还希望能讲的明白,讲的浅显易懂,感觉还是很难的。不过还好,做课程这件事情也是可以练习的,比如说我现在面对镜头讲一个东西的时候,就比一年前要好很多了。
136 0
【寒假每日一题】AcWing 4652. 纸张尺寸
目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
82 0