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

Hai học sinh A và B của trường trung học JOI tham gia kiểm tra bốn môn: Tin học, Toán, Khoa học tự nhiên và Tiếng Anh. Gọi \(S\) là tổng điểm bốn môn của A, \(T\) là tổng điểm bốn môn của B.

Yêu cầu

Cho điểm của hai học sinh, hãy in ra số lớn hơn trong hai tổng điểm \(S\) và \(T\). Nếu hai tổng bằng nhau, in ra \(S\) (cũng chính là \(T\)).

Dữ liệu vào

Đọc từ đầu vào chuẩn hai dòng:

• Dòng thứ nhất chứa bốn số nguyên, lần lượt là điểm Tin học, Toán, Khoa học tự nhiên và Tiếng Anh của A.
• Dòng thứ hai chứa bốn số nguyên, lần lượt là điểm Tin học, Toán, Khoa học tự nhiên và Tiếng Anh của B.

Các số trên cùng một dòng được ngăn cách bởi một dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là giá trị lớn hơn trong hai tổng điểm.

Ràng buộc

• Điểm của mỗi môn là một số nguyên từ \(0\) đến \(100\), kể cả hai đầu mút.

Phân nhóm

• Có \(5\) bộ dữ liệu được chấm độc lập, với tổng điểm tối đa là \(20\).

Ví dụ

100 80 70 60
80 70 80 90

320

100 80 70 60
80 70 60 100

310

Giáo sư M của Đại học JOI phụ trách một lớp lập trình gồm \(30\) sinh viên. Mỗi sinh viên có một số thứ tự từ \(1\) đến \(30\). Có \(28\) sinh viên đã nộp bài tập của lớp.

Yêu cầu

Cho số thứ tự của \(28\) sinh viên đã nộp bài, hãy tìm số thứ tự của hai sinh viên chưa nộp bài.

Dữ liệu vào

Đọc từ đầu vào chuẩn \(28\) dòng, mỗi dòng chứa một số nguyên là số thứ tự của một sinh viên đã nộp bài. Các số được cho theo thứ tự bất kỳ.

Dữ liệu ra

Ghi ra đầu ra chuẩn hai dòng:

• Dòng thứ nhất chứa số thứ tự nhỏ hơn trong hai sinh viên chưa nộp bài.
• Dòng thứ hai chứa số thứ tự lớn hơn.

Ràng buộc

• Mỗi số thứ tự là một số nguyên từ \(1\) đến \(30\).
• Có đúng \(28\) số thứ tự trong đầu vào và chúng đôi một khác nhau.

Phân nhóm

• Có \(5\) bộ dữ liệu được chấm độc lập, với tổng điểm tối đa là \(20\).

Ví dụ

3
1
4
5
7
9
6
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2
8

9
30
6
12
10
20
21
11
7
5
28
4
18
29
17
19
27
13
16
26
14
23
22
15
3
1
24
25

2
8

Gaius Julius Caesar là một vị tướng và chính khách của La Mã cổ đại. Theo các ghi chép, khi viết thư bí mật, ông thay A bằng D, B bằng E, C bằng F, và tương tự với các chữ cái khác: mỗi chữ được dịch tiến ba vị trí trong bảng chữ cái, quay vòng về đầu bảng khi vượt qua Z.

Một xâu chỉ gồm các ký tự thuộc bảng \(26\) chữ cái in hoa tiếng Anh đã được mã hóa theo cách này. Bảng tương ứng đầy đủ là:

Trước: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Sau:   D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Chẳng hạn, xâu JOI được mã hóa thành MRL; xâu gốc của bản mã FURDWLD là CROATIA.

Yêu cầu

Khôi phục xâu ban đầu từ xâu đã được mã hóa.

Dữ liệu vào

Đọc từ đầu vào chuẩn một dòng chứa xâu đã được mã hóa, chỉ gồm các chữ cái in hoa tiếng Anh.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chỉ chứa xâu ban đầu sau khi giải mã.

Ràng buộc

• Các ký tự trong xâu thuộc bảng chữ cái A đến Z.
• Độ dài xâu không vượt quá \(1000\).

Phân nhóm

• Có \(5\) bộ dữ liệu được chấm độc lập, với tổng điểm tối đa là \(20\).

