Dinh Can's Blog

Nhàn bị mẹ giao cho nhiệm vụ đó là đong gạo để mang lên KTX. Chị được mẹ đưa cho 2 loại xô, là loại 5 kg và 3 kg. Nhàn sẽ phải đong đủ số gạo mà mẹ cho bằng 2 loại xô trên.

        Ví dụ mẹ cho 18 kg thì Nhàn có thể đong bằng 3 xô 5 kg + 1 xô 3 kg hoặc 6 xô 3 kg. Hãy giúp chị ấy đong với số lượng xô ít nhất có thể, nếu không thể đong được, in ra -1.

Input: Dòng duy nhất chứa số N là số gạo mẹ Nhàn cho (0 < N < 5000).

Output: In ra đáp án của bài toán.

Ví dụ:

Hình dưới là cơ cấu của một đường tàu tại một ga xe lửa:

            Ban đầu ở đường ray A có chứa các toa tàu được đánh số thứ tự từ 1 đến n theo thứ tự từ trái qua phải, người ta muốn chuyển các toa đó sang ray C để có được một thứ tự mới là một hoán vị của (1, 2, …, n) theo quy tắc: chỉ chứa được các toa tàu chạy theo đường ray theo hướng mũi tên, có thể dùng đường ray B để lưu tạm các toa tàu trong quá trình di chuyển.

            Cho biết hoán vị cần có, hãy tìm phương án di chuyển ít nhất các toa tàu trên đường ray.

Dữ liệu vào:

-         Dòng 1: Một số nguyên dương n (n <= 10⁵).

-         Dòng 2: n số nguyên là hoán vị của các số từ 1 đến n.

Dữ liệu ra:

-         Nếu không có phương án thì đưa ra thông báo là NO

-         Nếu có phương án thì:

+ Dòng 1 đưa ra thông báo YES

+ Các dòng tiếp theo đưa ra các bước di chuyển ít nhất các toa tàu.

Ví dụ:

Cho 1 dãy sồ gồm N phần tử (N <= 100000), mỗi phần tử có 1 giá trị nằm trong khoảng [-10⁹, 10⁹]. Ban đầu, bạn sẽ ở vị trí ô số 0 với tổng điểm là 0. Mỗi nước đi, người chơi có thể di chuyển sang phải tối thiểu là 1 bước và tối đa là K bước (K <= 100). Khi dừng lại ở 1 ô nào đó thì giá trị của ô đó sẽ được cộng vào tổng điểm. Bạn có thể dừng cuộc chơi bất cứ lúc nào. Hãy tìm cách chơi sao cho tổng điểm nhận được là nhiều nhất.

Dữ liệu nhập:

-         Dòng đầu tiên chứa 2 số N, K.

-         Dòng thứ 2 chứa N số của dãy, mỗi số cách nhau 1 dấu cách.

Kết quả:

-         Số điểm lớn nhất có thể đạt được.

Ví dụ:

Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xóa đi một số ký tự trong xâu Y để được xâu X.

            Cho biết hai xâu ký tự A và B độ dài không quá 2000 ký tự, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B.

Input:

            - Dòng 1: chứa xâu A

            - Dòng 2: chứa xâu B

Output: Chỉ gồm một dòng ghi độ dài xâu C tìm được.

Ví dụ:

Trước công nguyên, nhà quân sự La Mã Julius Ceasar đã nghĩ ra phương pháp mã hóa một bản tin như sau: thay thế mỗi chữ trong bản tin bằng chữ đứng sau nó k vị trí trong bản chữ cái. Giả sử chọn k = 3, ta có bảng chuyển đổi như sau:

            Chữ ban đầu: a b c d e f g h i j k l m n o p q r s t u v w x y z

            Chữ thay thế: d e f g h i j k l m n o p q r s t u v w x y z a b c

            Giả sử bản tin là: 'attack' thi sau khi mã hóa sẽ có bản mã 'dwwdfn' và Ceasar gửi bản mã cho cấp dưới.

            Nhận được bản mã và khóa, cấp dưới của Ceasar chưa biết giải mã làm sao. Bạn hãy giúp họ đi nào.

Dữ liệu vào:

            - Dòng đầu tiên là bản tin đã được mã hóa, chỉ gồm các chữ cái la tinh thường, chiều dài không quá 100 ký tự.

            - Dòng thứ 2 là số nguyên thể hiện khóa k (1 <= k <= 25)

Dữ liệu ra: bản tin ban đầu.

Ví dụ: