NAP Champion Contest div 1+2

ami có \(n\) món đồ chơi. Món đồ chơi thứ \(i\) có màu \(c[i]\). Hôm nay, khi đem kho đồ chơi ra ngắm thì ami phát hiện thấy thiếu mất \(m\) món. Hãy tìm màu sắc của \(m\) món đồ chơi bị mất đó.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m \ (3 \leq n \leq 10^5, 1 \leq m \leq 2)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(c[i] \ (1 \leq c[i] \leq 10^5)\). Lưu ý, có thể có nhiều món đồ chơi có cùng màu
• Dòng thứ ba chứa \((n - m)\) số nguyên dương, là màu của các món đồ không bị mất.

Output

• In ra \(m\) số nguyên theo thứ tự tăng dần, là màu các món đồ chơi bị mất.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 100, m = 1\)
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 10^5, m = 1\)
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 100, m = 2\)
• Subtask \(4\) (\(25\%\) số điểm): \(n \leq 10^5, m = 2\)

Example

3 1
1 3 2
1 2

3

4 2
2 2 2 4
2 4

2 2

3 2
1 2 3
2

1 3

ami có một mảng \(a\) gồm \(n\) phần tử \(a_1\), \(a_2\), ..., \(a_n\). Hai dãy số \(a\) và \(b\) được gọi là giống nhau nếu nó thoả cả hai điều kiện sau

• Các số trong dãy \(a\) đều xuất hiện trong dãy \(b\).
• Các số trong dãy \(b\) đều xuất hiện trong dãy \(a\).

Ví dụ, dãy [1 2 3 4] và dãy [1 1 2 3 4 4] là giống nhau, còn dãy [5 12 2001] và [18 12 2001] là khác nhau.

Các bạn cần tìm một đoạn con chuẩn dài nhất của mảng \(a\) mà đoạn con đó giống với dãy \(a\).

Một đoạn con của \(a\) được gọi là chuẩn nếu nó có độ dài nhỏ hơn độ dài của \(a\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) là số phần tử trong mảng \(a\).

• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_i\) là một phần tử của mảng \(a\).

Output

• Hãy in ra độ dài đoạn con chuẩn dài nhất của \(a\) mà đoạn con này giống với dãy \(a\). Nếu không tồn tại đoạn con nào, các bạn cần in ra -1.

Scoring

Trong tất cả các test, \(1 \leq a_i \leq 1000\).

• Subtask \(1\) (\(50\%\) số điểm): \(1 \leq n \leq 100\).

• Subtask \(2\) (\(50\%\) số điểm): \(1 \leq n \leq 1000\).

Example

3
?2 3 6 

-1

2
?2 2 

1

Có \(n\) lá bài được đánh số từ \(1\) tới \(n\). Cho biết thứ tự ban đầu các lá bài trong bộ bài, bạn cần thực hiện \(q\) thao tác. Mỗi thao tác gồm hai số \(u, v\): hãy đổi vị trí của lá bài mang số \(u\) và lá bài mang số \(v\). Hãy in ra thứ tự các lá bài sau khi hoàn thành \(q\) thao tác.

Ví dụ, vị trí ban đầu các lá bài là \([1, 3, 2, 5, 4]\). Cần thực hiện hai thao tác \((1, 2)\) và \((2, 3)\).

• Sau thao tác \((1, 2)\), hai lá bài \(1\) và \(2\) bị tráo đổi vị trí. Vị trí các lá bài là \([2, 3, 1, 5, 4]\).
• Sau thao tác \((2, 3)\), hai lá bài \(2\) và \(3\) bị tráo. Thứ tự cuối cùng là \([3, 2, 1, 5, 4]\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n, q \ (1 \leq n, q \leq 2 \times 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a[i]\) là thứ tự ban đầu các lá bài. Biết rằng \(1 \leq a[i] \leq n\) và không có hai số nào bằng nhau.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v \ (1 \leq u, v \leq n, u \neq v)\) biểu thị một thao tác.

Output

In ra \(n\) số là thứ tự cuối cùng của các lá bài.

Ví dụ

Sample Input

5 2
1 3 2 5 4
1 2
2 3

Sample Output

3 2 1 5 4

Giới hạn

• Có \(30\%\) số điểm tương ứng với \(n, q \leq 200\).
• Có \(30\%\) số điểm tiếp theo tương ứng với \(n, q \leq 2000\).
• \(40 \%\) số điểm còn lại không có điều kiện gì thêm

Hằng đẳng thức đáng nhớ đã quá quen thuộc rồi. Hãy để sư phụ ami giới thiệu cho các bạn hằng đẳng thức đáng quên.

ami có một dãy số \(a\) gồm \(n\) phần tử \(a_1\), \(a_2\), ..., \(a_n\). Hẳng đẳng thức đáng quên của dãy số trên được tính bằng công thức sau:

\(A = \sum |i - j|\), với tất cả các cặp \(i \leq j\) và \(a_i\) = \(a_j\).

Nói cách khác, \(A\) là tổng khoảng cách các vị trí \((i, j)\) mà \(a_i = a_j\).

