How to solve Uva - 11628 - Another lottery?

Problem Link

Solution

https://github.com/morris821028/UVa/blob/master/volume116/11628%20-%20Another%20lottery.c

I don’t understand why the answer depends only on the last round.

Thank you.

participant wins 2i for every round
so if there are 2 participants and participant 1 wins all previous rounds and loses the m’th round, he would have lesser money
\sum_{i=1}^{m-1} 2i \lt 2m
hence choosing only the last is enough

1 Like

What about the case when no one wins the last round ? Won’t we have to judge based on all the other rounds ?

1 Like

the number of tickets sold in each round is at least 1…so 1 person has to win

2 Likes