Laser Puzzle

source: ACM-ICPC Japan Alumni Group Winter Contest 2009

raw_problem:
Problem E: Laser Puzzle

An explorer John is now at a crisis! He is entrapped in a <var>W</var>
times <var>H</var> rectangular room with a embrasure of laser beam. The
embrasure is shooting a deadly dangerous laser beam so that he cannot cross or
touch the laser beam. On the wall of this room, there are statues and a locked
door. The door lock is opening if the beams are hitting every statue.

In this room, there are pillars, mirrors and crystals. A mirror reflects
a laser beam. The angle of a mirror should be vertical, horizontal or diagonal.
A crystal split a laser beam into two laser beams with θ±(π/4)
where θ is the angle of the incident laser beam. He can push one mirror or
crystal at a time. He can push mirrors/crystals multiple times. But he can push
up to two of mirrors/crystals because the door will be locked forever when he
pushes the third mirrors/crystals.

To simplify the situation, the room consists of <var>W</var> times <var>H</var>
unit square as shown in figure 1.

Figure 1

He can move from a square to the neighboring square vertically or
horizontally. Please note that he cannot move diagonal direction. Pillars,
mirrors and crystals exist on the center of a square. As shown in the figure 2,
you can assume that a mirror/crystal moves to the center of the next square at
the next moment when he push it. That means, you don't need to consider a state
about pushing a mirror/crystal.

Figure 2

You can assume the following conditions:

the direction of laser beams are horizontal, vertical or diagonal,

the embrasure is shooting a laser beam to the center of the
	neighboring square,

the embrasure is on the wall,

he cannot enter to a square with pillar,

a mirror reflects a laser beam at the center of the square,

a mirror reflects a laser beam on the both side,

a mirror blocks a laser beam if the mirror is parallel to
	the laser beam,

a crystal split a laser beam at the center of the square,

diagonal laser does not hit a statue,

and he cannot leave the room if the door is hit by a vertical, horizontal or
	diagonal laser.

In order to leave this deadly room, he should push and move mirrors and
crystals to the right position and leave the room from the door. Your job is to
write a program to check whether it is possible to leave the room.

Figure 3 is an initial situation of the first sample input.

Figure 3

Figure 4 is one of the solution for the first sample input.

Figure 4

Input

The first line of the input contains two positive integers <var>W</var>
and <var>H</var> (2 < <var>W</var>, <var>H</var> <= 8). The map of the room is
given in the following <var>H</var> lines. The map consists of the following
characters:

'#': wall of the room,

'*': a pillar,

'S': a statue on the wall,

'/': a diagonal mirror with angle π/4 from the bottom side of the
	room,

'\': a diagonal mirror with angle 3π/4 from the bottom side of the
	room,

'-': a horizontal mirror,

'|': a vertical mirror,

'O': a crystal,

'@': the initial position of John,

'.': an empty floor,

'L': the embrasure,

'D': the door

The judges also guarantee that this problem can be solved without
extraordinary optimizations.

Output

Output "Yes" if it is possible for him to leave the room. Otherwise,
output "No".

Sample Input 1

7 8
##S####
#.....#
S.O...#
#.*|..#
L..*..#
#.O*..D
#.@...#
#######

Output for the Sample Input 1

Yes

Sample Input 2

8 3
###L####
S.../@.#
######D#

Output for the Sample Input 2

Yes

Sample Input 3

8 3
##L#####
S..\.@.#
######D#

Output for the Sample Input 3

No

source: aizu

question:
Problem E: Laser Puzzle
An explorer John is now at a crisis! He is entrapped in a $W$
times $H$ rectangular room with a embrasure of laser beam. The
embrasure is shooting a deadly dangerous laser beam so that he cannot cross or
touch the laser beam. On the wall of this room, there are statues and a locked
door. The door lock is opening if the beams are hitting every statue.
In this room, there are pillars, mirrors and crystals. A mirror reflects
a laser beam. The angle of a mirror should be vertical, horizontal or diagonal.
A crystal split a laser beam into two laser beams with θ±(π/4)
where θ is the angle of the incident laser beam. He can push one mirror or
crystal at a time. He can push mirrors/crystals multiple times. But he can push
up to two of mirrors/crystals because the door will be locked forever when he
pushes the third mirrors/crystals.
To simplify the situation, the room consists of $W$ times $H$
unit square as shown in figure 1.
![image](1.png)
Figure 1
He can move from a square to the neighboring square vertically or
horizontally. Please note that he cannot move diagonal direction. Pillars,
mirrors and crystals exist on the center of a square. As shown in the figure 2,
you can assume that a mirror/crystal moves to the center of the next square at
the next moment when he push it. That means, you don't need to consider a state
about pushing a mirror/crystal.
![image](2.png)
Figure 2
You can assume the following conditions:

- the direction of laser beams are horizontal, vertical or diagonal,
- the embrasure is shooting a laser beam to the center of the
	neighboring square,
- the embrasure is on the wall,
- he cannot enter to a square with pillar,
- a mirror reflects a laser beam at the center of the square,
- a mirror reflects a laser beam on the both side,
- a mirror blocks a laser beam if the mirror is parallel to
	the laser beam,
- a crystal split a laser beam at the center of the square,
- diagonal laser does not hit a statue,
- and he cannot leave the room if the door is hit by a vertical, horizontal or
	diagonal laser.

In order to leave this deadly room, he should push and move mirrors and
crystals to the right position and leave the room from the door. Your job is to
write a program to check whether it is possible to leave the room.
Figure 3 is an initial situation of the first sample input.
![image](3.png)
Figure 3
Figure 4 is one of the solution for the first sample input.
![image](4.png)
Figure 4
Input
The first line of the input contains two positive integers $W$
and $H$ (2 < $W$, $H$ <= 8). The map of the room is
given in the following $H$ lines. The map consists of the following
characters:

- '#': wall of the room,
- '*': a pillar,
- 'S': a statue on the wall,
- '/': a diagonal mirror with angle π/4 from the bottom side of the
	room,
- '\': a diagonal mirror with angle 3π/4 from the bottom side of the
	room,
- '-': a horizontal mirror,
- '|': a vertical mirror,
- 'O': a crystal,
- '@': the initial position of John,
- '.': an empty floor,
- 'L': the embrasure,
- 'D': the door

The judges also guarantee that this problem can be solved without
extraordinary optimizations.
Output
Output "Yes" if it is possible for him to leave the room. Otherwise,
output "No".
Sample Input 1

7 8
##S####
#.....#
S.O...#
#.*|..#
L..*..#
#.O*..D
#.@...#
#######

Output for the Sample Input 1

Yes

Sample Input 2

8 3
###L####
S.../@.#
######D#

Output for the Sample Input 2

Yes

Sample Input 3

8 3
##L#####
S..\.@.#
######D#

Output for the Sample Input 3

No

image_tags: Map Map Map Map

data_split: test


solutions: ["(a, b) = map(int, input().split())\nif a <= 16 / 2 and b <= 16 / 2:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "(a, b) = map(int, input().split())\nprint('Yay!' if a <= 8 and b <= 8 else ':(')\n", "(A, B) = map(int, input().split())\nif A <= 8 and B <= 8:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "(a, b) = map(int, input().split())\nprint('Yay!' if a < 9 and b < 9 else ':(')\n", "(a, b) = map(int, input().split())\nif abs(a - b) > 2:\n\tprint(':(')\nelse:\n\tprint('Yay!')\n", "(a, b) = map(int, input().split())\nif a > 8 or b > 8:\n\tprint(':(')\nelse:\n\tprint('Yay!')\n", "(A, B) = map(int, input().split())\nprint(['Yay!', ':('][A > 8 or B > 8])\n", "print('Yay!' if max(list(map(int, input().split()))) < 9 else ':(')\n", "(A, B) = map(int, input().split())\nprint(['Yay!', ':('][max(A, B) > 8])\n", "(a, b) = map(int, input().split(' '))\nprint([':(', 'Yay!'][max(a, b) < 9])\n", "(A, B) = map(int, input().split())\nans = 'Yay!' if max(A, B) <= 8 else ':('\nprint(ans)\n", "(a, b) = map(int, input().split())\nprint('Y:a(y !'[a // 9 | b // 9::2])\n", "(a, b) = map(int, input().split())\nprint([':(', 'Yay!'][a < 9 and b < 9])\n", "a = list(map(int, input().split()))\nprint('Yay!' if all((x <= 8 for x in a)) else ':(')\n", "lst = input().split()\na = int(lst[0])\nb = int(lst[1])\nif a <= 8 and b <= 8:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "(A, B) = map(int, input().split())\nprint([':(', 'Yay!'][A <= 8 and B <= 8])\n", "(A, B) = map(int, input().split())\nif max(A, B) <= 8:\n\tprint('Yay!')\n\texit()\nprint(':(')\n", "(a, b) = [int(x) for x in input().split()]\nprint('Yay!' if a <= 8 and b <= 8 else ':(')\n", "print('Yay!' if all(map(lambda num: int(num) <= 8, input().split())) else ':(')\n", "(a, b) = map(int, input().split())\nprint('Yay!' if abs(a - b) <= 1 else ':(')\n", "(A, B) = map(int, input().split())\nprint('Yay!' if A < 9 and B < 9 else ':(')\n", "ans = 'Yay!'\n(a, b) = map(int, input().split())\nif a > 8 or b > 8:\n\tans = ':('\nprint(ans)\n", "(a, b) = map(int, input().split())\nprint([':(', 'Yay!'][max(a, b) <= 8])\n", "if max(map(int, input().split())) <= 8:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "(A, B) = map(int, input().split())\nprint(':(' if A > 8 or B > 8 else 'Yay!')\n", "(a, b) = map(int, input().split())\nprint('Y:a(y !'[a > 8 or b > 8::2])\n", "(A, B) = map(int, open(0).read().split())\nprint('Yay!' if A <= 8 and B <= 8 else ':(')\n", "(n, m) = map(int, input().split())\nif n < 9 and m < 9:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "(a, b) = map(int, input().split())\nif a > 8 or b > 8:\n\tprint(':(')\n\texit()\nprint('Yay!')\n", "s = input()\nprint([':(', 'Yay!'][len(s) < 4 * ('9' not in s)])\n", "(A, B) = [int(x) for x in input().split()]\nprint('Yay!' if max(A, B) <= 8 else ':(')\n", "import sys\n\ndef input():\n\treturn sys.stdin.readline().rstrip()\n\ndef main():\n\tprint('Yay!' if all([True if int(x) < 9 else False for x in input().split()]) else ':(')\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "from functools import reduce\n\ndef solve(a, b):\n\tif a <= 8 and b <= 8:\n\t\treturn 'Yay!'\n\telse:\n\t\treturn ':('\n\ndef main():\n\t(a, b) = list(map(int, input().split()))\n\tprint('{}'.format(solve(a, b)))\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "(a, b) = list(map(int, input().split()))\nprint('Yay!' if max(a, b) <= 8 else ':(')\n", "import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools\nfrom collections import deque\nsys.setrecursionlimit(10 ** 7)\ninf = 10 ** 20\nmod = 10 ** 9 + 7\nDR = [1, -1, 0, 0]\nDC = [0, 0, 1, -1]\n\ndef LI():\n\treturn [int(x) for x in sys.stdin.readline().split()]\n\ndef LI_():\n\treturn [int(x) - 1 for x in sys.stdin.readline().split()]\n\ndef LF():\n\treturn [float(x) for x in sys.stdin.readline().split()]\n\ndef LS():\n\treturn sys.stdin.readline().split()\n\ndef I():\n\treturn int(sys.stdin.readline())\n\ndef F():\n\treturn float(sys.stdin.readline())\n\ndef S():\n\treturn input()\n\ndef main():\n\t(A, B) = LI()\n\tif A < 9 and B < 9:\n\t\tprint('Yay!')\n\telse:\n\t\tprint(':(')\nmain()\n", "(A, B) = map(int, input().split())\nprint(':(') if A >= 9 or B >= 9 else print('Yay!')\n", "(a, b) = map(int, input().split())\nprint(['Yay!', ':('][a > 8 or b > 8])\n", "(x, y) = map(int, input().split())\nres = 'Yay!'\nif x > 8 or y > 8:\n\tres = ':('\nprint(res)\n", "(A, B) = map(int, input().split())\nif abs(A - B) <= 1:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "import sys\ninput = sys.stdin.readline\n(a, b) = map(int, input().split())\nc = max(a, b)\nd = min(a, b)\ne = 16 - 2 * c\nif e < 0:\n\tprint(':(')\nelif e // 2 >= c - d:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "(a, b) = [int(x) for x in input().split()]\nprint(['Yay!', ':('][a > 8 or b > 8])\n", "(A, B) = map(int, input().split())\nans = 'Yay!'\nif A > 8 or B > 8:\n\tans = ':('\nprint(ans)\n", "x = input()\ny = x.split()\na = int(y[0])\nb = int(y[1])\nif a > 8 or b > 8:\n\tprint(':(')\nelse:\n\tprint('Yay!')\n", "print([':(', 'Yay!'][max(map(int, input().split())) < 9])\n", "print(['Yay!', ':('][max(map(int, input().split())) > 8])\n", "s = input()\nprint(':(' if len(s) > 3 or '9' in s else 'Yay!')\n", "(a, b) = map(int, input().split())\nc = abs(a - b)\nprint('Yay!' if a + b + c <= 16 else ':(')\n", "(a, b) = map(int, input().split())\nprint('Yay!' if 9 > max(a, b) else ':(')\n", "def mapt(fn, *args):\n\treturn tuple(map(fn, *args))\n\ndef Input():\n\treturn mapt(int, input().split(' '))\n\ndef main():\n\t(a, b) = Input()\n\tif a <= 8 and b <= 8:\n\t\tprint('Yay!')\n\telse:\n\t\tprint(':(')\nmain()\n", "(x, y) = input().split()\nif int(x) <= 8 and int(y) <= 8:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "print(['Yay!', ':(', ':('][sum([int(x) > 8 for x in input().split()])])\n", "(a, b) = map(int, input().split())\nprint(':Y(a y !'[16 - a - b >= max(a, b) - min(a, b)::2])\n", "(a, b) = map(int, input().split())\nif a >= 9 or b >= 9:\n\tprint(':(')\nelse:\n\tprint('Yay!')\n", "t = input()\nprint(['Yay!', ':('][len(t) > 3 or '9' in t])\n", "def get_input() -> tuple:\n\t(A, B) = list(map(int, input().split()))\n\treturn (A, B)\n\ndef main(A: int, B: int) -> None:\n\tans = str()\n\tif A <= 8 and B <= 8:\n\t\tans = 'Yay!'\n\telse:\n\t\tans = ':('\n\tprint(ans)\n\ndef __starting_point():\n\t(A, B) = get_input()\n\tmain(A, B)\n__starting_point()\n", "print([':(', 'Yay!'][eval('max(' + input().replace(' ', ',') + ')') <= 8])\n", "(n, k) = map(int, input().split())\nif abs(n - k) > 2:\n\tprint(':(')\nelse:\n\tprint('Yay!')\n", "(a, b) = map(int, input().split())\nprint([':(', 'Yay!'][a <= 8 and b <= 8])\n", "(x, y) = map(int, input().split())\nif x > 8 or y > 8:\n\tprint(':(')\nelse:\n\tprint('Yay!')\n", "import sys\nimport math\nsys.setrecursionlimit(10 ** 8)\nini = lambda : int(sys.stdin.readline())\ninm = lambda : map(int, sys.stdin.readline().split())\ninl = lambda : list(inm())\nins = lambda : sys.stdin.readline().rstrip()\ndebug = lambda *a, **kw: print('\\x1b[33m', *a, '\\x1b[0m', **dict(file=sys.stderr, **kw))\n(A, B) = inm()\nif A <= 8 and B <= 8:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "print(':(') if 0 in [0 for i in input().split() if int(i) > 8] else print('Yay!')\n", "s = input()\nprint(['Yay!', ':('][len(s) > 3 or '9' in s])\n", "A = list(map(int, input().split()))\nprint('Yay!' if max(A) <= 8 else ':(')\n", "print('Yay!' if max([int(i) for i in input().split()]) <= 8 else ':(')\n", "(A, B) = map(int, input().split())\nprint(':Y(a y !'[(A <= 8) * (B <= 8)::2])\n", "def main():\n\t(a, b) = list(map(int, input().split()))\n\tif a <= 8 and b <= 8:\n\t\tprint('Yay!')\n\telse:\n\t\tprint(':(')\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "print([':(', 'Yay!'][all((i < 9 for i in map(int, input().split())))])\n", "import sys\n(A, B) = list(map(int, input().split()))\nif A <= 8 and B <= 8:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "print('Yay!' if all([x < 9 for x in map(int, input().split())]) else ':(')\n", "print('Yay!' if all((int(i) <= 8 for i in input().split())) else ':(')\n", "(n, m) = map(int, input().split())\nprint('Yay!' if n <= 8 and m <= 8 else ':(')\n", "(x, y) = map(int, input().split())\nif x < 9 and y < 9:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "(A, B) = [int(x) for x in input().split()]\nprint('Yay!' if A < 9 and B < 9 else ':(')\n", "(a, b) = map(int, input().split())\nres = ':('\nif a <= 8 and b <= 8:\n\tres = 'Yay!'\nprint(res)\n", "print(':Y(a y !'[eval(input().replace(' ', '<9>'))::2])\n", "M = max([int(x) for x in input().split()])\nprint('Yay!' if M <= 8 else ':(')\n", "print('Yay!' if all((int(tok) <= 8 for tok in input().split())) else ':(')\n", "(x, y) = map(int, input().split())\nprint(['Yay!', ':('][x > 8 or y > 8])\n", "(A, B) = map(int, input().split())\nprint([':(', 'Yay!'][A < 9 and B < 9])\n", "print(['Yay!', ':(', ':('][sum([int(i) // 9 for i in input().split()])])\n", "(n, m) = [int(x) for x in input().split()]\nif n < 9 and m < 9:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "(a, b) = map(int, input().split())\nif abs(a - b) > 0:\n\tif a + b + abs(a - b) < 17:\n\t\tprint('Yay!')\n\telse:\n\t\tprint(':(')\nelse:\n\tprint('Yay!')\n", "(a, b) = list(map(int, input().split()))\nif a <= 8 and b <= 8:\n\tprint('Yay!')\n\treturn\nprint(':(')\n", "(A, B) = list(map(int, input().split()))\nans = str()\nif A <= 8 and B <= 8:\n\tans = 'Yay!'\nelse:\n\tans = ':('\nprint(ans)\n", "(a, b) = list(map(int, input().split()))\nif max(a, b) - min(a, b) <= 1:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "l = list(map(int, input().split()))\nif l[0] <= 8 and l[1] <= 8:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "(N, K) = map(int, input().split())\nprint('Yay!' if N <= 8 and K <= 8 else ':(')\n", "import sys\n\ndef input():\n\treturn sys.stdin.readline().strip()\n\ndef I():\n\treturn int(input())\n\ndef LI():\n\treturn list(map(int, input().split()))\n\ndef IR(n):\n\treturn [I() for i in range(n)]\n\ndef LIR(n):\n\treturn [LI() for i in range(n)]\n\ndef SR(n):\n\treturn [S() for i in range(n)]\n\ndef S():\n\treturn input()\n\ndef LS():\n\treturn input().split()\nINF = float('inf')\n(a, b) = LI()\nif a <= 8 and b <= 8:\n\tprint('Yay!')\nelse:\n\tprint(':(')\n", "(A, B) = map(int, input().split())\nif max(A, B) >= 9:\n\tprint(':(')\nelse:\n\tprint('Yay!')\n", "(a, b) = input().split()\na = int(a)\nb = int(b)\nif a <= 8:\n\tif b <= 8:\n\t\tprint('Yay!')\n\telse:\n\t\tprint(':(')\nelse:\n\tprint(':(')\n"]

difficulty: EASY

name: AtCoder Beginner Contest 100 - Happy Birthday!

source: atcoder

time_limit: 2.0 seconds

memory_limit: 1000.0 megabytes

raw_problem:
配点: <var>100</var> 点

問題文

もうすぐ E869120 君と square1001 君の <var>16</var> 才の誕生日が来る.

そこで, AtCoder 王国の高橋君は, 円形のケーキ <var>1</var> 個に放射状に切れ目を入れ <var>16</var> 等分したものを, 彼らにプレゼントした.

E869120 君はそのうち <var>A</var> 切れ、square1001 君は <var>B</var> 切れを食べようとした.

しかし, ケーキと一緒についていた紙を見ると, 「同じ人が隣り合う <var>2</var> 切れのケーキを両方取ってはならない」と書かれていた.

さて、彼らは紙に書かれたことを守って、<var>2</var> 人とも食べたい数のケーキを取ることができるだろうか？

制約

<var>A, B</var> は <var>1</var> 以上 <var>16</var> 以下の整数

<var>A+B</var> は <var>16</var> 以下である.

入力

入力は以下の形式で標準入力から与えられる.

<var>A</var> <var>B</var>

出力

紙に書かれたことを守って, E869120 君と square1001 君両方が, 食べたい数のケーキを取ることができるならば Yay!, そうでなければ :( と出力しなさい.

入力例 1

5 4

出力例 1

Yay!

下の図のようにケーキを取れば、<var>2</var> 人とも目標を達成することができる.

入力例 2

8 8

出力例 2

Yay!

下の図のようにケーキを取れば、<var>2</var> 人とも目標を達成することができる.

入力例 3

11 4

出力例 3

:(

この場合, 残念ながら目標を達成する方法は <var>1</var> つもない.

Score: <var>100</var> points

Problem Statement

E869120's and square1001's <var>16</var>-th birthday is coming soon.

Takahashi from AtCoder Kingdom gave them a round cake cut into <var>16</var> equal fan-shaped pieces.

E869120 and square1001 were just about to eat <var>A</var> and <var>B</var> of those pieces, respectively,

when they found a note attached to the cake saying that "the same person should not take two adjacent pieces of cake".

Can both of them obey the instruction in the note and take desired numbers of pieces of cake?

Constraints

<var>A</var> and <var>B</var> are integers between <var>1</var> and <var>16</var> (inclusive).

<var>A+B</var> is at most <var>16</var>.

Input

Input is given from Standard Input in the following format:

<var>A</var> <var>B</var>

Output

If both E869120 and square1001 can obey the instruction in the note and take desired numbers of pieces of cake, print Yay!; otherwise, print :(.

Sample Input 1

5 4

Sample Output 1

Yay!

Both of them can take desired number of pieces as follows:

Sample Input 2

8 8

Sample Output 2

Yay!

Both of them can take desired number of pieces as follows:

Sample Input 3

11 4

Sample Output 3

:(

In this case, there is no way for them to take desired number of pieces, unfortunately.

question:
E869120's and square1001's $16$-th birthday is coming soon.
Takahashi from AtCoder Kingdom gave them a round cake cut into $16$ equal fan-shaped pieces.
E869120 and square1001 were just about to eat $A$ and $B$ of those pieces, respectively,
when they found a note attached to the cake saying that "the same person should not take two adjacent pieces of cake".
Can both of them obey the instruction in the note and take desired numbers of pieces of cake?

Constraints

- $A$ and $B$ are integers between $1$ and $16$ (inclusive).
- $A+B$ is at most $16$.

Input

Input is given from Standard Input in the following format:
$A$ $B$

Output

If both E869120 and square1001 can obey the instruction in the note and take desired numbers of pieces of cake, print Yay!; otherwise, print :(.

Sample Input 1
5 4

Sample Output 1
Yay!

Both of them can take desired number of pieces as follows:
![image](1.png)

Sample Input 2
8 8

Sample Output 2
Yay!

Both of them can take desired number of pieces as follows:
![image](2.png)

Sample Input 3
11 4

Sample Output 3
:(

In this case, there is no way for them to take desired number of pieces, unfortunately.

image_tags: Patterns Patterns

data_split: test


Crop Circle

source: University of Aizu Programming Contest 2009, PCK Warm Up

raw_problem:
Problem 07: Crop Circle

アルゼンチンの広大な農地に突如ミステリーサークルが出没した。ミステリーサークルは重なっているもの、ポツンとあるもの、大きいもの、小さいものと合計 n 個確認された。

あるミステリーハンターが空中からミステリーサークルの全体像を撮影しようと試みたところ、各円の輪郭がはっきりしていなかったため、映像にその美しい模様を映し出すことが難しいことが分かった。

そこで、そのミステリーハンターは輪郭に沿って特殊素材の紐を設置し、輪郭を強調する提案をした。

紐を設置する部分は、あるミステリーサークルの円周上で、他のどのミステリーサークルにも含まれない部分である。

撮影隊は必要な紐の長さを計測するために、プログラムの作成をあなたに依頼した。各ミステリーサークルの中心座標と半径を入力し、設置する紐の長さを報告するプログラムを作成せよ。

参考として入出力例の１つ目と２つ目のケースをそれぞれ図１、図２に示す。紐の部分が太い線で示されている。

図１

図２

Input

入力として複数のデータセットが与えられる。各データセットは以下の形式で与えられる：

n　（ミステリーサークルの数：整数）

x1 y1 r1 　（1 個目のサークルの中心座標と半径：空白区切りの実数）

x2 y2 r2 　（2 個目のサークルの中心座標と半径：空白区切りの実数）

.

.

xn yn rn 　（n 個目のサークルの中心座標と半径：空白区切りの実数）

n が 0 のとき、入力の終わりを示す。

Output

各データセットに対して、紐の長さを１行に出力せよ。出力は 0.000001 以下の誤差を含んでもよい。

Constraints

n ≤ 100

-1000 ≤ xi, yi  ≤ 1000

0 < ri  ≤ 100

Sample Input

4
6 4 2
4 7 3
7 10 3
13 6 1
4
7 4 2
4 7 3
7 10 3
11 6 3
0

Output for the Sample Input

39.664699289572
45.627024663706

solutions: ["def string_to_float(s):\n    return list(map(float, s.split()))\n\ndef solve():\n    from sys import stdin\n    lines = stdin.readlines()\n    from itertools import combinations\n    from math import acos, pi\n    from cmath import phase\n    from bisect import insort\n    \n    while True:\n        n = int(lines[0])\n        if n == 0:\n            break\n        \n        circles = enumerate(map(string_to_float, lines[1:1+n]))\n        cross_data = [[] for i in range(n)]\n        included = [False] * n\n        r_sum = sum(map(lambda x: float(x.split()[2]), lines[1:1+n]))\n        ans = 2 * pi * r_sum\n        \n        for c1, c2 in combinations(circles, 2):\n            n1, xyr1 = c1\n            n2, xyr2 = c2\n            if included[n1] or included[n2]:\n                continue\n            \n            x1, y1, r1 = xyr1\n            x2, y2, r2 = xyr2\n            cn1 = x1 + y1 * 1j\n            cn2 = x2 + y2 * 1j\n            \n            v12 = cn2 - cn1\n            d = abs(v12)\n            if d >= r1 + r2:\n                continue\n            elif  d <= abs(r1 - r2):\n                if r1 < r2:\n                    ans -= 2 * pi * r1\n                    included[n1] = True\n                else:\n                    ans -= 2 * pi * r2\n                    included[n2] = True\n                continue\n            \n            a = acos((r1 ** 2 + d ** 2 - r2 ** 2) / (2 * r1 * d))\n            t = phase(v12)\n            s = t - a\n            e = t + a\n            cd = cross_data[n1]\n            if s >= -pi and e <= pi:\n                insort(cd, (s, -1))\n                insort(cd, (e, 1))\n            elif s < -pi:\n                insort(cd, (s + 2 * pi, -1))\n                insort(cd, (pi, 1))\n                insort(cd, (-pi, -1))\n                insort(cd, (e, 1))\n            else:\n                insort(cd, (s, -1))\n                insort(cd, (pi, 1))\n                insort(cd, (-pi, -1))\n                insort(cd, (e - 2 * pi, 1))\n            \n            a = acos((r2 ** 2 + d ** 2 - r1 ** 2) / (2 * r2 * d))\n            t = phase(-v12)\n            s = t - a\n            e = t + a\n            cd = cross_data[n2]\n            if s >= -pi and e <= pi:\n                insort(cd, (s, -1))\n                insort(cd, (e, 1))\n            elif s < -pi:\n                insort(cd, (s + 2 * pi, -1))\n                insort(cd, (pi, 1))\n                insort(cd, (-pi, -1))\n                insort(cd, (e, 1))\n            else:\n                insort(cd, (s, -1))\n                insort(cd, (pi, 1))\n                insort(cd, (-pi, -1))\n                insort(cd, (e - 2 * pi, 1))\n        \n        radius = map(lambda x: float(x.split()[2]), lines[1:1+n])\n        flag = 0\n        for cd, r in zip(cross_data, radius):\n            for ang, f in cd:\n                if flag == 0:\n                    s = ang\n                flag += f\n                if flag == 0:\n                    ans -= r * (ang - s)\n                    \n        print(ans)\n        \n        del lines[:1+n]\n\nsolve()\n"]

source: aizu

question:
Problem 07: Crop Circle

A mysterious crop circle suddenly appeared in the vast farmlands of Argentina. There were a total of n circles identified, overlapping ones, isolated ones, large ones, and small ones.

When a mystery hunter attempted to capture the entire view of the crop circles from the air, it became difficult to reflect their beautiful patterns on the video due to the unclear delineation of each circle.

Therefore, the mystery hunter proposed to enhance the outline by placing a special material string along the circumference.

The parts where the string will be placed, are on the circumference of a certain crop circle, which is not included in any other crop circle.

The photography team has commissioned you to create a program that inputs the central coordinates and radius of each crop circle, and reports the length of the string to be installed.

As a reference, the first and second cases of the input and output example are shown in Figure 1 and Figure 2, respectively. The portion of the string is indicated by a thick line.

![image](1.png)
Figure 1

![image](2.png)
Figure 2

Input

Multiple datasets are given as input. Each dataset is given in the following format:

n  (The number of crop circles: integer)
x_{1} y_{1} r_{1}  (Central coordinates and radius of the 1st circle: real numbers separated by space)
x_{2} y_{2} r_{2}  (Central coordinates and radius of the 2nd circle: real numbers separated by space)
.
.
x_{n} y_{n} r_{n}  (Central coordinates and radius of the nth circle: real numbers separated by space)

When n is 0, it indicates the end of the input.

Output

For each dataset, output the length of the string on one line. The output may contain an error of less than or equal to 0.000001.

Constraints

- n ≤ 100
- -1000 ≤ x_{i}, y_{i}  ≤ 1000
- 0 < r_{i}  ≤ 100

Sample Input

4
6 4 2
4 7 3
7 10 3
13 6 1
4
7 4 2
4 7 3
7 10 3
11 6 3
0

Output for the Sample Input

39.664699289572
45.627024663706

image_tags:
2D Geometry
2D Geometry

data_split: test


F. Ber Patio

problem_index: F

time_limit: 3 seconds

memory_limit: 512 megabytes

question:
Polycarp is a regular customer at the restaurant "Ber Patio". He likes having lunches there.
"Ber Patio" has special discount program for regular customers. A customer can collect bonuses and partially cover expenses in the restaurant.
Let's assume a customer currently has b bonuses and she has to pay r burles for a lunch. In this case the customer can use bonuses (1 bonus = 1 burle) to reduce the payment. She can cover at most half of the payment using bonuses. However, 1 bonus will be added to the customer's bonus balance per each 10 burles she paid.
Formally:
 -  a customer can choose any number x of bonuses to use (![image](1.png))), -  the customer's bonus balance is reduced by x, -  the customer pays r - x burles, -  the customer's bonus balance is increased by ⌊(r - x) / 10⌋ (i.e. integer division rounded down is used). Initially, there are b bonuses on Polycarp's account. Polycarp is going to have a lunch in "Ber Patio" for the next n days. He estimated the values a_{1}, a_{2}, ..., a_{n}, where a_{i} is the number of burles in a receipt for the i-th day. The sum over all receipts doesn't exceed 10^{5} burles.
Write a program to find the minimum number of burles Polycarp has to spend and an optimal strategy to use bonuses.

Input
The first line contains two integer numbers n and b (1 ≤ n ≤ 5000, 0 ≤ b ≤ 10^{5}) — number of days and initial number of bonuses Polycarp has.
The second line contains the integer sequence a_{1}, a_{2}, ..., a_{n} (1 ≤ a_{i} ≤ 1000), where a_{i} is the amount of burles in the i-th day's receipt.
It is guaranteed that the sum of all receipts does not exceed 10^{5} burles.

Output
On the first line, print the expected minimal number of burles to pay for all n receipts.
On the second line, print the sequence of integer numbers b_{1}, b_{2}, ..., b_{n}, where b_{i} is the number of bonuses to use on the i-th day. If there are multiple solutions, print any of them.

Examples
Input
3 21
12 75 52

Output
110
2 5 22

Input
3 39
58 64 33

Output
107
28 4 16

source: codeforces

raw_problem:
F. Ber Patio

time limit per test
3 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

Polycarp is a regular customer at the restaurant "Ber Patio". He likes having lunches there.

"Ber Patio" has special discount program for regular customers. A customer can collect bonuses and partially cover expenses in the restaurant.

Let's assume a customer currently has b bonuses and she has to pay r burles for a lunch. In this case the customer can use bonuses (1 bonus = 1 burle) to reduce the payment. She can cover at most half of the payment using bonuses. However, 1 bonus will be added to the customer's bonus balance per each 10 burles she paid.

Formally:

 a customer can choose any number x of bonuses to use ()),

 the customer's bonus balance is reduced by x,

 the customer pays r - x burles,

 the customer's bonus balance is increased by ⌊(r - x) / 10⌋ (i.e. integer division rounded down is used).

Initially, there are b bonuses on Polycarp's account. Polycarp is going to have a lunch in "Ber Patio" for the next n days. He estimated the values a1, a2, ..., an, where ai is the number of burles in a receipt for the i-th day. The sum over all receipts doesn't exceed 105 burles.

Write a program to find the minimum number of burles Polycarp has to spend and an optimal strategy to use bonuses.

Input

The first line contains two integer numbers n and b (1 ≤ n ≤ 5000, 0 ≤ b ≤ 105) — number of days and initial number of bonuses Polycarp has.

The second line contains the integer sequence a1, a2, ..., an (1 ≤ ai ≤ 1000), where ai is the amount of burles in the i-th day's receipt.

It is guaranteed that the sum of all receipts does not exceed 105 burles.

Output

On the first line, print the expected minimal number of burles to pay for all n receipts.

On the second line, print the sequence of integer numbers b1, b2, ..., bn, where bi is the number of bonuses to use on the i-th day. If there are multiple solutions, print any of them.

Examples

Input

3 21
12 75 52

Output

110
2 5 22

Input

3 39
58 64 33

Output

107
28 4 16

data_split: test


Sneak Attack

difficulty: HARD

source: open kattis

raw_problem:
You are in a game of laser tag, where the goal is to shoot
    and hit other players with the laser gun you are carrying.
    Running up to them and shooting sometimes works, but it leaves
    you more vulnerable to their counterattack than you would like.
    You have found that you can be sneakier if you bounce your shot
    off of a mirror before it hits them. This allows you to shoot
    around a corner, for example.

To practice your shots, you shoot at a wall (the target) by
    reflecting your shot off of a mirror. Write a program that
    tells you where on the target wall your laser would strike when
    shooting from different locations. The wall is considered to be
    infinitely long at $x=0$.

Input

Input consists of up to $1\,
    500$ test cases. Each test case consists of six
    space-separated real values, $x_1~ y_1~ x_2~ y_2~ x_3~ y_3$. The
    first four numbers represent the endpoints of the mirror, and
    the last two represent your position. You can be sure that
    $x_1 \neq x_2$, or
    $y_1 \neq y_2$, or both.
    You can also be sure that $x_1\cdot x_2>0$. You are not
    standing on the mirror. All coordinates are in the range
    $[-100,100]$ with at most
    $5$ digits past the
    decimal point. Input ends at end of file.

Output

For each test case, report the $y$-coordinates of the range of
    locations on the wall that you can hit if you shoot at the
    mirror. Hitting either side of the (infinitely thin) wall is
    considered a hit. Report the coordinates from least to
    greatest. If you can hit an infinitely-long section of the
    wall, use the terms <tt class="ttfamily">negative-infinity</tt>
    or <tt class="ttfamily">positive-infinity</tt> as appropriate.
    Ignore any potential occlusions, such as the laser hitting you,
    or the laser hitting the wall before getting to the mirror.
    Numeric answers should be accurate to within $0.0001$ units. If you can’t hit the
    wall at all, output <tt>can't hit the wall</tt>.

Sample Input 1
Sample Output 1

5 10 10 10 10 0
5 10 10 5 10 0
6 10 10 10 10 0

negative-infinity 0
5 12.5
negative-infinity -5

Sample Input 2
Sample Output 2

10 10 20 20 20 10

can't hit the wall

question:
You are in a game of laser tag, where the goal is to shoot and hit other players with the laser gun you are carrying. Running up to them and shooting sometimes works, but it leaves you more vulnerable to their counterattack than you would like. You have found that you can be sneakier if you bounce your shot off of a mirror before it hits them. This allows you to shoot around a corner, for example.
To practice your shots, you shoot at a wall (the target) by reflecting your shot off of a mirror. Write a program that tells you where on the target wall your laser would strike when shooting from different locations. The wall is considered to be infinitely long at$x=0$.
![image](1.png)
Input
Input consists of up to$1\, 500$test cases. Each test case consists of six space-separated real values,$x_1~ y_1~ x_2~ y_2~ x_3~ y_3$. The first four numbers represent the endpoints of the mirror, and the last two represent your position. You can be sure that$x_1 \neq x_2$, or$y_1 \neq y_2$, or both. You can also be sure that$x_1\cdot x_2>0$. You are not standing on the mirror. All coordinates are in the range$[-100,100]$with at most$5$digits past the decimal point. Input ends at end of file.

Output
For each test case, report the$y$-coordinates of the range of locations on the wall that you can hit if you shoot at the mirror. Hitting either side of the (infinitely thin) wall is considered a hit. Report the coordinates from least to greatest. If you can hit an infinitely-long section of the wall, use the termsnegative-infinityorpositive-infinityas appropriate. Ignore any potential occlusions, such as the laser hitting you, or the laser hitting the wall before getting to the mirror. Numeric answers should be accurate to within$0.0001$units. If you can’t hit the wall at all, outputcan't hit the wall.
Sample Input 1
5 10 10 10 10 0
5 10 10 5 10 0
6 10 10 10 10 0

Sample Output 1
negative-infinity 0
5 12.5
negative-infinity -5

Sample Input 2
10 10 20 20 20 10

Sample Output 2
can't hit the wall

data_split: test


solutions: ["import sys\ninput = sys.stdin.readline\n\ndef main():\n\tn = int(input())\n\tl = [list(map(int, input().split())) for i in range(n)]\n\txcal = [[0] * n for i in range(1 << n)]\n\tycal = [[0] * n for i in range(1 << n)]\n\tfor i in range(1 << n):\n\t\tfor j in range(n):\n\t\t\txcal[i][j] = abs(l[j][0])\n\t\t\tycal[i][j] = abs(l[j][1])\n\t\t\tfor k in range(n):\n\t\t\t\tif i >> k & 1:\n\t\t\t\t\txcal[i][j] = min(xcal[i][j], abs(l[j][0] - l[k][0]))\n\t\t\t\t\tycal[i][j] = min(ycal[i][j], abs(l[j][1] - l[k][1]))\n\t\t\txcal[i][j] *= l[j][2]\n\t\t\tycal[i][j] *= l[j][2]\n\tans = [float('INF')] * (n + 1)\n\tfor i in range(1 << n):\n\t\tcount = 0\n\t\tfor j in range(n):\n\t\t\tif i >> j & 1:\n\t\t\t\tcount += 1\n\t\tj = i\n\t\twhile j >= 0:\n\t\t\tj &= i\n\t\t\tcost = 0\n\t\t\tfor k in range(n):\n\t\t\t\tif not i >> k & 1:\n\t\t\t\t\tcost += min(xcal[j][k], ycal[i - j][k])\n\t\t\t\tif cost > ans[count]:\n\t\t\t\t\tbreak\n\t\t\tans[count] = min(ans[count], cost)\n\t\t\tj -= 1\n\tfor i in ans:\n\t\tprint(i)\nmain()\n", "N = int(input())\nX = []\nY = []\nP = []\nfor _ in range(N):\n\t(x, y, p) = map(int, input().split())\n\tX.append(x)\n\tY.append(y)\n\tP.append(p)\nDX = [[0] * N for _ in range(1 << N)]\nDY = [[0] * N for _ in range(1 << N)]\nfor (i, x) in enumerate(X):\n\tfor k in range(1 << N):\n\t\td = abs(x)\n\t\tfor (j, xx) in enumerate(X):\n\t\t\tif k & 1 << j:\n\t\t\t\td = min(d, abs(xx - x))\n\t\tDX[k][i] = d * P[i]\nfor (i, y) in enumerate(Y):\n\tfor k in range(1 << N):\n\t\td = abs(y)\n\t\tfor (j, yy) in enumerate(Y):\n\t\t\tif k & 1 << j:\n\t\t\t\td = min(d, abs(yy - y))\n\t\tDY[k][i] = d * P[i]\nANS = [1 << 100] * (N + 1)\nPC = [0] * (1 << N)\nfor i in range(1, 1 << N):\n\tPC[i] = PC[i ^ 1] + 1 if i % 2 else PC[i // 2]\nRA = []\nfor i in range(1 << N):\n\tt = []\n\tfor j in range(N):\n\t\tif i & 1 << j:\n\t\t\tt.append(j)\n\tRA.append(t)\nmm = (1 << N) - 1\nfor i in range(1 << N):\n\tm = i ^ mm\n\tj = m\n\twhile 1:\n\t\tans = 0\n\t\tfor k in RA[i ^ j ^ mm]:\n\t\t\tans += min(DX[i][k], DY[j][k])\n\t\tpc = PC[i] + PC[j]\n\t\tANS[pc] = min(ANS[pc], ans)\n\t\tif not j:\n\t\t\tbreak\n\t\tj = m & j - 1\nprint(*ANS, sep='\\n')\n", "import sys\n\ndef input():\n\treturn sys.stdin.readline().rstrip()\n\ndef main():\n\tn = int(input())\n\tli = []\n\tfor _ in range(n):\n\t\t(xi, yi, pi) = map(int, input().split())\n\t\tli.append([xi, yi, pi])\n\tli.sort(key=lambda x: x[2], reverse=True)\n\txx = [[abs(li[j][0]) for j in range(n)] for i in range(2 ** n)]\n\tyy = [[abs(li[j][1]) for j in range(n)] for i in range(2 ** n)]\n\tfor i in range(2 ** n):\n\t\tX = [0]\n\t\trest = []\n\t\tfor j in range(n):\n\t\t\tif i >> j & 1 == 1:\n\t\t\t\tX.append(li[j][0])\n\t\t\t\txx[i][j] = 0\n\t\t\telse:\n\t\t\t\trest.append(j)\n\t\tfor j in rest:\n\t\t\tres = 10 ** 15\n\t\t\tfor k in X:\n\t\t\t\tres = min(res, abs(li[j][0] - k))\n\t\t\txx[i][j] = res\n\tfor i in range(2 ** n):\n\t\tY = [0]\n\t\trest = []\n\t\tfor j in range(n):\n\t\t\tif i >> j & 1 == 1:\n\t\t\t\tY.append(li[j][1])\n\t\t\t\tyy[i][j] = 0\n\t\t\telse:\n\t\t\t\trest.append(j)\n\t\tfor j in rest:\n\t\t\tres = 10 ** 15\n\t\t\tfor k in Y:\n\t\t\t\tres = min(res, abs(li[j][1] - k))\n\t\t\tyy[i][j] = res\n\tindex_list = [2 ** q for q in range(n)]\n\tklist = [10 ** 15] * (n + 1)\n\tklist[n] = 0\n\txx = tuple(xx)\n\tyy = tuple(yy)\n\tfor xyr2 in range(3 ** (n - 1)):\n\t\txyr = xyr2\n\t\t(k, xopen, yopen) = (0, 0, 0)\n\t\tfor index in range(n - 1):\n\t\t\t(xyr, num) = divmod(xyr, 3)\n\t\t\tk += (num + 1) // 2\n\t\t\txopen += num % 2 * index_list[index]\n\t\t\tyopen += num // 2 * index_list[index]\n\t\tfor app in range(3):\n\t\t\t(k2, xopen2, yopen2) = (k, xopen, yopen)\n\t\t\tk2 += (app + 1) // 2\n\t\t\txopen2 += app % 2 * index_list[n - 1]\n\t\t\tyopen2 += app // 2 * index_list[n - 1]\n\t\t\tcost = 0\n\t\t\tfor w in range(n):\n\t\t\t\tcost += min(xx[xopen2][w], yy[yopen2][w]) * li[w][2]\n\t\t\tklist[k2] = min(klist[k2], cost)\n\tfor g in range(n + 1):\n\t\tprint(klist[g])\nmain()\n", "n = int(input())\nxyp = [list(map(int, input().split())) for i in range(n)]\ncost = [10 ** 20] * (1 << n)\ncost[0] = 0\nfor bitt in range(1, 1 << n):\n\txx = []\n\tyy = []\n\tpp = []\n\tm = 0\n\tfor i in range(n):\n\t\t(x, y, p) = xyp[i]\n\t\tif 1 << i & bitt:\n\t\t\txx.append(x)\n\t\t\tyy.append(y)\n\t\t\tpp.append(p)\n\t\t\tm += 1\n\tfor i in range(m):\n\t\tsx = xx[i]\n\t\tanss = 0\n\t\tfor (x, y, p) in zip(xx, yy, pp):\n\t\t\tanss += min(abs(y), abs(x), abs(sx - x)) * p\n\t\tcost[bitt] = min(cost[bitt], anss)\n\tfor j in range(m):\n\t\tsy = yy[j]\n\t\tanss = 0\n\t\tfor (x, y, p) in zip(xx, yy, pp):\n\t\t\tanss += min(abs(y), abs(x), abs(sy - y)) * p\n\t\tcost[bitt] = min(cost[bitt], anss)\ndp = [sum((min(abs(xyp[i][0]), abs(xyp[i][1])) * xyp[i][2] for i in range(n) if 1 << i & j)) for j in range(1 << n)]\nprint(dp[-1])\nfor j in range(n):\n\tfor i in range((1 << n) - 1, 0, -1):\n\t\tx = i\n\t\twhile x >= 0:\n\t\t\tx &= i\n\t\t\tdp[i] = min(dp[i], dp[i - x] + cost[x])\n\t\t\tx -= 1\n\tprint(dp[-1])\n", "import sys\ninput = sys.stdin.readline\nINF = 10 ** 13\n\ndef main():\n\tN = int(input())\n\tT = [[int(i) for i in input().split()] for j in range(N)]\n\tX_dist = [[0] * N for _ in range(1 << N)]\n\tY_dist = [[0] * N for _ in range(1 << N)]\n\tfor bit in range(1 << N):\n\t\tcur_x = [0]\n\t\tcur_y = [0]\n\t\tfor i in range(N):\n\t\t\tif bit & 1 << i:\n\t\t\t\tcur_x.append(T[i][0])\n\t\t\t\tcur_y.append(T[i][1])\n\t\tfor i in range(N):\n\t\t\tX_dist[bit][i] = T[i][2] * min((abs(cx - T[i][0]) for cx in cur_x))\n\t\t\tY_dist[bit][i] = T[i][2] * min((abs(cy - T[i][1]) for cy in cur_y))\n\tanswer = [INF] * (N + 1)\n\tfor i in range(1 << N):\n\t\tcnt = 0\n\t\tfor j in range(N):\n\t\t\tif i >> j & 1:\n\t\t\t\tcnt += 1\n\t\tj = i\n\t\twhile j >= 0:\n\t\t\tj &= i\n\t\t\tcost = 0\n\t\t\tfor k in range(N):\n\t\t\t\tif not i >> k & 1:\n\t\t\t\t\tcost += min(X_dist[j][k], Y_dist[i - j][k])\n\t\t\tanswer[cnt] = min(answer[cnt], cost)\n\t\t\tj -= 1\n\tfor ans in answer:\n\t\tprint(ans)\nmain()\n", "import sys\ninput = sys.stdin.readline\nN = int(input())\nXYP = [list(map(int, input().split())) for _ in range(N)]\nINF = 10 ** 18\n\ndef scores(Xs):\n\tL = len(Xs)\n\tdp = [[INF] * (L + 1) for _ in range(L + 1)]\n\tinit = 0\n\tfor (x, p) in Xs:\n\t\tinit += abs(x) * p\n\tif L == 0:\n\t\treturn [0]\n\tfor (ix, (x, p)) in enumerate(Xs):\n\t\tdp[ix][0] = init\n\t\tscore = 0\n\t\tfor (jx, (y, q)) in enumerate(Xs):\n\t\t\tscore += min(abs(y) * q, abs(x - y) * q)\n\t\tdp[ix][1] = score\n\tfor k in range(1, L):\n\t\tfor (ix, (x, p)) in enumerate(Xs):\n\t\t\tfor iy in range(ix + 1, L):\n\t\t\t\t(y, q) = Xs[iy]\n\t\t\t\ttmp = dp[ix][k]\n\t\t\t\tfor iz in range(ix + 1, L):\n\t\t\t\t\t(z, r) = Xs[iz]\n\t\t\t\t\tnew = abs(z - y)\n\t\t\t\t\tpre = min(abs(z), abs(z - x))\n\t\t\t\t\tif new < pre:\n\t\t\t\t\t\ttmp += (new - pre) * r\n\t\t\t\tdp[iy][k + 1] = min(dp[iy][k + 1], tmp)\n\tret = [INF] * (L + 1)\n\tfor k in range(L + 1):\n\t\tfor j in range(L + 1):\n\t\t\tret[k] = min(dp[j][k], ret[k])\n\treturn ret\nans = [INF] * (N + 1)\nfor bit in range(1 << N):\n\tXs = []\n\tYs = []\n\tfor (i, (x, y, p)) in enumerate(XYP):\n\t\tif 1 << i & bit:\n\t\t\tXs.append((x, p))\n\t\telse:\n\t\t\tYs.append((y, p))\n\tXs.sort()\n\tYs.sort()\n\tdpx = scores(Xs)\n\tdpy = scores(Ys)\n\tfor (i, x) in enumerate(dpx):\n\t\tfor (j, y) in enumerate(dpy):\n\t\t\tans[i + j] = min(ans[i + j], x + y)\nprint(*ans, sep='\\n')\n", "import sys\nN = int(input())\nXYP = [list(map(int, input().split())) for _ in range(N)]\nbits = 1 << N\nxmemo = [sys.maxsize] * (N * bits)\nymemo = [sys.maxsize] * (N * bits)\nfor b in range(bits):\n\tfor i in range(N):\n\t\txmemo[b * N + i] = min(XYP[i][2] * abs(XYP[i][0]), xmemo[b * N + i])\n\t\tymemo[b * N + i] = min(XYP[i][2] * abs(XYP[i][1]), ymemo[b * N + i])\n\t\tif not b & 1 << i:\n\t\t\tcontinue\n\t\tfor j in range(N):\n\t\t\txmemo[b * N + j] = min(XYP[j][2] * abs(XYP[i][0] - XYP[j][0]), xmemo[b * N + j])\n\t\t\tymemo[b * N + j] = min(XYP[j][2] * abs(XYP[i][1] - XYP[j][1]), ymemo[b * N + j])\nans = [sys.maxsize] * (N + 1)\nfor b in range(bits):\n\tb_ = b\n\tcnt = bin(b_).count('1')\n\twhile b_ >= 0:\n\t\tb_ &= b\n\t\tyi = b - b_\n\t\ttmp = 0\n\t\tfor i in range(N):\n\t\t\ttmp += min(xmemo[b_ * N + i], ymemo[yi * N + i])\n\t\tans[cnt] = min(ans[cnt], tmp)\n\t\tb_ -= 1\nfor i in range(N + 1):\n\tprint(ans[i])\n", "n = int(input())\ninfo = [list(map(int, input().split())) for i in range(n)]\nINF = 10 ** 13\ncosts = [INF] * n\nfor (i, (x, y, c)) in enumerate(info):\n\tcosts[i] = c * min(abs(x), abs(y))\nOFFSET = n\nx_dir = [INF] * ((1 << n) * OFFSET)\ny_dir = [INF] * ((1 << n) * OFFSET)\nfor bit_state in range(1 << n):\n\tfor (i, (xi, yi, c)) in enumerate(info):\n\t\tx_dir[bit_state * OFFSET + i] = min(costs[i], x_dir[bit_state * OFFSET + i])\n\t\ty_dir[bit_state * OFFSET + i] = min(costs[i], y_dir[bit_state * OFFSET + i])\n\t\tif not bit_state >> i & 1:\n\t\t\tcontinue\n\t\tfor (j, (xj, yj, c)) in enumerate(info):\n\t\t\tx_dir[bit_state * OFFSET + j] = min(x_dir[bit_state * OFFSET + j], c * abs(yi - yj))\n\t\t\ty_dir[bit_state * OFFSET + j] = min(y_dir[bit_state * OFFSET + j], c * abs(xi - xj))\nans = [INF] * (n + 1)\nfor bit_state in range((1 << n) - 1):\n\tx_bit = bit_state\n\tcnt = bin(bit_state).count('1')\n\twhile x_bit >= 0:\n\t\tx_bit &= bit_state\n\t\ty_bit = bit_state - x_bit\n\t\ttmp = 0\n\t\tfor i in range(n):\n\t\t\ttmp += min(x_dir[x_bit * OFFSET + i], y_dir[y_bit * OFFSET + i])\n\t\tans[cnt] = min(ans[cnt], tmp)\n\t\tx_bit -= 1\nans[-1] = 0\nfor res in ans:\n\tprint(res)\n", "def main():\n\tn = int(input())\n\txyp = [list(map(int, input().split())) for _ in [0] * n]\n\td = []\n\n\tdef calc(seq):\n\t\tm = len(seq)\n\t\tdp = [[10 ** 15] * (m + 1) for _ in [0] * (m + 1)]\n\t\tdp[0][0] = 0\n\t\tfor i in range(m):\n\t\t\ts = seq[i][0]\n\t\t\tfor j in range(i + 1):\n\t\t\t\ttemp = dp[j][0]\n\t\t\t\tfor (a, b) in seq[:i + 1]:\n\t\t\t\t\ttemp += min(abs(a), s - a) * b\n\t\t\t\tdp[j + 1][i + 1] = min(dp[j + 1][i + 1], temp)\n\t\t\t\ttemp2 = 10 ** 15\n\t\t\t\tfor k in range(1, i + 1):\n\t\t\t\t\ttemp = dp[j][k]\n\t\t\t\t\tt = seq[k - 1][0]\n\t\t\t\t\tfor (a, b) in seq[k:i + 1]:\n\t\t\t\t\t\ttemp += min(abs(a), a - t, s - a) * b\n\t\t\t\t\ttemp2 = min(temp2, temp)\n\t\t\t\tdp[j + 1][i + 1] = min(dp[j + 1][i + 1], temp2)\n\t\tfor i in range(m + 1):\n\t\t\tfor (a, b) in seq[:m]:\n\t\t\t\tdp[i][0] += abs(a) * b\n\t\t\tfor k in range(1, m + 1):\n\t\t\t\tt = seq[k - 1][0]\n\t\t\t\ttemp = 0\n\t\t\t\tfor (a, b) in seq[k:m]:\n\t\t\t\t\ttemp += min(abs(a), a - t) * b\n\t\t\t\tdp[i][k] += temp\n\t\tfor i in range(m + 1):\n\t\t\tdp[i] = min(dp[i])\n\t\tdp += [0] * (n - m)\n\t\treturn dp\n\txyp.sort()\n\tfor i in range(2 ** n):\n\t\t(x_list, y_list) = ([], [])\n\t\tfor j in range(n):\n\t\t\t(x, y, p) = xyp[j]\n\t\t\tif i & 1:\n\t\t\t\tx_list.append([x, p])\n\t\t\telse:\n\t\t\t\ty_list.append([y, p])\n\t\t\ti >>= 1\n\t\ty_list.sort()\n\t\td.append([calc(x_list), calc(y_list)])\n\tans = [10 ** 15] * (n + 1)\n\tfor (x, y) in d:\n\t\tfor i in range(n + 1):\n\t\t\tfor j in range(n - i + 1):\n\t\t\t\tans[i + j] = min(ans[i + j], x[i] + y[j])\n\tfor i in ans:\n\t\tprint(i)\nmain()\n", "def solve(N, X, Y, P):\n\tinf = 10 ** 18\n\tcnb_N = 2 ** N\n\tto_x = [[0] * N for _ in range(cnb_N)]\n\tto_y = [[0] * N for _ in range(cnb_N)]\n\tfor cn in range(cnb_N):\n\t\tfor n in range(N):\n\t\t\tto_x[cn][n] = abs(X[n]) * P[n]\n\t\t\tto_y[cn][n] = abs(Y[n]) * P[n]\n\t\t\tfor n2 in range(N):\n\t\t\t\tif cn >> n2 & 1:\n\t\t\t\t\tto_x[cn][n] = min(to_x[cn][n], abs(X[n] - X[n2]) * P[n])\n\t\t\t\t\tto_y[cn][n] = min(to_y[cn][n], abs(Y[n] - Y[n2]) * P[n])\n\tans = [inf] * (N + 1)\n\tfor cn in range(cnb_N):\n\t\tcount = 0\n\t\tfor i in range(N):\n\t\t\tcount += 1 if cn >> i & 1 else 0\n\t\tcn2 = cn\n\t\twhile cn2 >= 0:\n\t\t\tcn2 = cn2 & cn\n\t\t\tsubsum = 0\n\t\t\tfor n in range(N):\n\t\t\t\tif not cn >> n & 1:\n\t\t\t\t\tsubsum += min(to_x[cn - cn2][n], to_y[cn2][n])\n\t\t\tans[count] = min(ans[count], subsum)\n\t\t\tcn2 -= 1\n\tfor n in range(N + 1):\n\t\tprint(ans[n])\nN = int(input())\n(X, Y, P) = ([], [], [])\nfor _ in range(N):\n\ttmp = [int(i) for i in input().split()]\n\tX.append(tmp[0])\n\tY.append(tmp[1])\n\tP.append(tmp[2])\nsolve(N, X, Y, P)\n", "inf = 10 ** 15\n\ndef main():\n\timport sys\n\tinput = sys.stdin.readline\n\tN = int(input())\n\tX = []\n\tY = []\n\tP = []\n\tfor _ in range(N):\n\t\t(x, y, p) = map(int, input().split())\n\t\tX.append(x)\n\t\tY.append(y)\n\t\tP.append(p)\n\tdx = [[inf] * N for _ in range(1 << N)]\n\tdy = [[inf] * N for _ in range(1 << N)]\n\tfor i in range(1 << N):\n\t\tXline = [0]\n\t\tYline = [0]\n\t\tfor j in range(N):\n\t\t\tif i >> j & 1:\n\t\t\t\tXline.append(X[j])\n\t\t\t\tYline.append(Y[j])\n\t\tfor j in range(N):\n\t\t\tfor (x, y) in zip(Xline, Yline):\n\t\t\t\tdx[i][j] = min(dx[i][j], abs(x - X[j]))\n\t\t\t\tdy[i][j] = min(dy[i][j], abs(y - Y[j]))\n\tans = [inf] * (N + 1)\n\tbeki = [1 << j for j in range(N)]\n\tfor i in range(3 ** (N - 1)):\n\t\tM = i\n\t\tk = 0\n\t\tix = iy = 0\n\t\tJ = []\n\t\tfor j in range(N - 1):\n\t\t\t(M, m) = divmod(M, 3)\n\t\t\tif m == 0:\n\t\t\t\tJ.append(j)\n\t\t\telif m == 1:\n\t\t\t\tk += 1\n\t\t\t\tix += beki[j]\n\t\t\telse:\n\t\t\t\tk += 1\n\t\t\t\tiy += beki[j]\n\t\tfor x in range(3):\n\t\t\tkk = k\n\t\t\tix_ = ix\n\t\t\tiy_ = iy\n\t\t\tif x == 0:\n\t\t\t\tJ.append(N - 1)\n\t\t\telif x == 1:\n\t\t\t\tkk += 1\n\t\t\t\tix_ += beki[N - 1]\n\t\t\telse:\n\t\t\t\tkk += 1\n\t\t\t\tiy_ += beki[N - 1]\n\t\t\tcost = 0\n\t\t\tfor j in J:\n\t\t\t\tp = P[j]\n\t\t\t\tcost += min(dx[ix_][j], dy[iy_][j]) * p\n\t\t\tans[kk] = min(ans[kk], cost)\n\tfor c in ans:\n\t\tprint(c)\nmain()\n", "N = int(input())\nX = []\nY = []\nP = []\nINF = float('inf')\nfor i in range(N):\n\t(x, y, p) = list(map(int, input().split()))\n\tX.append(x)\n\tY.append(y)\n\tP.append(p)\nans = [INF for _ in range(N + 1)]\n\ndef calc(A):\n\tn = len(A)\n\tA.sort()\n\tdp = [[INF] * (n + 1) for _ in range(n + 1)]\n\tdp[0][0] = 0\n\tfor l in range(n):\n\t\tfor r in range(l + 1, n + 1):\n\t\t\tnow = INF\n\t\t\tfor k in range(l, r):\n\t\t\t\ts = 0\n\t\t\t\tfor i in range(l, r):\n\t\t\t\t\ts += abs(A[i][0] - A[k][0]) * A[i][1]\n\t\t\t\tnow = min(now, s)\n\t\t\tfor j in range(n):\n\t\t\t\tdp[r][j + 1] = min(dp[r][j + 1], dp[l][j] + now)\n\t\t\tnow = 0\n\t\t\tfor i in range(l, r):\n\t\t\t\tnow += abs(A[i][0]) * A[i][1]\n\t\t\tfor j in range(n + 1):\n\t\t\t\tdp[r][j] = min(dp[r][j], dp[l][j] + now)\n\tres = [INF for _ in range(n + 1)]\n\tfor j in range(n + 1):\n\t\tres[j] = dp[n][j]\n\treturn res\nfor s in range(1 << N):\n\tAX = []\n\tAY = []\n\tfor i in range(N):\n\t\tif s >> i & 1 == 1:\n\t\t\tAX.append((X[i], P[i]))\n\t\telse:\n\t\t\tAY.append((Y[i], P[i]))\n\tdx = calc(AX)\n\tdy = calc(AY)\n\tfor i in range(len(dx)):\n\t\tfor j in range(len(dy)):\n\t\t\tans[i + j] = min(ans[i + j], dx[i] + dy[j])\nfor t in ans:\n\tprint(t)\n", "import sys\nrl = sys.stdin.buffer.readline\nINF = sys.maxsize\nN = int(rl())\nPS = [tuple(map(int, rl().split())) for i in range(N)]\n\ndef bitcount(n):\n\tn = n - (n >> 1 & 6148914691236517205)\n\tn = (n & 3689348814741910323) + (n >> 2 & 3689348814741910323)\n\tn = n + (n >> 4) & 1085102592571150095\n\tn = n + (n >> 8)\n\tn = n + (n >> 16)\n\tn = n + (n >> 32)\n\treturn n & 127\n\ndef subsets(s):\n\tt = s\n\twhile t >= 0:\n\t\tt &= s\n\t\tyield t\n\t\tt -= 1\nxcost = [[INF] * N for _ in range(1 << N)]\nycost = [[INF] * N for _ in range(1 << N)]\nfor i in range(1 << N):\n\tfor j in range(N):\n\t\txcost[i][j] = abs(PS[j][0])\n\t\tycost[i][j] = abs(PS[j][1])\n\t\tfor k in range(N):\n\t\t\tif i >> k & 1 == 1:\n\t\t\t\txcost[i][j] = min(xcost[i][j], abs(PS[j][0] - PS[k][0]))\n\t\t\t\tycost[i][j] = min(ycost[i][j], abs(PS[j][1] - PS[k][1]))\nfor i in range(1 << N):\n\tfor j in range(N):\n\t\txcost[i][j] = xcost[i][j] * PS[j][2]\n\t\tycost[i][j] = ycost[i][j] * PS[j][2]\nans = [INF] * (N + 1)\nfor i in range(1 << N):\n\tsize = bitcount(i)\n\tfor j in subsets(i):\n\t\tcost = 0\n\t\tfor k in range(N):\n\t\t\tif i >> k & 1 == 0:\n\t\t\t\tcost += min(xcost[j][k], ycost[i - j][k])\n\t\tans[size] = min(ans[size], cost)\nfor a in ans:\n\tprint(a)\n", "INF = float('inf')\n(N, *XYP) = map(int, open(0).read().split())\nXYP = list(zip(*[iter(XYP)] * 3))\n\ndef solve(XP):\n\tM = len(XP)\n\tXP.sort()\n\tdp = [[INF] * (M + 1) for _ in range(M + 1)]\n\tdp[0][0] = 0\n\tfor (i, (x, p)) in enumerate(XP):\n\t\tdp[i + 1][0] = dp[i][0] + abs(x) * p\n\tfor (l, dpl) in enumerate(dp[:M]):\n\t\tfor r in range(l + 1, M + 1):\n\t\t\tval = INF\n\t\t\tfor (lx, _) in XP[l:r]:\n\t\t\t\tcur = 0\n\t\t\t\tfor (x, p) in XP[l:r]:\n\t\t\t\t\tcur += p * min(abs(x - lx), abs(x))\n\t\t\t\tval = min(val, cur)\n\t\t\tfor i in range(1, M + 1):\n\t\t\t\tdp[r][i] = min(dp[r][i], val + dpl[i - 1])\n\tres = [INF] * (N + 1)\n\tres[:M + 1] = dp[M]\n\treturn res\nA = [INF] * (N + 1)\nfor state in range(1 << N):\n\t(XP, YP) = ([], [])\n\tfor (i, (x, y, p)) in enumerate(XYP):\n\t\tif state >> i & 1:\n\t\t\tXP.append((x, p))\n\t\telse:\n\t\t\tYP.append((y, p))\n\t(X, Y) = (solve(XP), solve(YP))\n\tfor i in range(N + 1):\n\t\tfor j in range(N + 1 - i):\n\t\t\tA[i + j] = min(A[i + j], X[i] + Y[j])\nfor a in A:\n\tprint(a)\n", "def main():\n\tn = int(input())\n\txyp = [list(map(int, input().split())) for i in range(n)]\n\n\tdef caldp(a):\n\t\tn = len(a)\n\t\ta.sort()\n\t\tdp = [[float('INF')] * (n + 1) for i in range(n + 1)]\n\t\tdp[0][0] = 0\n\t\tfor l in range(n):\n\t\t\tfor r in range(l + 1, n + 1):\n\t\t\t\tnow = float('INF')\n\t\t\t\tfor k in range(l, r):\n\t\t\t\t\tcount = 0\n\t\t\t\t\tfor i in range(l, r):\n\t\t\t\t\t\tcount += abs(a[i][0] - a[k][0]) * a[i][1]\n\t\t\t\t\tnow = min(now, count)\n\t\t\t\tfor j in range(n):\n\t\t\t\t\tdp[r][j + 1] = min(dp[r][j + 1], dp[l][j] + now)\n\t\t\t\tnow = 0\n\t\t\t\tfor i in range(l, r):\n\t\t\t\t\tnow += abs(a[i][0]) * a[i][1]\n\t\t\t\tfor j in range(n + 1):\n\t\t\t\t\tdp[r][j] = min(dp[r][j], dp[l][j] + now)\n\t\tres = [float('INF')] * (n + 1)\n\t\tfor i in range(n + 1):\n\t\t\tres[i] = dp[-1][i]\n\t\treturn res\n\tans = [float('INF')] * (n + 1)\n\tfor s in range(1 << n):\n\t\tlx = []\n\t\tly = []\n\t\tfor i in range(n):\n\t\t\tif s >> i & 1:\n\t\t\t\tlx.append((xyp[i][0], xyp[i][2]))\n\t\t\telse:\n\t\t\t\tly.append((xyp[i][1], xyp[i][2]))\n\t\tlx = caldp(lx)\n\t\tly = caldp(ly)\n\t\tfor i in range(len(lx)):\n\t\t\tfor j in range(len(ly)):\n\t\t\t\tans[i + j] = min(ans[i + j], lx[i] + ly[j])\n\tfor i in ans:\n\t\tprint(i)\nmain()\n", "import bisect\nimport copy\nimport heapq\nimport sys\nimport itertools\nimport math\nfrom functools import lru_cache\nfrom collections import deque\ninput = sys.stdin.readline\nsys.setrecursionlimit(1000000)\nmod = 10 ** 9 + 7\n\ndef read_values():\n\treturn map(int, input().split())\n\ndef read_index():\n\treturn map(lambda x: int(x) - 1, input().split())\n\ndef read_list():\n\treturn list(read_values())\n\ndef read_lists(N):\n\treturn [read_list() for n in range(N)]\n\ndef main():\n\tN = int(input())\n\tP = read_lists(N)\n\tC = [1 << 62] * (N + 1)\n\tCX = [1 << 62] * (N * 2 ** N)\n\tCY = [1 << 62] * (N * 2 ** N)\n\tLX = [0] * 2 ** N\n\tLY = [0] * 2 ** N\n\tfor K in range(2 ** N):\n\t\tX = {0}\n\t\tY = {0}\n\t\tfor i in range(N):\n\t\t\tif K >> i & 1:\n\t\t\t\tX.add(P[i][0])\n\t\t\t\tY.add(P[i][1])\n\t\tfor (j, (xp, yp, cp)) in enumerate(P):\n\t\t\tfor x in X:\n\t\t\t\tCX[K * N + j] = min(abs(xp - x) * cp, CX[K * N + j])\n\t\t\tfor y in Y:\n\t\t\t\tCY[K * N + j] = min(abs(yp - y) * cp, CY[K * N + j])\n\t\tLX[K] = len(X)\n\t\tLY[K] = len(Y)\n\tfor T in range(2 ** N):\n\t\tp = format(T, '160b').count('1')\n\t\tif C[p] == 0:\n\t\t\tcontinue\n\t\tr = 1 << 62\n\t\ttx = T\n\t\twhile True:\n\t\t\tty = T - tx\n\t\t\tc = 0\n\t\t\tfor n in range(N):\n\t\t\t\tc += min(CX[tx * N + n], CY[ty * N + n])\n\t\t\tr = min(r, c)\n\t\t\tif tx == 0:\n\t\t\t\tbreak\n\t\t\ttx = tx - 1 & T\n\t\tC[p] = min(C[p], r)\n\tprint('\\n'.join(map(str, C)))\nmain()\n", "N = int(input())\ncity = []\nfor i in range(N):\n\t(x, y, p) = map(int, input().split())\n\tcity.append((x, y, p))\nxx = [[abs(city[j][0]) for j in range(N)] for i in range(2 ** N)]\nyy = [[abs(city[j][1]) for j in range(N)] for i in range(2 ** N)]\nfor i in range(2 ** N):\n\tX = [0]\n\trest = []\n\tfor j in range(N):\n\t\tif i >> j & 1 == 1:\n\t\t\tX.append(city[j][0])\n\t\t\txx[i][j] = 0\n\t\telse:\n\t\t\trest.append(j)\n\tfor j in rest:\n\t\tres = 10 ** 15\n\t\tfor k in X:\n\t\t\tres = min(res, abs(city[j][0] - k))\n\t\txx[i][j] = res\nfor i in range(2 ** N):\n\tY = [0]\n\trest = []\n\tfor j in range(N):\n\t\tif i >> j & 1 == 1:\n\t\t\tY.append(city[j][1])\n\t\t\tyy[i][j] = 0\n\t\telse:\n\t\t\trest.append(j)\n\tfor j in rest:\n\t\tres = 10 ** 15\n\t\tfor k in Y:\n\t\t\tres = min(res, abs(city[j][1] - k))\n\t\tyy[i][j] = res\nans = [10 ** 15 for i in range(N + 1)]\nfor i in range(2 ** N):\n\tcond = i\n\trest = [j for j in range(N) if i >> j & 1 == 0]\n\tcount = N - len(rest)\n\twhile True:\n\t\tX = cond\n\t\tY = i - cond\n\t\ttemp = 0\n\t\tfor j in rest:\n\t\t\ttemp += min(xx[X][j], yy[Y][j]) * city[j][2]\n\t\tans[count] = min(ans[count], temp)\n\t\tif cond == 0:\n\t\t\tbreak\n\t\telse:\n\t\t\tcond = cond - 1 & i\nfor i in range(N + 1):\n\tprint(ans[i])\n", "def main():\n\tfrom sys import setrecursionlimit, stdin, stderr\n\tfrom os import environ\n\tfrom collections import defaultdict, deque, Counter\n\tfrom math import ceil, floor\n\tfrom itertools import accumulate, combinations, combinations_with_replacement, product\n\tsetrecursionlimit(10 ** 6)\n\tdbg = (lambda *something: stderr.write('\\x1b[92m{}\\x1b[0m'.format(str(something) + '\\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0\n\tinput = lambda : stdin.readline().rstrip()\n\tLMIIS = lambda : list(map(int, input().split()))\n\tII = lambda : int(input())\n\tP = 10 ** 9 + 7\n\tINF = 10 ** 12\n\tN = II()\n\tpositions = deque()\n\tfor i in range(N):\n\t\tpositions.append(LMIIS())\n\tv = []\n\th = []\n\tfor i in range(2 ** N):\n\t\tv.append([INF] * N)\n\t\th.append([INF] * N)\n\tfor i in range(2 ** N):\n\t\tv_lines = deque([0])\n\t\th_lines = deque([0])\n\t\tfor j in range(N):\n\t\t\tif 2 ** j & i:\n\t\t\t\tv_lines.append(positions[j][0])\n\t\t\t\th_lines.append(positions[j][1])\n\t\tfor (j, (x, y, p)) in enumerate(positions):\n\t\t\tmin_x = INF\n\t\t\tmin_y = INF\n\t\t\tfor x_c in v_lines:\n\t\t\t\tmin_x = min(min_x, abs(x_c - x) * p)\n\t\t\tfor y_c in h_lines:\n\t\t\t\tmin_y = min(min_y, abs(y_c - y) * p)\n\t\t\tv[i][j] = min_x\n\t\t\th[i][j] = min_y\n\tans = [INF] * (N + 1)\n\tn_bit_mask = (1 << N) - 1\n\tfor pattern in range(2 ** N):\n\t\tcities = [i for i in range(N) if 2 ** i & pattern == 0]\n\t\tkey = N - len(cities)\n\t\tpattern_v = pattern\n\t\tpattern_h = 0\n\t\twhile True:\n\t\t\tsum_diff = 0\n\t\t\tfor i in cities:\n\t\t\t\tsum_diff += min(v[pattern_v][i], h[pattern_h][i])\n\t\t\tans[key] = min(ans[key], sum_diff)\n\t\t\tif pattern_v == 0:\n\t\t\t\tbreak\n\t\t\tpattern_v = pattern_v - 1 & pattern\n\t\t\tpattern_h = pattern - pattern_v\n\tprint('\\n'.join(map(str, ans)))\nmain()\n", "import sys\ninput = sys.stdin.readline\nN = int(input())\nP = [list(map(int, input().split())) for i in range(N)]\nANS = [1 << 60] * (N + 1)\nANS[-1] = 0\nDP1 = [20000] * N\nS = 0\nfor i in range(N):\n\t(x, y, p) = P[i]\n\tDP1[i] = min(abs(x), abs(y))\n\tS += DP1[i] * p\nANS[0] = S\n\ndef dfs(DP, now, used):\n\tfor next_town in range(now, N):\n\t\t(x, y, p) = P[next_town]\n\t\tDP2 = list(DP)\n\t\tS = 0\n\t\tfor i in range(N):\n\t\t\tDP2[i] = min(DP2[i], abs(P[i][0] - x))\n\t\t\tS += DP2[i] * P[i][2]\n\t\tANS[used + 1] = min(ANS[used + 1], S)\n\t\tdfs(DP2, next_town + 1, used + 1)\n\t\tDP2 = list(DP)\n\t\tS = 0\n\t\tfor i in range(N):\n\t\t\tDP2[i] = min(DP2[i], abs(P[i][1] - y))\n\t\t\tS += DP2[i] * P[i][2]\n\t\tANS[used + 1] = min(ANS[used + 1], S)\n\t\tdfs(DP2, next_town + 1, used + 1)\ndfs(DP1, 0, 0)\nfor i in range(1, N):\n\tANS[i] = min(ANS[i], ANS[i - 1])\nprint(*ANS)\n", "import itertools\nN = int(input())\ndata = []\nmin_value_0 = 0\nfor _ in range(N):\n\t(X, Y, P) = town = tuple(map(int, input().split()))\n\tdata.append(town)\n\tmin_value_0 += min(abs(X), abs(Y)) * P\nprint(min_value_0)\nB = 2 ** N\ntable_h = []\ntable_v = []\nfor b in range(B):\n\ttowns = []\n\ti = 0\n\tx = b\n\twhile x > 0:\n\t\tif x % 2 == 1:\n\t\t\ttowns.append(i)\n\t\tx //= 2\n\t\ti += 1\n\tdists_h = []\n\tdists_v = []\n\tfor i in range(N):\n\t\t(X0, Y0, P0) = data[i]\n\t\td_h = abs(X0)\n\t\td_v = abs(Y0)\n\t\tfor j in towns:\n\t\t\t(X1, Y1, P1) = data[j]\n\t\t\td_h = min(d_h, abs(X1 - X0))\n\t\t\td_v = min(d_v, abs(Y1 - Y0))\n\t\tdists_h.append(d_h * P0)\n\t\tdists_v.append(d_v * P0)\n\ttable_h.append(dists_h)\n\ttable_v.append(dists_v)\ntable = [min_value_0] * (N + 1)\nimport sys\nstack = [0] * N\ni = 0\nc = 0\nb0 = 0\nb1 = 0\nb = 1\nwhile True:\n\tif i == N:\n\t\tvalue = 0\n\t\tt1 = table_h[b0]\n\t\tt2 = table_v[b1]\n\t\tfor j in range(N):\n\t\t\tvalue += min(t1[j], t2[j])\n\t\tif table[c] > value:\n\t\t\ttable[c] = value\n\t\ti -= 1\n\t\tb //= 2\n\telse:\n\t\ts = stack[i]\n\t\tif s == 3:\n\t\t\tif i == 0:\n\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tstack[i] = 0\n\t\t\t\ti -= 1\n\t\t\t\tb //= 2\n\t\telse:\n\t\t\tif s == 0:\n\t\t\t\tb0 += b\n\t\t\t\tc += 1\n\t\t\telif s == 1:\n\t\t\t\tb0 -= b\n\t\t\t\tb1 += b\n\t\t\telse:\n\t\t\t\tb1 -= b\n\t\t\t\tc -= 1\n\t\t\tstack[i] = s + 1\n\t\t\ti += 1\n\t\t\tb *= 2\nfor i in range(1, N):\n\tprint(table[i])\nprint(0)\n", "import os, io\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n\ndef main():\n\tN = int(input())\n\tResident = []\n\tfor i in range(N):\n\t\t(x, y, p) = map(int, input().split())\n\t\tResident.append((x, y, p))\n\tminCost = [float('inf')] * (N + 1)\n\tpreCalRange = 1 << N\n\thorizontalLineDistance = []\n\tverticalLineDistance = []\n\tfor i in range(preCalRange):\n\t\trailRoad = bin(i)[2:]\n\t\trailRoad = '0' * (N - len(railRoad)) + railRoad\n\t\thorizontalLineDistance.append([])\n\t\tverticalLineDistance.append([])\n\t\tfor j in range(N):\n\t\t\thorizontalLineDistance[i].append(min(abs(Resident[j][0]), abs(Resident[j][1])))\n\t\t\tverticalLineDistance[i].append(min(abs(Resident[j][0]), abs(Resident[j][1])))\n\t\t\tfor k in range(N):\n\t\t\t\tif railRoad[k] == '1' and abs(Resident[j][0] - Resident[k][0]) < horizontalLineDistance[i][j]:\n\t\t\t\t\thorizontalLineDistance[i][j] = abs(Resident[j][0] - Resident[k][0])\n\t\t\t\tif railRoad[k] == '1' and abs(Resident[j][1] - Resident[k][1]) < verticalLineDistance[i][j]:\n\t\t\t\t\tverticalLineDistance[i][j] = abs(Resident[j][1] - Resident[k][1])\n\tpower2 = [1]\n\tfor i in range(N):\n\t\tpower2.append(power2[-1] * 2)\n\tloopCount = power2[N]\n\tfor i in range(loopCount):\n\t\tnumNewRailroad = bin(i)[2:].count('1')\n\t\tj = i\n\t\twhile j >= 0:\n\t\t\tj &= i\n\t\t\tgoodList1 = horizontalLineDistance[j]\n\t\t\tgoodList2 = verticalLineDistance[i - j]\n\t\t\tcost = 0\n\t\t\tfor k in range(N):\n\t\t\t\tcost += Resident[k][2] * min(goodList1[k], goodList2[k])\n\t\t\tif minCost[numNewRailroad] > cost:\n\t\t\t\tminCost[numNewRailroad] = cost\n\t\t\tj -= 1\n\tfor elem in minCost:\n\t\tprint(elem)\nmain()\n", "import sys\nread = sys.stdin.read\nreadline = sys.stdin.readline\n(n,) = map(int, readline().split())\nxyp = tuple((tuple(map(int, readline().split())) for _ in range(n)))\nN = 1 << n\nINF = 1 << 60\nresx = []\nresy = []\nfor i in range(n):\n\t(x, y, p) = xyp[i]\n\trx = [min(abs(x), abs(y))] * N\n\try = [min(abs(x), abs(y))] * N\n\tfor j in range(n):\n\t\tfor k in range(1 << j):\n\t\t\trx[k + (1 << j)] = min(rx[k], abs(x - xyp[j][0]))\n\t\t\try[k + (1 << j)] = min(ry[k], abs(y - xyp[j][1]))\n\tfor j in range(N):\n\t\trx[j] *= p\n\t\try[j] *= p\n\tresx.append(rx)\n\tresy.append(ry)\nans = [INF] * (n + 1)\nN = 3 ** n\np = tuple((3 ** i for i in range(n + 1)))\nrv = [0] * N\nrx = [0] * N\nry = [0] * N\nfor j in range(n):\n\tfor k in range(p[j]):\n\t\trv[k + p[j]] = rv[k + 2 * p[j]] = rv[k]\n\t\trv[k] += 1\n\t\trx[k + p[j]] = rx[k] | 1 << j\n\t\try[k + p[j]] = ry[k]\n\t\trx[k + 2 * p[j]] = rx[k]\n\t\try[k + 2 * p[j]] = ry[k] | 1 << j\nfor mask in range(N):\n\tv = rv[mask]\n\tx = rx[mask]\n\ty = ry[mask]\n\tr = 0\n\tfor i in range(n):\n\t\tr += min(resx[i][x], resy[i][y])\n\tif r < ans[v]:\n\t\tans[v] = r\nfor i in ans[::-1]:\n\tprint(i)\n", "import sys\nsysread = sys.stdin.buffer.readline\nread = sys.stdin.buffer.read\nsys.setrecursionlimit(10 ** 7)\nimport bisect\nINF = 1 << 50\n\ndef generate_dist_arr(X, Y, P):\n\tN = len(X)\n\tdist_arr_x = [[] for _ in range(1 << N)]\n\tdist_arr_y = [[] for _ in range(1 << N)]\n\tfor j in range(1 << N):\n\t\tx_lines_list = [0]\n\t\ty_lines_list = [0]\n\t\tfor k in range(N):\n\t\t\tif j >> k & 1:\n\t\t\t\tx_lines_list.append(X[k])\n\t\t\t\ty_lines_list.append(Y[k])\n\t\t(dist_xx, dist_yy) = ([INF] * N, [INF] * N)\n\t\tx_lines_list = sorted(x_lines_list)\n\t\ty_lines_list = sorted(y_lines_list)\n\t\tfor (idx, x) in enumerate(X):\n\t\t\tv = bisect.bisect_left(x_lines_list, x)\n\t\t\tpre_x = x_lines_list[min(v - 1, 0)]\n\t\t\tpost_x = x_lines_list[min(v, len(x_lines_list) - 1)]\n\t\t\tdist_xx[idx] = min(abs(pre_x - x), abs(post_x - x)) * P[idx]\n\t\tdist_arr_x[j] = dist_xx\n\t\tfor (idx, y) in enumerate(Y):\n\t\t\tv = bisect.bisect_left(y_lines_list, y)\n\t\t\tpre_y = y_lines_list[max(v - 1, 0)]\n\t\t\tpost_y = y_lines_list[min(v, len(y_lines_list) - 1)]\n\t\t\tdist_yy[idx] = min(abs(pre_y - y), abs(post_y - y)) * P[idx]\n\t\tdist_arr_y[j] = dist_yy\n\treturn (dist_arr_x, dist_arr_y)\n\ndef calc(val_list):\n\tval_list = sorted(val_list)\n\tn = len(val_list)\n\tdp = [[INF] * (n + 1) for _ in range(n + 1)]\n\tdp[0][0] = 0\n\tfor l in range(n + 1):\n\t\tfor r in range(l + 1, n + 1):\n\t\t\tnext_dist = INF\n\t\t\tfor k in range(l + 1, r + 1):\n\t\t\t\tsum = 0\n\t\t\t\tfor v in range(l + 1, r + 1):\n\t\t\t\t\tsum += abs(val_list[v - 1][0] - val_list[k - 1][0]) * val_list[v - 1][1]\n\t\t\t\tnext_dist = min(next_dist, sum)\n\t\t\tfor j in range(n):\n\t\t\t\tdp[r][j + 1] = min(dp[r][j + 1], dp[l][j] + next_dist)\n\t\t\tsum = 0\n\t\t\tfor v in range(l + 1, r + 1):\n\t\t\t\tsum += abs(val_list[v - 1][0]) * val_list[v - 1][1]\n\t\t\tnext_dist = sum\n\t\t\tfor j in range(n + 1):\n\t\t\t\tdp[r][j] = min(dp[r][j], dp[l][j] + next_dist)\n\treturn dp\n\ndef run():\n\tN = int(sysread())\n\t(X, Y) = ([], [])\n\tfor i in range(1, N + 1):\n\t\t(x, y, p) = map(int, sysread().split())\n\t\tX.append((x, p))\n\t\tY.append((y, p))\n\tans = [INF] * (N + 1)\n\tfor i in range(1 << N):\n\t\tx_town_list = []\n\t\ty_town_list = []\n\t\tfor k in range(N):\n\t\t\tif i >> k & 1:\n\t\t\t\tx_town_list.append(X[k])\n\t\t\telse:\n\t\t\t\ty_town_list.append(Y[k])\n\t\tdp_x = calc(x_town_list)[-1]\n\t\tdp_y = calc(y_town_list)[-1]\n\t\tfor i in range(len(dp_x)):\n\t\t\tfor j in range(len(dp_y)):\n\t\t\t\tval = dp_x[i] + dp_y[j]\n\t\t\t\tans[i + j] = min(ans[i + j], val)\n\tfor a in ans:\n\t\tprint(a)\nrun()\n", "n = int(input())\nXYP = [tuple(map(int, input().split())) for i in range(n)]\nX = [x for (x, y, p) in XYP]\nY = [y for (x, y, p) in XYP]\nP = [p for (x, y, p) in XYP]\npow2 = [2 ** i for i in range(n + 1)]\nDX = [[0] * n for s in range(pow2[n])]\nDY = [[0] * n for s in range(pow2[n])]\nfor s in range(1 << n):\n\tfor i in range(n):\n\t\tDX[s][i] = abs(X[i]) * P[i]\n\t\tDY[s][i] = abs(Y[i]) * P[i]\n\t\tfor j in range(n):\n\t\t\tif s & 1 << j:\n\t\t\t\tDX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])\n\t\t\t\tDY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])\nBC = [bin(s).count('1') for s in range(pow2[n])]\nA = [10 ** 20] * (n + 1)\nfor sx in range(pow2[n]):\n\trx = pow2[n] - 1 ^ sx\n\tsy = rx\n\tfor _ in range(pow2[n - BC[sx]]):\n\t\tsy = sy - 1 & rx\n\t\td = 0\n\t\tfor i in range(n):\n\t\t\td += min(DX[sx][i], DY[sy][i])\n\t\tc = BC[sx] + BC[sy]\n\t\tA[c] = min(A[c], d)\nprint(*A, sep='\\n')\n", "import sys\nint1 = lambda x: int(x) - 1\nread = sys.stdin.buffer.read\nreadline = sys.stdin.buffer.readline\nreadlines = sys.stdin.buffer.readlines\nsys.setrecursionlimit(500000)\nN = int(readline())\nXYP = [list(map(int, readline().split())) for _ in range(N)]\ncosts = [sys.maxsize] * N\nfor (i, (x, y, c)) in enumerate(XYP):\n\tcosts[i] = c * min(abs(x), abs(y))\nx_cost = [sys.maxsize] * ((1 << N) * N)\ny_cost = [sys.maxsize] * ((1 << N) * N)\nfor bit in range(1 << N):\n\tfor (i, (xi, yi, _)) in enumerate(XYP):\n\t\tx_cost[bit * N + i] = min(costs[i], x_cost[bit * N + i])\n\t\ty_cost[bit * N + i] = min(costs[i], y_cost[bit * N + i])\n\t\tif not bit & 1 << i:\n\t\t\tcontinue\n\t\tfor (k, (xk, yk, c)) in enumerate(XYP):\n\t\t\tx_cost[bit * N + k] = min(x_cost[bit * N + k], abs(xi - xk) * c)\n\t\t\ty_cost[bit * N + k] = min(y_cost[bit * N + k], abs(yi - yk) * c)\nans = [sys.maxsize] * (N + 1)\nfor bit in range(1 << N):\n\tcnt = bin(bit).count('1')\n\tbit_ = bit\n\twhile bit_ >= 0:\n\t\tbit_ &= bit\n\t\tcost = 0\n\t\ty_bit = bit - bit_\n\t\tfor k in range(N):\n\t\t\tcost += min(x_cost[bit_ * N + k], y_cost[y_bit * N + k])\n\t\tans[cnt] = min(ans[cnt], cost)\n\t\tbit_ -= 1\nfor i in range(N + 1):\n\tprint(ans[i])\n", "import sys\nread = sys.stdin.buffer.read\nreadline = sys.stdin.buffer.readline\nreadlines = sys.stdin.buffer.readlines\nN = int(readline())\nX = []\nY = []\nP = []\nfor _ in range(N):\n\t(x, y, p) = map(int, readline().split())\n\tX.append(x)\n\tY.append(y)\n\tP.append(p)\nDX = [[0] * N for _ in range(1 << N)]\nDY = [[0] * N for _ in range(1 << N)]\nfor (i, x) in enumerate(X):\n\tfor k in range(1 << N):\n\t\td = abs(x)\n\t\tfor (j, xx) in enumerate(X):\n\t\t\tif k >> j & 1:\n\t\t\t\td = min(d, abs(x - xx))\n\t\tDX[k][i] = d * P[i]\nfor (i, y) in enumerate(Y):\n\tfor k in range(1 << N):\n\t\td = abs(y)\n\t\tfor (j, yy) in enumerate(Y):\n\t\t\tif k >> j & 1:\n\t\t\t\td = min(d, abs(y - yy))\n\t\tDY[k][i] = d * P[i]\nPC = [0] * (1 << N)\nfor i in range(1 << N):\n\tPC[i] = PC[i // 2] + 1 if i % 2 else PC[i // 2]\nRA = []\nfor i in range(1 << N):\n\tt = []\n\tfor j in range(N):\n\t\tif i >> j & 1:\n\t\t\tt.append(j)\n\tRA.append(t)\nINF = 10 ** 31\nmm = (1 << N) - 1\nANS = [INF] * (N + 1)\nfor i in range(1 << N):\n\tm = i ^ mm\n\tj = m\n\tdxi = DX[i]\n\tpci = PC[i]\n\twhile True:\n\t\tdyj = DY[j]\n\t\tans = 0\n\t\tfor k in RA[i ^ j ^ mm]:\n\t\t\tans += min(dxi[k], dyj[k])\n\t\tpc = pci + PC[j]\n\t\tif ans < ANS[pc]:\n\t\t\tANS[pc] = ans\n\t\tif j == 0:\n\t\t\tbreak\n\t\tj = m & j - 1\nprint(*ANS, sep='\\n')\n", "INF = 10 ** 12\nN = int(input())\nX = [0] * N\nY = [0] * N\nP = [0] * N\nfor i in range(N):\n\t(X[i], Y[i], P[i]) = map(int, input().split())\nscore_X = []\nfor i in range(2 ** N):\n\tx = []\n\tI = i\n\tfor j in range(N):\n\t\ti = I\n\t\tscore = abs(X[j]) * P[j]\n\t\tfor k in range(N):\n\t\t\tif i & 1:\n\t\t\t\tscore = min(score, abs(X[j] - X[k]) * P[j])\n\t\t\ti >>= 1\n\t\tx.append(score)\n\tscore_X.append(x)\nscore_Y = []\nfor i in range(2 ** N):\n\ty = []\n\tI = i\n\tfor j in range(N):\n\t\ti = I\n\t\tscore = abs(Y[j]) * P[j]\n\t\tfor k in range(N):\n\t\t\tif i & 1:\n\t\t\t\tscore = min(score, abs(Y[j] - Y[k]) * P[j])\n\t\t\ti >>= 1\n\t\ty.append(score)\n\tscore_Y.append(y)\nans = [INF] * (N + 1)\nfor i in range(2 ** N):\n\tcnt = 0\n\tfor j in range(N):\n\t\tif i >> j & 1:\n\t\t\tcnt += 1\n\tj = i\n\twhile True:\n\t\tscore = 0\n\t\tfor k in range(N):\n\t\t\tif not i >> k & 1:\n\t\t\t\tscore += min(score_X[j][k], score_Y[i - j][k])\n\t\tans[cnt] = min(ans[cnt], score)\n\t\tif j == 0:\n\t\t\tbreak\n\t\tj = j - 1 & i\nfor i in range(N + 1):\n\tprint(ans[i])\n", "import sys\n(n, *towns) = map(int, sys.stdin.buffer.read().split())\nxxx = towns[0::3]\nyyy = towns[1::3]\nppp = towns[2::3]\nINF = 10 ** 18\nans = [INF] * (n + 1)\nprecalc_dist_x = []\nprecalc_dist_y = []\nfor bit in range(1 << n):\n\tdists_x = []\n\tdists_y = []\n\tfor i in range(n):\n\t\tx = xxx[i]\n\t\ty = yyy[i]\n\t\tdist_x = abs(x)\n\t\tdist_y = abs(y)\n\t\tt = bit\n\t\tj = 0\n\t\twhile t:\n\t\t\tif t & 1:\n\t\t\t\tdist_x = min(dist_x, abs(xxx[j] - x))\n\t\t\t\tdist_y = min(dist_y, abs(yyy[j] - y))\n\t\t\tt >>= 1\n\t\t\tj += 1\n\t\tdists_x.append(dist_x * ppp[i])\n\t\tdists_y.append(dist_y * ppp[i])\n\tprecalc_dist_x.append(dists_x)\n\tprecalc_dist_y.append(dists_y)\nfor bit in range(1 << n):\n\tk = (bit & 21845) + (bit >> 1 & 21845)\n\tk = (k & 13107) + (k >> 2 & 13107)\n\tk = (k & 3855) + (k >> 4 & 3855)\n\tk = (k & 255) + (k >> 8 & 255)\n\tvertical = bit\n\twhile vertical:\n\t\tcost = 0\n\t\tpcx = precalc_dist_x[vertical]\n\t\tpcy = precalc_dist_y[vertical ^ bit]\n\t\tfor i in range(n):\n\t\t\tcost += min(pcx[i], pcy[i])\n\t\tans[k] = min(ans[k], cost)\n\t\tvertical = vertical - 1 & bit\n\tcost = 0\n\tpcx = precalc_dist_x[0]\n\tpcy = precalc_dist_y[bit]\n\tfor i in range(n):\n\t\tcost += min(pcx[i], pcy[i])\n\tans[k] = min(ans[k], cost)\nprint('\\n'.join(map(str, ans)))\n", "import sys\ninput = sys.stdin.readline\nINF = float('inf')\nN = int(input().strip())\ndata = [list(map(int, input().split())) for _ in range(N)]\ncost_b = []\ncost_D = []\nfor b in range(1 << N):\n\ttowns = []\n\tcost = INF\n\tfor i in range(N):\n\t\tif b >> i & 1:\n\t\t\ttowns.append(data[i])\n\tfor i in range(len(towns)):\n\t\tX = towns[i][0]\n\t\tcost = min(cost, sum((abs(towns[j][0] - X) * towns[j][2] for j in range(len(towns)))))\n\tfor i in range(len(towns)):\n\t\tY = towns[i][1]\n\t\tcost = min(cost, sum((abs(towns[j][1] - Y) * towns[j][2] for j in range(len(towns)))))\n\tif len(towns) == 0:\n\t\tcost = 0\n\tcost_b.append(cost)\n\tcost_D.append(sum((min(abs(towns[j][0]), abs(towns[j][1])) * towns[j][2] for j in range(len(towns)))))\ndp = [[INF] * (N + 1) for i in range(1 << N)]\nfor i in range(1 << N):\n\tdp[i][0] = cost_D[i]\ncount = 0\nfor k in range(1, N + 1):\n\tfor i in range(1 << N)[::-1]:\n\t\tx = i\n\t\twhile x >= 0:\n\t\t\tx &= i\n\t\t\tnew = dp[i - x][k - 1] + cost_b[x]\n\t\t\tif dp[i][k] > new:\n\t\t\t\tdp[i][k] = new\n\t\t\tif new == 0:\n\t\t\t\tbreak\n\t\t\tx -= 1\nfor i in range(N + 1):\n\tprint(dp[-1][i])\n", "import sys\ninput = sys.stdin.readline\nINF = 10 ** 13\n\ndef main():\n\tN = int(input())\n\tX = []\n\tY = []\n\tP = []\n\tfor _ in range(N):\n\t\t(a, b, c) = (int(i) for i in input().split())\n\t\tX.append(a)\n\t\tY.append(b)\n\t\tP.append(c)\n\tX_dist = [[0] * N for _ in range(1 << N)]\n\tY_dist = [[0] * N for _ in range(1 << N)]\n\tfor bit in range(1 << N):\n\t\tcur_x = [0]\n\t\tcur_y = [0]\n\t\tfor i in range(N):\n\t\t\tif bit & 1 << i:\n\t\t\t\tcur_x.append(X[i])\n\t\t\t\tcur_y.append(Y[i])\n\t\tfor i in range(N):\n\t\t\tX_dist[bit][i] = P[i] * min((abs(cx - X[i]) for cx in cur_x))\n\t\t\tY_dist[bit][i] = P[i] * min((abs(cy - Y[i]) for cy in cur_y))\n\tanswer = [INF] * (N + 1)\n\tfor i in range(1 << N):\n\t\tcnt = 0\n\t\tfor j in range(N):\n\t\t\tif i >> j & 1:\n\t\t\t\tcnt += 1\n\t\tj = i\n\t\twhile j >= 0:\n\t\t\tj &= i\n\t\t\tcost = 0\n\t\t\tfor k in range(N):\n\t\t\t\tif not i >> k & 1:\n\t\t\t\t\tcost += min(X_dist[j][k], Y_dist[i - j][k])\n\t\t\tanswer[cnt] = min(answer[cnt], cost)\n\t\t\tj -= 1\n\tfor ans in answer:\n\t\tprint(ans)\nmain()\n", "import sys\ninput = sys.stdin.readline\nN = int(input())\na = [tuple(map(int, input().split())) for _ in range(N)]\ntable = [0] * N\nfor k in range(N):\n\ttable[k] = min(abs(a[k][0]), abs(a[k][1])) * a[k][2]\ntableudi = [10 ** 12 for _ in range((1 << N) * N)]\ntablelri = [10 ** 12 for _ in range((1 << N) * N)]\nfor i in range(1 << N):\n\tfor j in range(N):\n\t\tif i & 1 << j:\n\t\t\tfor k in range(N):\n\t\t\t\tud = min(abs(a[k][0] - a[j][0]) * a[k][2], table[k])\n\t\t\t\tlr = min(abs(a[k][1] - a[j][1]) * a[k][2], table[k])\n\t\t\t\ttableudi[i * N + k] = min(tableudi[i * N + k], ud)\n\t\t\t\ttablelri[i * N + k] = min(tablelri[i * N + k], lr)\n\t\telse:\n\t\t\tfor k in range(N):\n\t\t\t\ttableudi[i * N + k] = min(tableudi[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])\n\t\t\t\ttablelri[i * N + k] = min(tablelri[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])\nres = [10 ** 12] * (N + 1)\nfor t in range(1 << N):\n\ti = t + 0\n\tc = bin(t).count('1')\n\twhile True:\n\t\tx = i + 0\n\t\ty = t ^ x\n\t\trres = 0\n\t\tfor j in range(N):\n\t\t\trres += min(tableudi[x * N + j], tablelri[y * N + j])\n\t\tres[c] = min(res[c], rres)\n\t\tif i == 0:\n\t\t\tbreak\n\t\ti = i - 1 & t\nfor r in res:\n\tprint(r)\n", "import sys\nsys.setrecursionlimit(10 ** 6)\nint1 = lambda x: int(x) - 1\np2D = lambda x: print(*x, sep='\\n')\n\ndef II():\n\treturn int(sys.stdin.readline())\n\ndef MI():\n\treturn map(int, sys.stdin.readline().split())\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef LLI(rows_number):\n\treturn [LI() for _ in range(rows_number)]\n\ndef SI():\n\treturn sys.stdin.readline()[:-1]\n\ndef solve():\n\txc = [[0] * n for _ in range(1 << n)]\n\tyc = [[0] * n for _ in range(1 << n)]\n\tfor s in range(1 << n):\n\t\txcs = xc[s]\n\t\tycs = yc[s]\n\t\tfor (i, (x, y, p)) in enumerate(xyp):\n\t\t\txcost = abs(x)\n\t\t\tycost = abs(y)\n\t\t\tfor (j, (lx, ly, _)) in enumerate(xyp):\n\t\t\t\tif s >> j & 1 == 0:\n\t\t\t\t\tcontinue\n\t\t\t\tif abs(x - lx) < xcost:\n\t\t\t\t\txcost = abs(x - lx)\n\t\t\t\tif abs(y - ly) < ycost:\n\t\t\t\t\tycost = abs(y - ly)\n\t\t\txcs[i] = xcost * p\n\t\t\tycs[i] = ycost * p\n\tans = [inf] * (n + 1)\n\tfor s in range(1 << n):\n\t\tk = bin(s).count('1')\n\t\txs = (1 << n) - 1\n\t\twhile xs > 0:\n\t\t\txs &= s\n\t\t\txcs = xc[xs]\n\t\t\tycs = yc[s - xs]\n\t\t\tcur = 0\n\t\t\tfor i in range(n):\n\t\t\t\tcur += min(xcs[i], ycs[i])\n\t\t\tif cur < ans[k]:\n\t\t\t\tans[k] = cur\n\t\t\txs -= 1\n\tfor a in ans:\n\t\tprint(a)\ninf = 10 ** 16\nn = II()\nxyp = LLI(n)\nsolve()\n", "import sys\nint1 = lambda x: int(x) - 1\np2D = lambda x: print(*x, sep='\\n')\n\ndef II():\n\treturn int(sys.stdin.readline())\n\ndef MI():\n\treturn map(int, sys.stdin.readline().split())\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef LLI(rows_number):\n\treturn [LI() for _ in range(rows_number)]\n\ndef SI():\n\treturn sys.stdin.readline()[:-1]\n\ndef cal(xp):\n\tres = [inf] * (n + 1)\n\txp.sort()\n\tm = len(xp)\n\tdp = [[inf] * (m + 1) for _ in range(m + 1)]\n\tdp[0][0] = 0\n\tfor (l, (x, p)) in enumerate(xp):\n\t\tdp[l + 1][0] = dp[l][0] + abs(x) * p\n\tfor l in range(m):\n\t\tdpl = dp[l]\n\t\tfor r in range(l + 1, m + 1):\n\t\t\tdpr = dp[r]\n\t\t\tval = inf\n\t\t\tfor (lx, _) in xp[l:r]:\n\t\t\t\tcur = 0\n\t\t\t\tfor (x, p) in xp[l:r]:\n\t\t\t\t\tcur += min(abs(x - lx), abs(x)) * p\n\t\t\t\tval = min(cur, val)\n\t\t\tfor j in range(1, m + 1):\n\t\t\t\tdpr[j] = min(dpr[j], dpl[j - 1] + val)\n\tdpm = dp[m]\n\tfor i in range(m + 1):\n\t\tres[i] = dpm[i]\n\treturn res\ninf = 10 ** 16\nn = II()\nxyp = LLI(n)\nans = [inf] * (n + 1)\nfor s in range(1 << n):\n\txp = []\n\typ = []\n\tfor (i, (x, y, p)) in enumerate(xyp):\n\t\tif s >> i & 1:\n\t\t\txp.append((x, p))\n\t\telse:\n\t\t\typ.append((y, p))\n\txc = cal(xp)\n\tyc = cal(yp)\n\tfor i in range(n + 1):\n\t\tfor j in range(n + 1 - i):\n\t\t\tans[i + j] = min(ans[i + j], xc[i] + yc[j])\nfor a in ans:\n\tprint(a)\n", "from bisect import bisect_left\nn = int(input())\nxyp = [list(map(int, input().split())) for i in range(n)]\ninf = 1 << 63\ntate = [[] for i in range(1 << n)]\nyoko = [[] for i in range(1 << n)]\nstate_ind = [[] for i in range(1 << n)]\nfor state in range(1 << n):\n\ttmp_x = [0]\n\ttmp_y = [0]\n\tfor i in range(n):\n\t\tif state & 1 << i:\n\t\t\ttmp_x.append(xyp[i][0])\n\t\t\ttmp_y.append(xyp[i][1])\n\t\telse:\n\t\t\tstate_ind[state].append(i)\n\ttmp_x.sort()\n\ttmp_y.sort()\n\tx_score = [0] * n\n\ty_score = [0] * n\n\tnn = len(tmp_x)\n\tmm = len(tmp_y)\n\tfor (i, (x, y, p)) in enumerate(xyp):\n\t\tj = bisect_left(tmp_x, x)\n\t\tif j == 0:\n\t\t\tx_m = tmp_x[0] - x\n\t\telif j == nn:\n\t\t\tx_m = x - tmp_x[nn - 1]\n\t\telse:\n\t\t\tx_m = min(x - tmp_x[j - 1], tmp_x[j] - x)\n\t\tj = bisect_left(tmp_y, y)\n\t\tif j == 0:\n\t\t\ty_m = tmp_y[0] - y\n\t\telif j == mm:\n\t\t\ty_m = y - tmp_y[mm - 1]\n\t\telse:\n\t\t\ty_m = min(y - tmp_y[j - 1], tmp_y[j] - y)\n\t\tx_score[i] = x_m * p\n\t\ty_score[i] = y_m * p\n\ttate[state] = x_score\n\tyoko[state] = y_score\nans = [inf] * (1 << n)\nfor state in range(1 << n):\n\tj = state\n\twhile j >= 0:\n\t\tj &= state\n\t\ti = state ^ j\n\t\ttmp1 = 0\n\t\tfor k in state_ind[state]:\n\t\t\tif tate[i][k] < yoko[j][k]:\n\t\t\t\ttmp1 += tate[i][k]\n\t\t\telse:\n\t\t\t\ttmp1 += yoko[j][k]\n\t\t\tif tmp1 >= ans[state]:\n\t\t\t\tbreak\n\t\tif tmp1 < ans[state]:\n\t\t\tans[state] = tmp1\n\t\tj -= 1\ncnt = [0] * (1 << n)\nfor i in range(1 << n - 1):\n\tcnt[2 * i] = cnt[i]\n\tcnt[2 * i + 1] = cnt[i] + 1\nans_k = [inf] * (n + 1)\nfor state in range(1 << n):\n\tk = cnt[state]\n\tif ans_k[k] > ans[state]:\n\t\tans_k[k] = ans[state]\nprint(*ans_k, sep='\\n')\n", "import sys\nread = sys.stdin.read\nreadline = sys.stdin.readline\n(n,) = map(int, readline().split())\nxyp = tuple((tuple(map(int, readline().split())) for _ in range(n)))\nN = 1 << n\nINF = 1 << 60\nresx = []\nresy = []\nfor i in range(n):\n\t(x, y, p) = xyp[i]\n\trx = [abs(x)] * N\n\try = [abs(y)] * N\n\tfor j in range(n):\n\t\tfor k in range(1 << j):\n\t\t\trx[k + (1 << j)] = min(rx[k], abs(x - xyp[j][0]))\n\t\t\try[k + (1 << j)] = min(ry[k], abs(y - xyp[j][1]))\n\tfor j in range(N):\n\t\trx[j] *= p\n\t\try[j] *= p\n\tresx.append(rx)\n\tresy.append(ry)\ncnt = [n] * N\nfor j in range(n):\n\tfor k in range(1 << j):\n\t\tcnt[k + (1 << j)] = cnt[k] - 1\nans = [INF] * (n + 1)\nfor m0 in range(N):\n\tv = cnt[m0]\n\tmx = N - 1 & ~m0\n\twhile mx >= 0:\n\t\tmy = N - 1 ^ m0 ^ mx\n\t\tr = 0\n\t\tfor i in range(n):\n\t\t\tif m0 >> i & 1:\n\t\t\t\tr += min(resx[i][mx], resy[i][my])\n\t\tif r < ans[v]:\n\t\t\tans[v] = r\n\t\tmx = mx - 1 & ~m0\nfor i in ans:\n\tprint(i)\n"]

name: M-SOLUTIONS Programming Contest 2020 - M's Solution

source: atcoder

time_limit: 3.0 seconds

memory_limit: 1024.0 megabytes

raw_problem:
配点: <var>500</var> 点

問題文

新 AtCoder 市は以下のように、無限に広がる碁盤の目のような構造になっています。

新 AtCoder 市の中心には時計台があり、この座標を <var>(0, 0)</var> とする。

時計台を通る東西方向に一直線の道路があり、これを「東西大通り」とする。これは <var>2</var> 次元座標平面では <var>x</var> 軸に相当する。

そのほかにも、東西大通りに平行な道路が、距離 <var>1</var> ずつ間隔をあけて無限本存在する。これらは、直線 <var>y = (0 \ 以外の整数)</var> に相当する。

時計台を通る南北方向に一直線の道路があり、これを「南北大通り」とする。これは <var>2</var> 次元座標平面では <var>y</var> 軸に相当する。

そのほかにも、南北大通りに平行な道路が、距離 <var>1</var> ずつ間隔をあけて無限本存在する。これらは、直線 <var>x = (0 \ 以外の整数)</var> に相当する。

新 AtCoder 市には <var>N</var> 個の集落があります。<var>i</var> 個目の集落は、座標 <var>(X_i, Y_i)</var> の交差点上にあり、人口は <var>P_i</var> です。各市民は、これらの集落のうちいずれかひとつに住んでいます。

現時点で、鉄道路線は東西大通りに沿って無限に延びるものと、南北大通りに沿って無限に延びるものの <var>2</var> 本しかありません。

市長の M 君は、これでは通勤に不便だと考えたので、新たに <var>K</var> 本の通りを選んで、それぞれに沿って無限に延びる鉄道路線を建設することにしました。

ここで、新 AtCoder 市の各市民の「歩行距離」を、住んでいる集落から最も近い鉄道路線までの距離とします。

このとき、全ての市民の歩行距離の合計 <var>S</var> が最も小さくなるように鉄道路線を建設したいです。

さて、<var>K = 0, 1, 2, \dots, N</var> のそれぞれについて、鉄道路線建設後の <var>S</var> の最小値はいくつでしょうか？

制約

<var>1 \leq N \leq 15</var>

<var>-10 \ 000 \leq X_i \leq 10 \ 000</var>

<var>-10 \ 000 \leq Y_i \leq 10 \ 000</var>

<var>1 \leq P_i \leq 1 \ 000 \ 000</var>

<var>N</var> 個の集落の場所 <var>(X_i, Y_i)</var> はすべて異なる

入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

<var>N</var>
<var>X_1</var> <var>Y_1</var> <var>P_1</var>
<var>X_2</var> <var>Y_2</var> <var>P_2</var>
 <var>:</var>  <var>:</var>  <var>:</var>
<var>X_N</var> <var>Y_N</var> <var>P_N</var>

出力

答えを <var>N+1</var> 行に出力してください。

<var>i</var> 行目 <var>(i = 1, \ldots, N+1)</var> には、<var>K = i - 1</var> の場合の鉄道路線建設後の <var>S</var> の最小値を整数として出力してください。

入力例 1

3
1 2 300
3 3 600
1 4 800

出力例 1

2900
900
0
0

<var>K = 0</var> の場合、集落 <var>1, 2, 3</var> の住民は、鉄道路線にたどり着くためには、それぞれ距離 <var>1, 3, 1</var> 歩く必要があります。

したがって、全ての市民の歩行距離の合計 <var>S</var> は <var>1 \times 300 + 3 \times 600 + 1 \times 800 = 2900</var> となります。

<var>K = 1</var> の場合、東西大通りから距離 <var>4</var> だけ北の道路に鉄道路線を建設すると、集落 <var>1, 2, 3</var> の住民の歩行距離は <var>1, 1, 0</var> になります。

すると、<var>S = 1 \times 300 + 1 \times 600 + 0 \times 800 = 900</var> となります。

他にも多くの候補から建設場所を選べますが、そのうちどれも <var>S</var> を <var>900</var> より小さくすることはできません。

<var>K = 2</var> の場合、南北大通りから距離 <var>1, 3</var> だけ東の道路に鉄道路線を建設すると、新 AtCoder 市のすべての住民が歩行距離 <var>0</var> で鉄道路線にたどり着くことができるので、<var>S = 0</var> となります。また、<var>K = 3</var> の場合も、<var>S = 0</var> とすることができます。

<var>K = 0, 1, 2</var> の場合の最適な鉄道路線の建設方法を下図に示します。

青く塗られた道路が鉄道路線を敷設する道路を表します。

入力例 2

5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400

出力例 2

13800
1600
0
0
0
0

<var>K = 1, 2</var> の場合の最適な鉄道路線の建設方法を下図に示します。

入力例 3

6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200

出力例 3

26700
13900
3200
1200
0
0
0

<var>K = 3</var> の場合の最適な鉄道路線の建設方法を下図に示します。

入力例 4

8
2 2 286017
3 1 262355
2 -2 213815
1 -3 224435
-2 -2 136860
-3 -1 239338
-2 2 217647
-1 3 141903

出力例 4

2576709
1569381
868031
605676
366338
141903
0
0
0

<var>K = 4</var> の場合の最適な鉄道路線の建設方法を下図に示します。

Score: <var>500</var> points

Problem Statement

New AtCoder City has an infinite grid of streets, as follows:

At the center of the city stands a clock tower. Let <var>(0, 0)</var> be the coordinates of this point.

A straight street, which we will call East-West Main Street, runs east-west and passes the clock tower. It corresponds to the <var>x</var>-axis in the two-dimensional coordinate plane.

There are also other infinitely many streets parallel to East-West Main Street, with a distance of <var>1</var> between them. They correspond to the lines <var>\ldots, y = -2, y = -1, y = 1, y = 2, \ldots</var> in the two-dimensional coordinate plane.

A straight street, which we will call North-South Main Street, runs north-south and passes the clock tower. It corresponds to the <var>y</var>-axis in the two-dimensional coordinate plane.

There are also other infinitely many streets parallel to North-South Main Street, with a distance of <var>1</var> between them. They correspond to the lines <var>\ldots, x = -2, x = -1, x = 1, x = 2, \ldots</var> in the two-dimensional coordinate plane.

There are <var>N</var> residential areas in New AtCoder City. The <var>i</var>-th area is located at the intersection with the coordinates <var>(X_i, Y_i)</var> and has a population of <var>P_i</var>. Each citizen in the city lives in one of these areas.

The city currently has only two railroads, stretching infinitely, one along East-West Main Street and the other along North-South Main Street.

M-kun, the mayor, thinks that they are not enough for the commuters, so he decides to choose <var>K</var> streets and build a railroad stretching infinitely along each of those streets.

Let the walking distance of each citizen be the distance from his/her residential area to the nearest railroad.

M-kun wants to build railroads so that the sum of the walking distances of all citizens, <var>S</var>, is minimized.

For each <var>K = 0, 1, 2, \dots, N</var>, what is the minimum possible value of <var>S</var> after building railroads?

Constraints

<var>1 \leq N \leq 15</var>

<var>-10 \ 000 \leq X_i \leq 10 \ 000</var>

<var>-10 \ 000 \leq Y_i \leq 10 \ 000</var>

<var>1 \leq P_i \leq 1 \ 000 \ 000</var>

The locations of the <var>N</var> residential areas, <var>(X_i, Y_i)</var>, are all distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

<var>N</var>
<var>X_1</var> <var>Y_1</var> <var>P_1</var>
<var>X_2</var> <var>Y_2</var> <var>P_2</var>
 <var>:</var>  <var>:</var>  <var>:</var>
<var>X_N</var> <var>Y_N</var> <var>P_N</var>

Output

Print the answer in <var>N+1</var> lines.

The <var>i</var>-th line <var>(i = 1, \ldots, N+1)</var> should contain the minimum possible value of <var>S</var> after building railroads for the case <var>K = i-1</var>.

Sample Input 1

3
1 2 300
3 3 600
1 4 800

Sample Output 1

2900
900
0
0

When <var>K = 0</var>, the residents of Area <var>1</var>, <var>2</var>, and <var>3</var> have to walk the distances of <var>1</var>, <var>3</var>, and <var>1</var>, respectively, to reach a railroad.

Thus, the sum of the walking distances of all citizens, <var>S</var>, is <var>1 \times 300 + 3 \times 600 + 1 \times 800 = 2900</var>.

When <var>K = 1</var>, if we build a railroad along the street corresponding to the line <var>y = 4</var> in the coordinate plane, the walking distances of the citizens of Area <var>1</var>, <var>2</var>, and <var>3</var> become <var>1</var>, <var>1</var>, and <var>0</var>, respectively.

Then, <var>S = 1 \times 300 + 1 \times 600 + 0 \times 800 = 900</var>.

We have many other options for where we build the railroad, but none of them makes <var>S</var> less than <var>900</var>.

When <var>K = 2</var>, if we build a railroad along the street corresponding to the lines <var>x = 1</var> and <var>x = 3</var> in the coordinate plane, all citizens can reach a railroad with the walking distance of <var>0</var>, so <var>S = 0</var>. We can also have <var>S = 0</var> when <var>K = 3</var>.

The figure below shows the optimal way to build railroads for the cases <var>K = 0, 1, 2</var>.

The street painted blue represents the roads along which we build railroads.

Sample Input 2

5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400

Sample Output 2

13800
1600
0
0
0
0

The figure below shows the optimal way to build railroads for the cases <var>K = 1, 2</var>.

Sample Input 3

6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200

Sample Output 3

26700
13900
3200
1200
0
0
0

The figure below shows the optimal way to build railroads for the case <var>K = 3</var>.

Sample Input 4

8
2 2 286017
3 1 262355
2 -2 213815
1 -3 224435
-2 -2 136860
-3 -1 239338
-2 2 217647
-1 3 141903

Sample Output 4

2576709
1569381
868031
605676
366338
141903
0
0
0

The figure below shows the optimal way to build railroads for the case <var>K = 4</var>.

question:
New AtCoder City has an infinite grid of streets, as follows:

- At the center of the city stands a clock tower. Let $(0, 0)$ be the coordinates of this point.
- A straight street, which we will call East-West Main Street, runs east-west and passes the clock tower. It corresponds to the $x$-axis in the two-dimensional coordinate plane.
- There are also other infinitely many streets parallel to East-West Main Street, with a distance of $1$ between them. They correspond to the lines $\ldots, y = -2, y = -1, y = 1, y = 2, \ldots$ in the two-dimensional coordinate plane.
- A straight street, which we will call North-South Main Street, runs north-south and passes the clock tower. It corresponds to the $y$-axis in the two-dimensional coordinate plane.
- There are also other infinitely many streets parallel to North-South Main Street, with a distance of $1$ between them. They correspond to the lines $\ldots, x = -2, x = -1, x = 1, x = 2, \ldots$ in the two-dimensional coordinate plane.

There are $N$ residential areas in New AtCoder City. The $i$-th area is located at the intersection with the coordinates $(X_i, Y_i)$ and has a population of $P_i$. Each citizen in the city lives in one of these areas.
The city currently has only two railroads, stretching infinitely, one along East-West Main Street and the other along North-South Main Street.
M-kun, the mayor, thinks that they are not enough for the commuters, so he decides to choose $K$ streets and build a railroad stretching infinitely along each of those streets.
Let the walking distance of each citizen be the distance from his/her residential area to the nearest railroad.
M-kun wants to build railroads so that the sum of the walking distances of all citizens, $S$, is minimized.
For each $K = 0, 1, 2, \dots, N$, what is the minimum possible value of $S$ after building railroads?

Constraints

- $1 \leq N \leq 15$
- $-10 \ 000 \leq X_i \leq 10 \ 000$
- $-10 \ 000 \leq Y_i \leq 10 \ 000$
- $1 \leq P_i \leq 1 \ 000 \ 000$
- The locations of the $N$ residential areas, $(X_i, Y_i)$, are all distinct.
- All values in input are integers.

Input

Input is given from Standard Input in the following format:
$N$

$X_1$ $Y_1$ $P_1$

$X_2$ $Y_2$ $P_2$

$:$  $:$  $:$

$X_N$ $Y_N$ $P_N$

Output

Print the answer in $N+1$ lines.
The $i$-th line $(i = 1, \ldots, N+1)$ should contain the minimum possible value of $S$ after building railroads for the case $K = i-1$.

Sample Input 1
3
1 2 300
3 3 600
1 4 800

Sample Output 1
2900
900
0
0

When $K = 0$, the residents of Area $1$, $2$, and $3$ have to walk the distances of $1$, $3$, and $1$, respectively, to reach a railroad.
Thus, the sum of the walking distances of all citizens, $S$, is $1 \times 300 + 3 \times 600 + 1 \times 800 = 2900$.
When $K = 1$, if we build a railroad along the street corresponding to the line $y = 4$ in the coordinate plane, the walking distances of the citizens of Area $1$, $2$, and $3$ become $1$, $1$, and $0$, respectively.
Then, $S = 1 \times 300 + 1 \times 600 + 0 \times 800 = 900$.
We have many other options for where we build the railroad, but none of them makes $S$ less than $900$.
When $K = 2$, if we build a railroad along the street corresponding to the lines $x = 1$ and $x = 3$ in the coordinate plane, all citizens can reach a railroad with the walking distance of $0$, so $S = 0$. We can also have $S = 0$ when $K = 3$.
The figure below shows the optimal way to build railroads for the cases $K = 0, 1, 2$.
The street painted blue represents the roads along which we build railroads.
![image](1.png)

Sample Input 2
5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400

Sample Output 2
13800
1600
0
0
0
0

The figure below shows the optimal way to build railroads for the cases $K = 1, 2$.
![image](2.png)

Sample Input 3
6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200

Sample Output 3
26700
13900
3200
1200
0
0
0

The figure below shows the optimal way to build railroads for the case $K = 3$.
![image](3.png)

Sample Input 4
8
2 2 286017
3 1 262355
2 -2 213815
1 -3 224435
-2 -2 136860
-3 -1 239338
-2 2 217647
-1 3 141903

Sample Output 4
2576709
1569381
868031
605676
366338
141903
0
0
0

The figure below shows the optimal way to build railroads for the case $K = 4$.
![image](4.png)

image_tags: Map Map Map Map

data_split: test