USACO 2022 - US Open - Hạng Vàng

Trời ơi!!! Một cơn mưa táo!! Đến một lúc nào đó, các quả táo này sẽ rơi xuống trục số. Và cũng đến một lúc nào đó, các chú bò của nông dân John sẽ đến trục số và bắt đầu hứng táo.

Nếu như một quả táo chạm vào trục số mà không được hứng, nó sẽ biến mất mãi mãi. Ngược lại, nếu như một chú bò đến kịp lúc quả táo chạm đất, chú ta sẽ hứng được quả táo đó. Biết rằng mỗi chú bò chỉ có thể di chuyển một đơn vị khoảng cách mỗi giây và một khi đã hứng được một quả táo, chú ta sẽ đi ra khỏi trục số ngay lập tức.

Hãy cho biết số táo nhiều nhất hứng được là bao nhiêu nếu như các chú bò hứng một cách tối ưu!

Input

• Dòng đầu tiên là số \(N\) \((1 \le N \le 2 \times 10^5)\) là số lần một quả táo rơi trúng trục số hoặc một chú bò xuất hiện ở trục số.
• \(N\) dòng tiếp theo, mỗi dòng là bộ bốn số nguyên \(q_i, t_i, x_i, n_i\) \((q_i \in \{1, 2\}, 0 \le t_i \le 10^9, 0 \le x_i \le 10^9, 1 \le n_i \le 10^3)\):
  • Nếu \(q_i = 1\), \(n_i\) chú bò của bác John sẽ xuất hiện tại vị trí \(x_i\) vào thời điểm \(t_i\).
  • Nếu \(q_i = 1\), \(n_i\) quả táo sẽ rơi trúng trục số tại vị trí \(x_i\) vào thời điểm \(t_i\).
• Dữ liệu đảm bảo mọi cặp \((t_i, x_i)\) là đôi một khác nhau.

Output

• Số lượng táo lớn nhất mà đàn bò của John thu hoạch được.

Scoring

• \(100\%\) số test không có điều kiện ràng buộc.

5
2 5 10 100
2 6 0 3
2 8 10 7
1 2 4 5
1 4 7 6

10

5
2 5 10 100
2 6 0 3
2 8 11 7
1 2 4 5
1 4 7 6

9

Một chương trình bao gồm một chuỗi lệnh, mỗi lệnh thuộc một trong các dạng sau:

• \(1: \times d\). Trong đó \(d\) là một chữ số trong khoảng \([0,9]\).
• \(2: +s\). Trong đó \(s\) là tên của biến. Trong chương trình, tất cả các tên biến phải phân biệt.

Kết quả của một chương trình là biểu thức thu được sau khi áp dụng từng lệnh theo thứ tự, bắt đầu với \(0\). Ví dụ, kết quả của chương trình \([\times 3,+x, +y, \times 2, +z]\) là biểu thức \((0\times 3+x +y)\times 2+z=2\times x+2\times y+z\) . Các chương trình khác nhau có thể tạo ra các biểu thức giống nhau; ví dụ, \([+w,\times 0,+y,+x,\times 2,+z,\times 1]\) cũng sẽ tạo ra biểu thức \(2\times x+2\times y+z\).

Bessie và Elsie mỗi người có một chương trình gồm \(N (1\leq N \leq 2000)\) lệnh. Họ sẽ sắp xếp các lệnh này để tạo ra một chương trình mới có độ dài \(2N\). Lưu ý rằng có \(\frac {(2N)!} {N! \times N!}\) cách để thực hiện việc này, nhưng không phải tất cả các trường hợp sẽ tạo ra kết quả khác nhau.

Đếm số biểu thức phân biệt có thể được tạo ra bằng cách sắp xếp các lệnh trên, kết quả \(\% (1e9+7)\).

Mỗi bộ test chứa \(T(1 \leq T \leq 10)\) test con. Dữ liệu đầu vào đảm bảo rằng tổng \(N\) trên tất cả test con không vượt quá \(2000\).

Input

