Kicker (table football) is a board game based on football, in which players control the…
- User
Kicker (table football) is a board game based on football, in which players control the footballers' figures mounted on rods by using bars to get the ball into the opponent's goal. When playing two on two, one player of each team controls the goalkeeper and the full-backs (plays defence), the other player controls the half-backs and forwards (plays attack).
Two teams of company Q decided to battle each other. Let's enumerate players from both teams by integers from 1 to 4. The first and second player play in the first team, the third and the fourth one play in the second team. For each of the four players we know their game skills in defence and attack. The defence skill of the i-th player is ai, the attack skill is bi.
Before the game, the teams determine how they will play. First the players of the first team decide who will play in the attack, and who will play in the defence. Then the second team players do the same, based on the choice of their opponents.
We will define a team's defence as the defence skill of player of the team who plays defence. Similarly, a team's attack is the attack skill of the player of the team who plays attack. We assume that one team is guaranteed to beat the other one, if its defence is strictly greater than the opponent's attack and its attack is strictly greater than the opponent's defence.
The teams of company Q know each other's strengths and therefore arrange their teams optimally. Identify the team that is guaranteed to win (if both teams act optimally) or tell that there is no such team. Input
The input contain the players' description in four lines. The i-th line contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ 100) — the defence and the attack skill of the i-th player, correspondingly.
Output
If the first team can win, print phrase "Team 1" (without the quotes), if the second team can win, print phrase "Team 2" (without the quotes). If no of the teams can definitely win, print "Draw" (without the quotes).
Examples
Input
1 100 100 1 99 99 99 99
Output
Team 1
Input
1 1 2 2 3 3 2 2
Output
Team 2
Input
3 3 2 2 1 1 2 2
Output
Draw
Note
Let consider the first test sample. The first team can definitely win if it will choose the following arrangement: the first player plays attack, the second player plays defence.
Consider the second sample. The order of the choosing roles for players makes sense in this sample. As the members of the first team choose first, the members of the second team can beat them (because they know the exact defence value and attack value of the first team).
Assistant
We need to analyze a game of two teams, each consisting of two players. Players 1 and 2 are team 1; players 3 and 4 are team 2. For each player i, we have defence skill a_i and attack skill b_i.
Before the game, team 1 (players 1 and 2) decide who will play attack and who will play defence. Then team 2 (players 3 and 4) decide their attack/defence roles based on team 1's choice. After roles assigned, each team's defence is the defence skill of the player assigned to defence, and attack is the attack skill of the player assigned to attack.
We assume that one team is guaranteed to beat the other if its defence > opponent's attack AND its attack > opponent's defence. So it's a strict double condition.
The teams know each other's skills and act optimally. Team 1 chooses first (presumably to maximize their chance of winning? Actually they want to guarantee a win if possible). Team 2 then chooses after seeing team1's assignment, to guarantee their own win if possible? The problem statement: "The teams of company Q know each other's strengths and therefore arrange their teams optimally. Identify the team that is guaranteed to win (if both teams act optimally) or tell that there is no such team."
Interpretation: This is a sequential game: team 1 chooses an assignment (i.e., which of its two players is defender, which is attacker). Then team 2, knowing that assignment, chooses its own assignment. After both assignments, we evaluate if either team is guaranteed to beat the other? Actually "guaranteed to beat the other one" is defined as a condition that holds. But the phrase "is guaranteed to win" in the output asks: given optimal play from both sides, which team, if any, can force a win? That is, can team 1 choose an assignment such that no matter how team 2 assigns (or maybe team 2 will assign optimally to try to win themselves), team 1 will be guaranteed to beat team 2? Or if team 2 can respond to ensure they beat team 1? Or perhaps it's a minimax: team 1 wants to guarantee that they win (i.e., after both assignments, the condition for team1 beating team2 holds). Team 2 wants to prevent that and possibly guarantee their own win. Since team 2 moves after team 1, they can try to choose an assignment that makes team 2 win if possible, given team1's assignment. So the outcome depends on whether team 1 can pick an assignment such that for all possible assignments of team 2 (or specifically the best response by team 2), team 1 will win? But the problem says "both teams act optimally". That suggests that team 2 will choose an assignment that maximizes its own chance. Usually in such two-player sequential zero-sum games, we assume that if team 2 can force a win, they will. If not, they might try to force a draw (neither wins). But what is a draw? In the given examples, "Draw" means that neither team can guarantee a win. So we need to determine if team 1 has a strategy (choice of roles) that guarantees that after team 2's optimal response, team 1 wins. And if not, then check if team 2 has a strategy to guarantee a win given team 1's move? But team 2 moves second; they can respond to whatever team 1 does. So if for any possible team 1 assignment, team 2 can choose an assignment such that team 2 wins, then team 2 is guaranteed to win (since team 1 moves first and cannot avoid that). However, if there exists some team 1 assignment such that no matter what team 2 does, team 1 wins, then team 1 wins. If neither team can force a win, it's a draw.
But careful: The definition of "win" for a team is: its defence > opponent's attack AND its attack > opponent's defence. This condition is symmetric? Not exactly symmetric; it's about one team beating the other. For a given matchup, it's possible that both teams beat each other? Let's check: If team1 def > team2 attack and team1 attack > team2 def, then team1 beats team2. Could it be that simultaneously team2 def > team1 attack and team2 attack > team1 def? That would require both team1 def > team2 attack and team2 def > team1 attack, which implies team1 def > team2 attack and team2 def > team1 attack. Combined with attack > defence inequalities? Let's examine: For both to hold, we need team1 attack > team2 def and team2 attack > team1 def. But if team1 attack > team2 def and team2 attack > team1 def, then we have team1 attack > team2 def and team2 attack > team1 def. That doesn't necessarily contradict the first two, but let's consider numbers: Suppose team1: def=10, attack=5; team2: def=5, attack=10. Then team1 def (10) > team2 attack (10)? No, it's equal, need strictly greater. So not both. Could there be a scenario where both conditions hold? That would require team1 def > team2 attack AND team2 def > team1 attack. Then also team1 attack > team2 def AND team2 attack > team1 def. Summing or something: from team1 attack > team2 def and team2 def > team1 attack, impossible. So both can't be true simultaneously. Also, it's possible that neither condition holds (draw). So each matchup yields either Team1 wins, Team2 wins, or Draw (neither meets the strict double condition). So it's a deterministic outcome given assignments.
Thus we have a game tree: team 1 chooses one of two possible assignments (swap roles) for players 1 and 2. There are two possibilities: either (1 defends, 2 attacks) or (2 defends, 1 attacks). Then team 2, seeing that, chooses one of two assignments for players 3 and 4: (3 defends, 4 attacks) or (4 defends, 3 attacks). Then the outcome is determined. Since both teams act optimally, team 1 wants to end up with a win for itself, and team 2 wants to end up with a win for itself, presumably. But what if neither can force a win? Then they might aim to avoid the opponent's win, but the outcome could be a draw. Since it's a zero-sum game? But there are three possible outcomes: Team1 win, Team2 win, Draw. We need to decide which team, if any, can force a win assuming optimal play (i.e., team 2 will choose to maximize its own chance, and team 1 anticipates that). The problem likely expects that we check if team 1 has a move that leads to a win no matter what team 2 does? But that would be a very strong condition: team 1 would need that for both possible team2 assignments, the resulting matchup yields a team1 win. However, team 2 would obviously not pick an assignment that leads to team 1 win if they can pick one that leads to team2 win or draw. So team 1 cannot assume team2 will pick arbitrarily; they will pick the best response for team2. So we need to consider that team2 will choose an assignment that maximizes team2's outcome, i.e., if they can achieve a win, they will; else they will try to at least force a draw (avoid a loss). Similarly, team1 chooses its assignment to maximize its outcome given team2's optimal response.
This is a standard minimax with three outcomes. We can assign an ordering: For team1, outcomes: win > draw > loss. For team2, opposite: team2 win (which is team1 loss) > draw > team1 win. Actually from team2's perspective, they want team2 win, else draw, else team1 win.
Thus team1 will choose assignment that maximizes its own utility, anticipating team2's best response (which minimizes team1's utility, equivalently maximizes team2's). So we can compute for each team1 assignment s (two possibilities), the outcome after team2 chooses their best assignment (from team2's perspective). Then team1 picks the assignment that gives the best outcome for them among those two.
Then the final outcome is determined. The output asks: "Identify the team that is guaranteed to win (if both teams act optimally) or tell that there is no such team." So if after this minimax, the outcome is team1 win, print "Team 1". If team2 win, print "Team 2". If draw, print "Draw". That matches the examples.
Let's test with example 1:
Players: 1: a1=1, b1=100 2: a2=100, b2=1 3: a3=99, b3=99 4: a4=99, b4=99
Team1 assignments: Option A: player1 defence? Actually we need to decide who plays defence and who plays attack. Let's define assignment as (defender player index, attacker player index). Team1 can have: s1: (1 defends, 2 attacks): then team1 defence = a1 = 1, attack = b2 = 1. s2: (2 defends, 1 attacks): defence = a2 = 100, attack = b1 = 100.
Now team2 assignments: Team2 players: 3 and 4 both (99,99). So either assignment yields same: defence = 99, attack = 99.
Now evaluate outcomes for each team1 assignment and team2's best response (but team2 has only one effective outcome, but they would choose to maximize their win; both assignments identical, so outcome is same).
For s1: team1 def=1, att=1; team2 def=99, att=99. Check if team1 wins: def > opp att? 1 > 99? no. attack > opp def? 1 > 99? no. team2 wins? team2 def=99 > team1 att=1? yes, and team2 att=99 > team1 def=1? yes. So team2 wins.
For s2: team1 def=100, att=100; team2 def=99, att=99. team1 wins: 100 > 99 and 100 > 99 both true => team1 wins. team2 wins? 99 > 100? no. So team1 wins.
Thus from team1's perspective: if they choose s1, team2 will respond (any) leading to team2 win. If they choose s2, they get team1 win. Since team1 moves first and can choose s2, they guarantee a win. So output Team 1. That matches.
Example 2: Input: 1 1 2 2 3 3 2 2
Players: 1: a1=1,b1=1 2: a2=2,b2=2 3: a3=3,b3=3 4: a4=2,b4=2
Team1 assignments: s1: (1 def, 2 att) => def = a1=1, att = b2=2. s2: (2 def, 1 att) => def = a2=2, att = b1=1.
Team2 assignments: Players 3 and 4: (3:3,3) and (4:2,2). Options: t1: (3 def, 4 att) => def = a3=3, att = b4=2. t2: (4 def, 3 att) => def = a4=2, att = b3=3.
Now for each team1 assignment, team2 will choose the assignment that gives them best outcome.
Consider s1: team1 (def1=1, att1=2)
- t1: team2 def=3, att=2. Check: team1 wins? def1 > att2? 1>2? no; att1 > def2? 2>3? no. team2 wins? def2>att1? 3>2 yes; att2>def1? 2>1 yes => team2 wins.
- t2: team2 def=2, att=3. team1 wins? 1>3? no; 2>2? no (strict). team2 wins? def2>att1? 2>2? no; att2>def1? 3>1 yes but need both. So team2 does NOT win (since 2>2 false). So outcome is? Check team1 win condition: def1>att2? 1>3 false; att1>def2? 2>2 false. So neither team wins? Actually team2 condition: def2>att1 and att2>def1 -> def2=2 > att1=2? false (need strictly). So no one wins => Draw. Thus for s1, team2 can choose t1 to get a win. So team2 will choose t1 leading to team2 win.
Consider s2: team1 (def=2, att=1)
- t1: team2 def=3, att=2. Check: team1 wins? 2>2? false; 1>3? false. team2 wins? 3>1 true, 2>2 false => no. So Draw? Actually check team2: def2=3 > att1=1 true, att2=2 > def1=2? false (needs >). So no win for team2. So outcome Draw.
- t2: team2 def=2, att=3. team1 wins? 2>3? false; 1>2? false. team2 wins? def2=2 > att1=1 true, att2=3 > def1=2 true => team2 wins. So team2 can choose t2 to get a win. Thus for s2, team2 can choose t2 to get a win. So for both team1 assignments, team2 can force a win. So the best team1 can do is still lose. So overall outcome is team2 win. Output Team 2. That matches.
Example 3: Input: 3 3 2 2 1 1 2 2
Players: 1: a1=3,b1=3 2: a2=2,b2=2 3: a3=1,b3=1 4: a4=2,b4=2
Team1 assignments: s1: (1 def,2 att) => def=3, att=2 s2: (2 def,1 att) => def=2, att=3
Team2 assignments: t1: (3 def,4 att) => def=1, att=2 t2: (4 def,3 att) => def=2, att=1
Now evaluate:
s1: team1 (3,2)
- t1: team2 (1,2): team1 wins? def1>att2: 3>2 true; att1>def2: 2>1 true => team1 wins. So team2 would avoid that if possible.
- t2: team2 (2,1): team1 wins? 3>1 true; 2>2? false (needs >) => not team1 win. team2 wins? 2>2? false (def2>att1: 2>2 false) or 1>3 false. So draw. Thus for s1, team2 can choose t2 to force a draw (since t1 gives team1 win, t2 gives draw). So team2 will choose t2, outcome draw.
s2: team1 (2,3)
- t1: team2 (1,2): team1 wins? 2>2? false; 3>1 true but both needed, so no. team2 wins? 1>3 false. So draw? Check: team1 condition fails (2>2 false), team2 condition fails (1>3 false). So draw.
- t2: team2 (2,1): team1 wins? 2>1 true; 3>2 true => team1 wins. Thus for s2, team2 can choose t1 to force a draw (t2 gives team1 win). So outcome draw.
Thus both s1 and s2 lead to draw after team2's optimal response. So overall outcome draw. That matches.
So the minimax approach is correct.
Thus the solution: For each possible assignment of team1 (two choices), we compute the outcome after team2 chooses the best assignment for themselves (i.e., choose the assignment that yields the best outcome for team2, with preferences: team2 win > draw > team1 win). Then team1 chooses the assignment that gives the best outcome for team1 (team1 win > draw > team2 win). Then output accordingly.
Implementation: we can represent outcomes as integers: For team1 perspective: win = 2, draw = 1, lose = 0. Or use an enum. For each team1 assignment, compute outcomes for both team2 assignments, then team2 will choose the max from their perspective: we need to map outcomes to team2's utility. Since it's symmetric: team2's win corresponds to team1 lose (0), draw (1), team1 win (2) from team1 perspective. But team2 prefers: team2 win (i.e., outcome = team1 lose) > draw > team1 win. So from team1 perspective, team2's utility is decreasing: they want outcome value = 0 (team1 lose) best, then 1 (draw), then 2 (team1 win). So team2 will pick the assignment that minimizes the team1 outcome value? Actually if we use team1 outcome values: 2 (team1 win), 1 (draw), 0 (team1 lose). Then team2 prefers lower numbers. So team2 will pick the assignment that yields the minimal outcome value for team1. Yes. So for a given team1 assignment, the result after team2's optimal play is min over t (outcome(s,t)), where outcome(s,t) is as per team1's perspective (2,1,0). Then team1 will choose the assignment that maximizes that min. So it's a classic minimax.
Thus compute for each s: value = min_{t} outcome(s,t). Then team1's best value = max over s of value_s. Then if best = 2, output "Team 1". If best = 1, output "Draw". If best = 0, output "Team 2". But wait: In case best=0, that means that for all team1 assignments, team2 can force a team1 loss. So team2 wins overall. So that's correct.
But double-check: Is it possible that for a given s, team2 might have multiple assignments that give the same outcome from team2's perspective? Then they pick the one that gives team2 the best outcome, i.e., minimal team1 outcome. So min is appropriate.
Now we just need to compute outcome(s,t) given assignments.
Let team1 players indices: p and q (two). Let defender1 = d1, attacker1 = a1. Then defence1 = a[d1] (since a_i is defence), attack1 = b[a1]. Similarly for team2: defender2 = d2, attacker2 = a2; defence2 = a[d2], attack2 = b[a2].
Condition for team1 win: defence1 > attack2 AND attack1 > defence2. Condition for team2 win: defence2 > attack1 AND attack2 > defence1.
If neither, draw.
We can compute directly.
Implementation steps:
- Read a[1..4], b[1..4].
- For each team1 assignment: there are two possibilities: s0: d1=1, a1=2 s1: d1=2, a1=1
- For each s, iterate over team2 assignments: two possibilities: t0: d2=3, a2=4 t1: d2=4, a2=3
- For each t, compute outcome (0,1,2) from team1 perspective.
- For s, compute value_s = min(outcome(s,t0), outcome(s,t1))
- Then best = max(value_s0, value_s1)
- Output accordingly.
Edge Cases: All skills between 1 and 100, so no ties? But ties are possible as seen in examples. The condition requires strictly greater, so ties yield no win.
This is straightforward.
But is there any nuance about "guaranteed to win" meaning that for all possible assignments of the opponent, the team wins? That would be stronger than minimax. But as argued, team2 will choose optimally, not arbitrarily. The examples support the minimax interpretation because in example 2, team2 can win regardless of team1's choice, so they are guaranteed to win. In example 1, team1 can win because they have a choice that leads to win despite team2's optimal response. That's consistent with minimax. So it's fine.
Thus solution is simple.
We can also reason about it mathematically: Because the game is small, we could also brute-force all possibilities.
Now just code.
But wait, there might be a subtlety: The problem statement: "The teams of company Q know each other's strengths and therefore arrange their teams optimally." This might imply that they both choose simultaneously? But then it says: "Before the game, the teams determine how they will play. First the players of the first team decide who will play in the attack, and who will play in the defence. Then the second team players do the same, based on the choice of their opponents." So it's sequential.
Thus minimax.
Now double-check with some edge cases. Example where both teams have symmetrical skills, etc.
Thus answer.
But we need to ensure that we interpret the ordering of roles correctly: The first team chooses first. The second team chooses after, based on that. That's what we used.
Now we can implement.
One more nuance: The team that "guaranteed to win" means that after optimal play, that team will win. But what if both teams could force a win? That's impossible due to the nature of the condition. So fine.
Thus solution.
We'll implement in C++ (or Python). Since this is a typical problem, but the input is small.
But wait: There is a potential twist: The definition: "We assume that one team is guaranteed to beat the other one, if its defence is strictly greater than the opponent's attack and its attack is strictly greater than the opponent's defence." That's a condition for a team to beat the other. But does it guarantee that the team wins? It's the definition of winning. So okay.
Now code.
Pseudo:
read a[4], b[4].
function outcome(s,t): if s uses d1, a1; t uses d2, a2. d1_val = a[d1] a1_val = b[a1] d2_val = a[d2] a2_val = b[a2] if d1_val > a2_val and a1_val > d2_val: return 2 (team1 win) elif d2_val > a1_val and a2_val > d1_val: return 0 (team2 win) else: return 1 (draw)
Then:
s_options = [(1,2), (2,1)] t_options = [(3,4), (4,3)]
best = -1 for each (d1, a1) in s_options: min_val = 3 for each (d2, a2) in t_options: val = outcome(d1,a1,d2,a2) min_val = min(min_val, val) best = max(best, min_val)
if best == 2: print "Team 1" elif best == 1: print "Draw" else: print "Team 2"
That's it.
But we should test with examples.
Example 1: s0: d1=1,a1=2: val for t0: outcome? team1 lose =>0, t1: same =>0 => min_val=0. s1: d1=2,a1=1: val for t0: team1 win =>2, t1:2 => min_val=2 => best=2 => Team1.
Example2: s0: t0 -> team2 win =>0, t1 -> draw =>1 => min_val=0 s1: t0 -> draw =>1, t1 -> team2 win =>0 => min_val=0 => best=0 => Team2.
Example3: s0: t0 -> team1 win =>2, t1 -> draw =>1 => min_val=1 s1: t0 -> draw =>1, t1 -> team1 win =>2 => min_val=1 => best=1 => Draw.
Matches.
Now we should consider if there is any scenario where team2 might have more than two assignments? No, only two players. So correct.
Thus solution is done.
But wait, there's a nuance: The definition says: "The teams of company Q know each other's strengths and therefore arrange their teams optimally." That could be interpreted as they simultaneously choose? But the earlier sentence explicitly says first team decides then second based on that. So it's clear.
Thus answer.
Now code in Python.
We'll read 4 lines, parse ints.
Implementation:
def calc(d1, a1, d2, a2): def1 = a[d1-1] # using 0-index att1 = b[a1-1] def2 = a[d2-1] att2 = b[a2-1] if def1 > att2 and att1 > def2: return 2 if def2 > att1 and att2 > def1: return 0 return 1
Then main.
That's it.
But maybe we can optimize by reasoning, but not needed.
Now let's think about potential pitfalls: The indices: players 1..4 as given. Use 0-indexing.
Now the answer is ready.
But I recall a Codeforces problem named "Kicker" or something like that, and some solutions used a different logic: they check if team1 can force a win by checking if there exists an assignment such that for both possible assignments of team2, team1 wins. But that would be a stronger condition (win regardless of opponent's choice), which matches our minimax when the opponent cannot avoid loss? Actually if team1 can win for both t, then min_val = 2. That's best. But if team1 can only win for one t but opponent can choose the other t to avoid loss, then min_val < 2. That's captured by minimax.
Thus correct.
Now let's test some additional cases manually:
Case: Both teams have equal skills, like all players (a,b) = (5,5). Then s0: (1 def=5, 2 att=5). team2 any assignment yields def=5, att=5. For any combination: team1 win? 5>5 false. team2 win? 5>5 false. So draw. So both s give min_val=1. best=1 -> Draw. Good.
Case: Team1 has a super strong defence and attack if assigned correctly, but team2 can always counter? Already considered.
Case: Might there be a scenario where team2 can force a win even though team1 can force a win for some assignment? That cannot happen because if team1 can force a win, then for that assignment, team2 cannot have a response that gives them a win (since team1's min_val would be at least 2? Actually team1 forcing a win means there exists an s such that for all t, team1 wins => min_val=2. Then best=2. But if team2 can force a win overall, that would mean for each s, team2 has some t that gives team2 win, i.e., min_val=0 for all s. But both cannot be true because if there exists an s with min_val=2, then it's not true that for all s min_val=0. So both cannot happen simultaneously. So it's consistent.
Thus algorithm is correct.
Now consider a more complex scenario: Suppose team1 has two assignments: s1 gives outcomes (win, draw) -> min=1? Actually s1: t0 win (2), t1 draw (1) => min=1. s2 gives outcomes (draw, lose) => min=0. Then best = max(1,0) =1 => draw. So team1 cannot force win, team2 cannot force win because there is an s (s1) where team2 cannot force a win (they can only force draw at best). And from team2's perspective, they can force a win only if for all s they can force a win, which would require min_val=0 for both s. But here s1 min_val=1, so team2 cannot guarantee a win either. So draw. That seems plausible.
Now confirm that team2 cannot guarantee a win because team1 could choose s1 to avoid loss. That matches.
Thus solution done.
Implementation details: Read from stdin, output accordingly.
Now, could there be any scenario where the minimax yields a value that is not 0,1,2? No.
Thus we're done.
Now let's produce final answer. ```python import sys
def solve() -> None: data = sys.stdin.read().strip().split() if not data: return it = iter(data) a = [0] * 4 b = [0] * 4 for i in range(4): a[i] = int(next(it)) b[i] = int(next(it))
# indices are 0-based for arrays, but we use player numbers 1..4 for clarity team1_options = [(1, 2), (2, 1)] # (defender, attacker) team2_options = [(3, 4), (4, 3)] def outcome(d1: int, a1: int, d2: int, a2: int) -> int: # returns 2 if team1 wins, 0 if team2 wins, 1 if draw def1 = a[d1 - 1] att1 = b[a1 - 1] def2 = a[d2 - 1] att2 = b[a2 - 1] if def1 > att2 and att1 > def2: return 2 if def2 > att1 and att2 > def1: return 0 return 1 best = -1 for d1, a1 in team1_options: worst_for_team1 = 3 # larger than any outcome for d2, a2 in team2_options: val = outcome(d1, a1, d2, a2) if val < worst_for_team1: worst_for_team1 = val if worst_for_team1 > best: best = worst_for_team1 if best == 2: print("Team 1") elif best == 1: print("Draw") else: print("Team 2")if name == "main": solve()