USACO 2023 - Tháng 2 - Hạng Vàng

FJ đưa cho Bessie một mảng \(a\) có độ dài \(N(2\le N \le 500, -10^{15}\le a_i\le10^{15})\) với tất cả \(\frac{N*(N+1)}{2}\) dãy con liên tiếp đều có tổng đôi một khác nhau. Với mỗi chỉ số \(i\in[1,N]\) , hãy giúp Bessie tính lượng tối thiểu cần thay đổi với \(a_i\) sao cho có hai dãy con liền tiếp khác nhau có tổng bằng nhau.

Input

• Dòng đầu tiên chứa số \(N\).
• Dòng tiếp theo chứa \(a_1,a_2,...,a_N\)

Output

\(N\) dòng, dòng thứ \(i\) chứa lượng tối thiểu cần thay đổi với \(a_i\).

Scoring

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

Example

2
2 -3

2
3        

3
3 -10 4    

1
6
1

Có \(N\) đồng cỏ \((2\leq N\leq2*10^5)\), được nối với nhau bởi \(N-1\) con đường, sao cho chúng tạo thành một cây. Mỗi con đường mất \(1\) giây để vượt qua. Mỗi đồng cỏ ban đầu không có cỏ và cỏ của đồng cỏ thứ \(i\) phát triển với tốc độ \(a_i(1\leq a_i\leq10^8)\) đơn vị mỗi giây. Lúc đầu, nông dân John ở đồng cỏ 1 và cần phải lái xe vòng quanh để bón phân cho cỏ ở mọi đồng cỏ. Nếu anh ta đến thăm một đồng cỏ có \(x\) đơn vị cỏ thì sẽ cần \(x\) lượng phân bón. Đồng cỏ chỉ cần được bón phân trong lần đầu tiên đến và việc bón phân không mất thời gian.

Đầu vào chứa tham số \(T\in{0,1}\):

• Nếu \(T=0\), nông dân John phải kết thúc ở đồng cỏ \(1\).
• Nếu \(T=1\), nông dân John có thể kết thúc ở bất kỳ đồng cỏ nào.

Tính thời gian tối thiểu cần thiết để bón phân cho tất cả đồng cỏ và lượng phân bón tối thiểu cần với khoảng thời gian đó.

Input

• Dòng đầu tiên chứa số \(N\) và \(T\).
• Với mỗi dòng \(i\) từ \(2\) đến \(N\), có hai số \(p_i\) và \(a_i\) miêu tả một con đường. Đảm bảo rằng \(1 \leq p_i < i\).

Output

Lượng thời gian tối thiểu và lượng phân bón tối thiểu, cách nhau bằng khoảng trống.

Scoring

• Subtask \(1\): \(T=0\)
• Subtask \(2\): \(T=1\)
• Subtask \(3\): Không có đồng cỏ nào nối với hơn \(3\) con đường.

Example

5 0
1 1
1 2
3 1
3 4

8 21      

5 1
1 1
1 2
3 1
3 4    

6 29

Nông dân John viết \(N(1 \leq N\leq300)\) chữ số lên một vài mảnh giấy. Với mỗi \(i\in[1,N]\), mảnh giấy thứ \(i\) chứa chữ số \(a_i\) \((1\leq a_i \leq 9)\).

Những con bò có hai số nguyên yêu thích \(A\) và \(B (1\leq A\leq B<10^{18} )\) và muốn bạn trả lời \(Q\) truy vấn \((1\leq Q\leq5*10^4)\). Đối với truy vấn thứ i, đám bò sẽ đi qua các mảnh giấy \(l_i…r_i (1\leq l_i\leq r_i\leq N )\) từ trái sang phải, duy trì một chồng giấy. Đối với mỗi mảnh giấy, chúng sẽ thêm nó vào đầu chồng, vào cuối chồng hoặc không thêm vào. Cuối cùng, chúng sẽ đọc các mảnh giấy trong chồng từ trên xuống dưới, tạo thành một số nguyên. Trên tất cả \(3^{r_i−l_i+1}\) cách để chúng đưa ra lựa chọn, hãy đếm số cách tạo ra số nằm trong đoạn \([A,B]\) in ra số này với \(modulo\) \(10^9+7\).

Input

• Dòng đầu tiên chứa ba số \(N\), \(A\) và \(B\).
• Dòng thứ hai chứa \(a_1,a_2,..,a_N\).
• Dòng thứ ba chứa số \(Q\) - số truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i\) và \(r_i\).

Output

In ra kết quả mỗi truy vấn trên \(1\) dòng.

Scoring

• Subtask \(1\): \(B < 100\)
• Subtask \(2\): \(A=B\)
• Subtask \(3\): Không có điều kiện gì thêm.

Example

5 13 327
1 2 3 4 5
3
1 2
1 3
2 5

2
18
34