Quý - ôn tập THT KV B C2 - 13/6

Cho một xâu dài vô hạn chứa tất cả các số nguyên dương theo trình tự tăng dần:

\(12345678910111213141516171819202122232425 \ldots\)

Nhiệm vụ của bạn là xử lí \(q\) truy vấn trả lời cho câu hỏi: số nào nằm ở vị trí thứ \(k\) trong xâu?

Input

• Dòng đầu tiên chứa một số nguyên duy nhất \(q\): số lượng truy vấn.
• Sau đó gồm \(q\) dòng tiếp theo biểu diễn các truy vấn, mỗi dòng là một số nguyên \(k\): vị trí của kí tự cần tìm trong xâu (xâu được đánh số từ \(1\)).

Output

• Với mỗi truy vấn, in ra kết quả tương ứng trên từng dòng.

Constraints

• \(1 \le q \le 1000\)
• \(1 \le k \le 10^{18}\)

Example

Sample input

3
7
19
12

7
4
1

Cho đơn đồ thị vô hướng liên thông \(G = (V,E)\) gồm \(n\) đỉnh và \(m\) cạnh, các đỉnh được đánh số từ \(1\) đến \(n\) và các cạnh được đánh số từ \(1\) đến \(m\).

Biết cây khung của một đồ thị, đó chính là tập \(n\) đỉnh liên thông và tập các cạnh sao cho tổng trọng số của các cạnh là nhỏ nhất có thể.

Hãy tìm cây khung nhỏ nhất của đồ thị \(G\).

Input

• Dòng đầu tiên chứa \(2\) số nguyên dương \(n,m\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) có dạng \(3\) số nguyên \(u, v, c\). Trong đó (\(u,v\)) là chỉ số hai đỉnh đầu mút của cạnh thứ \(i\) và \(c\) trọng số của cạnh đó.

Output

• Gồm \(1\) dòng duy nhất: Ghi tổng trọng số của cây khung nhỏ nhất.

Constraints

• \(1 \leq n \leq 10000; 1 \leq m \leq 15000\)
• \(1 \leq u,v \leq n; 0 \leq c \leq 10000\)

Example

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

5

Cho \(n\) là một số nguyên dương và \(x = (x_1, x_2, ..., x_n)\) là một hoán vị của dãy số \((1, 2, ..., n)\). Với \(\forall i: 1 \le i \le n\), gọi \(t_i\) là số phần tử đứng trước giá trị \(i\) mà lớn hơn \(i\) trong dãy \(x\). Khi đó dãy \(t = (t_1, t_2,..., t_n)\) được gọi là dãy nghịch thế của \(x = (x_1, x_2, ..., x_n)\)

Ví dụ: Với \(n = 6\)

Dãy \(x = (3, 2, 1, 6, 4, 5)\) thì dãy nghịch thế của nó là \(t = (2, 1, 0, 1, 1, 0)\)

Dãy \(x = (1, 2, 3, 4, 5, 6)\) thì dãy nghịch thế của nó là \(t = (0, 0, 0, 0, 0, 0)\)

Dãy \(x = (6, 5, 4, 3, 2, 1)\) thì dãy nghịch thế của nó là \(t = (5, 4, 3, 2, 1, 0)\)

Input

Vào từ file văn bản IVECTOR.INP gồm:

• Dòng 1: Chứa số nguyên dương \(n \le 10^5\)
• Dòng 2: Chứa dãy hoán vị \(x\) gồm \(n\) số \(x_1, x_2, ..., x_n\)
• Dòng 3: Chứa dãy nghịch thế \(t\): gồm \(n\) số \(t_1, t_2,..., t_n\)

Output

Ghi ra file văn bản IVECTOR.OUT gồm:

• Dòng 1: Ghi lần lượt từng phần tử của dãy nghịch thế của \(x\)
• Dòng 2: Ghi lần lượt từng phần tử của dãy hoán vị của \(t\)

Example

6
1 2 3 4 5 6
2 1 0 1 1 0

0 0 0 0 0 0
3 2 1 6 4 5

Tí và Tèo rất thích chơi đùa với những viên ngọc. Hôm nay hai bạn có n viên ngọc trên bàn. Như vạn vật trên đời, mỗi viên ngọc có một vẻ đẹp riêng trong mắt mỗi người. Vì vậy, để giữ tình bạn thân thiết, Tí Tèo quyết định rằng, viên ngọc thứ \(i\) sẽ có vẻ đẹp \(a_i\) đối với Tí và \(b_i\) đối với Tèo. Tí và Tèo bắt đầu trò chơi như sau: hai bạn sẽ thay phiên bốc một viên ngọc trên bàn về phía mình. Sau khi bốc hết ngọc, điểm số của mỗi bạn sẽ là tổng vẻ đẹp các viên ngọc mà bạn đó lấy về phần mình.

Ví dụ nếu Tí bốc các viên 1, 3 và Tèo bốc các viên 2, 4 thì Tí được \(a_1+a_3\) điểm còn Tèo được \(b_2+b_4\) điểm. Mục tiêu của trò chơi là làm cho tổng điểm của mình trừ tổng điểm đối phương càng lớn càng tốt. Nói cách khác, đặt \(X\) là tổng điểm của Tí trừ tổng điểm của Tèo. Tí muốn \(X\) càng lớn càng tốt, còn Tèo muốn \(X\) càng nhỏ càng tốt. Biết rằng Tí đi trước và cả hai đều chơi tối ưu.

Yêu cầu: Hãy tính tổng điểm của Tí trừ tổng điểm của Tèo sau khi trò chơi kết thúc.

Input

• Dòng 1 chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n\).
• Dòng thứ ba chứa \(n\) số nguyên \(b_1,b_2,…,b_n\).

Output

• Ghi ra số nguyên là kết quả bài toán.

Constraints

• \(1\leq n\leq 10^5\)
• \(0\leq a_i\leq 10^9\) với \(1\leq i\leq n\)
• \(0\leq b_i\leq 10^9\) với \(1\leq i\leq n\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(a_i=b_i\) với mọi \(1\leq i\leq n\).
• Subtask \(2\) (\(40\%\) số điểm): \(n\leq 20\).
• Subtask \(3\) (\(20\%\) số điểm): \(n\leq 10^3\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
10 20 30
10 20 30 

20

2
10 20
20 10  

0

4
10 10 10 20
20 20 20 30

-10