JOI 2005/2006 - Vòng sơ khảo

Yêu cầu

Hai người A và B cùng lật lần lượt một lá bài có chữ số từ \(0\) đến \(9\). Người có số lớn hơn nhận cả hai lá và ghi tổng hai số; nếu bằng nhau, mỗi người nhận lá của mình và ghi số trên lá đó. Hãy tính tổng điểm cuối cùng.

Dữ liệu vào

Dòng đầu chứa \(n\). Mỗi dòng trong \(n\) dòng tiếp theo chứa số trên lá của A và B ở lượt tương ứng.

Dữ liệu ra

In điểm của A và B, cách nhau bởi một dấu cách.

Ràng buộc

• \(n\le10000\).

Ví dụ

10
3 9
1 1
4 4
4 2
8 4
0 8
1 2
0 1
3 0
8 2

36 29

Yêu cầu

Cho một bảng thay thế ký tự. Mỗi ký tự dữ liệu được thay đúng một lần nếu xuất hiện ở vế trái của bảng; ký tự vừa sinh ra không được thay tiếp. Chữ hoa và chữ thường khác nhau.

Dữ liệu vào

Dòng đầu chứa \(n\). \(n\) dòng tiếp theo mỗi dòng chứa hai ký tự trước và sau. Dòng kế chứa \(m\), rồi \(m\) dòng mỗi dòng chứa một ký tự dữ liệu.

Dữ liệu ra

In chuỗi sau biến đổi trên một dòng, không chèn khoảng trắng.

Ràng buộc

• Dữ liệu chỉ dùng chữ cái Latin và chữ số.
• \(m<10^8\).

Ví dụ

10
R F
d v
Q W
t Q
Y 3
1 E
r d
o V
w V
0 s
100
a
M
J
o
X
6
W
G
F
w
1
z
r
2
D
y
Z
T
R
3
2
s
O
Z
3
M
I
T
s
q
x
n
G
G
A
6
0
8
a
P
Y
A
8
p
t
S
g
A
6
f
D
C
d
f
g
H
4
y
p
F
v
H
H
8
6
O
T
8
F
w
M
k
4
z
w
t
j
J
C
l
9
u
6
H
I
z
c
d
O
t
m
Q
O
C
i
r
g
t
G
2

aMJVX6WGFVEzd2DyZTF32sOZ3MITsqxnGGA6s8aP3A8pQSgA6fDCvfgH4ypFvHH86OT8FVMk4zVQjJCl9u6HIzcvOQmWOCidgQG2

Yêu cầu

Một con xúc xắc ban đầu có mặt trên là \(1\), mặt nam là \(2\), mặt đông là \(3\); các mặt đối diện có tổng bằng \(7\). Thực hiện các lệnh North, East, South, West bằng cách lăn xúc xắc \(90^\circ\) theo hướng tương ứng. Right và Left quay xúc xắc \(90^\circ\) quanh trục thẳng đứng, giữ nguyên mặt trên và dưới.

Bắt đầu tổng bằng số \(1\) trên mặt trên ban đầu. Sau mỗi thao tác, cộng số mới trên mặt trên vào tổng.

Dữ liệu vào

Dòng đầu chứa số thao tác \(n\). Mỗi dòng trong \(n\) dòng tiếp theo chứa một trong sáu lệnh hợp lệ.

Dữ liệu ra

In tổng các giá trị mặt trên, gồm cả trạng thái ban đầu.

Ràng buộc

• \(n\le10000\).

Ví dụ

24
North
East
South
South
West
West
North
North
North
East
East
East
South
South
South
South
West
West
West
West
North
North
North
North

77

Yêu cầu

Có \(n\) cốc kích thước khác nhau trên ba khay A, B, C. Trên mỗi khay, cốc nhỏ hơn nằm dưới cốc lớn hơn. Mỗi lần chỉ chuyển cốc trên cùng; không được đặt cốc nhỏ lên cốc lớn; chỉ được chuyển giữa A–B hoặc B–C, không trực tiếp giữa A–C.

Hãy tìm số bước ít nhất để gom tất cả cốc lên A hoặc C. Nếu không thể thực hiện trong nhiều nhất \(m\) bước, in \(-1\).

Dữ liệu vào

Dòng đầu chứa \(n,m\). Ba dòng tiếp theo mô tả A, B, C: số đầu là lượng cốc, sau đó là kích thước các cốc theo thứ tự tăng dần.

Dữ liệu ra

In số bước nhỏ nhất, hoặc -1.

Ràng buộc

• \(1\le n\le15\).
• \(1\le m\le15000000\).
• Các kích thước \(1,2,\ldots,n\) xuất hiện đúng một lần.

Ví dụ

3 10
1 1
1 3
1 2

7

Yêu cầu

Có \(k\) bộ thẻ, mỗi bộ mang các số \(1\) đến \(n\). Sau khi xáo, chia thành \(n\) chồng, mỗi chồng \(k\) lá. Trò chơi bắt đầu ở chồng \(1\): rút lá trên cùng mang số \(i\) thì tiếp tục rút ở chồng \(i\). Thành công khi mọi chồng đều rỗng; thất bại nếu phải rút từ một chồng đã rỗng khi vẫn còn lá nơi khác.

Nếu thất bại, có thể khởi động lại tối đa \(m\) lần, mỗi lần từ chồng trái nhất còn lá. Mọi cách xáo ban đầu có xác suất như nhau. Hãy tính xác suất thành công \(p\) và in chính xác \(r\) chữ số thập phân, cắt bỏ các chữ số sau vị trí \(r\) mà không làm tròn.

Dữ liệu vào

Một dòng chứa \(n,k,m,r\).

Dữ liệu ra

In xác suất \(p\) với đúng \(r\) chữ số sau dấu chấm. Nếu khai triển kết thúc, vẫn phải in các chữ số 0 còn thiếu.

Ràng buộc

• \(1\le n\le10000\).
• \(1\le k\le100\).
• \(m\in\{0,1\}\).
• \(1\le r\le10000\).

Ví dụ

5 2 0 2

0.20