[URI ONLINE JUDGE] – 1444 – Drakes’ Racing

Pirabeiraba is a district of Joinville, where german settlers installed themselves at the start of the 20th century. Annually there is the cassava party, a tuber that is also known as macaxeira in the brazilian northeast region. To accompany the cassava, there’s nothing like a traditional germanic dish: the stuffed drake! For the culinary experts, there is a magic in this combination: drake with cassava. However, to kill the drake, you must capture him while his blood is very warm. For that, the drake must be tired. People say that his warm blood is synonymous with fertility, in other words: an aphrodisiac! But that’s for another story.

In this game of chasing the drake, an idea came of tiring them with a race between themselves. The physical space of the Society Rio da Prata is limited, because of that they built only three lanes to do these races. The races are made with groups of two and three drakes. The drakes who gets the first places on the races are then arranged again in groups of 2 or 3 for another round. This goes on until there’s only one drake left, the champion, which escapes from the saucepan (for now) as a prize. All the survivingdrakes must race in the round, that is, if it’s not possible to split all the drakes in groups of three, some groups of two must be formed in order to minimize the number of races. Examples are seen in the Figure 1.

Figure 1: Examples: competition with 4, 5 and 6 drakes.

The losing drakes will be the first to go to the saucepan. You were invited to eat drake with cassava, but in exchange you must write a program that calculates the number of races that must be made to determinate the champion drake.

Input

The program input is composed by various test cases. Each test case is composed by a line containing an integer n, where 0 ≤ n ≤ 100,000, and where n = 0 is used solely to mark the end of the input, which must be disconsidered.

Output

Your program must print in the standard output a line per test case, containing the number of races needed to choose the champion drake.

Sample Input Sample Output
3
4
5
6
0
1
3
3
3

 

my solution:

very simple like this:

 

#include <stdio.h>
int main(int argc, char const *argv[]) {
int n, r;
while(scanf("%d", &n) && n != 0) {
r = 0;
while(n > 1) {
if(n % 3 == 0) {
r += n / 3;
n /= 3;
}else {
r += (n / 3) + 1;
n = (n / 3) + 1;
}
}
printf("%d\n", r);
}
return 0;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s