Queue (Easy)
A group of people with heights is standing in a queue, with arbitrary order. They can see everyone in front (left) of them, until there is someone taller than them. For clarity, look at queue of 6 people :
The circle represents their height and the number below them indicates the number of people they can see.
Starting from the first person, you ask them the question "How many people can you see standing in front of you?" and note down their response. When you are going to trace back their heights, you noticed that some information is wrong! That is, it's not possible for the person to see that number of people despite the sequence of heights in the queue. Given the responses, find the first (leftmost) information that is wrong.
1 |
|
If you think that the person from the left is the one who gave wrong information, output your answer as 3. If all information are correct (possible to generate a sequence of heights), output your answer as 0.
The answer is 4.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The first person couldn't see anyone, so it must be 0 .
The second person must be taller than the first person, such that he can see 1 person in front of him.
The third person must be shorter than the second person, so he couldn't see anyone, hence 0 .
The forth person can only see 2 people, and that must include the third and the second person. The error follows, if the forth person can see the second person, then he must also be able to see the first person because the first person is shorter than the second person.
In conclusion, the answer is 4 .