Ví dụ

MRL

JOI

FURDWLD

CROATIA

Có \(2n\) lá bài mang các số từ \(1\) đến \(2n\), ban đầu được xếp thành một chồng theo thứ tự \(1,2,3,\ldots,2n\) từ trên xuống dưới.

Ta thực hiện một số thao tác sắp xếp lại chồng bài theo hai cách sau:

1. Cắt tại số nguyên \(k\): tách \(k\) lá trên cùng thành chồng \(A\), các lá còn lại thành chồng \(B\), rồi đặt chồng \(B\) lên trên chồng \(A\). Thứ tự các lá trong mỗi chồng được giữ nguyên.

   

2. Trộn xen kẽ: tách \(n\) lá trên cùng thành chồng \(A\), các lá còn lại thành chồng \(B\), rồi ghép lại thành một chồng có thứ tự từ trên xuống là lá thứ nhất của \(A\), lá thứ nhất của \(B\), lá thứ hai của \(A\), lá thứ hai của \(B\), \(\ldots\), lá thứ \(n\) của \(A\), lá thứ \(n\) của \(B\).

   

Yêu cầu

Thực hiện các thao tác được cho trong đầu vào và in số trên các lá bài theo thứ tự từ trên xuống dưới sau khi hoàn thành mọi thao tác.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng thứ nhất chứa số nguyên \(n\); số lá bài là \(2n\).
• Dòng thứ hai chứa số nguyên \(m\) là số thao tác.
• Mỗi dòng từ dòng thứ \(3\) đến dòng thứ \(m+2\) chứa một số nguyên \(k\), mô tả các thao tác theo thứ tự thực hiện. Nếu \(k=0\), thực hiện thao tác trộn xen kẽ. Nếu \(1\le k\le 2n-1\), thực hiện thao tác cắt tại \(k\).

