Đây là 2 bài khá hay và cũng có nhiều điểm tương đồng, tuy nhiên không phải giống hoàn toàn đâu nhé hì hì !
Bài 1
Một bộ bài được cho bởi N đống, mỗi đống chứa một số quân bài. Xem hình 1. Các đống được ký hiệu từ 1 đến N. Ta định nghĩa một nước đi khi nói p và chỉ ra số m. Khi đó m quân bài sẽ được chuyển từ đống p sang tất cả các đống hàng xóm. Đống p có hai hàng xóm là p-1 và p+1 nếu 1 < p < N, và có một hàng xóm là 2 nếu p=1, một hàng xóm là N-1 nếu p=N. Để ý rằng nước đi như vậy chỉ tồn tại nếu đống p có ít nhất 2m quân bài nếu p có hai hàng xóm và m quân bài nếu p có một hàng xóm.
Bài toán đặt ra là "làm phẳng" tất cả các đống sao cho các đống có số quân bài như nhau sau khi sử dụng ít nước đi nhất. Trong trường hợp có nhiều nghiệm chỉ cần chỉ ra 1 trong chúng.
· Dữ liệu đã cho bảo đảm rằng để giải quyết bài toán trên phải sử dụng tối đa là 10000 nước đi.
· 2 <= N <= 200
· 0 <= Ci <= 2000 với Ci là số quân bài ban đầu của đống i với 1<= i <= N
Input
Input là file text flat.inp có hai dòng
- Dòng đầu tiên: N
- Dòng thứ hai có N số nguyên là các giá trị Ci
Output
Output là tệp văn bản flat.out
- Dòng đầu tiên: số các nước đi (gọi số này là M)
- Mỗi dòng tiếp theo trong M dòng: các số tương ứng p, m
Số thứ tự các bước đi đúng theo thứ tự các dòng được mô tả ở trên.
Ví dụ
Flat.inp
Flat.out
Code:
5
5 2
3 4
2 4
3 1
4 2
Bài 2
Cho N số tự nhiên. Phép biến đổi P(i,j,d) giảm đồng lọat các phần tử từ phần tử thứ i đến phần tử thứ j của dãy xuống d đơn vị, d>0.
Hãy thực hiện một số ít nhất phép biến đổi dạn P để đưa dãy đã cho về dãy số tòan số 0.
Input
- Dòng đầu tiên ghi số N (1<=N<=30000)
- Các dòng tiếp theo ghi N của dãy, các số cách nhau ít nhất 1 khỏang trắng hoặc 1 dấu xuống dòng.
Output
- Dòng đầu hứa một số nguyên duy nhất K là số lần thực hiện các phép biến đổi dạng P để đưa dãy đã cho về dãy toàn số 0.
- K dòng tiếp theo ghi ra các phép biến đổi tương ứng.
Ví dụ :
Flat.inp
Flat.out
Code:
4
4 4 2
3 5 2
2 6 2
1 7 1
Bài tập lập trình san cột (Giống bài tháp Hà Nội)
