The Cat in the Hat
| The Cat in the Hat |
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;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).
these are the cats that get the work done.
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
出處: UVa Online Judge - The Cat in the Hat
問題敘述
現在有貓咪進去一個房間，房間非常髒亂所以需要打掃，但是這個貓咪不想自己掃地，所以牠戴了頂帽子把別的小貓咪裝進去，要別的小貓咪打掃(好奸詐)。不過在帽子裡面的小貓咪可以再戴帽子裝更小的貓咪，一直裝到小到沒有戴帽子的貓咪就要打掃了(真可憐)。裝貓咪的過程有個數學規律在裡面，就是假設此貓咪的身高為 h，帽子可以裝的貓咪數量為 n，則帽子裡面的貓咪身高為 h / (n + 1)，最小的貓咪身高為1(即不能再戴帽子且要打掃的貓咪)。題目每組資料會輸入兩個整數，第一個整數為第一個貓咪的身高，第二個整數為最後要打掃的貓咪數量，要求您輸出兩個整數，第一個整數為沒有打掃的貓咪數量，第二個整數為所有貓咪的總身高為多少。解題思路
此題很明顯是數學題，首先我們把算式列出來:設 n 為帽子可以裝貓咪的數量、k 為某個非負整數、c 為最後要打掃的貓咪數量、h 為初始貓咪的身高，可以列出以下兩個式子
n ^ k = c
h * (1 / (n + 1)) ^ k = 1
先將兩個算式都取 log
k * log(n) = log(c)
k * log(n + 1) = log(h)
將上面的算式除以下面的算式可以得到以下
log(n) / log(n + 1) = log(c) / log(h)
接著我們只要找出 n 讓等式成立就可以知道帽子裡可以裝多少貓咪了。知道 n 之後剩下的工作就相當簡單了，可以依據以下算式求出沒在打掃的貓咪:
n ^ 0 + n ^ 1
c++ 程式碼
#include <iostream>
#include <cmath>
using namespace std;
int main() {
while (true) {
int initHeight, workCat, n, k, height;
double rightC;
int notWorkCat = 0;
int totalHeight = 0;
cin >> initHeight >> workCat;
if (!initHeight && !workCat)
break;
if (workCat == 1)
n = 1;
else {
rightC = log(initHeight) / log(workCat);
for (n=2;; n++) {
double leftC = log(n + 1) / log(n);
if (leftC - rightC <= 0.0000000001)
break;
}
}
k = round(log(initHeight) / log(n + 1));
height = initHeight;
for (int i=0; i<k; i++) {
int cats = pow(n, i);
notWorkCat += cats;
totalHeight += height * cats;
height /= n + 1;
}
cout << notWorkCat << " " << totalHeight + workCat << endl;
}
return 0;
}
![\begin{figure}
\centering
\setlength{\unitlength}{0.0125in} %
\begin{picture}
(2...
...raisebox{0pt}[0pt][0pt]{$\bullet
\bullet \bullet$ }}}
\end{picture}
\end{figure}](http://uva.onlinejudge.org/external/1/101img2.gif)
where n is the number of blocks) should appear followed immediately by a colon. If there is at least a block on it, the colon must be followed by one space, followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. Don't put any trailing spaces on a line.
dollars thus earning a profit of 6.4 percent.
) that can be purchased with one unit of the currency of country 1.
line of the conversion table (country i). The first integer in the sequence is the country from which the profiting sequence starts. This integer also ends the sequence.
(length, width, and height). In 6 dimensions it is, perhaps, unclear what the box (4,5,6,7,8,9) represents; but we can analyze properties of the box such as the sum of its dimensions.
such that each box 
nests in box 
( 
.
) nests in a box E = ( 
) if there is some rearrangement of the 
such that when rearranged each dimension is less than the corresponding dimension in box E. This loosely corresponds to turning box D to see if it will fit in box E. However, since any rearrangement suffices, box D can be contorted, not just turned (see examples below).
of 
such that ( 
) ``fits'' in ( 
for all 
.
line in the sequence ( 
) gives the measurements for the 
) figures descriptions, one per line. The first character will designate the type of figure (``r'', ``c'' for rectangle or circle, respectively). This character will be followed by values which describe that figure.
) rectangles descriptions, one per line. The first character will designate the type of figure (``r'' for rectangle). This character will be followed by four real values designating the x-y coordinates of the upper left and lower right corners.