VM7WC '16 #5 Silver - Jayden Eats Chocolate

View as PDF
Submit solution
Points: 7
Time limit: 0.6s
Memory limit: 64M
Author:
JeffreyZ
Problem type

Jayden is a little kid that likes to eat chocolate. The enjoyment that he gets from eating chocolate increases exponentially depending on how many people eat it with him. Jayden has an infinite number of friends and he would like to share his chocolate with as many of his friends as possible.

The only thing that is more fun than eating chocolate is playing a game. The chocolate bar that he currently has is a 1 by N line of chocolate squares, and he decides to break up the entire bar into pieces of either X, Y, or Z consecutive squares to make this problem interesting, giving one piece to each friend. What is the highest number of friends that receive a piece of chocolate following these rules?

Input Specification

The first line will contain the positive integer N (1 \le N \le 10^5). The next line will contain the integers X, Y, and Z (1 \le X, Y, Z \le N). X, Y, and Z may share the same value.

Output Specification

On a single line, print the highest number of friends that can receive a piece of chocolate of X, Y, or Z squares. There will always be a valid answer.

Sample Input

13
3 9 4

Sample Output

4

Comments


  • 2
    rnpmat08_v2  commented on March 21, 2024, 11:44 p.m. ← edit 2

    can anyone explain why the strategy is not to split it into the smallest of x, y, z pieces? (ie. you take the smallest number out of x, y, z and then divide n by that number)

    edit: i understand now, you can't have leftover pieces that are not equal to x, y, or z. you must fully break the chocolate into pieces of size x, y, and z.


    • 2
      b_nary  commented on March 22, 2024, 12:03 a.m. ← edited

      "he decides to break up the entire bar into pieces of either X, Y, or Z consecutive squares"

      Let's say N = 31, X = 3, Y = 9, Z = 10. If you take the smallest (which is 3) and split it, you will have 10 pieces of 3, and 1 piece of 1 remaining. However, all the pieces must be of either size X, Y, or Z so this doesn't work (1 is not X, Y, or Z).

      Hope this helps :p


      • 0
        rnpmat08_v2  commented on March 23, 2024, 4:01 p.m. ← edited

        yeah i understand now, i thought it would be fine with the leftover piece of size 1. wording was kinda goofy


      • 0
        mart1n_dimitrov  commented on March 22, 2024, 8:56 a.m.

        I don't understand the condition, are we splitting every time by the same number for instance - 31 / 3 = 10 then 10 / 3 = 3 etc., or we can split by X once and then split by Y?


        • 0
          rnpmat08_v2  commented on March 23, 2024, 4:04 p.m.

          goal is to split the chocolate bar into as many pieces as possible, as long as each piece has size x, y, or z. this means that there can't be leftover pieces, so the strategy of dividing it into the smallest of x, y, or z could result in leftovers.


        • 1
          b_nary  commented on March 22, 2024, 9:52 p.m.

          You can split it the 1 by N chocolate bar however you want, as long as all the pieces are 1 by X, Y, or Z.

          for example, with a 1 by 10 chocolate bar, if X = 3, Y = 4, Z = 5:

          [_][_][_][_][_][_][_][_][_][_] (1 by 10 chocolate bar)

          the answer with be 3 pieces as we can split it into 1 by 3, 1 by 3, and 1 by 4.

          [_][_][_] | [_][_][_] | [_][_][_][_] (lines indicate splits)


  • 47
    1419903188  commented on Aug. 11, 2018, 9:48 a.m.

    Friends

    I wish I had an infinite number of friends, too. owo


    • -32
      puppy  commented on Nov. 23, 2019, 9:22 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.