đề thi lập trình olympia IT tuần 2

TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN CÂU LẠC BỘ LẬP TRÌNH CPT	CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc
	TPHCM, ngày  28 tháng 03 năm 2015

Cuộc Thi Lập Trình Olympia IT

Đề Chính Thức Tuần 2

Câu 1. (6đ)

Xâu biểu thức.
Cho biểu thức có các phần tử x, các số nguyên, các dấu +, -, *, / (chia lấy phần nguyên), và (), Hãy tính giá trị của biểu thức đã cho với từng giá trị của x cho trước.

Các số trong biểu thức cũng như giá trị của x luôn < 106

Input : biểu thức và các giá trị của x (40%test sẽ không có dấu ())

Output: các giá trị của biểu thức tương ứng với x

Ví Dụ:

Input:

5x+2      // biểu thức (<255 kí tự)
3            // số giá trị của x (<100)
1 2 3      // các giá trị của x (x<1000000)

Output:

7 12 17  // các giá trị của biểu thức tương ứng với các giá trị của x

Câu 2. (7đ)

Robot đang đứng ở vị trí 0 0 trong bản đồ. Robot có thể nhận các lệnh L: về phía bên trái, R: về bên phải, U: tiến về phía trước, D: lùi ra sau, B: quay lại vị trí trước đó (lưu ý, nếu robot đã thực hiện lênh U, R, sau đó nhận lệnh B, B thì robot sẽ thực hiện lệnh L, D, còn nếu robot chưa thực hiện lệnh nào thì lệnh B sẽ không có tác dụng) và lệnh T (turn around, lệnh này sẽ đọc thêm lệnh tiếp theo và khiến robot quay 180 độ về phía sau nếu lệnh tiếp theo là D, quay 90 độ theo kim đồng hồ nếu lệnh tiếp theo là R, quay 90 độ ngược kim đồng hồ nếu lệnh tiếp theo là L, khiến robot đứng yên không di chuyển nếu lệnh tiếp theo là B hay U.)

Ban đầu robot đang quay lên trên

Hãy tìm tọa độ của robot sau khi thực hiện xong n chuỗi lệnh. (robot sẽ vẫn giữ nguyên vị trí và hướng quay sau khi thực hiện xong 1 chuỗi lệnh)
Input
N (N<100)

N dòng, mỗi dòng là 1 chuỗi lệnh cho robot (mỗi dòng <255 kí tự)

(40% test sẽ không có lệnh T)

Output

N dòng, mỗi dòng là tọa độ robot sau khi thực hiện chuỗi lệnh của dòng tương ứng

Ví Dụ:

Input:

4
UDLRTBBBBTUTRTLTDU
UUUU
TLUUUU
BBBB

Output:

0 0
0 -4
4 -4
0 -4

Câu 3.(7đ)

Một con robot đang ở trong một ma trận. bản đồ được vẽ bởi các kí tự 0, 1, 2, 3 trong đó, 0 là đường mà robot có thể đi được, 1 là tường, robot không thể vượt qua, 2 là vị trí của robot còn 3 là đích. Ngoài ra trong ma trận còn có thể có các cổng dịch chuyển được đánh số từ 4 đến 9, với cổng thứ i, robot sẽ tốn i đơn vị thời gian để dịch chuyển đến cổng tương tự, robot tốn 1 đơn vị thời gian để di chuyển từ ô hiện tại sang ô bên cạnh. Hãy tính thời gian nhanh nhất robot có thể đến được đích

Input: (40% test sẽ không có cổng dịch chuyển)

M, N : số hàng và số cột của ma trận (M,N < 250)
M dòng, mỗi dòng là 1 chuỗi biểu thị ma trận đó

Output:

Thời gian cần thiết để robot đến được đích

Ví Dụ:

Input:

10 10
1110000001
0002011101
0111010001
0400010111
0111110011
1400111011
1110000011
1110111001
1113111101
1111111101

Output:

15

Lưu ý: Tất cả các bài đều nhập xuất từ file. Các file nhập xuất đặt tên theo định dạng sau: bai1.inp, bai1.out; bai2.inp, bai2.out; bai3.inp,bai3.out.