LCM of GCDs

source: International Collegiate Programming Contest, Asia Regional 2020, Japan

raw_problem:
LCM of GCDs

You are given a sequence of positive integers, followed by a number of instructions specifying
updates to be made and queries to be answered on the sequence. Updates and queries are given
in an arbitrary order.

Each of the updates replaces a single item in the sequence with a given value. Updates are
accumulated: all the following instructions are on the sequence after the specified replacement.

Each of the queries specifies a subsequence of the (possibly updated) sequence and the number
of items to exclude from that subsequence. One or more sets of integers will result depending
on which of the items are excluded. Each of such sets has the greatest common divisor (GCD)
of its members. The answer to the query is the least common multiple (LCM) of the GCDs of
all these sets.

  Figure H.1. Answering the last query "Q 2 5 2" of the Sample Input 1

Input

  The input consists of a single test case of the following format.

$n$ $m$
$a_1$ ... $a_n$
$c_1$
...
$c_m$

  The first line has two integers, $n$ and $m$. $n$ ($1 \leq n \leq 10^5$) is the length of the integer sequence, and $m$ ($1 \leq m \leq 10^5$) is the number of instructions. The original integer sequence $a_1, ...,  a_n$ is given in the second line. $1 \leq a_i \leq 10^6$ holds for $i = 1, ..., n$. Each of the following $m$ lines has either an update instruction starting with a letter U, or a query instruction starting with a letter Q.

  An update instruction has the following format.

U $j$ $x$

  The instruction tells to replace the $j$-th item of the sequence with an integer $x$. $1 \leq j \leq n$ and $1 \leq x \leq 10^6$ hold. Updates are accumulated: all the instructions below are on the sequence after the updates.

  A query instruction has the following format.

Q $l$ $r$ $k$

  Here, $l$ and $r$ specify the start and the end positions of a subsequence, and $k$ is the number of items to exclude from that subsequence, $b_l, ..., b_r$, where $b_1, ... , b_n$ is the sequence after applying all the updates that come before the query. $1 \leq l, 0 \leq k \leq 2$, and $l + k \leq r \leq n$ hold.

Output

No output is required for update instructions. For each of the query instructions, output a line with the LCM of the GCDs of the sets of the items in all the subsequences made by excluding
$k$ items from the sequence $b_l, ..., b_r$.

Sample Input 1

5 10
12 10 16 28 15
Q 1 3 1
Q 3 4 0
Q 2 2 0
Q 2 5 2
U 3 21
Q 1 3 1
Q 2 4 1
Q 3 5 1
Q 4 4 0
Q 2 5 2

 Sample Output 1

4
4
10
20
6
14
21
28
210

  For the first query of this test case, "Q 1 3 1", the subsequence is 12 10 16. Eliminating a single item results in three item sets, {12, 10}, {12, 16}, and {10, 16}. Their GCDs are 2, 4, and 2, respectively, and thus the output should be their LCM, 4.

  Note that, the update given as the fifth instruction, "U 3 21", changes the answer to the same query, "Q 1 3 1", given as the sixth instruction. The update makes the subsequence to 12 10 21. Thus the item sets after eliminating a single item are {12, 10}, {12, 21}, and {10, 21}. Their GCDs are 2, 3, and 1, respectively, and thus the output for this query should be their LCM, 6.

source: aizu

question:
LCM of GCDs

You are given a sequence of positive integers, followed by a number of instructions specifying
updates to be made and queries to be answered on the sequence. Updates and queries are given
in an arbitrary order.

Each of the updates replaces a single item in the sequence with a given value. Updates are
accumulated: all the following instructions are on the sequence after the specified replacement.

Each of the queries specifies a subsequence of the (possibly updated) sequence and the number
of items to exclude from that subsequence. One or more sets of integers will result depending
on which of the items are excluded. Each of such sets has the greatest common divisor (GCD)
of its members. The answer to the query is the least common multiple (LCM) of the GCDs of
all these sets.

![image](1.png)

  Figure H.1. Answering the last query "Q 2 5 2" of the Sample Input 1

Input

  The input consists of a single test case of the following format.

$n$ $m$
$a_1$ ... $a_n$
$c_1$
...
$c_m$

  The first line has two integers, $n$ and $m$. $n$ ($1 \leq n \leq 10^5$) is the length of the integer sequence, and $m$ ($1 \leq m \leq 10^5$) is the number of instructions. The original integer sequence $a_1, ...,  a_n$ is given in the second line. $1 \leq a_i \leq 10^6$ holds for $i = 1, ..., n$. Each of the following $m$ lines has either an update instruction starting with a letter U, or a query instruction starting with a letter Q.

  An update instruction has the following format.

U $j$ $x$

  The instruction tells to replace the $j$-th item of the sequence with an integer $x$. $1 \leq j \leq n$ and $1 \leq x \leq 10^6$ hold. Updates are accumulated: all the instructions below are on the sequence after the updates.

  A query instruction has the following format.

