Solution
UVa/11628 - Another lottery.c at master · morris821028/UVa · GitHub
I don’t understand why the answer depends only on the last round.
Thank you.
UVa/11628 - Another lottery.c at master · morris821028/UVa · GitHub
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
What about the case when no one wins the last round ? Won’t we have to judge based on all the other rounds ?
the number of tickets sold in each round is at least 1…so 1 person has to win