Cho dãy số nguyên ~A~ gồm ~n~ phần tử ~a_1, a_2, \dots, a_n~. Một dãy chỉ số ~1 \le i_1 < i_2 < \dots < i_k \le n~ mà ~a_{i_1} < a_{i_2} < \dots < a_{i_k}~, khi đó ~a_{i_1} < a_{i_2} < \dots < a_{i_k}~ được gọi là một dãy con tăng của ~A~. Hãy tìm độ dài dãy con tăng dài nhất của ~A~.

Input

• Dòng đầu ghi số nguyên dương ~n~ ~(n \le 1000)~.
• Dòng hai ghi dãy số nguyên ~A~ ~(|A_i| \le 10^9)~.

Output

• Một số nguyên là độ dài dãy con tăng đơn điệu dài nhất.

Sample Input 1

6
1 2 5 4 6 2

Sample Output 1

4

Sample Input 2

10
1 2 3 4 9 10 5 6 7 8

Sample Output 2

8

Đề bài

Trong các giờ thực hành môn Tin học, các học sinh rất thích sử dụng máy tính để chơi game. Tuy nhiên, trong quy định về môn học thì học sinh lại không được phép. Hôm nay, trong giờ thực hành Tin học về lập trình, thầy giáo đã đưa ra một trò chơi để cho học sinh được giải trí và cũng là để học tập.

Trò chơi có tên là "Bắn đĩa bay". Với trò chơi này, trước khi vào vị trí bắn, người chơi được cho quan sát ~N~ đĩa, trên mỗi đĩa ghi một số nguyên dương tương ứng với điểm có được nếu người chơi bắn trúng.

Súng để bắn đĩa là loại súng thể thao có hai nòng, tại mỗi thời điểm có thể nạp được tối đa ~2~ viên đạn, mỗi lần bóp cò chỉ bắn ra ~1~ viên đạn. Sau khi bắn ~1~ viên đạn hoặc bắn hết ~2~ viên đạn, người chơi có thể nạp lại đạn.

Như vậy, khi hệ thống phóng đĩa hoạt động, người chơi chỉ bắn được tối đa hai đĩa gần nhau rồi phải thực hiện thao tác nạp đạn trước khi muốn bắn tiếp. Biết rằng mỗi lần nạp đầy đạn thì sẽ có một đĩa đã bay qua tầm ngắm và người chơi không thể bắn được đĩa này.

Bạn là một người chơi, giả sử tỉ lệ bắn trúng đĩa của bạn là ~100%~. Hãy chọn một số đĩa để bắn sao cho tổng điểm thu được là lớn nhất.

Input

Vào từ tệp văn bản GAME.INP:

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~).
• Dòng thứ hai chứa ~N~ số nguyên ~a_i~ (~1 \leq a_i \leq 10^9~), là số điểm ghi trên các đĩa.

Output

Đưa ra tệp văn bản GAME.OUT một số nguyên là tổng điểm lớn nhất mà người chơi có thể đạt được.

Ví dụ

Sample Input

4
9 3 5 4

Sample Output

18

Giới hạn

• ~1 \leq N \leq 10^6~
• ~1 \leq a_i \leq 10^9~

Ghi chú

• Có ~40%~ số test tương ứng với ~40%~ số điểm của bài có ~1 \leq N \leq 20~.

Nguồn: đề thi trong file PDF (trang 2–3).

Mời thành công Loli trong việc về nhà, ông già lại tiếp tục đánh đố Loli bằng một câu hỏi khác. Lần này liên quan tới số Fibonacci. Ông già cần Loli tìm ra số fibonacci thứ ~N~ khi chia dư cho ~1770136969~.

Số Fibonacci là dãy số mà phần tử này là tổng của hai phần tử trước đó. VD: ~0, 1, 1, 2, 3, 5, 8, 13, 21, \dots~

Input:

• Gồm một dòng duy nhất chứa số nguyên ~N~ ~(1 \le N \le 10^6)~.

Output:

• Gồm một dòng duy nhất là kết quả của bài toán.

Sample Input 1

4

Sample Output 1

5

Sample Input 2

6

Sample Output 2

13