Q $l$ $r$ $k$

  Here, $l$ and $r$ specify the start and the end positions of a subsequence, and $k$ is the number of items to exclude from that subsequence, $b_l, ..., b_r$, where $b_1, ... , b_n$ is the sequence after applying all the updates that come before the query. $1 \leq l, 0 \leq k \leq 2$, and $l + k \leq r \leq n$ hold.

Output

No output is required for update instructions. For each of the query instructions, output a line with the LCM of the GCDs of the sets of the items in all the subsequences made by excluding
$k$ items from the sequence $b_l, ..., b_r$.

Sample Input 1

5 10
12 10 16 28 15
Q 1 3 1
Q 3 4 0
Q 2 2 0
Q 2 5 2
U 3 21
Q 1 3 1
Q 2 4 1
Q 3 5 1
Q 4 4 0
Q 2 5 2

 Sample Output 1

4
4
10
20
6
14
21
28
210

  For the first query of this test case, "Q 1 3 1", the subsequence is 12 10 16. Eliminating a single item results in three item sets, {12, 10}, {12, 16}, and {10, 16}. Their GCDs are 2, 4, and 2, respectively, and thus the output should be their LCM, 4.

  Note that, the update given as the fifth instruction, "U 3 21", changes the answer to the same query, "Q 1 3 1", given as the sixth instruction. The update makes the subsequence to 12 10 21. Thus the item sets after eliminating a single item are {12, 10}, {12, 21}, and {10, 21}. Their GCDs are 2, 3, and 1, respectively, and thus the output for this query should be their LCM, 6.

data_split: test


B. Dynamic Problem Scoring

problem_index: B

time_limit: 2 seconds

memory_limit: 256 megabytes

