Skip to content

Instantly share code, notes, and snippets.

@flutesa
Last active January 4, 2016 09:09
Show Gist options
  • Save flutesa/8600446 to your computer and use it in GitHub Desktop.
Save flutesa/8600446 to your computer and use it in GitHub Desktop.
#n = 10
#t1, t2 = 1, 2
#a, b, c, d = 0, 1, 1, 11
f = open('treasure.in', 'r')
n = int(f.readline())
t1, t2 = list(map(int, f.readline().split(" ")))
a, b, c, d = list(map(int, f.readline().split(" ")))
f.close()
#вычисление стоимости сокровищ
costs = list()
costs.append(0)
costs.append(t1)
costs.append(t2)
for i in range(3, n+1):
costs.append((a*costs[i-2] + b*costs[i-1] + c) % d)
#сумма на префиксах
sum = list()
sum.append(0)
for i in range(1, n + 1):
sum.append(sum[i - 1] + costs[i])
#сумма на отрезке с [l, r] = sum[r] - sum[l - 1]
#сумма ценности всех сокровищ, для быстрого нахождения суммы для Бен Ганна
#summ = sum[len(sum)-1] - sum[0]
summ = sum[n] - sum[0]
ans_i = 0
ans_j = 0
min = n + 1
l = 0
r = 0
for i in range(1, n):
#j = max(i, j)
j = i
flint = sum[j] - sum[i-1]
bengann = summ - flint
while flint < bengann and j < n:
j += 1
flint = sum[j] - sum[i-1]
bengann = summ - flint
if flint >= bengann and min > j - i:
min = j - i
ans_i = i
ans_j = j
#print(i, j)
#print(ans_i, ans_j)
f = open('treasure.out', 'w')
print(str(ans_i) + " " + str(ans_j), file=f)
f.close()
#решение за O(n)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment