注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4430  

2013-07-10 17:20:31|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4430
题意:
往蛋糕上放n支蜡烛,可以放r圈,第i圈上放k^i支,中心点处可以放也可以不放,问符合条件的r和k。如果有多种解法,取r*k较小的,如果还有相同的,去r小的。
题解:
枚举+二分。枚举r,因为n最大10^12,r最多枚举到40,然后二分k的结果,看是否有符合条件的k存在。

/*
* pro.cpp
*
* Created on: 2013-07-10
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const __int64 N=1000010;
const int M=1000010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const double eps=1e-7;
const double PI=acos(-1.0);


LL fun1(LL k,LL r,LL n)
{
LL s=0,t=k;
for(int i=0;i<r;i++)
{
s+=t;
if(s > n)
return N*N;//注意n最大到10^12, N需要注意下范围
t*=k;
}
return s;
}

LL fun(LL r,LL n)
{
if(r == 1)
return n;
LL mid,p,lef=2,rig=N;
while(lef <= rig)
{
mid=(lef+rig)/2;
p=fun1(mid,r,n);
if(p == n)
return mid;
if(n > p)
lef=mid+1;
else
rig=mid-1;
}
return -1;
}


int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
LL n,p,r,rr,rp;
while(scanf("%I64d",&n)!=EOF)
{
rr=N;rp=N;
for(r=1;r<=40;r++)
{
p=fun(r,n);
if(p!=-1)
{
if(r*p < rr*rp || (r*p == rr*rp && r < rr))
{
rr=r;
rp=p;
}
}

//中心可以放蜡烛也可以不放
p=fun(r,n-1);//看不放蜡烛是否符合条件
if(p!=-1)
{
if(r*p < rr*rp || (r*p == rr*rp && r < rr))
{
rr=r;
rp=p;
}
}
}
printf("%I64d %I64d\n",rr,rp);
}
return 0;
}


  评论这张
 
阅读(133)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018