영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Group | Points | Constraints |
|---|---|---|
| 1 | 4 | N = 1 |
| 2 | 12 | N ≤ 50, K_i ≤ 5 |
| 3 | 15 | N ≤ 200, K_i ≤ 5 |
| 4 | 10 | R_i, C_i ≤ 10 |
| 5 | 13 | N ≤ 200 |
| 6 | 16 | K_i = 1 |
| 7 | 30 | No 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