93 - ZOJ Monthly, July 2010 - F
The 2010 FIFA World Cup toke place between 11 June and 11 July 2010 in South Africa. For cc98, a gaming company, this is a good opportunity to make money. They use rules like Asian Handicap.
For a match, bookmakers will determine a integer K as handicap parameter according to difference of two teams' proficiencies. If the home team wins more than K scores (K<0 means home team loses less than |K| scores), it will be a WIN result. If they wins less than K scores, it will be a LOSE instead. And gamblers can bet on WIN or LOSE. When the match over, the gamblers whose chosen are right can win wagers. But when the difference is exactly K, all gamblers lost their money.
To make more profit, the research department of cc98 has found a formula to predict the result of a match. For every team, they will estimate two integers Pa and Pb. In a match, we assume two teams are Team1 (P1a, P1b) and Team2 (P2a, P2b). Team1 is the home team. Then they calculate a match number F (F = (P1a - P2a) * x1 + (P1b - P2b) * x2, where x1 and x2 are two important constants). They can predict the result by comparing F and K. F > K means a WIN result, and F < K means a LOSE.
It sounds fantastic. But unfortunately, the researchers in cc98 forget the exact values of x1 and x2. They only have a piece of paper where several matches are recorded. Each one contains team information, an integer K and the result (It is not a exactly score but only a WIN or LOSE). Now they have to determine an integer K for next match by these records.
If cc98 made K too large or too small, one result would inevitably be. The company may be bankrupt. They must avoid this situation. Now they want to know the safe range [a,b] of K (both a and b are integers), which means when a ≤ K ≤ b, both WIN and LOSE results are possible.
The first line is a integer T. Then T cases follow. There are no more than 20 cases.
For each case, there are N+2 lines. The first line is integer N (3 ≤ N ≤ 2000, which means N match records. The following N lines are N records. Each line contains 4 integers Da, Db, K and R (-10000 ≤ Da, Db, K ≤ 10000, R = -1 or 1).
Da is result of P1a - P2a. And Db is result of P1b - P2b. K is the handicap parameter for that match. At the end, the value of R is always 1 or -1. R = -1 means LOSE, while R = 1 means WIN.
The Last line of each case has two integers Dna and Dnb (-10000≤ Dna, Dnb ≤ 10000), indicating the team information in next match.
In all cases, at least one safe K can always be found. x1 and x2 are constant in one case, but may vary in different cases.
A single line contains two integers a and b, which shows the safe range of K.
For all cases -10000 ≤ a ≤ b ≤ 10000.
1 4 1 1 1 -1 1 -1 0 1 0 1 -1 1 1 0 0 1 1 2
Author: HUANG, Minzhi
Source: ZOJ Monthly, July 2010