首页 > ACM题库 > HDU-杭电 > HDU 1399 Starship Hakodate-maru-搜索-[解题报告] c-sharp
2013
12-09

HDU 1399 Starship Hakodate-maru-搜索-[解题报告] c-sharp

Starship Hakodate-maru

问题描述 :

The surveyor starship Hakodate-maru is famous for her two fuel containers with unbounded capacities. They hold the same type of atomic fuel balls.
There, however, is an inconvenience. The shapes of the fuel containers #1 and #2 are always cubic and regular tetrahedral respectively. Both of the fuel containers should be either empty or filled according to their shapes. Otherwise, the fuel balls become extremely unstable and may explode in the fuel containers. Thus, the number of fuel balls for the container #1 should be a cubic number (n^3 for some n = 0, 1, 2, 3, …) and that for the container #2 should be a tetrahedral number (n(n+1)(n+2)/6 for some n = 0, 1, 2, 3, …).

Hakodate-maru is now at the star base Goryokaku preparing for the next mission to create a precise and detailed chart of stars and interstellar matters. Both of the fuel containers are now empty. Commander Parus of Goryokaku will soon send a message to Captain Future of Hakodate-maru on how many fuel balls Goryokaku can supply. Captain Future should quickly answer to Commander Parus on how many fuel balls she requests before her ship leaves Goryokaku. Of course, Captain Future and her officers want as many fuel balls as possible.

For example, consider the case Commander Parus offers 151200 fuel balls. If only the fuel container #1 were available (i.e. if the fuel container #2 were unavailable), at most 148877 fuel balls could be put into the fuel container since 148877 = 53 * 53 * 53 < 151200 < 54 * 54 * 54. If only the fuel container #2 were available, at most 147440 fuel balls could be put into the fuel container since 147440 = 95 * 96 * 97 / 6 < 151200 < 96 * 97 * 98 / 6. Using both of the fuel containers #1 and #2, 151200 fuel balls can be put into the fuel containers since 151200 = 39 * 39 * 39 + 81 * 82 * 83 / 6. In this case, Captain Future’s answer should be "151200".

Commander Parus’s offer cannot be greater than 151200 because of the capacity of the fuel storages of Goryokaku. Captain Future and her officers know that well.

You are a fuel engineer assigned to Hakodate-maru. Your duty today is to help Captain Future with calculating the number of fuel balls she should request.

输入:

The input is a sequence of at most 1024 positive integers. Each line contains a single integer. The sequence is followed by a zero, which indicates the end of data and should not be treated as input. You may assume that none of the input integers is greater than 151200.

输出:

The output is composed of lines, each containing a single integer. Each output integer should be the greatest integer that is the sum of a nonnegative cubic number and a nonnegative tetrahedral number and that is not greater than the corresponding input number. No other characters should appear in the output.

样例输入:

100
64
50
20
151200
0

样例输出:

99
64
47
20
151200

#include <iostream>
using namespace std;

int flag,n;
int MAX;
int judge1(int n)
{
	flag=0;
	int i;
	for(i=0;;i++)
	{
		if(i*i*i==n)
		{
			flag=1;
			return i;
		}
		else if(i*i*i>n)
			return i;
	}
}

int judge2(int n)
{
	flag=0;
	int i;
	for(i=0;;i++)
	{
		if(i*(i+1)*(i+2)/6==n)
		{
			flag=1;
			return i;
		}
		else if(i*(i+1)*(i+2)/6>n)
			return i;
	}
}

void judge(int x,int y)
{
	int i,j;
	flag=0;
	MAX=-1;
	for(i=0;i<x;i++)
	{
		for(j=0;j<y;j++)
		{
			int x=i*i*i+j*(j+1)*(j+2)/6;
			if(x==n)
			{
				flag=1;
				return;
			}
			else if(x<n)
			{
				if(MAX<x)
					MAX=x;
			}
		}
	}
}
int main()
{
	int s1,s2;
	while(scanf("%d",&n),n)
	{
		s1=judge1(n);
		if(flag)
		{
			printf("%d/n",n);
			continue;
		}
		s2=judge2(n);
		if(flag)
		{
			printf("%d/n",n);
			continue;
		}
		judge(s1,s2);
		if(flag)
		{
			printf("%d/n",n);
			continue;
		}
		printf("%d/n",MAX);
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/xiaotaoqibao/article/details/5764591


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  3. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  4. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3