The Cat in the Hat
|
Source : UVA - V1 |
|
Time limit : 1 sec |
|
Memory limit : 32 M |
Submitted : 160, Accepted : 74
Background
(An homage to Theodore Seuss Geisel)
The Cat in the Hat is a nasty creature,
But the striped hat he is wearing has a rather nifty feature.
With one flick of his wrist he pops his top off.
Do you know what's inside that Cat's hat?
A bunch of small cats, each with its own striped hat.
Each little cat does the same as line three,
All except the littlest ones, who just say ``Why me?''
Because the littlest cats have to clean all the grime,
And they're tired of doing it time after time!
The Problem
A clever cat walks into a messy room which he needs to clean. Instead of doing the work alone, it decides to have its helper cats do the work. It keeps its (smaller) helper cats inside its hat. Each helper cat also has helper cats in its own hat, and so
on. Eventually, the cats reach a smallest size. These smallest cats have no additional cats in their hats. These unfortunate smallest cats have to do the cleaning.
The number of cats inside each (non-smallest) cat's hat is a constant, N. The height of these cats-in-a-hat is
times the height of the cat whose hat they are in.
The smallest cats are of height one;
these are the cats that get the work done.
All heights are positive integers.
Given the height of the initial cat and the number of worker cats (of height one), find the number of cats that are not doing any work (cats of height greater than one) and also determine the sum of all the cats' heights (the height of a stack of all cats
standing one on top of another).
The Input
The input consists of a sequence of cat-in-hat specifications. Each specification is a single line consisting of two positive integers, separated by white space. The first integer is the height of the initial cat, and the second integer is the number of
worker cats.
A pair of 0's on a line indicates the end of input.
The Output
For each input line (cat-in-hat specification), print the number of cats that are not working, followed by a space, followed by the height of the stack of cats. There should be one output line for each input line other than the ``0 0'' that terminates input.
Sample Input
216 125
5764801 1679616
0 0
Sample Output
31 671
335923 30275911
题目意思很麻烦。。我在网上搜了一下题意:
一隻神奇聰明貓走進了一間亂七八糟的房間,他不想自己動手收拾,他決定要找幫手來工作。於是他從他的帽子中變出了N隻小貓來幫他(變出來的貓,高度為原來貓的 1/(N+1) )。這些小貓也有帽子,所以每一隻小貓又從他的帽子中變出N隻小小貓來幫他。如此一直下去,直到這些小小小....貓小到不能再小(高度=1),他們的帽子無法再變出更小的貓來幫忙,而這些最小的貓只得動手打掃房間。注意:所有貓的高度都是正整數。
在這個問題中,給你一開始那隻貓的高度,以及最後動手工作的貓的數目(也就是高度為1的貓的數目)。要請你求出有多少隻貓是沒有在工作的,以及所有貓的高度的總和。
解题思路:
这个题,假设第一只猫每次可以分出q只猫出来。
并且总共分了n次。
那么
就有如下方程:
(1/h)=(1/(q+1))^n
w=q^n
直接解这个方程,是高次的,木有办法直接求出来。只能够用二分算法解。
解得q,n之后,剩下的非常好做了。两个都是等比数列求和就行了。
我的代码:
分享到:
相关推荐
若干百个,没细数,前几个下下来的有良心的回复一下帮我数数。
哈工大hoj1037,详细的源代码,附有注释,可以看懂。
在线OJ网址大全在线OJ网址大全在线OJ网址大全在线OJ网址大全
这是洛谷OJ题库导出文件,希望大家下载看看
OJ习题.zip
搭建OJ平台的工具,方便大家搭建自己的OJ,建议大家使用ubuntu14.04版本,比较稳定
西南科技大学OJ题答案西南科技大学OJ题答案西南科技大学OJ题答案西南科技大学OJ题答案西南科技大学OJ题答案
OJ系统的蓝桥杯题库,http://oj.xpuca.top/,这里有这些题的栗子。
湖南大学ACM-OJ的部分题目代码,对学习数据结构和算法很有帮助
这是大连东软信息学院的内部OJ题库,希望大家下载看看
这是聚石塔OJ题库导出文件,希望大家下载看看
oj 的c++类与对象之前包括类与对象的全答案
OJ基础部分代码 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 ...
HUSTOJ-SAE 安装次数 : 110 本系统为Online Judge 系统,可广泛用于教学、竞赛、招聘等用途。 九度OJ为本系统改造的典型案例。 文档、社区服务见项目首页,http://code.google.com/p/hustoj/ 安装应用 下载应用...
哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案
郑州轻工业大学在线评测系统(ZZULIOJ)部分答案。大一上学期自己做的,全部是c语言实现,不一定是最优解仅供参考。希望可以帮助到大家。
课程资源 杭电OJ1000-1099答案 ,仅供参考...
登录ssh,执行安装脚本:wget http://dl.hustoj.com/install-ubuntu-bt.shsudo bash install-ubu
很好的离线题库。。。。。 非常不错北大OJ题目