Connection Status:
Competition Arena > EqualizeBags

EqualizeBags

SRM 854 · 2024-04-24 · by misof

SRM 854 · 2024-04-24 · by misof · Greedy, Simple Math
Class Name: EqualizeBags
Return Type: String
Method Name: check
Arg Types: (int, vector<int>, int)
Problem Statement

Problem Statement

There are N bags of candy. The bags are numbered from 0 to N-1, inclusive. For each i, bag number i contains bags[i] pieces of candy.

You want to give the bags of candy to N kids. In order to do that, you need to make sure that each bag contains the same number of candies.

Before you give the bags to the kids, you want to eat some candies from the bags. More precisely, you would like to eat exactly E pieces of candy.


You are given the int N, the int[] bags and the int E. Determine whether it's possible to eat exactly E candies in such a way that after you are done eating, each bag contains the same number of candies. Return "possible" if it can be done and "impossible" if it cannot be done.

Notes

  • The return value is case-sensitive and must be all lowercase.

Constraints

  • N will be between 1 and 50, inclusive.
  • bags will have N elements.
  • Each element of bags will be positive.
  • The sum of all elements of bags will not exceed 10^9.
  • E will be between 0 and 10^9, inclusive.
Examples
0)
3
{5, 47, 5}
42
Returns: "possible"

If you eat all 42 candies from the middle bag (bag #1), you will be left with three bags containing 5 candies each.

1)
3
{5, 47, 5}
43
Returns: "impossible"

Regardless of how you eat 43 candies, the three bags won't be equal once you're done.

2)
3
{5, 47, 6}
43
Returns: "possible"

In this scenario you should eat 42 candies from bag #1 and one candy from bag #2.

3)
1
{47}
42
Returns: "possible"

If there's just one bag the condition "each bag contains the same number of candies" is always satisfied.

4)
1
{42}
47
Returns: "impossible"

There is no way to eat 47 candies in this scenario.

Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EqualizeBags with a public method string check(int N, vector<int> bags, int E) · 107 test cases · 2 s / 256 MB per case

Submitting as anonymous