TopCoder

Caido
Waimai

User's AC Ratio

88.9% (16/18)

Submission's AC Ratio

39.8% (49/123)

Tags

Description

  我們有一個無限大的xy平面和一台神奇的發球機器,對任何整數a,b,c,d,只要我們將發球機器置於點(a,b)(其中(a,b)表示x座標為ay座標為b的點),並設定發球機器將球拋至點(c,d),則發球機器會拋出一顆球至點(c,d),接著該球會反彈至點(acbd,bc+ad)並固著於點(acbd,bc+ad)上,從此不再移動。我們只允許將發球機器置於x座標和y座標都是整數的點上。
  愛麗絲想要讓六顆球分別固著於點(a1,b1),(a2,b2),(a3,b3),(a4,b4),(a5,b5),(a6,b6)上,其中對所有i{1,2,3,4,5,6}ai,bi都是整數且(ai,bi)(0,0)。但她希望發球機器始終都在同一個點上,也就是她要找到一個置放發球機器的點(p,q)(其中p,q都是整數),使得對所有i{1,2,3,4,5,6},皆存在x座標與y座標都是整數的點(ci,di),滿足 (pciqdi,qci+pdi)=(ai,bi),如果滿足上述條件的點很多,則愛麗絲要選擇其中距離原點(0,0)最遠的一個點作為(p,q),並將發球機器置於該點(p,q),然後告訴稻草人|p|+|q|的值。
  給定a1,b1,a2,b2,a3,b3,a4,b4,a5,b5,a6,b6,請算出稻草人被告知的值。

實際模考中未提供__int128型別。

Input Format

對所有i{1,2,3,4,5,6},測資的第i行為aibi(兩數間以空白區隔)。

子任務(測資) 額外限制 分數
1 (0~4) |ai|,|bi|10 6
2 (0~9) |ai|,|bi|100 13
3 (0~14) |ai|,|bi|1000 35
4 (0~19) |ai|,|bi|109 43
5 (0~26) |ai|,|bi|1015 3

Output Format

請輸出稻草人被告知的值。

Sample Input 1

-60 40
-4 32
-28 -16
-68 4
-100 -20
12 64

Sample Output 1

12

Sample Input 2

24 -31
27 -24
31 -34
36 -32
38 -37
-17 -59

Sample Output 2

7

Sample Input 3

4 9
22 -8
13 4
55 100
66 4
44 -7

Sample Output 3

1

Sample Input 4

12 -99
33 -81
39 -88
13 -1
62 41
68 34

Sample Output 4

13

Sample Input 5

81 100
100 99
34 56
-3 -87
-15 24
26 27

Sample Output 5

1

Sample Input 6

24 -31
27 -24
31 -34
36 -32
38 -37
-17 -59

Sample Output 6

7

Hints

Problem Source

題目取自2017 TOI選訓第四次模擬考pD

Subtasks

No. Testdata Range Score
1 0~4 6
2 0~9 13
3 0~14 35
4 0~19 43
5 0~26 3

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 262144 262144 1 2 3 4 5
1 900 262144 262144 1 2 3 4 5
2 900 262144 262144 1 2 3 4 5
3 900 262144 262144 1 2 3 4 5
4 900 262144 262144 1 2 3 4 5
5 900 262144 262144 2 3 4 5
6 900 262144 262144 2 3 4 5
7 900 262144 262144 2 3 4 5
8 900 262144 262144 2 3 4 5
9 900 262144 262144 2 3 4 5
10 900 262144 262144 3 4 5
11 900 262144 262144 3 4 5
12 900 262144 262144 3 4 5
13 900 262144 262144 3 4 5
14 900 262144 262144 3 4 5
15 900 262144 262144 4 5
16 900 262144 262144 4 5
17 900 262144 262144 4 5
18 900 262144 262144 4 5
19 900 262144 262144 4 5
20 900 262144 262144 5
21 900 262144 262144 5
22 900 262144 262144 5
23 900 262144 262144 5
24 900 262144 262144 5
25 900 262144 262144 5
26 900 262144 262144 5