solutions: ["n = int(input())\na = [list(map(int, input().split())) for i in range(n)]\nsolved = [0 for i in range(5)]\nscore = [0 for i in range(5)]\nfor i in range(n):\n\tfor j in range(5):\n\t\tsolved[j] += int(a[i][j] > -1)\nfor k in range(31 * n + 1):\n\tfor i in range(5):\n\t\ttot = n + k\n\t\tcur = solved[i]\n\t\tif a[0][i] > -1 and a[1][i] > -1 and (a[0][i] > a[1][i]):\n\t\t\tcur += k\n\t\tscore[i] = 500\n\t\twhile score[i] < 3000 and 2 * cur <= tot:\n\t\t\tcur *= 2\n\t\t\tscore[i] += 500\n\tres = [0, 0]\n\tfor j in range(2):\n\t\tfor i in range(5):\n\t\t\tif a[j][i] > -1:\n\t\t\t\tres[j] += score[i] / 250 * (250 - a[j][i])\n\tif res[0] > res[1]:\n\t\tprint(k)\n\t\treturn\nprint('-1')\n", "def get_value(parters, solved):\n\tif solved * 32 <= parters:\n\t\treturn 3000\n\tif solved * 16 <= parters:\n\t\treturn 2500\n\tif solved * 8 <= parters:\n\t\treturn 2000\n\tif solved * 4 <= parters:\n\t\treturn 1500\n\tif solved * 2 <= parters:\n\t\treturn 1000\n\treturn 500\n\ndef points(value, time):\n\treturn value - value // 500 * time\nn = int(input())\nt = [0] * n\nfor i in range(n):\n\tt[i] = list(map(int, input().split()))\nvalue = [0] * 5\nsolve = [0] * 5\nfor i in range(5):\n\tsolved = 0\n\tfor j in range(n):\n\t\tif t[j][i] != -1:\n\t\t\tsolved += 1\n\t\telse:\n\t\t\tt[j][i] = 250\n\tvalue[i] = get_value(n, solved)\n\tsolve[i] = solved\nvasya = 0\nfor i in range(5):\n\tvasya += points(value[i], t[0][i])\npetya = 0\nfor i in range(5):\n\tpetya += points(value[i], t[1][i])\npot = [[0] * 20000 for i in range(5)]\nfor problem in range(5):\n\tfor cur_ac in range(20000):\n\t\tnew_value = 0\n\t\tif t[0][problem] < t[1][problem]:\n\t\t\tnew_value = get_value(n + cur_ac, solve[problem])\n\t\telif t[0][problem] != 250:\n\t\t\tnew_value = get_value(n + cur_ac, solve[problem] + cur_ac)\n\t\telse:\n\t\t\tnew_value = get_value(n + cur_ac, solve[problem])\n\t\twin = points(new_value, t[0][problem]) - points(new_value, t[1][problem]) - points(value[problem], t[0][problem]) + points(value[problem], t[1][problem])\n\t\tpot[problem][cur_ac] = win\nres = -1\nfor i in range(20000):\n\ttmp = 0\n\tfor pr in range(5):\n\t\tif len(pot[pr]) <= i:\n\t\t\ttmp += pot[pr][-1]\n\t\telse:\n\t\t\ttmp += pot[pr][i]\n\tif tmp > petya - vasya:\n\t\tres = i\n\t\tbreak\nprint(res)\n", "import sys\ninf = 10 ** 9 + 7\n\ndef solve():\n\tn = int(sys.stdin.readline())\n\tv = [int(vi) for vi in sys.stdin.readline().split()]\n\tp = [int(pi) for pi in sys.stdin.readline().split()]\n\tcnt = [0] * 5\n\tfor i in range(5):\n\t\tif v[i] != -1:\n\t\t\tcnt[i] += 1\n\t\tif p[i] != -1:\n\t\t\tcnt[i] += 1\n\tfor i in range(n - 2):\n\t\ta = [int(ai) for ai in sys.stdin.readline().split()]\n\t\tfor j in range(5):\n\t\t\tif a[j] != -1:\n\t\t\t\tcnt[j] += 1\n\tfor i in range(10 ** 5):\n\t\tif check(n, v, p, cnt, i):\n\t\t\tprint(i)\n\t\t\treturn\n\tprint(-1)\n\ndef check(n, v, p, cnt, m):\n\ttot = n + m\n\tsolved = cnt[:]\n\tdif = 0\n\tfor i in range(5):\n\t\tif p[i] != -1 and v[i] > p[i]:\n\t\t\tsolved[i] += m\n\tfor i in range(5):\n\t\tif solved[i] * 2 > tot:\n\t\t\tmax_score = 500\n\t\telif solved[i] * 4 > tot:\n\t\t\tmax_score = 1000\n\t\telif solved[i] * 8 > tot:\n\t\t\tmax_score = 1500\n\t\telif solved[i] * 16 > tot:\n\t\t\tmax_score = 2000\n\t\telif solved[i] * 32 > tot:\n\t\t\tmax_score = 2500\n\t\telse:\n\t\t\tmax_score = 3000\n\t\tif v[i] == p[i] == -1:\n\t\t\tpass\n\t\telif v[i] == -1:\n\t\t\tdif -= max_score * (250 - p[i]) // 250\n\t\telif p[i] == -1:\n\t\t\tdif += max_score * (250 - v[i]) // 250\n\t\telse:\n\t\t\tdif += max_score * (p[i] - v[i]) // 250\n\treturn dif > 0\nsolve()\n", "n = int(input())\nt = [0] * n\nfor i in range(n):\n\tt[i] = list(map(int, input().split()))\nvalue = [0] * 5\nsolve = [0] * 5\nfor i in range(5):\n\tsolved = 0\n\tfor j in range(n):\n\t\tif t[j][i] != -1:\n\t\t\tsolved += 1\n\t\telse:\n\t\t\tt[j][i] = 250\n\tif solved * 2 > n:\n\t\tvalue[i] = 500\n\telif solved * 4 > n:\n\t\tvalue[i] = 1000\n\telif solved * 8 > n:\n\t\tvalue[i] = 1500\n\telif solved * 16 > n:\n\t\tvalue[i] = 2000\n\telif solved * 32 > n:\n\t\tvalue[i] = 2500\n\telse:\n\t\tvalue[i] = 3000\n\tsolve[i] = solved\nvasya = 0\nfor i in range(5):\n\tvasya += value[i] - value[i] // 250 * t[0][i]\npetya = 0\nfor i in range(5):\n\tpetya += value[i] - value[i] // 250 * t[1][i]\npot = [[0] * 20000 for i in range(5)]\nfor problem in range(5):\n\tif t[0][problem] < t[1][problem]:\n\t\tcur_ac = 0\n\t\twhile 1:\n\t\t\tif solve[problem] * 32 <= n + cur_ac:\n\t\t\t\twin = 3000 - 3000 // 250 * t[0][problem] - (3000 - 3000 // 250 * t[1][problem]) - (value[problem] - value[problem] // 250 * t[0][problem] - (value[problem] - value[problem] // 250 * t[1][problem]))\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telif solve[problem] * 16 <= n + cur_ac:\n\t\t\t\twin = 2500 - 2500 // 250 * t[0][problem] - (2500 - 2500 // 250 * t[1][problem]) - (value[problem] - value[problem] // 250 * t[0][problem] - (value[problem] - value[problem] // 250 * t[1][problem]))\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telif solve[problem] * 8 <= n + cur_ac:\n\t\t\t\twin = 2000 - 2000 // 250 * t[0][problem] - (2000 - 2000 // 250 * t[1][problem]) - (value[problem] - value[problem] // 250 * t[0][problem] - (value[problem] - value[problem] // 250 * t[1][problem]))\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telif solve[problem] * 4 <= n + cur_ac:\n\t\t\t\twin = 1500 - 1500 // 250 * t[0][problem] - (1500 - 1500 // 250 * t[1][problem]) - (value[problem] - value[problem] // 250 * t[0][problem] - (value[problem] - value[problem] // 250 * t[1][problem]))\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telif solve[problem] * 2 <= n + cur_ac:\n\t\t\t\twin = 1000 - 1000 // 250 * t[0][problem] - (1000 - 1000 // 250 * t[1][problem]) - (value[problem] - value[problem] // 250 * t[0][problem] - (value[problem] - value[problem] // 250 * t[1][problem]))\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telse:\n\t\t\t\twin = 500 - 500 // 250 * t[0][problem] - (500 - 500 // 250 * t[1][problem]) - (value[problem] - value[problem] // 250 * t[0][problem] - (value[problem] - value[problem] // 250 * t[1][problem]))\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\tcur_ac += 1\n\t\t\tif cur_ac == 20000:\n\t\t\t\tbreak\n\telif t[0][problem] != 250:\n\t\tcur_ac = 0\n\t\twhile 1:\n\t\t\tif solve[problem] * 32 + cur_ac <= n + cur_ac:\n\t\t\t\twin = 3000 - 3000 // 250 * t[0][problem] - (3000 - 3000 // 250 * t[1][problem]) - (value[problem] - value[problem] // 250 * t[0][problem] - (value[problem] - value[problem] // 250 * t[1][problem]))\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telif solve[problem] * 16 + cur_ac <= n + cur_ac:\n\t\t\t\twin = 2500 - 2500 // 250 * t[0][problem] - (2500 - 2500 // 250 * t[1][problem]) - (value[problem] - value[problem] // 250 * t[0][problem] - (value[problem] - value[problem] // 250 * t[1][problem]))\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telif solve[problem] * 8 + cur_ac <= n + cur_ac:\n\t\t\t\twin = 2000 - 2000 // 250 * t[0][problem] - (2000 - 2000 // 250 * t[1][problem]) - (value[problem] - value[problem] // 250 * t[0][problem] - (value[problem] - value[problem] // 250 * t[1][problem]))\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telif solve[problem] * 4 + cur_ac <= n + cur_ac:\n\t\t\t\twin = 1500 - 1500 // 250 * t[0][problem] - (1500 - 1500 // 250 * t[1][problem]) - (value[problem] - value[problem] // 250 * t[0][problem] - (value[problem] - value[problem] // 250 * t[1][problem]))\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telif solve[problem] * 2 + cur_ac <= n + cur_ac:\n\t\t\t\twin = 1000 - 1000 // 250 * t[0][problem] - (1000 - 1000 // 250 * t[1][problem]) - (value[problem] - value[problem] // 250 * t[0][problem] - (value[problem] - value[problem] // 250 * t[1][problem]))\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telse:\n\t\t\t\twin = 500 - 500 // 250 * t[0][problem] - (500 - 500 // 250 * t[1][problem]) - (value[problem] - value[problem] // 250 * t[0][problem] - (value[problem] - value[problem] // 250 * t[1][problem]))\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\tcur_ac += 1\n\t\t\tif cur_ac == 20000:\n\t\t\t\tbreak\n\telse:\n\t\tcur_ac = 0\n\t\twhile 1:\n\t\t\tif solve[problem] * 32 <= n + cur_ac:\n\t\t\t\twin = -(3000 - 3000 // 250 * t[1][problem]) - -(value[problem] - value[problem] // 250 * t[1][problem])\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telif solve[problem] * 16 <= n + cur_ac:\n\t\t\t\twin = -(2500 - 2500 // 250 * t[1][problem]) - -(value[problem] - value[problem] // 250 * t[1][problem])\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telif solve[problem] * 8 <= n + cur_ac:\n\t\t\t\twin = -(2000 - 2000 // 250 * t[1][problem]) - -(value[problem] - value[problem] // 250 * t[1][problem])\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telif solve[problem] * 4 <= n + cur_ac:\n\t\t\t\twin = -(1500 - 1500 // 250 * t[1][problem]) - -(value[problem] - value[problem] // 250 * t[1][problem])\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telif solve[problem] * 2 <= n + cur_ac:\n\t\t\t\twin = -(1000 - 1000 // 250 * t[1][problem]) - -(value[problem] - value[problem] // 250 * t[1][problem])\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\telse:\n\t\t\t\twin = -(500 - 500 // 250 * t[1][problem]) - -(value[problem] - value[problem] // 250 * t[1][problem])\n\t\t\t\tpot[problem][cur_ac] = win\n\t\t\tcur_ac += 1\n\t\t\tif cur_ac == 20000:\n\t\t\t\tbreak\nres = -1\nmaxi = 0\nfor i in range(5):\n\tmaxi = max(maxi, len(pot[i]))\nfor i in range(maxi):\n\ttmp = 0\n\tfor pr in range(5):\n\t\tif len(pot[pr]) <= i:\n\t\t\ttmp += pot[pr][-1]\n\t\telse:\n\t\t\ttmp += pot[pr][i]\n\tif tmp > petya - vasya:\n\t\tres = i\n\t\tbreak\nprint(res)\n", "from sys import stdin, stdout\nfractionBoundaries = [1 / 2, 1 / 4, 1 / 8, 1 / 16, 1 / 32, 0]\nscoreList = [500, 1000, 1500, 2000, 2500, 3000]\n\ndef assessScores(n, Vsol, Psol, solvers):\n\tvScore = 0\n\tpScore = 0\n\tfor i in range(5):\n\t\tfor j in range(6):\n\t\t\tif solvers[i] / n > fractionBoundaries[j]:\n\t\t\t\tqnScore = scoreList[j]\n\t\t\t\tbreak\n\t\tif Vsol[i] >= 0:\n\t\t\tvScore += qnScore - qnScore * Vsol[i] // 250\n\t\tif Psol[i] >= 0:\n\t\t\tpScore += qnScore - qnScore * Psol[i] // 250\n\treturn vScore > pScore\n\ndef main():\n\tn = int(stdin.readline().rstrip())\n\tVsol = [int(x) for x in stdin.readline().rstrip().split()]\n\tPsol = [int(x) for x in stdin.readline().rstrip().split()]\n\tsolvers = [0] * 5\n\tfor _ in range(n - 2):\n\t\ta = [int(x) for x in stdin.readline().rstrip().split()]\n\t\tfor i in range(5):\n\t\t\tif a[i] >= 0:\n\t\t\t\tsolvers[i] += 1\n\tfor i in range(5):\n\t\tif Vsol[i] >= 0:\n\t\t\tsolvers[i] += 1\n\t\tif Psol[i] >= 0:\n\t\t\tsolvers[i] += 1\n\tnewSolvers = 0\n\tvWins = []\n\tpWins = []\n\tfor i in range(5):\n\t\tif Vsol[i] < Psol[i] and Vsol[i] >= 0 or (Vsol[i] >= 0 and Psol[i] < 0):\n\t\t\tvWins.append(i)\n\t\telif Psol[i] < Vsol[i] and Psol[i] >= 0 and (Vsol[i] >= 0):\n\t\t\tpWins.append(i)\n\tif len(vWins) == 0:\n\t\tprint(-1)\n\telse:\n\t\twhile not assessScores(n + newSolvers, Vsol, Psol, solvers) and newSolvers <= 100000007:\n\t\t\tsolversNeeded = 9999999999999\n\t\t\tfor i in range(5):\n\t\t\t\tif i in vWins:\n\t\t\t\t\tcurrentRatio = solvers[i] / (newSolvers + n)\n\t\t\t\t\tfor j in range(6):\n\t\t\t\t\t\tif solvers[i] / (newSolvers + n) > fractionBoundaries[j]:\n\t\t\t\t\t\t\tnextBoundary = fractionBoundaries[j]\n\t\t\t\t\t\t\tbreak\n\t\t\t\t\tif nextBoundary != 0:\n\t\t\t\t\t\tif solvers[i] % nextBoundary == 0:\n\t\t\t\t\t\t\tsolversNeeded = min([solvers[i] // nextBoundary - (newSolvers + n), solversNeeded])\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tsolversNeeded = min([solvers[i] // nextBoundary - (newSolvers + n) + 1, solversNeeded])\n\t\t\t\telif i in pWins and Vsol[i] > 0:\n\t\t\t\t\tcurrentRatio = solvers[i] / (newSolvers + n)\n\t\t\t\t\tfor j in range(6):\n\t\t\t\t\t\tif solvers[i] / (newSolvers + n) > fractionBoundaries[j]:\n\t\t\t\t\t\t\tif j > 0:\n\t\t\t\t\t\t\t\tnextBoundary = fractionBoundaries[j - 1]\n\t\t\t\t\t\t\t\tsolversNeeded = min([(nextBoundary * (newSolvers + n) - solvers[i]) // (1 - nextBoundary) + 1, solversNeeded])\n\t\t\t\t\t\t\tbreak\n\t\t\tnewSolvers += solversNeeded\n\t\t\tfor x in pWins:\n\t\t\t\tsolvers[x] += solversNeeded\n\t\tif newSolvers > 1000000007:\n\t\t\tprint(-1)\n\t\telse:\n\t\t\tprint(int(newSolvers))\nmain()\n", "def f(v, x, n):\n\tif v < 0:\n\t\treturn 0\n\telif x << 1 > n:\n\t\treturn int(500 * (1 - v / 250))\n\telif x << 2 > n:\n\t\treturn int(1000 * (1 - v / 250))\n\telif x << 3 > n:\n\t\treturn int(1500 * (1 - v / 250))\n\telif x << 4 > n:\n\t\treturn int(2000 * (1 - v / 250))\n\telif x << 5 > n:\n\t\treturn int(2500 * (1 - v / 250))\n\telse:\n\t\treturn int(3000 * (1 - v / 250))\nn = int(input())\na = [list(map(int, input().split())) for _ in range(n)]\nc = [sum((_[i] >= 0 for _ in a)) for i in range(5)]\nans = -1\nfor i in range(10000):\n\t(p, q) = (0, 0)\n\tfor j in range(5):\n\t\t(x, y) = (c[j], n)\n\t\tif a[0][j] > a[1][j] and a[1][j] >= 0:\n\t\t\tx += i\n\t\tp += f(a[0][j], x, n + i)\n\t\tq += f(a[1][j], x, n + i)\n\tif p > q:\n\t\tans = i\n\t\tbreak\nprint(ans)\n"]

