【COGS 396】[网络流24题] 魔术球问题

题目传送门：http://cogs.top/cogs/problem/problem.php?pid=396
离线版题目：http://paste.ubuntu.com/18780019/

贪心即可。因为枚举一下，1600以内，加上比自己小的数为完全平方数没有多解，所以只要能加，加上去就好
当然， 正解是最少路径覆盖+二分，然而为什么要闲得蛋疼写Dinic ╮(╯-╰)╭
另外，COGS的浮点运算取整是辣鸡QAQ，害的我wa了好几发……

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

const int MAXN = 10000;
const int MX = 1600;

int n,tot,arr[MAXN],vout;

inline bool judge(int num){
	for (int i=1;i<=tot;i++){
		int tmp = sqrt(arr[i]+num);
		if (tmp*tmp == arr[i]+num){
			arr[i] = num; 
			return true;
		}
	}
	if (tot < n) {arr[++tot] = num; return true;}
	return false;
}

int main(){  
	freopen("balla.in","r",stdin);
	freopen("balla.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=MX;i++)
		if (judge(i)) vout=i;
		else {printf("%d\n",i-1);break;}
	return 0;
}