-
Notifications
You must be signed in to change notification settings - Fork 184
/
Copy pathd.py
executable file
·77 lines (74 loc) · 1.71 KB
/
d.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#!/usr/bin/env python2
# https://abc081.contest.atcoder.jp/tasks/arc086_b
import math
def a(xs, m):
k = xs.index(m) + 1
ops = []
a = xs[0];
for i in range(1, len(xs)):
b = xs[i]
if a > b:
d = a - b
n = int(math.ceil(d / float(m)))
d2 = m - b
n2 = int(math.ceil(d2 / float(m)))
if n2 > 0 and n2 < n:
b += n2 * m
ops.append((k, i + 1, n2))
k = i + 2
m = b
d = b - a
n = int(math.ceil(d / float(m)))
b += n * m
ops.append((k, i + 1, n))
a = b
return ops
def b(xs, m):
k = xs.index(m) + 1
ops = []
a = xs[-1]
for i in range(len(xs) - 2, -1, -1):
b = xs[i]
if a < b:
d = a - b
n = int(math.ceil(d / float(m)))
d2 = m - b
n2 = int(math.ceil(d2 / float(m)))
if n2 > 0 and n2 < n:
b += n2 * m
ops.append(k, i, n2)
k = i + 1
m = b
d = a - b
n = int(math.ceil(d / float(m)))
b += n * m
ops.append((k, i, n))
a = b
return ops
n = input()
xs = map(int, raw_input().split())
M = max(xs)
m = min(xs)
if M > 0 and m >= 0:
ops = a(xs, M)
c = len(ops)
elif M <= 0 and m < 0:
ops = b(xs, m)
c = len(ops)
else:
ops1 = a(xs, M)
ops2 = b(xs, m)
c1 = 0
for _, _, n in ops1: c1 += n
c2 = 0
for _, _, n in ops2: c2 += n
if c1 <= c2:
ops = ops1
c = c1
else:
ops = ops2
c = c2
print c
for a, b, n in ops:
for _ in range(n):
print a, b