Yên Bái tổ chức hội chợ nông sản. Dọc đại lộ Nguyễn Thái Học, ban tổ chức đã xây dựng ~m~ gian hàng liền nhau đánh số lần lượt ~1, 2, \dots, m~. Tuy nhiên chỉ có ~n~ gian hàng trong số chúng được thuê. Gian hàng thứ ~i~ được thuê có số hiệu ~x_i~. Không có hai gian hàng được thuê có cùng số hiệu.

Để tiết kiệm chi phí, ban tổ chức chỉ che mưa cho những gian hàng được thuê bằng những tấm bạt. Một tấm bạt phủ được từ gian hàng số hiệu ~u~ đến gian hàng số hiệu ~v~ ~(u \le v)~ được coi là có kích thước ~v-u+1~. Giá của một tấm bạt kích thước ~w~ là ~C_w~. Chú ý rằng những tấm bạt kích thước lớn hơn không nhất thiết phải đắt hơn những tấm bạt kích thước nhỏ hơn.

Hãy giúp ban tổ chức tính số tiền ít nhất để có thể mua bạt che tất cả các gian hàng được thuê. Chú ý rằng trong phương án tối ưu các tấm bạt có thể phủ chồng lên nhau ở một số gian hàng.

Input:

• Vào từ file văn bản MARKET.INP:
• Dòng đầu ghi hai số nguyên dương ~n,\ m~ ~(1\le n\le5000,\ 1\le m\le10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~x_1,\ x_2,\ldots,x_n\ \ (1\le x_i\le m,\ x_i\neq x_j\ \forall i\neq j)~.
• Dòng thứ ba chứa m số nguyên ~C_1,C_2,\ldots,C_m\ \ (1\le C_i\le10^6)~ là giá của những tấm bạt kích thước ~1, 2, \dots, m~.

Output:

• Ghi ra file văn bản MARKET.OUT một số nguyên duy nhất là chi phí nhỏ nhất tìm được.

Sample Input 1

6 12
1 2 11 8 4 12 
2 3 4 4 8 9 15 16 17 18 19 19

Sample Output 1

9

Giải thích

Bờm và những chiếc ly

Bờm có N ly với vô hạn thể tích, và mỗi ly chứa một ít nước. Bờm muốn uống hết toàn bộ lượng nước, nhưng anh ấy không muốn uống từ quá K ly. Bờm có thể đổ hết nước từ ly này sang ly khác. Tuy nhiên, cần cân nhắc trong việc chọn ly, bởi vì không phải ly nào cũng cách Bờm cùng khoảng cách. Chính xác hơn, thời gian để đổ nước từ ly được đánh dấu i vào ly được đánh dấu j là Cij. Hãy giúp Bờm tìm một cách đổ nước vào ly sao cho tổng thời gian là ít nhất có thể.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên dương N, K ~(1 ≤ K ≤ N ≤ 20)~.
• N dòng tiếp theo, mỗi dòng chứa N số nguyên dương ~Cij~ ~(0 ≤ Cij ≤ 10^5)~.
• Dòng thứ i, cột thứ j chứa giá trị ~Cij~. Đảm bảo ~Cii~ = 0.

Kết quả:

• In ra tổng thời gian ít nhất có thể.

Ví dụ:

WATER.INP:

3 3
0 1 1
1 0 1
1 1 0

WATER.OUT:

0

WATER.INP:

3 2
0 1 1
1 0 1
1 1 0

WATER.OUT:

1

WATER.INP:

5 2
0 5 4 3 2
7 0 4 4 4
3 3 0 1 2
4 3 1 0 5
4 5 5 5 0

WATER.OUT:

5

Giải thích:

Với test cuối, để Bờm đạt được tổng thời gian là 5, anh ấy cần đổ:

• Từ ly 4 vào ly 3 (thời gian 1)
• Từ ly 3 vào ly 5 (thời gian 2)
• Từ ly 1 vào ly 5 (thời gian 2)

Tổng cộng: 1 + 2 + 2 = 5

Chú ý:

• 40% số test có N ≤ 10

Có ~N~ lá bài ~(3 ≤ N ≤ 100)~, trên mỗi lá bài ghi một số nguyên dương không vượt quá ~1000~. Các quân bài được xếp thành một chồng. Người ta lần lượt rút các lá bài bên trong chồng bài (tức là trừ lá bài trên cùng và dưới cùng), mỗi lần rút một quân cho đến khi chỉ còn lại lá trên cùng và dưới cùng. Chi phí rút một lá bài là tích ba số ghi ở lá bài trên lá được rút, lá bài dưới lá được rút và số ghi trên lá bài được rút. Khi rút hết ~N-2~ lá bài, ta có tổng chi phí rút bài. Mỗi trình tự rút bài sẽ có một tổng chi phí.

Ví dụ, ~N=5~ và số ghi trên các lá bài là ~10 1 50 20 5~. Nếu lần lượt rút các lá bài có các số ~1~, ~20~ và ~50~, thì tổng chi phí là:

~10*1*50 + 50*20*5 + 10*50*5 = 500 + 5000 + 2500 = 8000~

Còn nếu rút các lá với số 50, 20 và 1 thì tổng chi phí sẽ là:

~1*50*20 + 1*20*5 + 10*1*5 = 1000 + 100 + 50 = 1150~

Yêu cầu: Hãy tính tổng chi phí nhỏ nhất khi rút hết N-2 lá bài.

Input:

Dòng đầu tiên ghi số ~N~.

Dòng thứ hai ghi ~N~ số ~A_1, A_2, ..., A_n~ là các số ghi trên lá bài.

Output:

Tổng chi phí nhỏ nhất tìm được.

Sample Input 1

5
10 1 50 20 5

Sample Output 1

1150

Sample Input

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

Sample Output

4
3 4 5 6

Sample Input

123456781234
567812345678

Sample Output

56781234

Sample Input

6
2
6
5
1
7
3

Sample Output

21 4
2
3
5
6

HD sáng tạo ra một phương pháp nén dữ liệu mới như sau:

• Cho dãy ~N~ phần tử bằng ~1~.
• Sử dụng các chữ số từ ~1~ đến ~A~ để nén dãy phần tử ban đầu sao cho tổng các phần tử sau khi nén bằng ~N~.

Ví dụ: Với ~N = 5, A = 3~ ta có thể các cách nén như sau: ~(1,1,1,1,1)~ thành ~(1,2,1,1); (1,2,2); (2,1,2); (3; 2); \dots~.

Yêu cầu: Cho ~N~ và ~A~. Hãy đếm số cách nén khác nhau?

Input:

Vào từ file văn bản COMPRESS.INP:

• Một dòng duy nhất chứa ~2~ số nguyên ~N~ và ~A~ ~(1 ≤ A ≤ N ≤ 50)~.

Output:

Ghi ra file văn bản COMPRESS.OUT:

• Một số duy nhất là số cách nén khác nhau.

Ví dụ:

COMPRESS.INP

2 1

COMPRESS.OUT

1

Câu 2. (6,0 điểm) Việc làm

Một cơ quan XYZ muốn sắp xếp lại các vị trí việc làm để tăng hiệu quả lao động. Có N vị trí việc làm cần phải sắp xếp lại cho phù hợp, biết hiệu suất của cán bộ thứ i mà làm ở vị trí thứ j là ~a[i,j]~. Hãy sắp xếp N cán bộ vào N vị trí sao cho đạt hiệu quả lao động cao nhất cho toàn cơ quan.

Dữ liệu vào: Từ tập văn bản "VIECLAM.INP" gồm:

• Dòng 1: Số nguyên dương ~N~ ~(N ≤ 20)~.
• N dòng sau, mỗi dòng ghi ~N~ số nguyên ~a[i,j]~ ~(0 < a[i,j] < 1000)~ là hiệu suất của cán bộ thứ i làm việc ở vị trí j.

Kết quả: Ghi ra tập văn bản "VIECLAM.OUT" gồm:

• Một số duy nhất là tổng hiệu suất cao nhất đạt được.

Ví dụ:

VIECLAM.INP:

4
5 2 7 4
8 3 1 6
2 9 5 3
7 1 2 9

VIECLAM.OUT:

33

Giải thích:

Người 1 ở vị trí 3, hiệu suất 7 Người 2 ở vị trí 1, hiệu suất 8 Người 3 ở vị trí 2, hiệu suất 9 Người 4 ở vị trí 4, hiệu suất 9 Tổng hiệu suất: 33.

Đề bài

Cho một lưới ô vuông kích thước ~N \times N~ (~0 < N < 1000~). Tại một ô bất kỳ trên lưới, chỉ có thể di chuyển sang phải một ô hoặc đi xuống dưới một ô. Hãy tìm đường đi có tổng lớn nhất từ ô ~(1,1)~ đến ô ~(N,N)~.

Input

Từ tệp văn bản "MAXSUM.INP" gồm nhiều dòng:

• Dòng 1: Ghi số nguyên dương ~N~ là kích thước của lưới ô vuông (~0 < N < 1000~).
• ~N~ dòng tiếp theo, mỗi dòng ghi ~N~ số nguyên ~a[i,j]~ (~|a[i,j]| < 100~).

Output

Ghi ra tệp văn bản "MAXSUM.OUT" gồm:

• Một số duy nhất là tổng lớn nhất trên đường đi tìm được.

Ví dụ

Sample Input

5
2 7 2 6 5
7 1 8 1 4
4 9 3 6 4
1 1 9 5 2
9 5 2 6 1

Sample Output

46

Ghi chú (nếu có)

Giải thích: Đường đi ~(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3) \to (4,3) \to (4,4) \to (5,4) \to (5,5)~, có tổng lớn nhất là ~46~.

Hai đội Bình Minh và Rạng Đông thi đấu. Mỗi khi một đội ghi điểm, các cầu thủ đội còn lại phải chống đẩy số lần đúng bằng số điểm hiện tại của đội đối phương. Ví dụ, lần đầu đội Bình Minh ghi ~7~ điểm, đội Rạng Đông chống đẩy ~7~ lần. Lần thứ hai ghi ~3~ điểm (được tổng ~10~ điểm), đội Rạng Đông phải chống đẩy ~10~ lần. Tương tự, đội Bình Minh ghi tiếp ~2~ điểm, đội Rạng Đông chống đẩy tiếp ~12~ lần. Tổng số lần chống đẩy trong trường hợp này là ~7+10+12=29~.

An là một thành viên ở đội Rạng Đông. An đếm được mình đã chống đẩy tất cả ~N~ lần. Hỏi số điểm tối đa đội Bình Minh đã ghi được là bao nhiêu?

Input:

Vào từ file văn bản "PUSHUPS.INP":

• Dòng đầu chứa hai số nguyên dương ~N,\ M\ (N\le5000,\ \ M\le10)~ với ~N~ - số lần An chống đẩy trong trận đấu, ~M~ – số cách ghi điểm mà đội Bình Minh có thể thực hiện.
• Dòng thứ hai chứa ~M~ số nguyên dương ~S_i\ (S_i\le20)~ là số điểm tương ứng mà đội Bình Minh có thể ghi theo ~M~ cách tương ứng. Mỗi cách ghi điểm có thể thực hiện nhiều lần.

Output:

Ghi ra file văn bản "PUSHUPS.OUT" một số nguyên duy nhất là số điểm tối đa mà đội Bình Minh đã ghi được. Ghi ra ~-1~ nếu không tìm ra cách ghi điểm thỏa mãn trong trường hợp An nhớ nhầm.

Sample Input 1

29 3
7 2 3

Sample Output 1

14

Giải thích

• Số điểm lần lượt ghi là ~3, 2, 2, 7~. Số lần chống đẩy ~3+5+7+14=29~.

Alice và Bob chơi trò bốc xu từ tháp được xây dựng bởi ~N~ đồng xu. Hai bạn chọn hai số nguyên dương khác nhau ~K~ và ~L~. Hai người lần lượt đi. Alice di trước. Mỗi người, khi đến lượt mình, được bốc khỏi tháp ~1~, ~K~ hoặc ~L~ xu. Ai bốc được đồng xu (hoặc các đồng xu) cuối cùng là thắng. Sau rất nhiều lần chơi, Alice nhận thấy rằng có những trường hợp mình chắc chắn thắng không phụ thuộc vào cách đi của Bob, ngược lại, có trường hợp dù đi thế nào Bob vẫn thắng. Trước ván chơi mới Alice nóng lòng muốn biết mình có thắng được hay không.

Yêu cầu: Cho ~N~, ~K~ và ~L~. Hãy xác định Alice hay Bob sẽ thắng.

Input:

Vào từ file văn bản "COINS.INP":

• Dòng đầu tiên chứa 3 số nguyên ~K~, ~L~ và ~m~, trong đó ~m~ – số ván chơi ~(1 < K < L < 10, 3 < m < 50)~,
• Dòng thứ 2 chứa ~m~ số nguyên ~N_1, N_2, \dots, N_m~, trong đó ~N_i~ – số xu trong tháp ở ván chơi thứ ~i\ (1 \le N_i \le 10^6,\ i \in [1;m])~.

Output:

Ghi ra file văn bản "COINS.OUT" xâu ~m~ ký tự, ký tự thứ ~i~ là 'A' nếu Alice thắng được và bằng 'B' nếu Bob thắng.

Sample Input 1

2 3 5
3 12 113 25717 88888

Sample Output 1

ABAAB

Có ~n~ khách hàng đang xếp hàng gửi tiền vào ngân hàng ~X~. Số tiền mà mỗi khách hàng muốn gửi lần lượt là ~a_1, a_2, \dots, a_n~. Với mỗi người gửi tiền, thư ký ngân hàng phải tốn thời gian là ~1~ phút để hoàn tất thủ tục hồ sơ. Các khách hàng rất bận và họ chỉ có thể chờ trong một khoảng thời gian nào đó mà thôi, sau khoảng thời gian đó họ sẽ đi và không gửi tiền nữa. Thời gian mà các khách hàng có thể chờ lần lượt là ~t_1, t_2, \dots, t_n~ (tính theo phút). Chủ ngân hàng rất là tham lam, ông ta luôn muốn làm sao để có được nhiều tiền gửi nhất. Bạn hãy giúp thư ký lựa chọn thứ tự gửi tiền của các khách hàng sao cho số tiền ngân hàng có được là nhiều nhất (có thể phải chấp nhận từ chối một số khách hàng để đạt được mục đích).

Input:

Vào từ file văn bản "BANK.INP":

• Dòng thứ nhất là số nguyên ~n\ (1 \le n \le 10^4)~.
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~a_i~ và ~t_i\ (1 \le a_i \le 10^5,\ 0 \le t_i \le 1000)~.

Output:

Ghi ra file văn bản "BANK.OUT" một số nguyên xác định tổng số tiền nhiều nhất có thể thu được.

Sample Input 1

4
10 1
20 2
5 2
12 0

Sample Output 1

42

Sample Input 2

3
10 0
20 1
5 1

Sample Output 2

30

Subtasks

• 60% số test có ~n \le 20,\ 0 \le t_i \le 100~.
• 40% số test còn lại không có ràng buộc gì thêm.

Sau khi mua một nùi truyện segg về, Loli cần phải cất giữ chúng ở trong một kệ sách. Kệ sách nhà Loli có ~n~ vị trí để đựng sách, các vị trí được đánh số lần lượt từ ~1~ tới ~n~. Ban đầu sẽ không có sách trên kệ. Mỗi ngày, Loli sẽ thực hiện một số thay đổi trên kệ sách. Có ~4~ hành động Loli có thể làm:

• ~1\ x~: Đặt một cuốn sách vào vị trí thứ ~x~. Nếu đã có sách ở vị trí ~x~ từ trước, giữ nguyên.
• ~2\ x~: Lấy cuốn sách (nếu có) ở vị trí thứ ~x~ ra.
• ~3~: Đảo ngược trạng thái trên kệ. Những vị trí có sách sẽ được lấy ra, và những vị trí không có sách sẽ được thêm sách vào.
• ~4\ x~: Đưa kệ sách trở về quá khứ, trạng thái kệ sách y hệt như ngày thứ ~x~. Nếu ~x=0~, thì trạng thái sẽ là ban đầu – tức là khi chưa có sách.

Sau mỗi ngày Loli muốn biết có bao nhiêu sách trên kệ. Bạn hãy code giúp Loli nhé!

Input:

Lấy từ tệp SHELF.INP gồm:

• Dòng đầu tiên chứa số nguyên ~n\ (1\le n\le4000)~ – số vị trí trong kệ sách.
• Dòng tiếp theo chứa số nguyên ~q\ (1\le q\le5\times10^5)~ – số ngày cần tính.
• ~q~ dòng cuối cùng chứa các hành động trong ~q~ ngày theo quy ước phía trên.

Output:

Ghi ra tệp SHELF.OUT:

• Gồm ~q~ dòng, mỗi dòng chứa một số thể hiện số sách trên kệ vào ngày đó.

Sample Input 1

4
4
1 1
3
2 4
4 0

Sample Output 1

1
3
2
0

Ràng buộc

• 30% số test có ~q\le10^3~.
• 30% số test có ~n\le150~.
• 40% số test không có ràng buộc gì thêm.