Đề thi học sinh giỏi lớp 9 THCS tỉnh Vĩnh Phúc năm 2013 môn Tin học

Tổng quan về đề thi

Lập chương trình giải các bài toán sau:

Bài 1. TIỀN XU

Bờm có rất nhiều đồng tiền xu, chúng có một trong hai mệnh giá: đồng hoặc đồng. Việc bảo quản tiền xu rất phiền phức, vì vậy, Bờm muốn tiêu hết chúng thật nhanh. Cụ thể hơn, mỗi khi mua một món hàng giá trị đồng, Bờm muốn chỉ thanh toán bằng tiền xu và sử dụng cách dùng nhiều đồng xu nhất.

Chẳng hạn, nếu Bờm có hai loại tiền xu mệnh giá 3 đồng và 5 đồng, khi phải thanh toán lượng tiền 32 đồng, Bờm có hai cách trả: cách thứ nhất sử dụng 9 xu mệnh giá 3 đồng và 1 xu mệnh giá 5 đồng, cách còn lại sử dụng 4 xu mệnh giá 3 đồng và 4 xu mệnh giá 5 đồng. Cách thứ nhất sẽ được Bờm lựa chọn vì giúp Bờm tiêu nhiều đồng xu hơn.

Cho A, B, C. hãy xác định số đồng xu nhiều nhất có thể sử dụng để thanh toán chính xác số tiền đồng hoặc chỉ ra rằng không có cách thanh toán chỉ sử dụng hai loại đồng xu mệnh giá A, B.

Dữ liệu (COINS.INP)

- Dòng 1: ba số nguyên A, B, C(1 ≤ A, B ≤ 5000; 1 ≤ C ≤ 10⁶).

Kết quả (COINS.OUT)

- Dòng 1: số nguyên là số đồng xu nhiều nhất có thể sử dụng để thanh toán, số này bằng −1 nếu không có cách thanh toán.

Bài 2. BẬC ĐỐI XỨNG

Xâu đối xứng là xâu đọc từ trái qua phải giống như đọc từ phải qua trái, chẳng hạn các xâu ′abba ′, ′madam ′ là các xâu đối xứng.

Người ta định nghĩa bậc đối xứng của xâu S, kí hiệu deg(S), như sau:

- Nếu S không phải là xâu đối xứng hoặc S có độ dài bằng 1 thì bậc đối xứng của S bằng 0 (viết là: deg(S) = 0)

- Nếu là xâu đối xứng có độ dài lớn hơn 1, giả sử S = S1S2…SN (N > 1), thì bậc đối xứng của S được tính theo công thức: deg(S) = 1 + deg(T), trong đó xâu T là nửa trái của S theo nghĩa: T = S1S2 …Sk với k = (N + 1) div 2.

Chẳng hạn:
- deg(′x') = 0 vì ′x′ có độ dài bằng 1
- deg(′x0′) = 0 vì ′x0′ không đối xứng
- deg(′x0x' ) = 1 vì deg(′x0x′) = 1 + deg(′x0′)
- deg(′x0xx0x') = 2 vì deg('x0xx0x ′) = 1 + deg(′ x0x')

Cho xâu độ dài không vượt quá 200 chỉ gồm các chữ cái Latin in thường, hãy xác định bậc đối xứng của .

Dữ liệu (PALINDEG.INP)

- Dòng 1: xâu S

Kết quả (PALINDEG.OUT)

- Dòng 1: số nguyên là bậc đối xứng của xâu S.

Bài 3. DÃY CON

Cho dãy số nguyên A = (a1, a2, … , aN) và số nguyên dương M. Hãy tìm cách xóa bỏ trong dãy A một số phần tử sao cho dãy con thu được có nhiều phần tử nhất đồng thời trong dãy con này không có hai phần tử nào có tổng chia hết cho M.

Chẳng hạn, với N = 5, M = 3, A = (1, 2,3,4,5), dãy con dài nhất thu được có độ dài 3, có 4 dãy con như vậy, đó là (1,2,3); (1,3,4); (2,3,5); (3,4,5).

Dữ liệu (CONFLICT.INP)

- Dòng 1: hai số nguyên N, M (1 ≤ N ≤ 10 ; 2 ≤ M ≤ 10⁵)

- Dòng 2: số nguyên a1, a2, … , aN (|ai| ≤ 10 ∀i = 1 ÷ N).

Kết quả (CONFLICT.OUT)

- Dòng 1: số nguyên K là số phần tử của dãy con thu được,

- Dòng 2: K số nguyên là chỉ số trong dãy ban đầu của các phần tử dãy con thu được, các số đưa ra theo trật tự tăng. Nếu có nhiều cách xóa cho dãy con độ dài K hỏa mãn yêu cầu bài toán thì chỉ cần đưa ra một cách.