difficulty: HARD

source: codeforces

raw_problem:
B. Dynamic Problem Scoring

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Vasya and Petya take part in a Codeforces round. The round lasts for two hours and contains five problems.

For this round the dynamic problem scoring is used. If you were lucky not to participate in any Codeforces round with dynamic problem scoring, here is what it means. The maximum point value of the problem depends on the ratio of the number of participants who solved the problem to the total number of round participants. Everyone who made at least one submission is considered to be participating in the round.

Pay attention to the range bounds. For example, if 40 people are taking part in the round, and 10 of them solve a particular problem, then the solvers fraction is equal to 1 / 4, and the problem's maximum point value is equal to 1500.

If the problem's maximum point value is equal to x, then for each whole minute passed from the beginning of the contest to the moment of the participant's correct submission, the participant loses x / 250 points. For example, if the problem's maximum point value is 2000, and the participant submits a correct solution to it 40 minutes into the round, this participant will be awarded with 2000·(1 - 40 / 250) = 1680 points for this problem.

There are n participants in the round, including Vasya and Petya. For each participant and each problem, the number of minutes which passed between the beginning of the contest and the submission of this participant to this problem is known. It's also possible that this participant made no submissions to this problem.

With two seconds until the end of the round, all participants' submissions have passed pretests, and not a single hack attempt has been made. Vasya believes that no more submissions or hack attempts will be made in the remaining two seconds, and every submission will pass the system testing.

