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

Taro thường mua hàng ở cửa hàng tạp hóa JOI. Cửa hàng có đủ các đồng xu mệnh giá \(500\), \(100\), \(50\), \(10\), \(5\) và \(1\) yên, và luôn trả tiền thừa bằng số đồng xu ít nhất.

Taro trả bằng một tờ \(1000\) yên. Hãy tính số đồng xu trong khoản tiền thừa mà Taro nhận được.

Dữ liệu vào

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

Một dòng chứa một số nguyên \(A\), là số tiền phải thanh toán, với \(1 \le A < 1000\).

Dữ liệu ra

Ghi ra đầu ra chuẩn.

Ghi một dòng chứa số đồng xu trong khoản tiền thừa.

Chấm điểm

Có \(5\) bộ dữ liệu, mỗi bộ \(4\) điểm; tổng cộng \(20\) điểm.

Ví dụ

380

4

1

15

Cho một xâu chỉ gồm các chữ cái tiếng Anh in hoa. Hãy đếm riêng số vị trí mà ba ký tự liên tiếp tạo thành JOI và số vị trí mà ba ký tự liên tiếp tạo thành IOI. Các lần xuất hiện có thể chồng lấn nhau.

Chẳng hạn, trong xâu JOIOIOI, JOI xuất hiện một lần và IOI xuất hiện hai lần.

Dữ liệu vào

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

Một dòng chứa xâu gồm không quá \(10000\) chữ cái tiếng Anh in hoa.

Dữ liệu ra

Ghi ra đầu ra chuẩn.

Ghi hai dòng: dòng đầu là số lần xuất hiện của JOI, dòng thứ hai là số lần xuất hiện của IOI.

Chấm điểm

Có \(5\) bộ dữ liệu, mỗi bộ \(4\) điểm; tổng cộng \(20\) điểm.

Ví dụ

JOIJOI

2
0

JOIOIOIOI

1
3

JOIOIJOINXNXJIOIOIOJ

2
3

Taro và Hanako chơi một trò chơi với \(2n\) lá bài, mỗi lá mang một số nguyên khác nhau từ \(1\) đến \(2n\). Mỗi người được chia \(n\) lá bài. Hai người lần lượt đánh bài theo các quy tắc sau:

• Nếu trên bàn chưa có bài, người chơi có thể đánh bất kỳ lá bài nào mình đang giữ.
• Nếu trên bàn đã có bài, chỉ được đánh lá có số lớn hơn số trên lá vừa được đánh gần nhất.
• Nếu có lá hợp lệ thì bắt buộc phải đánh. Nếu không có, người chơi bỏ lượt, toàn bộ bài trên bàn được dọn đi và đến lượt đối phương.

Ban đầu trên bàn không có bài và Taro đi trước. Trò chơi kết thúc ngay khi một người hết bài. Điểm của mỗi người bằng số lá bài đối phương còn giữ khi trò chơi kết thúc.

Cả hai luôn đánh lá có số nhỏ nhất trong số những lá có thể đánh. Biết các lá bài được chia cho Taro, hãy tính điểm của Taro và Hanako.

Dữ liệu vào

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

Dòng đầu chứa số nguyên \(n\) với \(1 \le n \le 100\).

\(n\) dòng tiếp theo, mỗi dòng chứa số trên một lá bài được chia cho Taro. Các số này khác nhau và nằm trong đoạn từ \(1\) đến \(2n\). Hanako nhận các lá còn lại.

Dữ liệu ra

Ghi ra đầu ra chuẩn.

Ghi điểm của Taro trên dòng đầu và điểm của Hanako trên dòng thứ hai.

Chấm điểm

Có \(5\) bộ dữ liệu, mỗi bộ \(4\) điểm; tổng cộng \(20\) điểm.

Ví dụ

5
1
7
9
6
10

3
0

10
8
7
14
18
4
11
3
17
5
19

2
0

Bạn đang tìm một chòm sao trong ảnh bầu trời. Ảnh chứa đúng một bản sao có cùng hình dạng, hướng và kích thước với chòm sao cần tìm; ảnh có thể chứa những ngôi sao khác.

Biết tọa độ các ngôi sao của chòm sao và tọa độ các ngôi sao trong ảnh, hãy tìm phép tịnh tiến biến các tọa độ của chòm sao thành tọa độ của nó trong ảnh. Không xoay hoặc thay đổi kích thước chòm sao.

Dữ liệu vào

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

Dòng đầu chứa số ngôi sao \(m\) của chòm sao. \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x,y\), cách nhau bởi dấu cách, là tọa độ một ngôi sao.

Dòng thứ \(m+2\) chứa số ngôi sao \(n\) trong ảnh. \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x,y\) là tọa độ một ngôi sao trong ảnh.

\(1 \le m \le 200\), \(1 \le n \le 1000\). Mọi tọa độ đều từ \(0\) đến \(1000000\). Trong mỗi tập, các ngôi sao có tọa độ đôi một khác nhau. Đáp án tồn tại và duy nhất.

Dữ liệu ra

Ghi ra đầu ra chuẩn.

Ghi hai số nguyên trên một dòng, cách nhau bởi dấu cách: độ tịnh tiến theo trục \(x\), rồi độ tịnh tiến theo trục \(y\).

