12
$\begingroup$

There are a group of people standing in line for a taco stand. This taco stand is special in that it's slogan is "The older you are, the more you get!". To make sure though that there isn't any funny business, the owner of the stand has set up a few rules:

  1. Everyone standing in line will get at least 1 taco
  2. Each person can only see (compare) themselves to the person in front and behind them
  3. The owner wants to hand out as few tacos as possible

How does the taco stand owner decide how many tacos to give to each one such that all 3 rules apply.

Examples:

  1. For the following ages of the people in the line: 10, 20, 25, 36. The owner can hand out the following amount of tacos: 1, 2, 3, 4

  2. For the following ages: 10, 19, 25, 20. He can hand out: 1, 2, 3, 1

    Explanation: Since the last person in the line cannot see past the person in front of him, we can safely give him 1 taco and all rules apply.

Notes & Clarification: The taco owner can see the whole line and knows their ages. The people have lined up randomly and cannot be moved. There could be neighbours with the same age. Furthermore, Rule 2 means that, indeed, the taco owner is not as generous as one might think. If we focus on one person, then the following has to hold:

  1. If I am older than the person in front of me, I will get more tacos than him
  2. If I am older than the person behind me, I will get more tacos than him
  3. If I am younger than the person in front of me, he will get more tacos than me
  4. If I am younger than the person behind me, he will get more tacos than me

So the slogan is "localized" in a sense

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ No, there are four rules. The fourth is that no one can observe the "older people get more tacos" rule being violated. That should be explicitly be stated in the list of rules. $\endgroup$
    – Acccumulation
    Commented Nov 3, 2017 at 16:45
  • 2
    $\begingroup$ Yeah... The age rule really needs a clearer statement. As it stands the only statement of it is the slogan "The older you are the more you get!" but this is violated by the second example where the 10 and 20 year old both get one taco. I assume the interpretation is as Accumulation says that nobody can observe the slogan being incorrect but I shouldn't need to be assuming... $\endgroup$
    – Chris
    Commented Nov 3, 2017 at 16:48
  • $\begingroup$ Yes, you guys are right. Added some notes and clarification $\endgroup$
    – user475680
    Commented Nov 3, 2017 at 17:10
  • 3
    $\begingroup$ Since you know the ages of people on both sides of you, do you also need to take into account how many tacos they get compared to each other? Say I'm 23, the person in front of me is 24, and the person behind me is 25. Obviously I'll get the least of the three of us, but shouldn't the person behind me get more than the person ahead of me? $\endgroup$
    – DqwertyC
    Commented Nov 3, 2017 at 18:14
  • $\begingroup$ The one behind you would get more than you for certain, but can potentially receive less than/equal tacos to the one in front of you. This is because he can't see the one in front of you, he can only see in front and behind himself For example: 19, 24, 23, 25. The taco allocation that would fit this example is: 1, 2, 1, 2. $\endgroup$
    – user475680
    Commented Nov 3, 2017 at 23:06

3 Answers 3

Reset to default
11
$\begingroup$

I'll assume the owner knows all the ages in advance, but can't change the order. I'll also assume no two neighbors have the same age.

Find each person in line whose age is less than both neighbors. Give those people 1 taco. Then repeat the following procedure until everyone has tacos:
Find all people where all the younger neighbors have already been assigned numbers. Give them 1 more taco than the maximum of their younger neighbors.

This can be modified to handle people with the same age:

Treat each group of neighbors with the same age as a single person in the above. Then give each person in the group the same number of tacos.

If the order can be changed, the owner can

sort the customers and then interleave the first half with the second half. Then the customers just get 1-2-1-2-... tacos each.

If the owner doesn't know all the ages in advance, I don't think it's possible to do better than

