Olympic Truyền thống 30/4 2023 - Tin học - Khối 11

Trò chơi ở đây là một đường đua gồm ba dải ô song song mỗi dải có \(n+2\) ô, đều được đánh số từ \(0\) (ở đầu trái) đến \(n+1\) (ở đầu phải).

Ví dụ, Xét hình dưới đây, với \(n=6\):

Các ô từ 1 đến \(n\) của mỗi dải đều có ghi một số nguyên. Mỗi người chơi xuất phát từ ô ở cột \(0\), liên tục tiến về phía trước bằng cách nhảy lò cò (nhảy bằng một chân) theo quy tắc sau đây:

• Nếu đang đứng ở một ô ở dải giữa thì bước tiếp theo sẽ nhảy về phía trước vào một trong hai ô ở dải hai bên.
• Nếu đang đứng ở một ô không phải dải giữa thì bước tiếp theo sẽ nhảy về phía trước vào một ô ở dải giữa.
• Lúc ban đầu đang đứng ở vị trí xuất phát thì có thể nhảy vào ô ở dải nào cũng được.

Lượt chơi kết thúc khi người chơi nhảy vào ô ở cột \(n+1\), là ô cuối cùng của đường đua.

Ngoài ra, nếu đang đứng ở ô \(i\ (i = 0, 1, ..., n)\) thì trong bước tiếp theo, chỉ có thể nhảy vào ô \(j\) sao cho: \(i+1\le j\le i+p\), trong đó \(p\) là một số nguyên dương cho trước không lớn hơn \(n\) (đương nhiên phải có \(j \le n+1\)). \(p\) được gọi là độ dài tối đa của bước nhảy.

Điểm số mà người chơi giành được sau lượt chơi chính là tổng của tất cả các số thuộc các ô mà người chơi đã nhảy vào đó.

Yêu cầu: Xác định điểm số tối đa mà một người chơi có thể đạt được.

Input

• Dòng đầu ghi hai số nguyên \(n\) và \(p\ (2\le n\le 10^5,1\le p\le min(50,n) )\);
• Dòng thứ hai ghi \(n\) số nguyên, lần lượt là các số ghi trên các ô từ đầu trái của dải ô thứ nhất;
• Dòng thứ ba ghi \(n\) số nguyên, lần lượt là các số ghi trên các ô từ đầu trái của dải ô thứ hai (dải ở giữa).
• Dòng thứ tư ghi \(n\) số nguyên, lần lượt là các số ghi trên các ô từ đầu trái của dải ô thứ ba.
• Tất cả các số ghi trên các ô nói trên đều có giá trị tuyệt đối không lớn hơn \(10 000\).

Output

• Ghi ra một số nguyên, là điểm số tối đa tìm được.

Scoring

• \(30\%\) số test ứng với \(30\%\) số điểm của bài này có \(1 ≤n<20\) và \(p≤4\);
• \(20\%\) số test ứng với \(20\%\) số điểm của bài này có \(20<n<50\);
• \(50\%\) số test ứng với \(50\%\) số điểm của bài này thỏa yêu cầu đề bài.

Example

63 
3 -4 -5 5 10 2 
6 2-3 -2 1 -1 
-2 13 1 0 7 4 

27 

Cho một đồ thị vô hướng \(A\) có \(N\) đỉnh và \(M\) cạnh. Dựa vào đồ thị \(A\) cho trước, một đồ thị \(B\) cũng có \(N\) đỉnh và \(N \times (N-1)/2 − M\) cạnh được định nghĩ như sau: với hai đỉnh \(u\) và \(v\) bất kỳ, nếu không có cạnh nối giữa chúng trong đồ thị \(A\) thì sẽ có cạnh nối giữa \(u\) và \(v\) trong đồ thị \(B\).

Yêu cầu: Hãy cho biết số lượng thành phần liên thông có trong \(B\).

Input

• Dòng đầu tiên chứa số nguyên \(T\) cho biết số lượng test có trong bài. Mỗi test bao gồm:
  • Dòng đầu chứa 2 số nguyên \(N\) và \(M\) được mô tả trong đề bài.
  • \(M\) dòng tiếp theo mỗi dòng chứa 2 số nguyên \(u\) và \(v\ (1 \le u, v \le N)\) cho biết có cạnh nối giữa hai đỉnh \(u\) và \(v\).