Chấm điểm

Có \(5\) bộ dữ liệu, mỗi bộ \(4\) điểm; tổng cộng \(20\) điểm.

Ví dụ

5
8 5
6 4
4 3
7 10
0 10
10
10 5
2 7
9 7
8 10
10 2
1 2
8 1
6 7
6 0
0 9

2 -3

5
904207 809784
845370 244806
499091 59863
638406 182509
435076 362268
10
757559 866424
114810 239537
519926 989458
461089 424480
674361 448440
81851 150384
459107 795405
299682 6700
254125 362183
50795 541942

-384281 179674

Công ty bánh kẹo IOI nướng bánh gạo senbei theo phương pháp truyền thống: nướng mặt trước trên than trong một khoảng thời gian cố định, lật bánh rồi nướng mặt sau trong một khoảng thời gian cố định. Máy nướng xếp bánh thành \(R\) hàng và \(C\) cột.

Ngay trước lúc máy lật toàn bộ bánh, một trận động đất làm một số bánh bị lật. Than vẫn ở trạng thái thích hợp, nhưng nếu tiếp tục nướng mặt trước thì những bánh đó sẽ bị quá lửa và không thể bán được.

Máy có thể lật đồng thời một số hàng hoặc một số cột, nhưng không thể lật riêng từng chiếc bánh. Để kịp thời gian, bạn chỉ được chọn một số hàng và lật chúng đồng thời một lần, sau đó chọn một số cột và lật chúng đồng thời một lần. Có thể không chọn hàng nào hoặc không chọn cột nào.

Hãy tìm số bánh lớn nhất có thể nướng cả hai mặt đúng cách để bán được. Đó là số bánh ở trạng thái nướng mặt sau sau hai thao tác trên.

Dữ liệu vào

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

Dòng đầu chứa \(R,C\), với \(1 \le R \le 10\) và \(1 \le C \le 10000\).

\(R\) dòng tiếp theo mô tả trạng thái ngay sau động đất. Dòng thứ \(i\) trong phần này chứa \(C\) số \(a_{i,1},\ldots,a_{i,C}\). Giá trị \(1\) nghĩa là mặt trước đang được nướng, còn \(0\) nghĩa là mặt sau đang được nướng.

Dữ liệu ra

Ghi ra đầu ra chuẩn.

Ghi một dòng chứa số bánh lớn nhất có thể bán được.

Chấm điểm

Có \(5\) bộ dữ liệu, mỗi bộ \(4\) điểm; tổng cộng \(20\) điểm.

Ví dụ

2 5
0 1 0 1 0
1 0 0 0 1

9

3 6
1 0 0 0 1 0
1 1 1 0 1 0
1 0 1 1 0 1

15

Nước JOI có \(n\) hòn đảo được đánh số từ \(1\) đến \(n\). Bạn làm việc tại trung tâm bán vé tàu. Khách hàng lần lượt gửi yêu cầu đi từ một đảo đến một đảo khác với tổng giá vé nhỏ nhất; họ có thể đổi tàu nhiều lần. Nếu không thể đi bằng tàu thì phải báo rằng không có hành trình phù hợp.

Các tuyến tàu mới liên tục được mở. Hãy xử lý các thông tin và yêu cầu theo đúng thứ tự nhận được, dùng tất cả các tuyến đã được thông báo trước thời điểm mỗi yêu cầu.

Dữ liệu vào

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

Dòng đầu chứa \(n,k\) với \(1 \le n \le 100\), \(1 \le k \le 5000\).

Mỗi dòng trong \(k\) dòng tiếp theo có một trong hai dạng:

• 0 a b: yêu cầu tìm giá vé nhỏ nhất từ đảo \(a\) đến đảo \(b\), với \(1 \le a,b \le n\), \(a \ne b\).
• 1 c d e: mở một tuyến tàu hai chiều giữa \(c\) và \(d\), giá vé mỗi chiều là \(e\), với \(1 \le c,d \le n\), \(c \ne d\), \(1 \le e \le 1000000\).

Ban đầu không có tuyến tàu nào. Có không quá \(1000\) dòng thông báo mở tuyến. Có thể có nhiều tuyến tàu giữa cùng một cặp đảo.

Dữ liệu ra

Ghi ra đầu ra chuẩn.

Với mỗi yêu cầu loại 0, ghi một dòng chứa tổng giá vé nhỏ nhất, hoặc \(-1\) nếu không thể đến đích. Các câu trả lời phải theo thứ tự yêu cầu. Nếu có \(m\) yêu cầu thì đầu ra có \(m\) dòng.

Chấm điểm

Có \(5\) bộ dữ liệu, mỗi bộ \(4\) điểm; tổng cộng \(20\) điểm.

Ví dụ

3 8
1 3 1 10
0 2 3
1 2 3 20
1 1 2 5
0 3 2
1 1 3 7
1 2 1 9
0 2 3

-1
15
12

5 16
1 1 2 343750
1 1 3 3343
1 1 4 347392
1 1 5 5497
1 2 3 123394
1 2 4 545492
1 2 5 458
1 3 4 343983
1 3 5 843468
1 4 5 15934
0 2 1
0 4 1
0 3 2
0 4 2
0 4 3
0 5 3

5955
21431
9298
16392
24774
8840