Thi thử Tin học trẻ Khu vực bảng A - ngày 01

Trò chơi Bang! là board game quá quen thuộc đối với nhóm bạn của Nhật. Trong ván đấu sẽ có \(3\) phe: cảnh sát, kẻ cướp và kẻ phản bội. Mục tiêu của cảnh sát là giết hết kẻ cướp và phản bội, mục tiêu của kẻ cướp là giết cảnh sát trưởng, còn của kẻ phản bội là người sống sót cuối cùng.

Mỗi người chơi đều có những lá bài để chiến đấu, và lá Bang! là lá tấn công cơ bản. Trong đó, lá bài Đấu súng có lẽ là lá bài khiến lá Bang! trở nên mạnh nhất.
Giả sử người chơi A ra lá Đấu súng để thách đấu người chơi B, hai người sẽ lần lượt đấu súng như sau:

• Đầu tiên, nếu B không có lá Bang!, B thua và cuộc đấu súng dừng ngay lập tức. Ngược lại, người B sẽ phải đưa ra một lá Bang!
• Tiếp theo, nếu A không có là Bang!, A thua và cuộc đấu súng dừng ngay lập tức. Ngược lại, người A sẽ phải đưa ra một lá Bang!
• Tương tự cuộc đấu súng tiếp tục tới lượt của B, A, B, A, ... cho tới khi một trong hai người chơi không thể đưa ra lá Bang!.

Bàn chơi hiện tại có \(n\) người chơi, với người chơi thứ \(i\) có \(a_i\) lá Bang!. Có \(T\) sự kiện, mỗi sự kiện gồm hai số \(u, v\), đại diện cho việc người chơi thứ \(u\) thách đấu người chơi thứ \(v\). Hai người sẽ đấu theo đúng quy tắc luân phiên như trên tới khi một trong hai không còn lá Bang! để ra.

Hỏi sau \(T\) sự kiện, mỗi người chơi còn bao nhiêu lá Bang! trong tay?

Chú ý: Việc thua trong cuộc đấu Đấu súng chỉ ảnh hưởng tới việc tiêu hao lá Bang! trong tay; kết quả mạng sống (thua, thắng) không ảnh hưởng đến lượt chơi tiếp theo và mọi người chơi đều tiếp tục tham gia đầy đủ các sự kiện.

Input

• Dòng đầu tiên chứa số tự nhiên \(n\) \((1 \leq n \leq 2 \times 10^5)\).
• Dòng thứ hai chứa dãy số tự nhiên \(a\) \((1 \leq a_i \leq 10^9)\) gồm \(n\) phần tử cách nhau bằng dấu cách.
• Dòng thứ ba số \(T\) \((1 \leq t \leq 2 \times 10^5)\).
• \(T\) dòng tiếp theo, dòng thứ \(i\) gồm hai số \(u_i, v_i\).

Output

• In ra một dòng là dãy số tự nhiên \(a\).

Scoring

• \(50\%\) số điểm có \(t \leq 1000\) và \(a_i \leq 100\).
• \(50\%\) số điểm không có rằng buộc gì thêm.

Example

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

0 0 0 1 3

Dựa trên một câu chuyện có thật?

Trong kì thi tuyển sinh, Nhật là một trong những thí sinh tiêu biểu tham gia kì thi. Không may, do quá chủ quan, mà Nhật đã trượt chuyên Lê Quý Đôn, với điểm môn chuyên là \(2,88\) - một con số cực kì tệ. May thay, nhờ khối tài sản lên đến hàng tỉ Zimbabwe và quan hệ rộng, Nhật đã nhờ được một hacker, xâm nhập vào hệ thống trường, xóa tường lửa để thực hiện mưu đồ đen tối.

Sau khi sửa danh sách, Nhật muốn độ đẹp trai của danh sách là lớn nhất. Danh sách điểm của \(N\) thí sinh được biểu diễn thành bảng \(a\) gồm \(N\) hàng và \(4\) cột, hàng thứ \(i\) gồm 4 ô điểm \(a_{i,1}, a_{i,2}, a_{i,3}, a_{i,4}\) ứng với điểm 4 môn từ trái sang phải là Toán, Văn, Anh và Tin của thí sinh thứ \(i\). Hacker có vô hạn thao tác; với mỗi thao tác, hắn có thể chọn hai số trong cùng một hàng hoặc một cột và đổi chỗ.

