루미 알고리즘

#1609다이아Eating Chocolate

PO 2025 훈련 캠프코딩출제 Olle Lapidus영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Olle and Lisa have received N types of chocolate bars of various shapes from their parents, which they now plan to eat together (the chocolate bars, not the parents). Each chocolate bar is a rectangle consisting of R_i × C_i squares, and they have received k_i identical copies of the i:th type. The chocolate bars are placed on a table, and to eat them, they take turns making the following move:

  • Choose a chocolate bar from the table.
  • Break it into two parts so that both parts are rectangles with integer side lengths.
  • Eat the smaller part.
  • Put the remaining larger part back on the table.

If the chosen chocolate bar has size 1 × 1, they eat it directly and do not place anything back on the table. They have already decided that Lisa will start.

Due to sibling affection, they will always choose a chocolate bar from the table that, after splitting it in two and placing the larger piece back, ensures that they eat as much as possible in that move. If there are multiple such choices, they arbitrarily select one. Additionally, Olle is very concerned about fairness and wants the total number of chocolate squares they eat to be as equal as possible. To achieve this goal, he may choose to throw away at most one chocolate bar in the trash before they begin, without Lisa noticing.

Let V_O and V_L be the number of squares that Olle and Lisa eat, respectively, given that they both eat in a gluttonous manner. Your task is to determine the minimum possible difference, i.e., |V_O - V_L|, after Olle has thrown away at most one chocolate bar.

Input

The first line contains the number N (1 ≤ N ≤ 10^5), the number of chocolate bars on the table.

Then follow N lines, where the i-th line contains the numbers R_i, C_i, and k_i (1 ≤ R_i, C_i ≤ 10^6, 1 ≤ k_i ≤ 10^9), whose meaning is described above.

Output

Print an integer: the minimum value of |V_O - V_L| as described above.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
14N = 1
212N ≤ 50, K_i ≤ 5
315N ≤ 200, K_i ≤ 5
410R_i, C_i ≤ 10
513N ≤ 200
616K_i = 1
730No additional constraints.

Explanation of Sample 1

Olle throws away the chocolate bar of size 2 × 2. Then, they will each eat one square of chocolate twice, meaning V_O = V_L.

Explanation of Sample 2

In this test case, it is optimal for Olle not to throw away any chocolate bar. They will then eat exactly the same amount of chocolate.

예제

예제 1

입력
3
1 2 1
2 2 1
2 1 1
출력
0

예제 2

입력
1
1 1 4
출력
0

예제 3

입력
3
4 7 1
8 8 1
4 1 1
출력
10

예제 4

입력
4
12 34 1
13 37 2
20 25 3
1 101 4
출력
94

출처 표기

출처: Programmeringsolympiaden 2025년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.