Chỉ thực hiện đúng \(m\) thao tác đã khai báo. Bỏ qua dữ liệu nếu có sau dòng thứ \(m+2\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(2n\) dòng. Dòng thứ \(i\) chứa số trên lá bài thứ \(i\) tính từ trên xuống dưới sau khi hoàn thành các thao tác.

Ràng buộc

• \(1\le n\le 100\).
• \(1\le m\le 1000\).
• Mỗi thao tác được biểu diễn bởi một số nguyên \(k\) thỏa mãn \(0\le k\le 2n-1\).

Phân nhóm

• Có \(5\) bộ dữ liệu được chấm độc lập, với tổng điểm tối đa là \(20\).

Ví dụ

2
2
1
0

2
4
3
1

3
4
2
4
0
0

1
5
4
3
2
6

Bạn phụ trách quản lý chất lượng tại một nhà máy sản xuất máy móc. Mỗi chiếc máy cần ba linh kiện: một bộ nguồn, một động cơ và một dây cáp. Nhà máy có \(a\) bộ nguồn mang số từ \(1\) đến \(a\), \(b\) động cơ mang số từ \(a+1\) đến \(a+b\), và \(c\) dây cáp mang số từ \(a+b+1\) đến \(a+b+c\).

Một số linh kiện có thể bị hỏng. Để tìm hiểu linh kiện nào bị hỏng và linh kiện nào hoạt động bình thường, nhà máy tiến hành kiểm tra bằng cách nối một bộ nguồn, một động cơ và một dây cáp, rồi cho máy chạy thử. Nếu cả ba linh kiện đều hoạt động bình thường, máy chạy đúng và lần kiểm tra được đánh giá là đạt. Nếu có ít nhất một linh kiện bị hỏng, máy không chạy đúng và lần kiểm tra được đánh giá là không đạt. Máy đòi hỏi độ chính xác cực cao để hoạt động, nên không có trường hợp linh kiện bị hỏng mà máy tình cờ vẫn chạy đúng.

Bạn được cung cấp danh sách kết quả kiểm tra. Mỗi kết quả cho biết số hiệu của bộ nguồn, động cơ và dây cáp đã sử dụng, cùng với việc lần kiểm tra đó đạt hay không đạt.

Yêu cầu

Dựa trên tất cả kết quả kiểm tra, phân loại từng linh kiện vào một trong ba loại: chắc chắn bị hỏng, chắc chắn hoạt động bình thường, hoặc chưa thể xác định là hỏng hay bình thường.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng thứ nhất chứa ba số nguyên \(a,b,c\), lần lượt là số bộ nguồn, số động cơ và số dây cáp.
• Dòng thứ hai chứa số nguyên \(N\) là số lần kiểm tra trong danh sách.
• Mỗi dòng trong \(N\) dòng tiếp theo chứa bốn số nguyên \(i,j,k,r\): lần kiểm tra sử dụng bộ nguồn \(i\), động cơ \(j\) và dây cáp \(k\); \(r=1\) biểu thị kết quả đạt, còn \(r=0\) biểu thị kết quả không đạt.

Các số trên cùng một dòng được ngăn cách bởi một dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn \(a+b+c\) dòng. Dòng thứ \(i\) ứng với linh kiện mang số \(i\) (\(1\le i\le a+b+c\)), chứa:

• \(0\) nếu có thể khẳng định linh kiện đó bị hỏng từ các kết quả kiểm tra.
• \(1\) nếu có thể khẳng định linh kiện đó hoạt động bình thường từ các kết quả kiểm tra.
• \(2\) nếu các kết quả kiểm tra chưa đủ để xác định linh kiện đó bị hỏng hay hoạt động bình thường.

Ràng buộc

• \(1\le a,b,c\le 100\).
• \(1\le N\le 1000\).
• Trong mỗi lần kiểm tra: \(1\le i\le a\), \(a+1\le j\le a+b\), \(a+b+1\le k\le a+b+c\) và \(r\in\{0,1\}\).

Phân nhóm

• Có \(5\) bộ dữ liệu được chấm độc lập, với tổng điểm tối đa là \(20\).

Ví dụ

2 2 2
4
2 4 5 0
2 3 6 0
1 4 5 0
2 3 5 1

2
1
1
0
1
0

Thành phố JOI nơi Taro sinh sống có dạng bàn cờ, được tạo bởi \(a\) con đường thẳng chạy theo hướng bắc–nam và \(b\) con đường thẳng chạy theo hướng đông–tây.

Các đường bắc–nam được đánh số \(1,2,\ldots,a\) theo thứ tự từ tây sang đông. Các đường đông–tây được đánh số \(1,2,\ldots,b\) theo thứ tự từ nam lên bắc. Giao điểm của đường bắc–nam thứ \(i\) tính từ phía tây và đường đông–tây thứ \(j\) tính từ phía nam được ký hiệu là \((i,j)\).

Taro sống gần giao lộ \((1,1)\) và đi xe đạp đến trường trung học JOI gần giao lộ \((a,b)\). Xe đạp chỉ có thể đi dọc theo các con đường. Để rút ngắn thời gian đi học, Taro chỉ di chuyển về phía đông hoặc phía bắc.

Hiện tại, có \(n\) giao lộ \((x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\) đang thi công. Taro không thể đi qua các giao lộ này.

Yêu cầu

Tính số lộ trình \(m\) để Taro đi từ giao lộ \((1,1)\) đến giao lộ \((a,b)\), chỉ đi về phía đông hoặc phía bắc và tránh mọi giao lộ đang thi công.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng thứ nhất chứa hai số nguyên \(a,b\) ngăn cách bởi một dấu cách, lần lượt là số đường bắc–nam và số đường đông–tây.
• Dòng thứ hai chứa số nguyên \(n\) là số giao lộ đang thi công.
• Với mỗi \(i\) từ \(1\) đến \(n\), dòng thứ \(i+2\) chứa hai số nguyên \(x_i,y_i\) ngăn cách bởi một dấu cách, cho biết giao lộ \((x_i,y_i)\) đang thi công.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chỉ chứa số nguyên \(m\) là số lộ trình đi học của Taro.

Ràng buộc

• \(1\le a,b\le 16\).
• \(1\le n\le 40\).
• \(1\le x_i,y_i\le 16\) với mọi \(1\le i\le n\).

Phân nhóm

• Có \(5\) bộ dữ liệu được chấm độc lập, với tổng điểm tối đa là \(20\).

Ví dụ

5 4
3
2 2
2 3
4 2

5