UVA 4855 Hyper Box
You live in the universe X where all the
physical laws and constants are different
from ours. For example all of their objects
are N-dimensional. The living beings
of the universe X want to build an
N-dimensional monument. We can consider
this N dimensional monument as an
N-dimensional hyper-box, which can be
divided into some N dimensional hypercells.
The length of each of the sides of
a hyper-cell is one. They will use some
N-dimensional bricks (or hyper-bricks) to
build this monument. But the length of
each of the N sides of a brick cannot be
anything other than fibonacci numbers. A
fibonacci sequence is given below:
1, 2, 3, 5, 8, 13, 21, . . .
As you can see each value starting from 3 is the sum of previous 2 values. So for N = 3 they can
use bricks of sizes (2,5,3), (5,2,2) etc. but they cannot use bricks of size (1,2,4) because the length 4
is not a fibonacci number. Now given the length of each of the dimension of the monument determine
the minimum number of hyper-bricks required to build the monument. No two hyper-bricks should
intersect with each other or should not go out of the hyper-box region of the monument. Also none of
the hyper-cells of the monument should be empty.
Input
First line of the input file is an integer T (1 ≤ T ≤ 100) which denotes the number of test cases. Each
test case starts with a line containing N (1 ≤ N ≤ 15) that denotes the dimension of the monument
and the bricks. Next line contains N integers the length in each dimension. Each of these integers will
be between 1 and 2000000000 inclusive.
Output
For each test case output contains a line in the format Case x: M where x is the case number (starting
from 1) and M is the minimum number of hyper-bricks required to build the monument.
Sample Input
2
2
4 4
3
5 7 8
Sample Output
Case 1: 4
Case 2: 2
题意: 给一个n维空间的的物体,给出每一维的长度。问有最少几个比它体积小的物体组成它,要求这些物体的边必须是斐波那契数列
里边的数。
思路: 假设边长是斐波那契数就无论他,假设不是,比这个边长小的最大的斐波数减起,一直减到0。减了几个斐波数。也就是这条边
最少分解成几个斐波数,最后每一维相乘即为结果。
#include<stdio.h>
#include<string.h>
int fb[60];
int main(){
int t,ok,n,cas=1;
int a[20];
fb[1]=1; fb[2]=2;
for(int i=3;i<55;i++)
fb[i]=fb[i-1]+fb[i-2];
scanf("%d",&t);
while(t--){
int cnt=0;
long long sum=1;//结果不用long long 会错
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%d",&a[i]);
for(int i=0;i<n;++i){
cnt=ok=0; int k;
for(int j=1;j<55;j++){
if(a[i]==fb[j]){
ok=2;
break;
}
if(a[i]<fb[j]){
ok=1;
k=j;
break;
}
}
if(ok==1){
int x=a[i];
while(x){
while(fb[k]>x)
k--;
x-=fb[k];
cnt++;
}
}
if(ok!=2)//ok==2时证明这条边是斐波数
sum*=cnt;//注意是相乘。,
}
printf("Case %d: %lld\n",cas++,sum);
}
return 0;
}
最新文章
- poj1142.Smith Number(数学推导)
- Tornado-简介
- java时间戳转date(转)
- CUBRID学习笔记 36 在net中添加多行记录
- CUBRID学习笔记 35 net驱动错误码和信息 cubrid教程示例
- 几个Unicode新知识:扩展ANSI有很多种(256个字符),Unicode表示ANSI字符时高字节为0,Unicode不包括古代字符
- L010-oldboy-mysql-dba-lesson10
- redhat 5.0 python2.4升级到2.7
- centos 下使用sublime
- (Problem 28)Number spiral diagonals
- ES6之Promise
- Spark算子篇 --Spark算子之aggregateByKey详解
- node编写定时任务,for循环只执行一遍的解决办法
- elk的备份与恢复【转】
- 轻量的web框架Bottle
- _npc
- jfixed使固定行列可编辑表格
- 重启 IIS7 应用或者应用程序池的批处理bat
- PHP进阶-网络编程基础概念
- POSTGRESQL 锁表的问题