BalancedGame
SRM 254 · 2005-07-26 · by Enogipe
SRM 254 · 2005-07-26 · by Enogipe · Simple Math, Simple Search, Iteration
Problem Statement
Problem Statement
You will be given a String[] , conflicts, where each element represents a single player in a multiplayer game. Element i represents player i, and character j of element i represents whether player i will win ('W'), tie ('T'), or lose ('L') against player j.
Your task is to ensure that each player wins against at least p% of the other players, and loses against at least q% of the other players. You should return the 0-based index of the first player in the input (lowest index) that does not meet these requirements, or -1 if all players meet them. Note that if there are N players total, then at least ceil((N-1)*p/100) of the characters in element i must be 'W' for player i to meet the requirements. The formula for losses is analogous.
Your task is to ensure that each player wins against at least p% of the other players, and loses against at least q% of the other players. You should return the 0-based index of the first player in the input (lowest index) that does not meet these requirements, or -1 if all players meet them. Note that if there are N players total, then at least ceil((N-1)*p/100) of the characters in element i must be 'W' for player i to meet the requirements. The formula for losses is analogous.
Notes
- The i-th character of the i-th element of conflicts will always be 'T' and can be ignored.
- The function 'ceil' in ceil((N-1)*p/100) returns the least integer greater than or equal to its argument. For example, ceil(1.5)=2 and ceil(4)=4.
Constraints
- p and q will be between 0 and 100, inclusive.
- conflicts will have between 2 and 50 elements, inclusive.
- Each element of conflicts will have the same number of characters ('W', 'L' and 'T') as the number of elements in conflicts.
- If the j-th character of the i-th element of conflicts is 'W', 'L', or 'T' then the i-th character of the j-th element will be 'L', 'W' or 'T' respectively.
- The i-th character of the i-th element of conflicts will always by 'T'.
Examples
0)
{"TWWW",
"LTWW",
"LLTW",
"LLLT"}
20
20
Returns: 0
Player 0 cannot lose and player 3 cannot win, so these players are not balanced. Return the lowest index of an unbalanced player.
1)
{"TWWW",
"LTWW",
"LLTW",
"LLLT"}
0
0
Returns: -1
Now there are no balancing constraints, so even though player 0 cannot lose and player 3 cannot win, the characters are balanced.
2)
{"TTT",
"TTT",
"TTT"}
1
1
Returns: 0
Even with such lax balancing constraints, a perfectly matched set of characters is not balanced in the sense we are looking for.
3)
{"TWWTTWWLWWWWLWWWLTLL","LTWLTTLLLWLLTLWLLWLW","LLTWLLTWWWLTLLTWLWWW","TWLTLLWLLTWLLLWWTLLT","TTWWTTLTWTTWTWWLTLWW","LTWWTTWWWWWWWLLTLTLL","LWTLWLTWLLTLWTLWTTLT","WWLWTLLTWLWLTWLWLWWL","LWLWLLWLTLLLWWWWLLTT","LLLTTLWWWTWWLWWLLLLW","LWWLTLTLWLTWLLWLWWTW","LWTWLLWWWLLTLWWWLWTW","WTWWTLLTLWWWTWLTLTTT","LWWWLWTLLLWLLTWLWLLW","LLTLLWWWLLLLWLTLLLWL","LWLLWTLLLWWLTWWTWWWW","WWWTTWTWWWLWWLWLTLWL","TLLWWTTLWWLLTWWLWTWW","WWLWLWWLTWTTTWLLLLTL","WLLTLWTWTLLLTLWLWLWT"}
5
10
Returns: -1
4)
{"TLWWLWLTTLWWWTWWTTWLWWLLWLWLWWLWLWT","WTWWWWTLWLLLWTTLWWWWTWWTLLWLTWLLWWW","LLTWWWWWWTTLLLWWWLLWLLWWWLLLWWTWLTT","LLLTWWWLTLLWWWLWWLWTTWWTLLWLLTWTLWT","WLLLTTWTTWWLTLWTTWLLWTLWWTLWWWWLLWT","LLLLTTLTWWLLWTLTLTTWWWWTWWWLTTWWWWW","WTLLLWTWWLWWWLTWWLLWTWLLWLWLWLLWLLL","TWLWTTLTLLLLLWWWLWTTWLWTLLWLWLTLWLL","TLLTTLLWTWTLWTLWWLWWWWWWLTLWWLWLTWW","WWTWLLWWLTWTTTWWLWWWWWLWWWLWLTLWWWT","LWTWLWLWTLTLWLWWWLWTLTWWWWWLWLTWLLL","LWWLWWLWWTWTLWWWWLLWTWLLWLLWLTWLWTT","LLWLTLLWLTLWTTLTLLLLWWTLLLLWTWLTLTT","TTWLWTWLTTWLTTWLWTLLLWWWWWWTLTWWTWL","LTLWLWTLWLLLWLTTLWTLLLWLTLWWWTTLLLL","LWLLTTLLLLLLTWTTLWLLWTWWLLLWWWTLTWL","TLLLTWLWLWLLWLWWTWWLWWTWWLLWTWLLWWT","TLWWLTWLWLWWWTLLLTLTWLLLWWWWLWLWTLW","LLWLWTWTLLLWWWTWLWTWWLLWLLLTWLLWWLW","WLLTWLLTLLTLWWWWWTLTWLWLTWTWLLWTWWL","LTWTLLTLLLWTLWWLLLLLTLWLWLLWWLTTLWW","LLWLTLLWLLTLLLWTLWWWWTTWTWWLTWTWWLW","WLLLWLWLLWLWTLLLTWWLLTTWWWTTTWTLTWL","WTLTLTWTLLLWWLWLLWLWWLLTWLLWLWTWTWT","LWLWLLLWWLLLWLTWLLWTLTLLTWLWWTLWWTW","WWWWTLWWTLLWWLWWWLWLWLLWLTTWLWLLTLL","LLWLWLLLWWLWWLLWWLWTWLTWWTTLWLLLTTT","WWWWLWWWLLWLLTLLLLTLLWTLLLWTWLLWLWT","LTLWLTLLLWLWTWLLTWLWLTTWLWLLTLTWLLW","LLLTLTWWWTWTLTTLLLWWWLLLTLWWWTWTLTW","WWTLLLWTLWTLWLTTWWWLTTTTWWWWTLTTWWL","LWLTWLLWWLLWTLWWWLLTTLWLLWWLLTTTLLT","WLWWWLWLTLWLWTWTLTLLWLTTLTTWWWLWTLW","LLTLLLWWLLWTTLWLLWWLLWLLTWTLWTLWWTW","TLTTTLWWLTWTTWWWTLLWLLWTLWTTLLWTLLT"}
18
15
Returns: -1
Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BalancedGame with a public method int result(vector<string> conflicts, int p, int q) · 50 test cases · 2 s / 256 MB per case