Mock CCC '15 S1 - Dupvoting

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types

2015 Mock CCC by Alex and Timothy

Currently, one of the most popular social news websites is seddit. On seddit, one user can submit a link to content while other users can say things in the comments. A great news aggregator like this is community-driven. Naturally, it employs a system where users can review and rate content. Many websites, including seddit, use a voting system where each user can give a submission either an upvote (worth +1 point) or a downvote (worth -1 point). The score of a submission is therefore the total points across all users who have voted on it.

Recently, seddit is trying a new system where a new "dupvote" button is introduced. It's simple, really — if an upvote contributes +1 to the net score of a submission, then a dupvote simply contributes +2 to the net score. The downvote button still works as expected. This system will allow users to express support for quality content that's really exceptional.

As an avid user of seddit, you really enjoy this new system, but you are unsatisfied with one aspect of the site. For a given post, the site displays its net points P (-2\,000 \le P \le 2\,000) and the number of users U (3 \le U \le 1\,000) that have voted on the content. However, you have no idea what ratio of these votes are dupvotes, upvotes, or downvotes.

The hacker in you decided to analyse the site's JavaScript. To your amusement, you've discovered a little bug which allows you to see a simple ratio R1:R2 (1 \le R1, R2 \le 1\,000) for each post. You know that this is a ratio of two of the values in the number of dupvotes, upvotes, and downvotes, but you don't know anything about which two. For a given post, you would like to calculate all possible triplets for the number of dupvotes, upvotes, and downvotes that could make up the total net points for that post.

Input Specification

Line 1 of input will contain a single integer P, the net points on the post.
Line 2 of input will contain a single integer U, the number of users that have voted.
Line 3 of input will contain a single integer R1, the first number in the ratio.
Line 4 of input will contain a single integer R2, the second number in the ratio.

Output Specification

Output a single integer, the number of possible combinations of dupvotes, upvotes, and downvotes that can result in a net score of P points on the post. It is guaranteed that all three of these values are positive.

Sample Input


Sample Output


Explanation of Sample

The net score on the post is +2 as a result of 5 users voting. It is guaranteed that a ratio of 2:1 exists between either the dupvotes and upvotes, dupvotes and downvotes, or upvotes and downvotes. If there is 1 dupvote, 2 upvotes, and 2 downvotes, then the net score would be +2 and the ratio of upvotes to dupvotes would be 2:1. In fact, this is the only solution.


  • 0
    frankvp11  commented on Sept. 21, 2022, 4:33 p.m.

    Hi! I tried to submit but I got an error. When I tried it on my compiler it compiles and runs just fine. Also if you are going to look at it, can you tell me if my solution is correct?

  • 1
    QWERTYL  commented on April 2, 2022, 9:04 p.m.

    For those who can't get test cases 3, 4, and 5, take a careful look at the output specification.

  • 0
    LOLWHATOMGBBQ  commented on Feb. 15, 2015, 2:59 p.m.

    Is R1 and R1 guaranteed to be coprime of each other .

    • 0
      LOLWHATOMGBBQ  commented on Feb. 15, 2015, 2:59 p.m.


      • 2
        FatalEagle  commented on Feb. 15, 2015, 3:10 p.m.

        Don't assume anything not explicitly stated.