阿兹特克金字塔问题
Problem A. Aztec Pyramid
Input file: aztec.in
Output file: aztec.out
Time limit: 2 seconds
Memory limit: 256 megabytes
Aztec emperor Cuitl´ahuac is going to build a pyramid in his honor. This pyramid should be taller than
previous ones.
The Aztec pyramid is build out of stone blocks. Each block is 1×1×1-hunab cube. Cuitl´ahuac places
first block on the ground during the foundation ceremony. Each of the following blocks must share a face
with at least one of the previous blocks.
The block is stable if it stands on the ground, or it stands on another block, that has a block or the
ground next to each face. To stand the test of time the pyramid must be stable i.e. each block of it must
be stable.
Cuitl´ahuac asks you to determine the height of the tallest stable pyramid that can be built out of available
blocks.
Input
The only line of the input file contains a single integer number n — the number of available blocks,
including the first one (1 ≤ n ≤ 109).
Output
Output the height of the tallest stable pyramid that may be built out of n blocks. The height must be
output in hunabs.
Examples
aztec.in aztec.out
6 2
5 1
20 3
--------------------编程问答-------------------- 不知是否可以?
import java.io.*;
public class AztecCsdn
{
public static void main(String[] args)
{
try
{
long begin= System.currentTimeMillis();
BufferedReader br = new BufferedReader(new InputStreamReader(
new FileInputStream("aztec.in")));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(
new FileOutputStream("aztec.out")));
String s = br.readLine();
int blockNumber= Integer.parseInt(s); //从文件读入给定的砖块数。
CalculateLayers cl = new CalculateLayers(blockNumber); //生成用于计算的对象。
int layers = cl.getLayer();
System.out.println("aztec.in\ttaztec.out");
System.out.println(blockNumber+"\t"+layers);
bw.write(""+layers);
bw.flush();
br.close();
bw.close();
long end=System.currentTimeMillis();
System.out.println("use time ="+(end-begin)+"ms");
}
catch(IOException ioe)
{
ioe.printStackTrace();
}
}
}
//类CalculateLayers，创建对象时要给出砖块数。
//计算方法是：
//从第一层开始计算，每层最少需要的砖块数。如一层，一块就够；垒二层
//至少需要5+1=6块。
//层间砖块的数量关系是，每增加一层，砖块数是以前所有层的砖块数加上新加层的砖块数。
//每层的砖块数是上一层的砖块数加上 4*（层数-1）。（可画图看出规律）。
//类里用到的变量：
// layer 记录层数
// lastLayerNumber 当前层的砖块数。
// lastBlocks 所有层砖块的总数。
// 这些变量，每增加一层，都要更新。
class CalculateLayers
{
private int blockNumber; //给定的砖块数。
private int layer=1; //
private int lastLayerNumber=1; //保证第一层的砖数为1。
private int lastBlocks=0; //到这一层的砖块总数。
private int n=0;
//set get methods for blockNumber.
public void setBlockNumber(int blockNumber)
{
this.blockNumber=blockNumber;
}
public int getBlockNumber()
{
return blockNumber;
}
//constructors.
public CalculateLayers()
{
this.blockNumber = 1;
}
public CalculateLayers(int blockNumber)
{
this.blockNumber = blockNumber;
}
//method for getting the layer.
public int getLayer()
{
while(true)
{
n=cal(layer);
if(n<blockNumber) //垒layer层用砖数小于给定的砖数
{ //可以再垒。
layer+=1;
}
else if(n>blockNumber) //超过给定的砖数，不能垒了。
{ //返回可垒的数 layer-1.
return layer-1;
}
else //刚好可以垒layer层。
{
return layer;
}
}
}
public int cal(int layer)
{
int layerNumber=((layer-1)<<2)+lastLayerNumber; //计算出这一层的砖数.
lastLayerNumber=layerNumber; //保存这个数.
int total=layerNumber+lastBlocks; //总砖块数等于这层加上以前所有层的。
lastBlocks=total; //保存。
return total;
}
}
结果:
aztec.in taztec.out
1000000000 1144
use time =8ms
补充：Java , Java相关
