Humble Numbers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 16312 Accepted Submission(s): 7082
Problem Description
A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... shows the first 20 humble numbers.
Write a program to find and print the nth element in this sequence
Write a program to find and print the nth element in this sequence
Input
The input consists of one or more test cases. Each test case consists of one integer n with 1 <= n <= 5842. Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line saying "The nth humble number is number.". Depending on the value of n, the correct suffix "st", "nd", "rd", or "th" for the ordinal number nth has to be used like it is shown in the sample output.
Sample Input
1
2
3
4
11
12
13
21
22
23
100
1000
5842
0
Sample Output
The 1st humble number is 1.
The 2nd humble number is 2.
The 3rd humble number is 3.
The 4th humble number is 4.
The 11th humble number is 12.
The 12th humble number is 14.
The 13th humble number is 15.
The 21st humble number is 28.
The 22nd humble number is 30.
The 23rd humble number is 32.
The 100th humble number is 450.
The 1000th humble number is 385875.
The 5842nd humble number is 2000000000.
题意:
也同样是找第 N 个丑数。质因子只允许是 2, 3, 5, 7。
思路:
与 USACO 那题一样。坑爹的地方在于输出,第1,2,3 个要输出 st,nd,rd。但是 11,12,13 却不用,判断的时候应该判断 n % 10 == 1 && n % 100 != 11 这样子判断。并且结果要离线处理好。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const ll INF = 5000000000; int p[5], f[5]; ll hum[6000]; void solve () { p[1] = 2, p[2] = 3, p[3] = 5, p[4] = 7; for (int i = 1; i <= 4; ++i) f[i] = 1; hum[1] = 1; for (int k = 2; k <= 5842; ++k) { ll Min = INF; for (int i = 1; i <= 4; ++i) { while (p[i] * hum[ f[i] ] <= hum[k - 1]) ++f[i]; Min = min(Min , p[i] * hum[ f[i] ]); } hum[k] = Min; } } int main() { solve(); int n; while (~scanf("%d", &n) && n) { printf("The %d", n); if (n % 10 == 1 && n % 100 != 11) printf("st "); else if (n % 10 == 2 && n % 100 != 12) printf("nd "); else if (n % 10 == 3 && n % 100 != 13) printf("rd "); else printf("th "); printf("humble number is %lld.\n", hum[n]); } return 0; }
相关推荐
Humble Numbers 一道简单DP题
ros humble的key
The Humble Programmer,当年图灵奖的演技录
1972图灵奖获得者Edsger W. Dijkstra讲稿
com.humble.SlayTheSpire.apk
Python脚本提取所有Humble键并自动在Steam上赎回它们。 这主要是设计成一种“设置后忘”的工具,可以最大程度地成功将密钥输入Steam,从而确保不会赎回Steam游戏。 该脚本将同时登录Humble和Steam,从而使整个过程...
Humble是一组松散耦合的工具,旨在使用go和构建客户端和混合Web应用程序。 Humble专为编写前端代码而设计,完全与后端无关。 您可以将Humble与以任何语言编写的任何后端服务器结合使用。 如果您确实选择同时编写...
如果使用Maven,则将Humble部署到Maven中央存储库。 要将其包含在您的项目中(请注意:这将包括所有操作系统的工件),请将其添加到pom.xml中: ... ... < groupId>io.humble < artifactId>humble-video-...
如果您有兴趣签出最新的书籍捆绑包(如果有),只需单击Humble Bundle主页顶部的“书籍捆绑包”标签。 例如常规捆绑包,将有多个层次。 顶层将显示可用于“按需支付”的内容。 下面是“超越平均水平”(绿色)层,...
从Humble Bundle库中下载所有内容! 第一次运行可能需要一段时间,因为它将下载所有内容。 之后,它将仅下载已更新或丢失的内容。 产品特点 支持Humble Trove (-- --trove标志) 每次运行时从您的Humble Bundle...
资源来自pypi官网。 资源全名:humble-0.1.2.tar.gz
Humble Key Restriction 描述 查看 Humble Bundle Key 的激活激活限制插件 它能帮你在 Humble 的 Download 界面显示 Key 的激活限制信息。 安装 安装 (推荐)、 或者其它用户脚本管理工具 安装脚本 就可以用啦 XD ...
做的很辛苦, 里面附有注释,大家支持一下吧...
从HUMBLE买的的unity开发进阶书籍慈善包,包含untiy性能优化,shader,C#,项目实例,企业增强现实项目,Unity认证程序员:考试指南等等。进阶高级开发必备书籍(但是注意一点,是全英文)
谦逊的 谦虚是一个简单的图形约简引擎。 我的意思很简单。 基本上是应用于图的规则列表。 规则使用我能想到的最简单的模式匹配算法,将其天真地转换为if语句。 规则可以延迟应用; 仅在最高级别,并且由规则决定,...
Humble Trove下载器 快速而肮脏的脚本,用于从下载适用于所有操作系统的所有游戏。 您需要订阅Humble Monthly才能下载这些游戏。 现有文件的md5校验和与Humble Bundle API报告的内容进行了比较。 如果不匹配,则...
Humble_Pal Humble Pal 通过自动化和跟踪扩展了 Humble Bundle 的功能。
谦虚捆绑(非官方)API只是Humble Bundle的非官方API为什么? 实际上有两个主要原因。 首先,可能也是最重要的一个,这是Telegram上的后端。 第二个原因是因为我想研究微服务,所以我将通道背后的逻辑分为模块,这...
hb下载器自动化实用程序,用于下载您的Humble Bundle产品 http://www.humblebundle.com该软件包未得到Humble Bundle,Inc.的认可,支持或关联。 它是根据MIT许可分发的,如果您同意该许可的条款,则可以免费使用,...
最基础的DP题目解题报告,适合初学者!动态规划(DP1) ...解题报告: 1001 计算直线的交点数 1002 FatMouse's Speed1003 Common ... 1006 免费馅饼 1007 Humble Numbers1008 Monkey and Banana 1009 龟兔赛跑 1010 数塔