KNIGHTSR - The Knights of the Round Circle

no tags 

A group of Jedi Knights is having a competition. One of the Knights at random stands within a circle. The other Knights, in a random order, challenge him. If a challenger de- feats the Knight of the Round Circle, that Knight must leave the contest. The challenger then becomes the new Knight of the Round Circle and, as such, will face all subsequent challengers until he is defeated. If the current Knight of the Round Circle wins the chal- lenge, he stays within the circle and the challenger must leave the competition. The Knight within the circle at the end of the competition is deemed the winer. You may assume that no two Knights have exactly the same skill and that a stronger Knight will always defeat a weaker Knight.

Suppose there are three Knights in the competition. If the strongest one happens to stand in the circle first, he will not be defeated, so no one will ever leave the circle. If the weakest one happens to be first in the circle, he will be kicked out after his first match. If th e Knight that defeated him was the strongest, he will win the final challenge as well (so only one Knight will ever leave the circle),otherwise the strongest Knight will kick the middle Knight out of the circle during his challenge (so that two Knights leave the circle). If the middle Knight stands in the circle first, he will be the only one kicked out of the circle, no matter what order the other two come at him. All in all, an average of 5/6 or 0.83 Knight will leave the circle during the competition.

You are to compute the average number of Knights to leave the circle during a competition given the number of Knights in the competition.


The input consists of several lines. Each line (but the last) will contain one positive decimal integer no larger than 10000. This integer is followed by exactly one . These integers represent the number of Knights in the competition. The last line will contain one zero, followed by . This line is not to be processed; it merely signifies the end of the input.


The output cases are to appear in the same order in wich they appear in the input. For each case, you are to print With c competitors, a Jedi Knight will be replaced approximately t times. c is the number of competitors in this case and should be a decimal integer. t is the average number of times a Jedi Knight leaves the circle and should be a floating point decimal number with exactly two digits following the decimal point. There should always be at least one digit before the decimal point (use 0.50 rather .50, for example) The statement should be followed by two ’s, wich is to say that a blank line should follow every output case.



With 3 competitors, a Jedi Knight will be replaced approximately 0.83 times.

With 1000 competitors, a Jedi Knight will be replaced approximately 6.49 times.

hide comments
Ouditchya Sinha: 2013-06-05 13:35:55

Piece of Cake! :)

Akshaya Gupta: 2013-05-28 15:15:27

nice one

Out0fbounds: 2012-10-13 23:05:26

very easy one.. my c++ sol had a total 7 line and 255 characters.. :P

unXled: 2012-06-25 07:51:10

typecasting costed me 2 compile error !
think in a dynamic way :)

data: 2012-06-24 21:26:00

easy one
try to think dif :)

Ponsamuel Mervin: 2010-11-24 14:45:41

if middle first, there are two possibilities:
strongest challenging first and win, then weakest challenging next and fails = 1,
weakest challenging first and fails and then strongest challenging next and wins = 1
In both cases only middle will be knocked out.
So (0+0)+(1+1)+(1+2) =5/6

A. Muh. Primabudi: 2010-10-28 04:23:08

is there anyone tell me, why 3 = 5/6?
strongest first = 0 leave.
middle first = 1 leave
weaker first = 1+2 leave
= 4/6?

Added by:Daniel Gómez Didier
Time limit:0.509s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:2007 U.Nacional - Circuito de Maratones ACIS / REDIS