Các bạn cần tính hằng đẳng thức này như một bài tập về nhà.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) là số phần tử trong mảng \(a\).

• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_i\) là một phần tử của mảng \(a\).

Output

• Hãy in ra kết quả của hằng đẳng thức đáng quên.

Scoring

• Trong tất cả các test, \(1 \leq a_i \leq n\).

• Subtask \(1\) (\(25\%\) số điểm): \(1 \leq n \leq 100\).

• Subtask \(2\) (\(25\%\) số điểm): \(1 \leq n \leq 1000\).

• Subtask \(3\) (\(50\%\) số điểm): \(1 \leq n \leq 10^5\).

Example

3
 2 3 1

0

4
 2 1 2 1

4

Cho một mảng \(A\) gồm \(n\) số nguyên khác nhau. Tìm số lượng bộ ba "hòa hợp" được tạo nên từ mảng \(A\).

Biết rằng, một bộ ba \((a,b,c)\) được gọi là "hòa hợp" nếu chúng khác nhau từng đôi một và thỏa mãn \(1\) trong \(2\) điều kiện sau:

• \(a,b,c\) nguyên tố cùng nhau từng đôi một

• \(a,b,c\) không nguyên tố cùng nhau từng đôi một

(Hai bộ \(A\) và \(B\) được coi là khác nhau nếu tồn tại phần tử \(k\) thỏa mãn \(k\in A\) và \(k\notin B\))

Ghi chú: Hai số \(x,y\) được coi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng là \(1\)

Input

• Dòng thứ nhất chứa số nguyên \(T(1\le T\le 15)\) - số lượng testcase.

• \(T\) block tiếp theo, mỗi block có dạng:

• Dòng thứ nhất chứa số nguyên \(n(3\le n\le 1000)\)

• Dòng thứ hai chứa số \(n\) số nguyên \(a_1,a_2,..,a_n(2\le a_i<10^5)\) khác nhau

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1\le n\le 20\)

• Subtask \(2\) (\(60\%\) số điểm): Còn lại

Example

2
3
2 3 6
3
2 3 5

0
1

• Cho hai số nguyên dương \(n\) và \(m\).

Ma trận \(A\) được gọi là ma trận "ảo diệu" nếu ma trận \(A\) thỏa mãn các điều kiện sau:

• Ma trận \(A\) gồm \(2^{n}\) hàng và \(2^{m}\) cột.

• Ta sắp xếp các số từ \(0\) đến \(2^{n+m}-1\) vào các ô của ma trận \(A\) sao cho hai số ở \(2\) ô kề nhau khác nhau đúng \(1\) bit trong biểu diễn nhị phân

(Hai ô được xem là kề nhau nếu chúng có chung \(1\) cạnh chung). Và đặc biệt ma trận này là ma trận tuần hoàn, tức là ứng với mỗi hàng, ô bên trái nhất và ô bên phải nhất kề nhau, và ứng với mỗi cột, ô trên cùng nhất và ô dưới cùng nhất kề nhau.

Yêu cầu: Cho hai số \(n,m\). Xuất ra ma trận "ảo diệu"

Input

• Một dòng duy nhất chứa hai số nguyên dương \(n,m(n+m\le 20)\)

Output

• In ra đáp án cần tìm. (Nếu có nhiều đáp án, in ra một đáp án bất kì, ngược lại nếu không có đáp án nào thỏa mãn, in ra "Happy New Year")

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m = 1\) hoặc \(n = 1\)

• Subtask \(2\) (\(20\%\) số điểm): \(m+n\le 5\)

• Subtask \(3\) (\(60\%\) số điểm): Còn lại

Example

1 1

0 1 
2 3

Cho mảng \(A\) gồm \(n\) phần tử và ta có một phép toán như sau:

• Cùng một lúc ta có thể chọn nhiều cặp khác nhau và hoán đổi vị trí chúng cho nhau (Biết rằng các cặp này không được giao nhau).

Hỏi ta cần thực hiện ít nhất bao nhiêu phép toán trên để dãy đã cho không giảm.

Input

• Dòng thứ nhất chứa số nguyên \(n(1\le n\le 1000)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1\le a_i\le 10^9)\)

Output

• Dòng thứ nhất chứa số \(k\) - số phép toán tối thiểu cần dùng

• \(k\) dòng tiếp theo, mỗi dòng in ra có dạng như sau: \(p\text{ }i_1\text{ }j_1 \text{ }i_2\text{ }j_2...i_p\text{ }j_p\). Trong đó \(p\) là số cặp ta chọn để hoán đổi vị trí, tiếp theo là \(p\) cặp \((i_u,j_u)(1\le u\le p;i_u\ne j_u)\) thể hiện chỉ số của cặp cần hoán đổi vị trí cho nhau. (Chú ý: Hai cặp chỉ số \(A,B\) gọi là giao nhau nếu tồn tại số \(k\) thỏa mãn \(k\in A\) và \(k\in B\)). Nếu có nhiều đáp án, in ra đáp án bất kì.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1\le n\le 10\)

• Subtask \(1\) (\(60\%\) số điểm): Còn lại

Example

3
1 3 2 

1
1 2 3