Output

• Với mỗi test:
  • Dòng đầu là một số nguyên cho biết số lượng thành phần liên thông có trong test đó.
  • Dòng thứ 2 in ra độ lớn của từng thành phần liên thông theo thứ tự tăng dần.

Scoring

• \(1 \le T \le 100\); \(1 \le N \le 2 \times 10^5\); \(1 \le M\le min (N\times (N-1)/2,2\times 10^5)\); Tổng của \(N\) và \(M\) trong các test \(\le 2\times 10^5\)
• \(20\%\) có \(T = 10\) và \(N \le 20\);
• \(20\%\) số test ứng với \(20\%\) số điểm có \(T = 20\) và \(N \le 100\);
• \(20\%\) số test ứng với \(20\%\) số điểm có \(T = 100\) và \(N \le 100\);
• \(40\%\) còn lại số test ứng với \(40\%\) số điểm có \(T = 100\) và \(N\) như giới hạn bên trên

Example

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

2
2 2
1
3 

CMô hình giá là một trong những công cụ yêu thích của những nhà đầu tư (NĐT). Bằng việc theo dõi giá giao dịch của một mặt hàng trong một khoảng thời gian, NĐT có thể tìm thấy một mô hình giá được lặp lại trong những thời điểm khác nhau để từ đó có những quyết định đầu tư hợp lý. Một mô hình giá H có chiều dài \(N\) được cho bởi một hoán vị \((H_1, H_2, \dots H_N)\) của tập các số \({1, 2, N}\). Các giao dịch này được đánh số thứ tự từ 1 đến \(N\), hoán vị trên cho biết trong \(N\) giao dịch liên tiếp thì các mức so sánh giá giao dịch lần lượt là \(H_1, H_2, ..., H_N\). Mức giá giao dịch thấp nhất là 1, tiếp đến là 2, và mức giá giao dịch cao nhất là \(N\). Khi xét \(N\) giao dịch \(A\) liên tiếp bất kỳ, ta nói mô hình giá \(H\) được lặp lại nếu so sánh giá giao dịch tại phiên thứ \(i\) và \(j\) là \(A_i < A_j\) khi và chỉ khi (tương đương với) \(H_i < H_j\) với mọi \(i, j\) trong khoảng \([1..N]\).

Yêu cầu: Cho trước \(M\) phiên giao dịch, các giao dịch này được đánh số từ 1 đến \(M\), và một mô hình giá có chiều dài \(N\). Hãy viết một chương trình cho biết mô hình giá trên được lặp lại bao nhiêu lần và vị trí những lần đó trong M giao dịch.

Input

• Dòng đầu là hai số nguyên \(N\) và \(M\) cho biết chiều dài của mô hình giá và số phiên giao dịch đang xét.
• Dòng thứ hai chứa \(N\) số nguyên \(H_i\) là một hoán vị của tập các số \({1, 2, 3, ..., N}\), trong đó \(1\le H \le N\) và \(H_i \neq Hj\) với mọi \(i, j\).
• Dòng thứ ba chứa \(M\) số nguyên \(G_i\ (1≤ G_i ≤ 10^9)\) lần lượt là giá giao dịch trong \(M\) phiên. Để thuận lợi trong thống kế, bạn có thể giả sử các số \(G_i\) luôn khác nhau.

Output

• Dòng đầu là một số nguyên \(D\) cho biết số lần mô hình giá được lặp lại.
• Dòng thứ hai chứa \(D\) số nguyên là chỉ số các phiên giao dịch đầu tiên khi mô hình giá lặp lại, các chỉ số này được sắp tăng dần. Nếu \(D = 0\) thì dòng thứ hai không xuất gì.

Scoring

• \(20\%\) test ứng với \(20\%\) số điểm của bài có \(1 <N\le 100\) và \(1 <M\le 1000\);
• \(30\%\) test ứng với \(30\%\) số điểm của bài có \(1<N\le 5000\) và \(1<M\le 20 000\);
• \(50\%\) test ứng với \(50\%\) số điểm của bài có \(1 <N, M ≤ 1 000 000\).

Example

6 12 
2 5 3 4 1 6 
10 45 25 30 5 47 31 35 4 50 33 20 

2
1 5