giving each person tacos equal to their age.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Well, equal to their age less the age at which one can reasonably be expected to stand in line to buy tacos (this was a very young age for me) $\endgroup$
    – Strawberry
    Commented Nov 3, 2017 at 17:33
  • 3
    $\begingroup$ What of the scenario {21, 22, 23, 20, 25, 21}? This would result in each person getting {1, 2, 3, 1, 2, 1}. The 20yo would see that the 23yo got more than the 25yo, even if the rule was satisfied for the 20yo. $\endgroup$
    – David K
    Commented Nov 3, 2017 at 18:39
  • 3
    $\begingroup$ @DavidK See example 2 in the question. Customers don't care whether the people around them are treated fairly, they just want more tacos than their younger neighbors. That said, it's fairly easy to generalize this solution if we just look at the two people on either side. $\endgroup$
    – user27014
    Commented Nov 3, 2017 at 18:48
0
$\begingroup$

The first person in line gets 1 taco. From there increment 1 taco for everyone that is older than the person in front of them. If they are the same age as the person in front of them, give them the same amount of tacos. If they are younger than the person in front of them, reset to 1 taco.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ But if the first person in line is 30, and the second person is 20, then your method would give them both 1 taco. $\endgroup$
    – Acccumulation
    Commented Nov 3, 2017 at 16:50
  • 3
    $\begingroup$ Also, per @Accumulation 's comment, if you reset to 1 taco based on who is in front of someone, and the person behind them is younger, then this person (the "reset to zoro" guy) can see that he did not get more tacos than the person behind him. He only gets one, and so does the guy behind him. That violates the rules, doesn't it? $\endgroup$
    – user41655
    Commented Nov 3, 2017 at 17:21
0
$\begingroup$

The taco maker would make put all the people into groups(not physically but on a piece of paper or his mind) starting with the first person, where a group is defined as a row of people who follow a trend of that group of either inc and/or staying the same (i.e. if the ages were {15,20,22,22,25,27,27,30,30,30}), dec and/or staying the same (i.e. if the ages were {50,50,20,19,18,18,18,17,17,17,16}).

For example lets say we have 12 people in line {12,14,16,16,15,14,13,21,20,20,19,18} then groups would be the following G1 = {12,14,16,16}, G2 = {15,14,13}, and G3 = {21,20,20,19,18}.

Each group i, would have the following information attached to it: the ranking (R) of the Ages(where ties are given the same rank, in ascending order), the max rank(M) of the Ages,the trend (T) of the group i:decreasing(dec) or increasing(inc). So for the example above for i =1 you have G1 = {12,14,16,16}, R1 = {1,2,3,3}, M1 = 3, and T1 = Inc; G2 = {15,14,13}, R2 = {3,2,1}, M2 = 3, and T2 = Dec; G3 = {21,20,20,19,18}, R3 = {4,3,3,2,1},M3 = 4, and T3 = Dec.

NOTE: Now consider for a moment the individuals in a group x, with Tx = Inc. The last person in group x will have an individual after him that will be younger than him(if the person behind the last person in group x was the same age or older they would be included in the group. Also for a group y with Ty = Dec then the last person will have an individual after him that will be older than him.

Rules for giving out tacos for any Group i, with k being the total number of people in group i:

  1. If Ti is Inc and Ti-1 is Dec then the number of tacos person j will have is Rj +1 , else Rj; For j = 1 to k-1(first person in that group to the second to last person in that group) This is because if the group before hand has been decreasing then the last person in the group before hand would have had 1 taco, so the current group that is increasing will have the first person start out with 2 tacos. If the group beforehand was increasing then then the last person of the previous group would have been older than the first person of the current group, so the first person would start out with 1 taco.

  2. If Ti is Inc and Ti+1 is Dec and Mi+1 > Mi then the number of tacos person k will have is (Mi+1) + 1, else Rk; This is because if the next group is decreasing then to have the most efficient distribution of tacos in the decreasing group is to have the first person in the decreasing group to have M tacos, but since the last person of the current group will be older than the first person of the decreasing group, the last person in our group will need to have more than M tacos.

Following these rules makes sure that you keep giving the minimal amount of tacos while still satisfying the conditions.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.