Coffee Crisis

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

problem header

Julie is studying a bachelor of computer science, and is gearing up for an insanely long semester with hellish workloads.

Her plan of attack for the coming twelve weeks is a frenzy of caffeine consumption, and luckily she knows just the barrista to help. Kyle is a special barrista, who only sells a single, special, coffee each day. Kyle's coffee has three characteristics:

  • Duration: How long the effects of the coffee last, in days.
  • Strength: How many assignments the coffee will allow you to complete in a day.
  • Caffeine Content: How much caffeine is in the drink, in tens of mg.

Every day, Kyle will also offer the standard coffee, which has 1 Duration, 1 Strength, and 1 Caffeine Content. To avoid over-dependence and eventually numbing the effects of the coffee, Julie has imposed the following rules:

  • She cannot drink one coffee while still receiving the effects of another coffee
  • If a coffee has x Caffeine Content, she will not drink another coffee for x days.

Within these bounds, deciding which coffee to drink on which days is stumping Julie, since she hasn't finished her algorithms unit yet. Can you help her complete as many assignments as possible?


Input will begin with two integers, D, the number of days in the semester, and N, the number of special coffees that Kyle will offer throughout the semester. Input will follow with N lines, containing 4 space separated integers:

  • T_i: the day on which coffee is sold (Days are indexed from 1)
  • D_i: the duration of the coffee.
  • S_i: the strength of the coffee.
  • C_i: the caffeine content.


Output should begin with a single integers, A, the number of assignments Julie can complete. The next line should contain N characters, each character a_i is either a * or -, representing whether Julie purchased the ith special coffee from input (Assume that Julie purchased the standard coffees where possible)


  • 1 \leq D \leq 10^9
  • 1 \leq N \leq 10^5
  • 1 \leq T_i \leq D
  • 1 \leq D_i \leq 10^9
  • 1 \leq S_i \leq 10^3
  • 1 \leq C_i \leq 10^9
  • All T_i will be unique

Example Run

For input

30 4
6 12 20 14
19 12 10 100
13 8 20 30
3 10 20 4

One possible output is:


Julie can complete 2+20x10+20x8 assignments buy drinking the standard coffee for 2 days, the special coffee on day 3, the special coffee on day 13. She cannot instead drink the special coffees on days 6 and 19, because there is too much caffeine in coffee 6. For a similar reason, she cannot drink the standard coffee from days 21-30.


  • 0
    OptimalBrainDamage  commented on Oct. 1, 2022, 11:40 p.m. edit 2

    _ignore this_

  • 0
    OptimalBrainDamage  commented on Oct. 1, 2022, 11:38 p.m.

    Just checking, are we supposed to assume that we don't buy a special coffee on a certain day, we're allowed to buy the standard coffee instead on the same day? I thought this wasn't the case because of this line "On days where Kyle isn't feeling too creative, he'll offer the standard coffee", but I just tried a submission the other way and it worked. Could I get some clarification on this?

  • 0
    Reply2019  commented on Oct. 1, 2022, 3:08 p.m.

    Hello, I have a problem about my submission. I can not submit the code. It occurs an error: "An internal error occurred while grading, and the MCPC administrators have been notified. In the meantime, try resubmitting in a few seconds.". I have been waiting 10 minutes. Hope you can help me! Thanks alot.

    • 0
      admin  commented on Oct. 1, 2022, 3:13 p.m.

      Hi, Please ensure your output contains 2 lines:

      • The number of assignments solved AND
      • The "punchcard" representation of which coffees you consumed.