Cho một khu đất vàng có kích thước n×n mét, được chia thành từng ô đất cạnh 1×1 gồm n hàng n cột, các hàng được đánh số từ 1 tới n từ trên xuống dưới, các cột được đánh số từ 1 tới n từ trái qua phải.

Nhằm cổ vũ phong trào công nghệ thông tin, ban tổ chức cuộc thi Khoa học kỹ thuật quốc gia đã quyết định thưởng cho đội vô địch một phần của khu đất vàng theo quy tắc sau:

• Đội vô địch chọn một ô ở hàng x, cột y.
• Ban tổ chức kẻ 2 đường chéo đi qua ô [x,y] trên bản đồ khu đất. Từ 2 đường chéo đi qua ô [x,y] ban đầu sẽ tạo được 2 hình chữ nhật nằm trong khu đất hình vuông. Mỗi hình chữ nhật nhận một đường chéo là một cạnh của hình chữ nhật.
• Toàn bộ ô đất được bao phủ trong 2 hình chữ nhật chéo sẽ thuộc về đội vô địch.

Yêu cầu: Cho kích cỡ của khu đất được sử dụng để trao giải và vị trí ô đất mà đội vô địch đã lựa chọn. Tính diện tích đất đội vô địch nhận được.

Dữ liệu: Vào từ file văn bản AREA.INP: Một dòng duy nhất chứa 3 số nguyên dương n,x,y (x,y≤n≤〖10〗^18)

Kết quả: Ghi ra file văn bản AREA.OUT gồm một dòng duy nhất chứa 1 số nguyên dương là diện tích đất thưởng cho đội vô địch cuộc thi. Ví dụ:

AREA.INP AREA.OUT 9 3 6 51

Giới hạn:

• Có 50% số test có n≤1000.
• 50% số test còn lại không có ràng buộc gì thêm.

Tài liệu tham khảo

Cho dãy n số nguyên $a_i$ và q truy vấn có dạng x, l như sau:

• Cộng $a_x$ lên $l^2$ đơn vị, cộng $a_{(}x+1)$ lên $(l-1{)}^2$ đơn vị, …, cộng $a_{(}x+l-1)$ lên $1^2$ đơn vị.

Ví dụ: dãy số [1,0,-2,5,4] sau truy vấn {2,3} sẽ trở thành [1,9,2,6,4].

Yêu cầu: Cho dãy số nguyên và q truy vấn. Tìm ra dãy số sau khi thực hiện toàn bộ q truy vấn.

Dữ liệu: Vào từ file văn bản SQUARE.INP:

• Dòng đầu tiên chứa 2 số nguyên dương n,q (n,q≤${10}^6$).
• Dòng thứ hai chứa n số nguyên $a_i$ ($|a_i|\le {10}^9$).
• q dòng sau, dóng thứ i chứa 2 số nguyên dương x, l (x+l-1≤n) đại diện truy vấn thứ i.

Kết quả: Ghi ra file văn bản SQUARE.OUT: Một dòng duy nhất chứa n số nguyên là dãy số sau khi biến đổi qua q truy vấn.

Ví dụ: SQUARE.INP

5 3
1 0 -2 5 4
2 3
3 1
3 3

SQUARE.OUT

1 9 12 10 5

Ràng buộc:

• Có 20% số điểm của bài với n,q≤1000
• Có 40% số test có n,q≤10^5
• Số test còn lại không có giới hạn gì thêm.

Tài liệu tham khảo

Một cửa hàng tạp hoá có bán n loại sản phẩm, sản phẩm thứ i có giá tiền là $a_i$. Cửa hàng đưa ra một phương án khuyến mãi mua sắm cho các khách hàng như sau:

• Chương trình áp dụng khi mua toàn bộ n sản phẩm.
• Cứ mỗi k sản phẩm liên tiếp (từ sản phẩm thứ i tới sản phẩm thứ i+k-1), khách hàng sẽ được miễn phí đúng x sản phẩm (nghĩa là cứ mỗi k sản phẩm liên tiếp trên thứ tự danh sách, khách hàng cần trả tiền cho đúng k-x sản phẩm).

Yêu cầu: Hãy tìm ra số tiền ít nhất cần phải sử dụng để mua toàn bộ n sản phẩm 1 lần theo chương trình khuyến mãi.

Dữ liệu: Vào từ file văn bản SHOP.INP:

• Dòng đầu tiên chứa 3 số nguyên dương n,k,x (1≤x≤k≤n,n≤2000,k≤20,x≤5).
• Dòng thứ hai chứa n số nguyên dương $a_i$ ($a_i\le {10}^9$) là giá trị của các sản phẩm.

Kết quả: Ghi ra file văn bản SHOP.OUT:

• Một dòng duy nhất chứa 1 số nguyên dương là số tiền nhỏ nhất để mua hàng.

Ví dụ:

SHOP.INP

5 3 1
3 1 4 2 2

SHOP.OUT

7

Giải thích:

Khách hàng chỉ cần trả tiền sản phẩm 2, 3 và 5, được miễn phí sản phẩm 1, 4 (Trong 3 sản phẩm từ 1-3, chỉ trả tiền 2 sản phẩm là 2 và 3, từ 2-4 chỉ trả tiền cho 2 và 3, từ 3-5 chỉ trả tiền cho 3 và 5). Tổng tiền là 1 + 4 + 2 = 7.

Ràng buộc:

• Có 20% số điểm của bài với n≤20
• Có 40% số test có k≤10
• Số test còn lại không có giới hạn gì thêm.

Tài liệu tham khảo

Domino là một trò chơi sắp đặt các miếng gỗ hình chữ nhật có số ở 2 đầu liên tiếp với nhau sao cho 2 đầu nối tiếp của các miếng domino phải bằng nhau (tương tự như trò chơi nối chữ).

Trong trò chơi lần này, các miếng domino sẽ được ghi số từ 1 tới 9 ở mỗi đầu thay vì từ 1 tới 6 như phiên bản phổ thông. Bạn cần xác định xem với n miếng domino cho trước liệu có thể ghép tất cả chúng lại thành một đường thẳng hay không.

Yêu cầu: Cho n miếng domino, xác định khả năng nối toàn bộ n miếng thành một đường thẳng và tìm ra cách ghép nối có thứ tự từ điển nhỏ nhất có thể.

Dữ liệu: Vào từ file văn bản DOMINO.INP:

• Dòng đầu chứa số nguyên dương n (n≤10^5) - số miếng domino.
• n dòng tiếp theo, mỗi dòng chứa hai số nguyên x và y (1≤x≠y≤9) mô tả 2 đầu của 1 miếng domino.

Kết quả: Ghi ra file văn bản DOMINO.OUT:

• Dòng đầu ghi ra YES nếu có thể nối được n miếng domino, ngược lại in ra NO.
• Nếu có thể nối domino, dòng thứ hai in ra dãy domino nối được với thứ tự từ điển nhỏ nhất.

Ví dụ: DOMINO.INP

3
1 2
3 1
4 5

DOMINO.OUT

NO

Ví dụ 2:

DOMINO.INP

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

DOMINO.OUT

YES

Giải thích: ghép 31 12 21 12 23 34

Ràng buộc:

• Có 20% số test có n≤20
• Có 30% số test có n≤ 1000
• Có 50% số test không có giới hạn gì thêm.

Tài liệu tham khảo