anime contest div 2

Trong một chuyến đi tuần tra cổng thành Maria của đội trinh sát, cả đội bống thấy một lổ thủng lớn ở cổng thành (không biết do con quái vật nào phá) khiến cho các titan từ ngoài tràn vào bên trong cổng thành đe doạ tính mạng của các cư dân. Nhưng may mắn thay ở gần đó không có làng nào sinh sống cả. Và đội đã bịt được lổ hổng bằng khả năng hóa cứng của Eren. Mikasa khi trèo lên cổng Maria nhìn xuống đã đếm được số các titan tràn vào trong. Nhiệm vụ của các thành viên của đội trinh sát là giết được hết các titan trong khi đợi chi viện. Cho cách để giết được \(1\) con titan bạn phải đâm vào gáy nó sâu ít nhất \(1.5mm\), sau mỗi lần đâm bạn mất \(1\) lưỡi dao. Được biết mỗi con dao có \(8\) lưỡi dao và mỗi thành viên đều mang theo \(4\) con dao, thêm nữa là các bộ cơ động \(3d\) đã được bơm khí đầy đủ.

Yêu cầu: Bạn được cho một số \(N\) và \(M\) lần lượt là số lượng con titan và số lượng thành viên có trong đoàn trinh sát đó. Hãy tính xem liệu với các thành viên đó thì số lượng các titan tràn vào có được tiêu diệt hết không.

Input

• Dòng thứ nhất là \(T\) số lượng testcase.
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(N,M\) là số lượng titan và số các thành viên trong đội trinh sát.

Output

• Nếu với số lượng các thành viên hiện có mà giết được hết bọn titan thì in ra “YES” còn không thì in ra “NO”..

Constraints

• \(1 \leq T \leq 10^5\)
• \(1 \leq N,M \leq 10^{18}\)

Example

2
12 4 
150 4 

YES
NO

bin9638 là trưởng dòng họ Joseph đồng thời là người sở hữu tất cả stand mạnh nhất thế giới như: The World, Platinum, Gold Experience Requiem, King Crimson,... Hôm nay anh có \(1\) trận chiến với kẻ địch của mình là Muzan Kibutsuji để giải cứu em gái anh là Nezuko. Để giải cứu Nezuko thì anh phải tiêu diệt \(n\) kẻ địch \((n≤10^5)\), kẻ địch thứ \(i (i ≤ n)\) đứng ở vị trí nguyên dương \(A_i (1≤ A_i ≤ 10^9)\). bin9638 cũng đồng thời sở hữu \(m\) stand \((m ≤ 10^5 )\), stand thứ \(i(i ≤ m)\) có phạm vi tấn công là \(B_i\) và mức độ tiêu tốn chakra là \(C_i\) \((1≤ B_i, C_i ≤ 10^9)\). Mỗi lần tấn công stand thứ \(i\) sẽ có thể tiêu diệt \(1\) kẻ thù trong phạm vi \(B_i\) và tiêu tốn \(C_i\) chakra. bin9638 luôn đứng cố định ở vị trí \(0\).

bin9638 muốn tiêu diệt hết kẻ thù sao cho lượng chakra tiêu tốn là ít nhất, khổ nỗi cậu ấy không biết nên sử dụng stand thế nào cho hợp lí. Hãy giúp bin9638 nhé !

Yêu cầu:

• tính lượng chakra tối thiểu để tiêu diệt kẻ địch.

Input:

• Dòng đầu tiên lần lượt là \(2\) số \(n\) và \(m\).
• Dòng thứ \(2\) là dãy \(A\).
• \(m\) dòng tiếp theo mỗi dòng gồm hai số là \(B_i\) và \(C_i\) tương ứng.

Output:

• \(1\) số duy nhất là kết quả, nếu không thể tiêu diệt hết kẻ địch thì in ra "bin9638 da mat Nezuko".

Scoring

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

Example

4 2
1 2 3 4 
5 5
3 1

8

4 1
1 2 3 10 
9 1

bin9638 da mat Nezuko

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