Unfortunately, Vasya is a cheater. He has registered 109 + 7 new accounts for the round. Now Vasya can submit any of his solutions from these new accounts in order to change the maximum point values of the problems. Vasya can also submit any wrong solutions to any problems. Note that Vasya can not submit correct solutions to the problems he hasn't solved.

Vasya seeks to score strictly more points than Petya in the current round. Vasya has already prepared the scripts which allow to obfuscate his solutions and submit them into the system from any of the new accounts in just fractions of seconds. However, Vasya doesn't want to make his cheating too obvious, so he wants to achieve his goal while making submissions from the smallest possible number of new accounts.

Find the smallest number of new accounts Vasya needs in order to beat Petya (provided that Vasya's assumptions are correct), or report that Vasya can't achieve his goal.

Input

The first line contains a single integer n (2 ≤ n ≤ 120) — the number of round participants, including Vasya and Petya.

Each of the next n lines contains five integers ai, 1, ai, 2..., ai, 5 ( - 1 ≤ ai, j ≤ 119) — the number of minutes passed between the beginning of the round and the submission of problem j by participant i, or -1 if participant i hasn't solved problem j.

It is guaranteed that each participant has made at least one successful submission.

Vasya is listed as participant number 1, Petya is listed as participant number 2, all the other participants are listed in no particular order.

Output

Output a single integer — the number of new accounts Vasya needs to beat Petya, or -1 if Vasya can't achieve his goal.

Examples

Input

2
5 15 40 70 115
50 45 40 30 15

Output

2

Input

3
55 80 10 -1 -1
15 -1 79 60 -1
42 -1 13 -1 -1

Output

3

Input

5
119 119 119 119 119
0 0 0 0 -1
20 65 12 73 77
78 112 22 23 11
1 78 60 111 62

Output

27

Input

4
-1 20 40 77 119
30 10 73 50 107
21 29 -1 64 98
117 65 -1 -1 -1

Output

-1

Note

In the first example, Vasya's optimal strategy is to submit the solutions to the last three problems from two new accounts. In this case the first two problems will have the maximum point value of 1000, while the last three problems will have the maximum point value of 500. Vasya's score will be equal to 980 + 940 + 420 + 360 + 270 = 2970 points, while Petya will score just 800 + 820 + 420 + 440 + 470 = 2950 points.

In the second example, Vasya has to make a single unsuccessful submission to any problem from two new accounts, and a single successful submission to the first problem from the third new account. In this case, the maximum point values of the problems will be equal to 500, 1500, 1000, 1500, 3000. Vasya will score 2370 points, while Petya will score just 2294 points.

In the third example, Vasya can achieve his goal by submitting the solutions to the first four problems from 27 new accounts. The maximum point values of the problems will be equal to 500, 500, 500, 500, 2000. Thanks to the high cost of the fifth problem, Vasya will manage to beat Petya who solved the first four problems very quickly, but couldn't solve the fifth one.

question:
Vasya and Petya take part in a Codeforces round. The round lasts for two hours and contains five problems.
For this round the dynamic problem scoring is used. If you were lucky not to participate in any Codeforces round with dynamic problem scoring, here is what it means. The maximum point value of the problem depends on the ratio of the number of participants who solved the problem to the total number of round participants. Everyone who made at least one submission is considered to be participating in the round.
![image](1.png)
Pay attention to the range bounds. For example, if 40 people are taking part in the round, and 10 of them solve a particular problem, then the solvers fraction is equal to 1 / 4, and the problem's maximum point value is equal to 1500.
If the problem's maximum point value is equal to x, then for each whole minute passed from the beginning of the contest to the moment of the participant's correct submission, the participant loses x / 250 points. For example, if the problem's maximum point value is 2000, and the participant submits a correct solution to it 40 minutes into the round, this participant will be awarded with 2000·(1 - 40 / 250) = 1680 points for this problem.
There are n participants in the round, including Vasya and Petya. For each participant and each problem, the number of minutes which passed between the beginning of the contest and the submission of this participant to this problem is known. It's also possible that this participant made no submissions to this problem.
With two seconds until the end of the round, all participants' submissions have passed pretests, and not a single hack attempt has been made. Vasya believes that no more submissions or hack attempts will be made in the remaining two seconds, and every submission will pass the system testing.
Unfortunately, Vasya is a cheater. He has registered 10^{9} + 7 new accounts for the round. Now Vasya can submit any of his solutions from these new accounts in order to change the maximum point values of the problems. Vasya can also submit any wrong solutions to any problems. Note that Vasya can not submit correct solutions to the problems he hasn't solved.
Vasya seeks to score strictly more points than Petya in the current round. Vasya has already prepared the scripts which allow to obfuscate his solutions and submit them into the system from any of the new accounts in just fractions of seconds. However, Vasya doesn't want to make his cheating too obvious, so he wants to achieve his goal while making submissions from the smallest possible number of new accounts.
Find the smallest number of new accounts Vasya needs in order to beat Petya (provided that Vasya's assumptions are correct), or report that Vasya can't achieve his goal.

Input
The first line contains a single integer n (2 ≤ n ≤ 120) — the number of round participants, including Vasya and Petya.
Each of the next n lines contains five integers a_{i, 1}, a_{i, 2}..., a_{i, 5} ( - 1 ≤ a_{i, j} ≤ 119) — the number of minutes passed between the beginning of the round and the submission of problem j by participant i, or -1 if participant i hasn't solved problem j.
It is guaranteed that each participant has made at least one successful submission.
Vasya is listed as participant number 1, Petya is listed as participant number 2, all the other participants are listed in no particular order.

Output
Output a single integer — the number of new accounts Vasya needs to beat Petya, or -1 if Vasya can't achieve his goal.

Examples
Input
2
5 15 40 70 115
50 45 40 30 15

Output
2

Input
3
55 80 10 -1 -1
15 -1 79 60 -1
42 -1 13 -1 -1

Output
3

Input
5
119 119 119 119 119
0 0 0 0 -1
20 65 12 73 77
78 112 22 23 11
1 78 60 111 62

Output
27

Input
4
-1 20 40 77 119
30 10 73 50 107
21 29 -1 64 98
117 65 -1 -1 -1

Output
-1

Note
In the first example, Vasya's optimal strategy is to submit the solutions to the last three problems from two new accounts. In this case the first two problems will have the maximum point value of 1000, while the last three problems will have the maximum point value of 500. Vasya's score will be equal to 980 + 940 + 420 + 360 + 270 = 2970 points, while Petya will score just 800 + 820 + 420 + 440 + 470 = 2950 points.
In the second example, Vasya has to make a single unsuccessful submission to any problem from two new accounts, and a single successful submission to the first problem from the third new account. In this case, the maximum point values of the problems will be equal to 500, 1500, 1000, 1500, 3000. Vasya will score 2370 points, while Petya will score just 2294 points.
In the third example, Vasya can achieve his goal by submitting the solutions to the first four problems from 27 new accounts. The maximum point values of the problems will be equal to 500, 500, 500, 500, 2000. Thanks to the high cost of the fifth problem, Vasya will manage to beat Petya who solved the first four problems very quickly, but couldn't solve the fifth one.

tags: ['Complete search', 'Greedy algorithms']

data_split: test


Bubble Puzzle

source: ACM-ICPC Japan Alumni Group Winter Camp 2010 Day 4

raw_problem:
Problem B: Bubble Puzzle

A browser-based puzzle game called "Bubble Puzzle" is now popular on the Internet.

The puzzle is played on a 4 × 4 grid, and initially there are several bubbles in the grid squares. Each bubble has a state expressed by a positive integer, and the state changes when the bubble gets stimulated. You can stimulate a bubble by clicking on it, and this will increase the bubble's state by 1. You can also click on an empty square. In this case, a bubble with state 1 is newly created in the square.

When the state of a bubble becomes 5 or higher, the bubble blows up and disappears, and small waterdrops start flying in four directions (up, down, left and right). These waterdrops move one square per second. At the moment when a bubble blows up, 4 waterdrops are in the square the bubble was in, and one second later they are in the adjacent squares, and so on.

A waterdrop disappears either when it hits a bubble or goes outside the grid. When a waterdrop hits a bubble, the state of the bubble gets increased by 1. Similarly, if a bubble is hit by more than one water drop at the same time, its state is increased by the number of the hitting waterdrops. Please note that waterdrops do not collide with each other.

As shown in the figure above, waterdrops created by a blow-up may cause other blow-ups. In other words, one blow-up can trigger a chain reaction. You are not allowed to click on any square while waterdrops are flying (i.e., you have to wait until a chain reaction ends). The goal of this puzzle is to blow up all the bubbles and make all the squares empty as quick as possible.

Your mission is to calculate the minimum number of clicks required to solve the puzzle.

Input

The input consists of 4 lines, each contains 4 nonnegative integers smaller than 5. Each integer describes the initial states of bubbles on grid squares. 0 indicates that the corresponding square is empty.

Output

Output the minimum number of clicks to blow up all the bubbles on the grid in a line. If the answer is bigger than 5, output -1 instead. No extra characters should appear in the output.

Sample Input 1

4 4 4 4
4 4 4 4
4 4 4 4
4 4 4 4

Output for the Sample Input 1

1

Sample Input 2

2 4 4 1
2 4 4 1
2 4 4 1
2 4 4 1

Output for the Sample Input 2

5

Sample Input 3

2 4 3 4
2 2 4 4
3 3 2 2
2 3 3 3

Output for the Sample Input 3

3

solutions: ["from functools import reduce\nimport operator\ndef solve():\n    L = 4; M = 5\n    MP = [list(map(int, input().split())) for i in range(L)]\n    memo = {(0,)*(L**2): 0}\n    dd = ((-1, 0), (0, -1), (1, 0), (0, 1))\n    INF = 10\n    def dfs(k, R):\n        key = reduce(operator.add, map(tuple, R))\n        if key in memo:\n            return memo[key]\n        if k == 0:\n            return INF\n        r = INF\n        for i in range(L):\n            for j in range(L):\n                v = R[i][j]\n                R0 = [e[:] for e in R]\n                if R0[i][j] < 4:\n                    R0[i][j] += 1\n                    r = min(r, dfs(k-1, R0) + 1)\n                    continue\n                R0[i][j] = 0\n                S = [(j, i, a) for a in range(4)]\n                cnt = 1\n                while S:\n                    T = []\n                    for x, y, d in S:\n                        dx, dy = dd[d]\n                        nx = x + dx; ny = y + dy\n                        if not 0 <= nx < L or not 0 <= ny < L:\n                            continue\n                        if R0[ny][nx]:\n                            R0[ny][nx] += 1\n                        else:\n                            T.append((nx, ny, d))\n                    for y in range(L):\n                        for x in range(L):\n                            if R0[y][x] >= 5:\n                                R0[y][x] = 0\n                                cnt += 1\n                                T.extend((x, y, a) for a in range(4))\n                    S = T\n                r = min(r, dfs(k-1, R0) + 1)\n        memo[key] = r\n        return r\n    res = dfs(5, MP)\n    print(res if res < INF else -1)\nsolve()\n"]

source: aizu

question:
Problem B: Bubble Puzzle

A browser-based puzzle game called "Bubble Puzzle" is now popular on the Internet.

The puzzle is played on a 4 × 4 grid, and initially there are several bubbles in the grid squares. Each bubble has a state expressed by a positive integer, and the state changes when the bubble gets stimulated. You can stimulate a bubble by clicking on it, and this will increase the bubble's state by 1. You can also click on an empty square. In this case, a bubble with state 1 is newly created in the square.

When the state of a bubble becomes 5 or higher, the bubble blows up and disappears, and small waterdrops start flying in four directions (up, down, left and right). These waterdrops move one square per second. At the moment when a bubble blows up, 4 waterdrops are in the square the bubble was in, and one second later they are in the adjacent squares, and so on.

A waterdrop disappears either when it hits a bubble or goes outside the grid. When a waterdrop hits a bubble, the state of the bubble gets increased by 1. Similarly, if a bubble is hit by more than one water drop at the same time, its state is increased by the number of the hitting waterdrops. Please note that waterdrops do not collide with each other.

![image](1.png)

As shown in the figure above, waterdrops created by a blow-up may cause other blow-ups. In other words, one blow-up can trigger a chain reaction. You are not allowed to click on any square while waterdrops are flying (i.e., you have to wait until a chain reaction ends). The goal of this puzzle is to blow up all the bubbles and make all the squares empty as quick as possible.

Your mission is to calculate the minimum number of clicks required to solve the puzzle.

Input

The input consists of 4 lines, each contains 4 nonnegative integers smaller than 5. Each integer describes the initial states of bubbles on grid squares. 0 indicates that the corresponding square is empty.

Output

Output the minimum number of clicks to blow up all the bubbles on the grid in a line. If the answer is bigger than 5, output -1 instead. No extra characters should appear in the output.

Sample Input 1

4 4 4 4
4 4 4 4
4 4 4 4
4 4 4 4

Output for the Sample Input 1

1

Sample Input 2

2 4 4 1
2 4 4 1
2 4 4 1
2 4 4 1

Output for the Sample Input 2

5

Sample Input 3

2 4 3 4
2 2 4 4
3 3 2 2
2 3 3 3

Output for the Sample Input 3

3

data_split: test