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ụ:

Trong Học kỳ I vừa qua, Tý đạt được danh hiệu học sinh giỏi nên được bố thưởng. Biết Tý là học sinh rất đam mê Toán và Tin học nên bố muốn thử thách Tý bằng một trò chơi có thưởng như sau:

            Bố có rất nhiều hộp khối lập phương giống nhau xếp thành một hàng thẳng và được đánh số ký hiệu bằng các số tự nhiên lẻ bắt đầu từ 1; 3; 5; … Trong các hộp đó có duy nhất 1 hộp đựng phần thưởng, các hộp khác là hộp rỗng. Bố cho Tý biết hộp đựng phần thưởng là hộp chính giữa của một đoạn dài nhất (ít nhất là 3 hộp liên tiếp) có tổng các số ký hiệu ghi trên các hộp bằng số m.

            Yêu cầu: Với số m cho trước, hãy tìm số ký hiệu của hộp có chứa phần thưởng.

            Dữ liệu vào: Đọc ở file văn bản THUONG.INP số nguyên dương m (m <= 10¹⁶).

            Dữ liệu ra: Ghi ra file văn bản THUONG.OUT một số k là số ký hiệu của hộp có chứa phần thưởng.

            Ví dụ:

            Giải thích:

            Các hộp được đánh số ký hiệu là 1; 3; 5; 7; 9; 11; 13; 15; 17; 19; 21; 23; 25; …

Cho hai số nguyên dương N và M. Ta sắp xếp N số nguyên dương liên tiếp 1; 2; 3; …; N thành một dãy số gồm có M đoạn liên tiếp như sau: Đoạn thứ nhất gồm tất cả các số chia hết cho M; đoạn thứ hai gồm tất cả các số chia M dư 1; đoạn thứ 3 gồm tất cả các số chia M dư 2; …; đoạn thứ M gồm tất cả các số chia M dư M – 1. Các số trong mỗi đoạn cũng được sắp xếp theo thứ tự tăng dần.

            Yêu cầu: Cho trước 3 số nguyên dương N; M; T. Tìm số thứ T trong dãy sắp thứ tự như trên.

Ví dụ: Với N = 10; M = 4; T = 8. Dãy số được sắp xếp như sau: 4; 8; 1; 5; 9; 2; 6; 10; 3; 7. Số hạng thứ 8 trong dãy trên là 10.

Input: ba số nguyên dương N; M; T nằm trên một dòng (1 < M < N <= 10¹⁶; M <= 10⁶; T <= N), mỗi số.

Output: một số X là số hạng thứ T trong dãy sắp thứ tự như trên.

Input	Output
10 4 8	10

ĐỀ THI HSG TIN HỌC CẤP TỈNH KHÁNH HÒA 2022-2023

THUẬT TOÁN SẮP XẾP QUICK SORT

DÃY CON TĂNG DÀI NHẤT

Cho mảng số nguyên A gồm N phần tử, hãy tìm dãy con (không nhất thiết các phần tử phải liên tiếp) tăng dài nhất của mảng A.

Dữ liệu vào:

·        Dòng đầu tiên là N (1 ≤ N ≤ 1000)

·        Dòng thứ 2 gồm N phần tử của mảng A (1 ≤ A_i ≤ 1000)

Dữ liệu ra:

            In ra độ dài của dãy con tăng dài nhất.

Ví dụ:

 BÀI TOÁN CÁI TÚI

Một tên trộm có 1 cái túi có thể mang các đồ vật với trọng lượng tối đa là V. Hiện tại tên trộm muốn lựa chọn các đồ vật trong N đồ vật để ăn trộm, mỗi đồ vật có trọng lượng là w[i] và có giá trị là v[i]. Hãy xác định tổng giá trị lớn nhất của các đồ vật mà tên trộm này lựa chọn sao cho trọng lượng của chúng không vượt quá V.

Dữ liệu vào:

·                Dòng đầu ghi 2 số N và V (N, V ≤ 1000).

·                Dòng thứ 2 ghi N số của mảng w.

·                Dòng thứ 3 ghi N số của mảng v.

Dữ liệu ra:

            In ra giá trị lớn nhất có thể đạt được.

Ví dụ: