anime contest div 1

Hôm nay, những nhân vật thông minh nhất vũ trụ anime như \(Conan, Kira, L, Sakamoto, Armin, ...\) đang tranh giải "Bộ não vàng" do algorit tổ chức. bin9638 cũng là một trong những người tham gia cuộc thi này. Để chiến thắng cuộc thi thì phải giải được bài toán mà algorit đưa ra như sau:

Cho một dãy số nguyên dương \(A_1,A_2,...,A_N\) gồm \(N\) phần tử .

Cho \(Q\) thao tác , mỗi thao tác gồm 2 số nguyên dương \(x\) và \(y\) , thao tác này làm tất cả phần tử đang mang giá trị \(x\) trong mảng chuyển thành giá trị \(y\). Với mỗi thao tác hãy tính tổng tất cả các phần tử của mảng

bin9638 rất muốn trở thành nhân vật thông minh nhất vũ trụ anime nhưng vì những đối thủ của anh quá giỏi nên đành nhờ các bạn giúp đỡ. Hãy giúp cậu ấy nhé !

• Yêu cầu : Sau mỗi thao tác hãy tính lại tổng tất cả các phần tử của mảng .

Input

• Dòng đầu tiên gồm 2 số nguyên dương \(N\) và \(Q\) \(. (N , Q \le 10^6)\)
• Dòng tiếp theo gồm các số nguyên dương \(A_1,A_2,...,A_N\) \(. (A_i \le 10^{12})\)
• \(Q\) dòng tiếp theo gồm 2 số nguyên dương \(x , y\) \(. (x,y \le 10^{12})\)

Output

• Gồm \(Q\) dòng , mỗi dòng là tổng giá trị của mảng .

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N,Q \le 10^3 , A_i \le 10^9.\)*
• Subtask \(2\) (\(30\%\) số điểm): \(N,Q \le 10^5 , A_i \le 10^6.\)*
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm .*

Example

5 3
1 2 3 5 4
1 2
2 3
3 4 

16
18
21

Hôm nay Roronoa Zoro, thợ săn quỷ mạnh nhất đang đến tiki shop để mua nhận luân kiếm cho trận chiến sống còn với chúa quỷ Muzan sắp tới. Khi Zoro tới thì chủ tiệm là algorit đang loay hoay xếp kiếm, algorit mãi chưa xếp xong kiếm nên đành nhờ Zoro giúp xếp hộ kiếm.

Trong tiệm \(N\) thanh kiếm có trọng lượng , độ dài , độ cao lần lượt là \(C_i , W_i , H_i\) , chiều rộng của mỗi thanh kiếm bằng với chiều rộng của tủ kiếm. Trọng lượng và độ dài của mỗi ngăn mà tủ kiếm có thể chứa là \(P\) và \(Q\) .

Bây giờ algorit muốn nhờ Zoro chia \(N\) hộp thành các đoạn liên tiếp để xếp vào ngăn. Biết độ cao của mỗi ngăn là độ cao của thanh kiếm cao nhất trong các hộp đã được xếp vào ngăn. Nếu Zoro giúp được thì algorit sẽ tặng cho anh \(1\) thanh kiếm Trung Quốc hàng xịn, hãy giúp anh ấy nhé !

• Yêu cầu : Hãy tính chiều cao tối thiểu của tủ khi xếp các kiếm vào tủ 1 cách tối ưu .

Input

• Dòng đầu tiên gồm 3 số nguyên dương \(N , P , Q\) . \((N \le 9999, (P,Q) \le 10^{12})\)
• N dòng tiếp theo gồm 3 số nguyên dương \(C_i , W_i , H_i\) . \((C_i \le P,W_i \le Q,H_i \le 10^9)\)

Output

• Gồm 1 số nguyên dương duy nhất là kết quả của bài toán .

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \le 400 , P \le 10^3 , Q \le 10^3 , H_i \le 10^3 .\)
• Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm .*

Example

5 18 16
5 7 3
6 5 4
2 1 9
8 4 2
3 2 3 

12

Sau khi xem xong MV "Ice Cream" của Blackpink, bin9638 và algorit liền đặt ngay vé máy bay sang Hàn Quốc để có thể ăn kem tại quán và nói chuyện với các idol của mình. Lúc bin9638 và algorit tới quán kem "Blackpink" thì đúng lúc quán kem này đang có chương trình phát kem cho các em nhỏ. Cụ thể, có \(n\) đứa trẻ lần lượt có độ tuổi là \(A_1 , A_2 , ... , A_n\) đang đứng trước quán chờ nhận kem, đứa trẻ thứ \(i\) có độ tuổi là \(A_i\) . Chương trình phát kem của Blackpink cũng rất đặc biệt, mỗi đứa trẻ phải có ít nhất \(1\) que kem , khi có \(2\) đứa trẻ đứng gần nhau , đứa trẻ lớn hơn sẽ được phát nhiều kem hơn, nếu \(2\) đứa trẻ cùng tuổi đứng cạnh nhau thì phát tùy ý. Tuy nhiên vì còn phải đi phát kem ở nhiều nơi nữa nên Blackpink muốn số kem được phát là tối thiểu.

Lisa, quản lí của quán kem này biết bin9638 và algorit là những người rất thông minh nên muốn nhờ họ tính giúp số kem tối thiểu cần phát. Nếu tính được thì bin9638 và algorit sẽ được tặng \(2\) que kem, hơn nữa họ còn sẽ được chụp ảnh chung và có được chữ kí của Blackpink nữa đấy. Hãy giúp họ nhé !

Yêu cầu:

• Hãy tìm số lượng kem tối thiểu đề chia cho \(n\) đứa trẻ.

Input:

• Dòng đầu tiên gồm \(1\) số nguyên dương \(n\) . \((n \le 10^6)\)
• Dòng thứ \(2\) là dãy số \(A_1 , A_2 , ... , A_n\) là độ tuổi của nhứng đứa trẻ . \((A_i \le 10^9)\)

Output:

• Dòng đầu tiên gồm một số nguyên dương duy nhất là số lượng kem tối thiểu.
• Dòng thứ \(2\) là dãy \(C_i\) tương ứng với số kem phát cho đứa trẻ thứ \(i\).

Scoring:

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^3\)
• Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm.

Example

5
1 2 1000000000 2 1 

9
1 2 3 2 1 

3
1 2 2 

4
1 2 1 

Uzumaki algorit nổi tiếng là \(1\) ninja nổi tiếng có rất nhiều nhẫn thuật mạnh, không chỉ thế anh còn sở hữu tuyệt kĩ thông não chi thuật mà cho dù kẻ thù mạnh đến thế nào cũng sẽ bị tẩy não. Trận chiến với Madara lần này cũng không phải ngoại lệ, sau khi đã ăn \(1\) rổ hành từ Madara không còn cách nào khác algorit đành phải dùng chiêu thông não chi thuật của mình. Tiếc thay lần này Madara lại là \(1\) kẻ địch rất cứng rắn nên dù có thuyết phục hay tẩy não thế nào cũng không có tác dụng. Trong lúc tưởng chừng như chẳng còn hi vọng nào thì bỗng ông bụt hiện ra, bụt nói nếu algorit giải được bài toán này thì có thể thông não Madara.

Bài toán là Cho dãy số nguyên gôm n phần tử , \(A_1 , A_2 , ... , A_n\).

Chúng ta có thể biến đổi \(k\) lần , với các lần biến đổi là chọn một phần tử của mảng đó tăng lên \(x\) đơn vị hoặc giảm đi \(x\) đơn vị . Hãy biến đổi tối ưu sao cho tích của mảng đạt kết quả lớn nhất .

algorit vì mãi lo nghĩ cho thằng bạn của mình là *Uchiha *bin9638 nên đã quên hết kiến thức toán rồi. Hãy giúp algorit nhé !

Input:

• Dòng đầu tiên gồm \(3\) số nguyên dương \(n , k , x , mod . ( n \le 3*10^5 , k \le 3*10^5 , x \le 10^{12} , mod \le 10^{18}\))
• Dòng thứ hai là dãy số \(A_1 , A_2 , ... , A_n\) . (\(|A_i| \le 10^{12}\))

Output:

• Là một số nguyên duy nhất , là kết quả của bài toán , vì kết quả của bài toán rất lớn nên kết quả sẽ được lấy dư khi chia cho \(mod\).*

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, k, x, |A_i|\) \(\le 10^3\) , \(mod = 10^9 + 7.\)
• Subtask \(2\) (\(20\%\) số điểm): \(n\) và \(k \le 2.10^5 , |A_i|\) và \(x \le 10^9, mod = 10^9 + 7.\)
• Subtask \(3\) (\(60\%\) số điểm): không có ràng buộc gì thêm.

