MagicalSpheres
SRM 409 · 2008-07-10 · by slex
Problem Statement
Once upon a time, there lived a powerful wizard who created spheresCount magical spheres. These spheres, when connected together, were a source of unimaginable power. To prevent anyone else from using them, the wizard created fakeSpheresCount spheres that are indistinguishable from the real ones, but don't hold any magical power.
You are determined to find out which spheres are real, and use them to rule the world. To accomplish this, you want to gather a team of gnomes to try every combination of spheresCount spheres out of (spheresCount + fakeSpheresCount) spheres, even if it takes centuries. You will assign combinations to each gnome beforehand, and you will not test any combination more than once. Unfortunately, the gnomes have a labor union that won't allow some gnomes to have more work than others. Therefore, you must select a team size that will allow you to assign an equal number of combinations to each gnome.
Return the maximum possible team size less than or equal to gnomesAvailable that allows even distribution of the work.
Constraints
- spheresCount will be between 1 and 1,000,000,000, inclusive.
- fakeSpheresCount will be between 1 and 1,000,000,000, inclusive.
- availableGnomes will be between 1 and 100000, inclusive.
3 1 3 Returns: 2
We have a total of four spheres, lets call them {a,b,c,d}. We need to check all triplets to find which of them are real. The different triplets are: {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}. Since there are four possibilities to check, we can divide it between two gnomes, by assigning two to each of them.
3 3 50 Returns: 20
With three fake spheres, there are 20 triplets to check. You can use 20 gnomes and assign one of the triplets to each of them.
4 3 4 Returns: 1
15634 456 5000 Returns: 4990
1 1 1 Returns: 1
Submissions are judged against all 83 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MagicalSpheres with a public method int divideWork(int spheresCount, int fakeSpheresCount, int gnomesAvailable) · 83 test cases · 2 s / 256 MB per case