Điểm tuyển sinh của mỗi thí sinh được tính như sau: Toán \(+\) Văn \(+\) Anh \(+\) \(3\) \(\times\) Tin. Biết rằng độ đẹp trai của danh sách là tổng điểm tuyển sinh của \(N\) thí sinh, hỏi độ đẹp trai lớn nhất của danh sách là bao nhiêu?

Input

• Dòng đầu tiên chứa số tự nhiên \(n\) \((1 \leq n \leq 2 \times 10^5)\).
• \(N\) dòng tiếp theo, với dòng thứ \(i\) gồm bốn số tự nhiên \(a_{i,1}, a_{i,2}, a_{i,3}, a_{i,4}\) \((1 \leq a_{i, j} \leq 10^9)\).

Output

• In ra một dòng là độ đẹp trai lớn nhất của danh sách.

Scoring

• \(25\%\) số điểm có \(n = 1\).
• \(50\%\) số điểm có \(n \leq 3\).
• \(25\%\) số điểm không có rằng buộc gì thêm.

Example

2
10 1 1 1
1 1 9 1

63

Vào sáng ngày \(24/06/2025\), khi các bạn học sinh được giải Nhất bảng \(B\) thành phố Đà Nẵng đang nghe giảng, thì bùm một cái, con quái vật với thân hình là Tung Tung Tung Sahur, tự xưng là người hơn Nguyễn Nhân Danh thêm một chữ k đã tấn công vào trụ sở. Nhận thấy điềm chẳng lành, anh Hiếu đang dạy đã vội vã dùng thuật toán để tìm đường đi ngắn nhất chạy thoát, các học sinh khác cũng đã chạy trốn, chỉ còn lại mình Sĩ Quý với thuật toán tham lam mà không tìm được đường ra. May thay, Quý đã nhận ra được quy luật.

Con đường chạy thoát của Quý được biểu diễn dưới một mảng \(A\) gồm \(n\) số tự nhiên, với \(A_i\) là độ cao của tòa nhà thứ \(i\). Con quái vật có thể chọn một đoạn con liên tiếp từ \(l\) đến \(r\) có độ dài từ \(2\) trở lên, và biến tất cả các tòa nhà trong đó thành chênh lệch độ cao giữa \(A_l\) và \(A_r\). Mục tiêu của con quái vật là biến tất cả các tòa nhà sao cho tổng độ cao là lớn nhất. Nhận được tin, mọi người cố gắng tìm ra đáp án để giải cứu Quý. Bạn là một trong những giải Nhất bảng \(B\) (tương lai), hãy cố gắng tìm ra tổng mảng \(A\) lớn nhất.

Input

• Dòng đầu tiên chứa số tự nhiên \(n\) \((2 \leq n \leq 2 \times 10^5)\).
• Dòng thứ hai chứa dãy số tự nhiên \(A\) \((1 \leq A_i \leq 10^9)\) gồm \(n\) phần tử cách nhau bằng dấu cách.

Output

• In ra một dòng là tổng mảng \(A\) lớn nhất.

Scoring

• \(20\%\) số điểm có \(n=2\).
• \(20\%\) số điểm có \(n=3\).
• \(30\%\) số điểm có \(n \leq 10^3\)
• \(30\%\) số điểm không có ràng buộc gì thêm

Example

3
3 5 9

27

Elon Musk mua lại Twitter vào năm \(2022\) và đổi tên thành \(\mathbb{X}\).
Việc đầu tiên ông làm là mã hóa dữ liệu, và để mã hóa thì ông cần tạo ra các khóa có dạng của một số \(\mathbb{X}\).

Số \(\mathbb{X}\) là một số tự nhiên có ít nhất \(2\) chữ số, với chữ số hàng đơn vị lớn hơn hẳn các chữ số còn lại. VD: \(13\), \(102\) là số \(\mathbb{X}\), còn \(53\) và \(202\) thì không phải.

Cho hai số \(L\) và \(R\), hỏi có bao nhiêu số \(\mathbb{X}\) nằm trong khoảng từ \(L\) tới \(R\)?

Input

• Dòng đầu tiên chứa số tự nhiên \(L\).
• Dòng thứ hai chứa số tự nhiên \(R\) \((1 \leq L \leq R \leq 10^{18})\).

Output

• In ra một dòng số lượng số \(\mathbb{X}\) nằm trong khoảng từ \(L\) tới \(R\).

Scoring

• \(30\%\) số điểm có \(r \leq 1\ 000\ 000\).
• \(40\%\) số điểm có \(L=1; R = 10^K\) với \(1 \leq K \leq 18\).
• \(30\%\) số điểm không có ràng buộc gì thêm.

Example

55
105

14