Example

5 1 3 101
2 2 2 2 2

80

Sau khi bị pain hack pay làng thì làng lá hiện đang trong công cuộc xây dựng lại. Hôm nay Uzumaki bin9638, hokage của làng lá và Uchiha algorit, người còn lại cuối cùng của tộc Uchiha đang lên kế hoạch xây dựng lại làng. Ngôi làng gồm \(n\) ngôi nhà được đánh số từ \(1\) tới \(n\) \((n \le 2*10^5)\) và có \(n-1\) con đường nối \(2\) ngôi nhà bất kì sao cho tất của các nhà đều được liên thông với nhau, mỗi con đường sẽ có độ dài \(w\) \((w \le 10^9)\).

Ngôi làng bây giờ có \(q\) \((q \le 2*10^5)\) bộ ba ngôi nhà wibu. Với mỗi bộ ba ngôi nhà này bin9638 và algorit muốn tính giá trị nhỏ nhất của \(wibu(a,x)+wibu(b,x)+wibu(c,x)\) với \(wibu(u,v)\) là khoảng cách để đi từ nhà \(u\) đến nhà \(v\). Ở đây \(x\) là \(1\) ngôi nhà bất kì trong làng.

Input

• Dòng đầu tiên là số \(n\).
• \(n-1\) dòng tiếp theo mỗi dòng là \(3\) số \(u, v, w\) biểu thị có đường nối \(2\) nhà \(u\) và \(v\) với độ dài \(w\).
• Dòng tiếp theo là số \(q\).
• \(q\) dòng tiếp theo là các truy vấn, mỗi truy vấn gồm \(3\) số \(a,b,c\).

Output

• Gồm \(q\) dòng là kết quả cho các truy vấn.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n , q \le 15\)
• Subtask \(2\) (\(30\%\) số điểm): \(n , q \le 1000\)
• Subtask \(3\) (\(40\%\) số điểm): \(n , q \le 2*10^5\)

Example

4
1 2 1
2 3 2
1 4 3
2
1 2 3 
1 2 4 

3
4

Nezuko là \(1\) cô bé xinh đẹp, dễ thương, là em gái quốc dân, crush trong mơ của bao thằng wibu. Hôm nay Nezuko đã khám phá ra số “Wibu”. Số “Wibu” là \(1\) số tự nhiên mà tổng các chữ số nguyên tố cùng nhau với tổng \(wibu\) của các chữ số với \(wibu(i)=\)\(1^2+2^2+…+i^2\) \((0 \leq i \leq 9)\).

Ví dụ số \(20\), có tổng các chữ số là \(2+0=2\) và tổng \(wibu=wibu(2)\)\(+wibu(0)=5\) nguyên tố cùng nhau nên là số “Wibu”. Còn số \(33\) có tổng các chữ số là \(3+3=6\) và tổng \(wibu=wibu(3)\)\(+wibu(3)=28\) không nguyên tố cùng nhau nên không phải.

bin9638 cũng là \(1\) người crush Nezuko lâu năm. Bây giờ bin9638 đang muốn tính tổng các số “Wibu” trong đoạn từ \(l\) đến \(r\) \((l,r \leq 10^{18})\) để lấy le với Nezuko, nhưng khổ nỗi bây giờ bin9638 đang mãi hóng movie mới của Kimetsu No Yaiba nên không có thời gian tính toán. Các bạn hãy giúp bin9638 nhé.

Vì kết quả có thể rất lớn nên các bạn hãy in kết quả chia lấy dư cho \(10^9+7\).

Yêu cầu:

• Tính tổng các số “Wibu” trong đoạn \([l,r]\)

Input

• Dòng đầu tiên là số truy vấn \(q\) \((q ≤ 10^5)\).
• \(q\) dòng tiếp theo mỗi dòng là \(2\) số \(l,r\).

Output

• Gồm \(q\) dòng, mỗi dòng là kết quả cho truy vấn tương ứng.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(l,r \leq 10^6\), \(q ≤ 10\).

• Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm.

Example

2
19 20
1 100

20
3268