Starship Hakodate-maru
Time Limit : 2000/1000ms (Java/Other)Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 3Accepted Submission(s) : 2
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
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.
Input
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.
Output
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.
Sample Input
Sample Output
Source
Asia 2001, Hakodate (Japan)
题意:
给你一个数n,判断在n之下,最大能够表示为k^3+m*(m+1)*(m+2)/6形式的数
思路:
先开始,枚举m,然后验证k是不是一个三次方的数,结果TLE了。
后来想了下,发现在验证3次方的这一步太花费时间,于是想到了用预处理
可以事先预处理一个数组,里面存上i^3,这样以后在查询的时候效率就大大提高
算法复杂度:O(n^(3/2))
我的代码:
分享到:
相关推荐
Verilog硬件描述语言编码风格 1. 文件头规定 // **************************************************************************** // Copyright (c) 2007, HDU ICCAD // ------------------------------------------...
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
6 5518491-A • HDU450-146J1FC 4∼128 S.P,NOTE.8 7 5518492-A • HDU450-72K1FC 4∼128 S.P,NOTE.9 8 2105845-1 • DUMMY CANISTER 0∼124 9 5513938-A • AC BOX(3 PHASE/30A) 2 S.P,NOTE.3 10 5513939-A • AC ...
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
杭州电子科技大学ACM Steps中Chapter One-Section Two的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
杭电acm解题报告 详细解析2000-2099 适合acm初学者
hdu-winter-2020 存放2020寒假hdu相关的训练,problems下存放集训的专题,contests下存放寒假比赛,包括七场PTA天梯训练赛 luogu 存放洛谷相关练习,problems下存放平时刷题,contests存放月赛题目 nowcoder 存放...
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
flutter_web_browser 一个flutter插件,可使用和打开网页。 此插件正在开发中,API可能会更改。入门安装从pub安装库: dependencies: flutter_web_browser: "^0.14.0"导入库import 'package:flutter_web_browser/...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
自己积累的部分杭电oj的(hdu)解题代码。。大家有空来看看。 基本上是自己写的哈。有错误之处请指教、
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
第一章 功能简介本章介绍HDU-EID-V2开发板的功能,使大家对该开发板的功能及特点有个基本了解。1. 处理器( MCU)HDU-EID-V2 开发板的处理器
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
杭电oj4405,一道简单的概率dp题目
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
很适合ACM初学者的文档, 题目,代码,解体思路一应俱全
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
题目连接 题意: 求一个有向图n个点 m 条边,是否是强连通分量,如果是输出Yes, 不是输出No. 数据范围 n < 10000, m < 100000 思路: Tarjan模板题 补习: ... Tarjan求有向图的强连通分量, ...