Mô tả:

Cho một tờ giấy hình chữ nhật kích thước ~M \times N~ (đơn vị cm) và một số tự nhiên ~K~.

Yêu cầu:

Nếu cắt những hình vuông có kích thước ~K \times K~ từ tờ giấy này, hãy tính tổng diện tích của phần giấy còn lại (phần giấy không bị cắt).

Dữ liệu vào:

• Gồm ba số tự nhiên ~M, N, K~ lần lượt mỗi số trên một dòng (~1 \leq M, N, K \leq 10^9~).

Kết quả:

• Một số nguyên duy nhất là diện tích còn lại của phần giấy.

Ví dụ:

INP	OUT	GIẢI THÍCH
8 7 3	20	Diện tích còn lại là phần gạch sọc
10 10 5	0

Mô tả:

Cho mạch mã gốc DNA bốn loại nucleotide ~A, T, G, C~. Để tiết kiệm bộ nhớ, mạch mã gốc được nén lại thành một chuỗi ~S~ gồm các cặp là số lần xuất hiện liên tiếp nucleotide và loại nucleotide tương ứng.

• Ví dụ:
  Mạch mã gốc ~AAACATGGGGA~ nên thành ~3A1C2A1T4G1A~.

Các nucleotide ở hai mạch của phân tử DNA liên kết với nhau theo nguyên tắc bổ sung:

• ~A~ liên kết với ~T~.
• ~T~ liên kết với ~A~.
• ~G~ liên kết với ~C~.
• ~C~ liên kết với ~G~.

Nhờ biết trình tự nucleotide trên một mạch có thể suy ra trình tự của mạch còn lại.

• Ví dụ:
  Mạch mã gốc là ~AAAACATGGGGA~.
  Trình tự nucleotide trên mạch bổ sung của đoạn DNA này là: ~TTTTGTACCCCT~.

Yêu cầu:

Cho một chuỗi ký tự ~S~ mô tả mạch mã gốc DNA sau khi đã nén. Hãy lập trình xác định mạch bổ sung của mạch mã gốc sau khi giải nén.

Dữ liệu:

• Một chuỗi ~S~ có độ dài không vượt quá 1000.
• Dữ liệu đảm bảo chuỗi sau khi giải nén có độ dài không vượt quá ~10^5~.

Kết quả:

• Chuỗi ký tự là mạch bổ sung của mạch mã gốc sau khi giải nén.

Ví dụ:

Ràng buộc:

1. 20% số test ứng với 20% số điểm của bài thỏa mãn: độ dài chuỗi ~S~ là 2, trong đó ký tự đầu tiên là chữ số, ký tự thứ hai là một trong 4 chữ cái ~A, T, G, C~.
2. 20% số test khác ứng với 20% số điểm của bài thỏa mãn: có duy nhất một loại nucleotide.
3. 40% số test khác ứng với 40% số điểm của bài thỏa mãn: số lần xuất hiện liên tiếp nucleotide ~A, T, G, C~ nhỏ hơn 10.
4. 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Mô tả:

Nam treo một dãy đèn gồm ~N~ bóng đèn, được đánh số từ 1 đến ~N~, từ trái sang phải. Mỗi bóng đèn có thể hiển thị hai màu: màu vàng hoặc màu đỏ. Nam đã lập trình để điều khiển màu của các bóng đèn. Khi khởi động, tất cả bóng đèn đều màu vàng.

• Chương trình của Nam có ~M~ lệnh, mỗi lệnh tương ứng với một lần gọi mà lệnh của dãy đèn.
• Khi gọi một lệnh với giá trị X, màu của một đoạn từ vị trí ~X-K~ đến ~X+K~ tính từ bóng đèn thứ X sẽ đổi trạng thái từ màu vàng sang màu đỏ, hoặc ngược lại.

Nam muốn kiểm tra màu hiện tại của một bóng đèn sau khi thực hiện chương trình.

Dữ liệu vào:

• Dòng đầu tiên gồm bốn số nguyên dương lần lượt là ~N, M, Q, K~ (~1 \leq N \leq 10^9; 1 \leq M \leq 10^5; 1 \leq Q \leq 10^5; 0 \leq K \leq N~).
• Dòng thứ hai gồm ~M~ số nguyên dương ~X_i~ mô tả tham số của lệnh thứ ~i~ (~1 \leq X_i \leq N~).
• Dòng thứ ba gồm ~Q~ số nguyên dương ~P_i~ mô tả câu hỏi thứ ~i~ (~1 \leq P_i \leq N~).

Kết quả:

• Gồm ~Q~ dòng, mỗi dòng là câu trả lời cho câu hỏi thứ ~i~. Nếu bóng đèn tại vị trí ~P_i~ đang có màu vàng thì ghi ra ký tự ~V~, ngược lại ghi ra ký tự ~D~.

Ràng buộc:

1. 60% số test ứng với 60% số điểm của bài thỏa mãn: ~N, M, Q, K \leq 10^3~.
2. 20% số test khác ứng với 20% số điểm của bài thỏa mãn: ~N, M \leq 10^5~.
3. 20% số test còn lại ứng với 20% số điểm không có ràng buộc bổ sung.

Ví dụ:

Giải thích ví dụ:

Mô tả:

An đi mua ~M~ sản phẩm khác nhau, các sản phẩm được đánh số từ 1 đến ~M~. Ở chợ có ~N~ quầy hàng xếp thành hàng ngang được đánh số từ 1 đến ~N~, từ trái sang phải.
Quầy hàng thứ ~i~ chỉ bán một loại sản phẩm duy nhất là ~A_i~ (~1 \leq A_i \leq M~) và mỗi sản phẩm trong ~M~ sản phẩm luôn tồn tại ít nhất một quầy hàng bán sản phẩm loại đó. Thời gian để An mua sản phẩm tại quầy hàng thứ ~i~ là ~T_i~ phút. Thời gian để di chuyển giữa hai quầy hàng liên kề là 1 phút.

Yêu cầu:

1. An phải mua đủ ~M~ sản phẩm theo đúng thứ tự 1, 2, 3, ..., ~M~.
2. An có thể bắt đầu từ một quầy hàng bất kỳ bán sản phẩm ~1~.
3. Tính tổng thời gian nhỏ nhất để An mua xong tất cả ~M~ sản phẩm.

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên dương ~N, M~ (~1 \leq M \leq N \leq 10^5~).
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~1 \leq A_i \leq M~), mô tả các sản phẩm được bán tại quầy hàng.
• Dòng thứ ba gồm ~N~ số nguyên ~T_1, T_2, ..., T_N~ (~1 \leq T_i \leq 10^9~), mô tả thời gian để mua hàng tại mỗi quầy.

Kết quả:

• Một số nguyên duy nhất là tổng thời gian nhỏ nhất để An mua đủ ~M~ sản phẩm theo yêu cầu đề bài.

Ràng buộc:

1. 10% số test ứng với 10% số điểm của bài thỏa mãn: ~M = 1~.
2. 20% số test khác ứng với 20% số điểm của bài thỏa mãn: ~M = N~.
3. 30% số test khác ứng với 30% số điểm của bài thỏa mãn: ~N \leq 2000~.
4. 30% số test còn lại ứng với 30% số điểm không có ràng buộc bổ sung.

Ví dụ:

Mô tả:

Cho một bảng vuông kích thước ~N \times N~ và ~N~ là số lẻ, là các số tự nhiên từ 1 đến ~N^2~.
Các hàng của bảng được đánh số từ 1 tới ~N~, từ trên xuống dưới; các cột của bảng được đánh số từ 1 tới ~N~, từ trái sang phải. Ban đầu, các số từ 1 đến ~N^2~ được xếp vào bảng lần lượt từ trái sang phải, từ trên xuống dưới. Khi ~N = 5~ thì bảng vuông sẽ có dạng như Hình 1.

Hình 1

Luật chơi:

Có ~Q~ lượt chơi, mỗi lượt chơi quản trò sẽ cấp cho người chơi thông tin là ba số nguyên ~P, X, Y~ (~1 \leq P \leq N^2; 1 \leq X, Y \leq N~).
Người chơi cần đưa số nguyên ~P~ đến vị trí hàng ~X~, cột ~Y~ với số lần dịch bảng nhỏ nhất bằng cách:

1. Dịch cả số trên hàng chứa số ~P~ sang phải hoặc sang trái một ô theo vòng tròn cho đến khi số ~P~ nằm trên cột ~Y~.
2. Dịch cả số trên cột ~Y~ lên trên hoặc xuống dưới một ô theo vòng tròn cho đến khi số ~P~ nằm trên hàng ~X~.

Hình 2

• Lưu ý: Mỗi thao tác dịch hàng hoặc cột trên được tính là một lần dịch bảng.

Yêu cầu:

• Cho thông tin ~Q~ lượt chơi. Hãy lập trình đưa ra số lần dịch bảng nhỏ nhất tìm được tương ứng với mỗi lượt.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên dương ~N, Q~ (~1 \leq N \leq 30000; 1 \leq Q \leq 2000~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~P, X, Y~ (~1 \leq P \leq N^2; 1 \leq X, Y \leq N~), mô tả thông tin của mỗi lượt chơi.

Kết quả:

• Gồm ~Q~ dòng, dòng thứ ~i~ tương ứng là số lần dịch bảng nhỏ nhất để đưa số ~P~ đến vị trí ~X, Y~.

Ví dụ:

INP	OUT	GIẢI THÍCH
5 3 17 2 5 5 4 2 18 1 1	4 2 4	- Lượt 1: Đưa 17 đến hàng 2, cột 5 mất 4 lần dịch (mô tả ở Hình 2). - Lượt 2: Đưa 5 đến hàng 4, cột 2 mất 2 lần dịch. - Lượt 3: Đưa 18 đến hàng 1, cột 1 mất 4 lần dịch.

Ràng buộc:

1. 40% số test ứng với 40% số điểm của bài thỏa mãn: ~N < 100; Q \leq 100~.
2. 40% số test khác ứng với 40% số điểm của bài thỏa mãn: ~N < 1500; Q \leq 1500~.
3. 20% số test còn lại ứng với 20% số điểm không có ràng buộc bổ sung.