Bai Toan 4-99

4. Đèn giao thông

Bài toán

Đường giao thông tại thành phố Dingilville được xây dựng theo một kiểu đặc biệt. Thành phố có
những bục binh và các con đường nối các bục binh này. Giữa hai bục binh có ít nhất là một
đường. Không có đường đi vào nối bục binh với chính nó. Các đường đi trong thành phố đều là
hai chiều. Tại mỗi bục binh có treo một đèn, sẽ có màu xanh và đỏ thay đổi nhau. Đường đi giữa
hai bục binh chỉ cho phép nếu các đèn tại 2 bục binh này cùng màu tại thời gian bắt đầu đi từ bục
binh này đến bục binh kia. Nếu điều kiện trên không thoả mãn, các phương tiện cần phải chờ tại
các bục binh. Người ta cho môt bản đồ thành phố bao gồm:

•

Thời gian chạy trên các đường (số nguyên)

•

Thời gian đèn sáng của các màu tại mỗi bục binh (số nguyên)

•

Màu ban đầu tại mỗi bục binh và thời gian còn lại cho đến khi đổi màu tại bục binh này.

Yêu cầu của bài toán là tìm một đường đi với ít thời gian nhất từ một bục binh xuất phát ban đầu
đến một bục binh đích. Tr-ờng hợp có nhưiều đường đi chỉ cần chỉ ra một trong chúng.

Hạn chế kỹ thuật


<=
tic
<=
100 với tic - là thời gian cho màu C tại bục binh i, với C là hoặc B - xanh, P -
đỏ.

•

1
<=
ric
<=
tic với ric - thời gian còn lại của màu ban đầu C tại bục binh i.

Input

Input là tệp

lights.inp

•

Dòng đầu tiên ghi 2 số: đó là mã số của bục binh xuất phát và bục binh đích cần tìm
đường đi.

•

Dòng thứ 2 ghi hai số N, M.

•

<=
U
<=
700, 1
<=
V
<=
700 với U,V - chiều rộng (tây - đông) và cao (nam - bắc) của
bản đồ.

•

0
<=
C
<=
10

•

- 30000
<=
Hxy
<=
30000 với Hxy - là số nguyên chỉ ra chiều cao của ô vuông tại địa chỉ
(x, y), với 1
<=
x
<=
U, 1


Page 1
3

Trắc nghiệm

Chương trình của bạn chỉ được phép chạy trong 60 giây.Page 2
Bai Toan 5-99

5. Làm phẳng
Bài toán

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.
Hình 1. Năm đống với 0, 7, 8, 1 và 4 quân bài

<=
N

Input

Input là file text
flat.inp
có hai dòng

Dò đầ tiê N
Page 1
2
•

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)

•Page 2