Recaman's Sequence
Time Limit: 3000MS Memory Limit: 60000K
Total Submissions: 17939 Accepted: 7450
Description
The Recaman's sequence is defined by a0 = 0 ; for m > 0, am = am−1 − m if the rsulting am is positive and not already in the sequence, otherwise am = am−1 + m.
The first few numbers in the Recaman's Sequence is 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9 ...
Given k, your task is to calculate ak.
Input
The input consists of several test cases. Each line of the input contains an integer k where 0 <= k <= 500000.
The last line contains an integer −1, which should not be processed.
Output
For each k given in the input, print one line containing ak to the output.
Sample Input
7
10000
-1
Sample Output
20
18658
Source
POJ2081
比较值得注意的是数组中已存在的数不再放入数组中,而数组很大(0 <= k <= 500000),因此定义另一个数组来储存该数是否已存在,以此避免查找,减少运行时间。
#include<stdio.h>
int f[500001];
bool b[10000000] = {1, 0}; //一个足够大的数组来储存是否已存在
int main(){
f[0] = 0;
for(int i = 1; i < 500001; ++i){
int n = f[i - 1] - i;
if(n < 0 || b[n]){
n = f[i - 1] + i;
}
b[n] = 1;
f[i] = n;
}
int m;
while(scanf("%d", &m) && (m + 1)){
printf("%d\n", f[m]);
}
return 0;
}
=======================签 名 档=======================
原文地址(我的博客):http://www.clanfei.com/2012/04/445.html
欢迎访问交流,至于我为什么要多弄一个博客,因为我热爱前端,热爱网页,我更希望有一个更加自由、真正属于我自己的小站,或许并不是那么有名气,但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================
分享到:
相关推荐
poj两道题的c++实现。已经测试过可以通过oj
北大ACM在线评测系统POJ的题目非常之多,如果只盲目做题,恐难以各种类型题目考虑周全。此列表把各种题型做分类,按照此表可做针对性练习。献给所有愿意ACM刚入门的童鞋。。
北大ACM在线评测系统POJ的题目解题报告。涵盖各种类型的acm题目。值得参考借鉴。打包下载。
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
POJ上面题目的解题报告。涵盖挺多的。可作参考。代码都正确。ACM新手入门必下~~ 加油...
ACM PKU_poj 1197 仓库问题源代码,愿与大家共享。若谁更好的代码,多谢提供。
ACM_算法模板集史上最完整收藏版223页全免费版.pd
背包九讲2.0_算法_动态规划_ACM_
博弈论的经典入门书,适合于学习ACM的人或想学习写AI的人-Classic introductory book on game theory, ACM for learning to write the person or AI who want to learn 对于搞ACM/ICPC有很大帮助,里面涉及博弈论,...
在进行ACM编程训练时做字符串专题的一些题目(POJ1782,POJ1790,POJ1951,POJ2003,POJ2121)
杭电hdu acm资料所用杭电的acm题
ACM_算法模板程序设计协会ACM算法模板集ACM_算法模板程序设计协会ACM算法模板集ACM训练ACM集训算法入门参考手册
浙江大学ACM题解JU_ACM_All_Anwer,里面一本非常好的chm电子书,浙大的所有ACM题及题解都在了,对学习ACM的朋友非常的好~还等什么呢?
acm,动态规划类问题分析,并附有这些问题的详细代码
noi试题和解析,对于参加acm非常有帮助
ACM_基础篇
ACM_exercisecodeforOVaOJconnectingto算法竞赛入门训练指南.zip
Pascal acm_timus_ural_1148.pas
Pascal acm_timus_ural_1099.pas