UVA 107 The Cat in the Hat

The Cat in the Hat

题面翻译

帽中之猫
（向Theodore Seuss Geisel致敬）

译者注释： 此人为美国著名的作家和漫画家，其儿童绘本最出名。A Cat in a hat是其作品名

帽中之猫是一个让人讨厌的生物。

但是它戴的条纹帽却相当的漂亮。

猫轻轻挥了挥手臂，它的帽子就弹了出来。

你知道它帽子里有什么吗？

是一群小猫，每个小猫也都有自己的条纹帽。

你知道它帽子里有什么吗？

是一群小猫，每个小猫也都有自己的条纹帽。

…(无限递归)

但是最小的猫，它会说“为什么是我？”

因为最小的猫必须清理房间里所有的脏，让它们烦躁的是，每次都是它们来干活。

一只聪明的猫走进了他需要清理的房间里，但是它没有干活。

因为它决定让它帽子中的助手猫来做这件事，它的帽子里有小猫来当它的助手，每个助手猫的帽子也有自己的助手小猫………直到最小的猫没有了它的助手小猫，而且这些最小的猫得来打扫。

正文
每个（不是最小的）猫的帽子内，猫的数量是一个常数N。这些猫的身高是它们所在的帽子的高度的1/n+1倍。

已知最小的猫的身高为1，并且它们就是在干活的猫猫，并且所有的（猫的）身高都是正整数。

给出一开始的猫的身高，和干活的猫的数量（身高为1），找出没有做任何工作的猫（高度大于1的猫）的数量，也求出所有猫的高度（所有猫站在另外的猫的所有猫的高度）的总和。

输入
包含多组数据输入，每个第一个整数是一开始猫的高度，第二个数是工作的小猫的数量。空格隔开。

0 0 表示结束输入

输出
对于每个输入（帽中之猫要求），输出多少只猫没有在打扫，空格隔开，之后是初始猫的帽子中的所有猫的高度。对于每个输入，占据单独一行。

‘0 0’　除外。

Translated by @paizhang @Himself65

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

216 125
5764801 1679616
0 0
1
2
3

样例输出 #1

31 671
335923 30275911
1
2

代码

#include

using namespace std;

const double eps=1e-10;

int h,m;

double n,k;

int main()
{

	while(cin>>h>>m)
	{
		if(h==0&&m==0)
		{
			break;
		}
		
		n=1.0;
		
		while(fabs( log(n)/log(m) - log(n+1)/log(h) )>=eps) 
		{
			n++;
		}
		
		k=int (log(h) / log(n+1)+0.5);
		
		if((int) n==1)
		{
			cout<<k<<" "; 
		}
		else 
		{
			cout<<int (0.5+(1-pow(n,k))/(1-n))<<" ";
		}
		
		cout<<int (0.5+(1-pow(n/(n+1),k+1))*(n+1)*h)<<"\n";
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43