• Dòng đầu tiên chứa số \(T\), số lượng test con.
• Dòng đầu tiên của mỗi test chứa số \(N\).
• Dòng thứ hai của mỗi test chứa chương trình của Bessie, được biểu thị bằng một xâu có độ dài \(N\). Mỗi ký tự, hoặc là một chữ số \(𝑑∈[0,9]\) biểu thị lệnh loại 1, hoặc ký tự \(+\) biểu thị lệnh loại 2.
• Dòng thứ ba của mỗi test chứa chương trình của Elsie, có cùng định dạng như của Bessie.
• Trong mỗi test, tên biến của các lệnh là khác nhau. Tên biến không được cung cấp vì chúng không ảnh hưởng đến câu trả lời.

Output

• Số lượng các biểu thức phân biệt có thể được tạo ra, \(\%(1e9+7)\).

Scoring

• Subtask \(1\): \(N \leq 6\)
• Subtask \(2\): \(\sum N \leq 100\)
• Subtask \(3\): \(\sum N \leq 500\)
• Subtask \(4\): Không có điều kiện gì thêm.

Example

4
1
0
1
3
12+
+02
3
0++
++9
4
5+++
+6+1

1
3
9
9        

Nông dân John đã tiến hành một nghiên cứu về sự tiến hóa của các giống bò khác nhau. Kết quả là một cây có gốc với \(N\) (\(1 \leq N \leq 10^5\)) nút đánh số từ \(1\) đến \(N\), mỗi nút tương ứng với một giống bò. Với mỗi \(i \in [2, N]\), nút cha của \(i\) là nút \(p_i\) (\(1 \leq p_i < i\)), nghĩa là giống \(i\) tiến hóa từ giống \(p_i\). Nút \(j\) được gọi là tổ tiên của nút \(i\) nếu \(j = p_i\) hoặc \(j\) là tổ tiên của \(p_i\).

Mỗi nút \(i\) tương ứng với giống bò được gán số nguyên \(s_i\). Sự "mất cân bằng" của cây là giá trị lớn nhất của \(|s_i - s_j|\) trên tất cả các cặp nút \((i, j)\) với \(j\) là tổ tiên của \(i\).

Nông dân John không biết giá trị chính xác của \(s_i\) của mỗi giống, nhưng ông biết giới hạn dưới và giới hạn trên của những giá trị này. Công việc của bạn là gán giá trị nguyên của \(s_i \in [l_i, r_i]\) (\(0 \leq l_i \leq r_i \leq 10^9\)) cho mỗi nút sao cho sự mất cân bằng của cây là nhỏ nhất.

Input

• Dòng đầu tiên chứa số \(T\) (\(1 \leq T \leq 10\)) - số lượng bộ dữ liệu, và số nguyên \(B \in \{0, 1\}\).
• Với mỗi bộ dữ liệu:
  • Dòng đầu tiên chứa số \(N\), sau đó là \(N-1\) số nguyên \(p_2, p_3, \dots, p_N\).
  • \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i, r_i\).
• Dữ liệu đảm bảo tổng \(N\) của tất cả các bộ dữ liệu không vượt quá \(10^5\).

Output

Với mỗi bộ dữ liệu, in ra \(1\) hoặc \(2\) dòng dựa vào giá trị của \(B\):

• Dòng đầu in ra độ mất cân bằng nhỏ nhất.
• Nếu \(B = 1\), dòng thứ \(2\) in ra \(N\) số nguyên \(s_1, s_2, \dots, s_N\) cách nhau bởi dấu cách.

Example

3 0
3
1 1
0 100
1 1
6 7
5
1 2 3 4
6 6
1 6
1 6
1 6
5 5
3
1 1
0 10
0 1
9 10

3
1
4

3 1
3
1 1
0 100
1 1
6 7
5
1 2 3 4
6 6
1 6
1 6
1 6
5 5
3
1 1
0 10
0 1
9 10

3
3 1 6
1
6 5 5 5 5
4
5 1 9

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(l_i = r_i\) với mọi \(i\).
• Subtask \(2\) (\(20\%\) số điểm): \(p_i = i - 1\) với mọi \(i\).
• Subtask \(3\) (\(60\%\) số điểm): Không có điều kiện gì thêm.
• Với mỗi subtask, một nửa số điểm sẽ có \(B = 0\), nửa còn lại sẽ có \(B = 1\).