JOI 2009/2010 - Vòng sơ khảo

Taro đã mua \(10\) quyển sách. Một hôm sau đó, cậu muốn xem lại giá các quyển sách trên hóa đơn, nhưng hóa đơn bị bẩn khiến cậu không đọc được giá của một quyển. Cậu quyết định tính giá của quyển sách đó từ tổng giá của cả \(10\) quyển và giá của \(9\) quyển còn lại.

Giá của mỗi quyển sách đều là số nguyên dương. Không cần xét đến thuế tiêu dùng.

Yêu cầu

Hãy viết chương trình in ra giá của quyển sách có giá không đọc được trên hóa đơn.

Dữ liệu vào

Dữ liệu vào gồm \(10\) dòng, mỗi dòng chứa một số nguyên dương.

• Dòng đầu tiên chứa tổng giá của \(10\) quyển sách.
• Các dòng từ \(2\) đến \(10\) chứa giá đọc được của \(9\) quyển sách còn lại.

Dữ liệu ra

In ra một dòng chỉ chứa giá của quyển sách có giá không đọc được trên hóa đơn.

Ràng buộc

• Giá của mỗi quyển sách là số nguyên dương.
• Tổng giá của \(10\) quyển sách không vượt quá \(10\,000\).

Ví dụ

9850
1050
800
420
380
600
820
2400
1800
980

600

JOI đang chơi trò chơi sugoroku một mình. Bàn chơi gồm \(N\) ô nằm trên một đường thẳng, mỗi ô có ghi một chỉ dẫn di chuyển. Ô thứ \(1\) là điểm xuất phát, còn ô thứ \(N\) là đích.

Cho đến khi về đích, JOI lặp lại thao tác sau: gieo xúc xắc, tiến từ ô hiện tại một số ô bằng số chấm gieo được, rồi thực hiện chỉ dẫn trên ô vừa đến. Sau khi di chuyển theo chỉ dẫn, JOI không thực hiện tiếp chỉ dẫn ở ô đến mới.

JOI được xem là về đích cả khi dừng đúng ở ô thứ \(N\) lẫn khi vị trí đến vượt quá ô thứ \(N\).

Yêu cầu

Cho bàn chơi và kết quả của \(M\) lần gieo xúc xắc. Hãy viết chương trình xác định JOI về đích sau bao nhiêu lần gieo xúc xắc.

Dữ liệu vào

Dữ liệu vào gồm \(1+N+M\) dòng.

• Dòng đầu tiên chứa hai số nguyên \(N,M\), cách nhau bởi một dấu cách. \(N\) là số ô trên bàn chơi, còn \(M\) là số kết quả gieo xúc xắc được cho.

• \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên. Số nguyên ở dòng \(1+i\) (\(1\le i\le N\)) biểu diễn chỉ dẫn trên ô thứ \(i\). Gọi số nguyên này là \(X\):

  • Nếu \(X=0\), không làm gì.
  • Nếu \(X>0\), tiến \(X\) ô.
  • Nếu \(X<0\), lùi \(|X|\) ô, trong đó \(|X|\) là giá trị tuyệt đối của \(X\).

• \(M\) dòng tiếp theo, mỗi dòng chứa một số nguyên. Số ở dòng \(1+N+j\) (\(1\le j\le M\)) là số chấm trong lần gieo xúc xắc thứ \(j\).

Dữ liệu ra

In ra một dòng chỉ chứa một số nguyên là số lần gieo xúc xắc cho đến khi JOI về đích.

Ràng buộc

• \(2\le N\le 1000\).
• \(1\le M\le 1000\).
• Mỗi số nguyên biểu diễn chỉ dẫn nằm trong khoảng từ \(-999\) đến \(999\).
• Mỗi kết quả gieo xúc xắc là một số nguyên từ \(1\) đến \(6\).
• Các số ở dòng \(2\) và dòng \(1+N\) luôn bằng \(0\), tức là chỉ dẫn tại ô xuất phát và ô đích đều là không làm gì.
• Không có ô nào mang chỉ dẫn khiến JOI di chuyển về trước ô thứ \(1\).
• Trong mọi bộ dữ liệu chấm, JOI về đích sau không quá \(M\) lần gieo xúc xắc.

Ví dụ

10 5
0
0
5
6
-3
8
1
8
-4
0
1
3
5
1
5

5

10 10
0
-1
-1
4
4
-5
0
1
-6
0
1
5
2
4
6
5
5
4
1
6

6

Bạn quyết định mời những người bạn của mình trong trường và những người bạn của các bạn ấy đến dự tiệc Giáng sinh.

Trường của bạn có \(n\) học sinh, được đánh số từ \(1\) đến \(n\). Bạn là học sinh mang số \(1\). Bạn có một danh sách ghi lại những cặp học sinh là bạn của nhau.

Yêu cầu

Dựa vào danh sách đã cho, hãy viết chương trình tính số học sinh bạn sẽ mời đến dự tiệc Giáng sinh.

Dữ liệu vào

Dữ liệu vào gồm \(2+m\) dòng.

• Dòng đầu tiên chứa số học sinh trong trường \(n\).
• Dòng thứ hai chứa độ dài danh sách \(m\).
• Dòng \(2+i\) (\(1\le i\le m\)) chứa hai số nguyên \(a_i,b_i\), cách nhau bởi một dấu cách, cho biết học sinh mang số \(a_i\) và học sinh mang số \(b_i\) là bạn của nhau.

Dữ liệu ra

In ra một dòng chỉ chứa số học sinh bạn sẽ mời đến dự tiệc Giáng sinh.

Ràng buộc

• \(2\le n\le 500\).
• \(1\le m\le 10\,000\).
• \(1\le a_i<b_i\le n\) với \(1\le i\le m\).
• Trong các dòng từ \(3\) đến \(2+m\), không có hai dòng biểu diễn cùng một quan hệ bạn bè.

Ví dụ

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

3

6
5
2 3
3 4
4 5
5 6
2 5

0

Hanako đang chơi xếp \(n\) thẻ bài (\(4\le n\le 10\)). Trên mỗi thẻ có ghi một số nguyên từ \(1\) đến \(99\). Cô quyết định chọn \(k\) thẻ trong số đó (\(2\le k\le 4\)), rồi xếp thành một hàng ngang để tạo thành một số nguyên. Hanako có thể tạo ra tất cả bao nhiêu số nguyên khác nhau?

Ví dụ, xét \(5\) thẻ ghi các số \(1,2,3,13,21\) và chọn \(3\) thẻ để tạo một số nguyên. Xếp các thẻ \(2,1,13\) theo thứ tự này tạo ra số nguyên \(2113\). Xếp các thẻ \(21,1,3\) theo thứ tự này cũng tạo ra số nguyên \(2113\). Như vậy, những cách chọn thẻ khác nhau có thể tạo ra cùng một số nguyên.

Yêu cầu

Cho các số nguyên ghi trên \(n\) thẻ bài. Hãy viết chương trình tính số lượng số nguyên khác nhau có thể tạo ra bằng cách chọn \(k\) thẻ và xếp chúng thành một hàng ngang.

Dữ liệu vào

Dữ liệu vào gồm \(2+n\) dòng.

• Dòng đầu tiên chứa số thẻ bài \(n\).
• Dòng thứ hai chứa số thẻ cần chọn \(k\).
• Dòng \(2+i\) (\(1\le i\le n\)) chứa số nguyên ghi trên thẻ thứ \(i\).

Dữ liệu ra

In ra một dòng chỉ chứa số lượng số nguyên khác nhau mà Hanako có thể tạo ra.

Ràng buộc

• \(4\le n\le 10\).
• \(2\le k\le 4\).
• Số ghi trên mỗi thẻ là một số nguyên từ \(1\) đến \(99\).

Ví dụ

4
2
1
2
12
1

7

6
3
72
2
12
7
2
1

68

Thành phố ở Canada nơi JOI sinh sống được chia thành các ô bàn cờ bởi \(w\) con đường thẳng chạy theo hướng bắc–nam và \(h\) con đường thẳng chạy theo hướng đông–tây.

Các con đường theo hướng bắc–nam được đánh số \(1,2,\ldots,w\) từ tây sang đông. Các con đường theo hướng đông–tây được đánh số \(1,2,\ldots,h\) từ nam lên bắc. Ký hiệu \((i,j)\) là giao lộ giữa con đường bắc–nam thứ \(i\) tính từ phía tây và con đường đông–tây thứ \(j\) tính từ phía nam.

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

Để giảm tai nạn giao thông, thành phố có quy định sau:

• Xe đã rẽ tại một giao lộ không được rẽ tại giao lộ ngay kế tiếp.

Nói cách khác, sau khi rẽ tại một giao lộ, xe không được chỉ đi thêm một đoạn đường giữa hai giao lộ liên tiếp rồi lại rẽ. Với quy định này, JOI có bao nhiêu đường đi làm khác nhau?

Yêu cầu

Cho \(w\) và \(h\). Hãy viết chương trình in ra số dư khi chia số đường đi làm của JOI cho \(100\,000\).

Dữ liệu vào

Dữ liệu vào gồm một dòng chứa hai số nguyên \(w,h\), cách nhau bởi một dấu cách. \(w\) là số con đường theo hướng bắc–nam và \(h\) là số con đường theo hướng đông–tây.

Dữ liệu ra

In ra một dòng chỉ chứa số dư khi chia số đường đi làm của JOI cho \(100\,000\).

Ràng buộc

• \(2\le w\le 100\).
• \(2\le h\le 100\).

Ví dụ

3 4

5

15 15

43688

Năm nay, ông già Noel lại bay đến thị trấn JOI. Mọi ngôi nhà trong thị trấn đều có trẻ em, nên ông phải đi phát quà đến tất cả các nhà. Tuy nhiên, chú tuần lộc đi cùng ông năm nay hơi kém định hướng và chỉ có thể hạ xuống trên các công trình, nên ông cần khéo léo lựa chọn đường đi để phát quà cho mọi nhà.

Thị trấn JOI được chia thành các ô theo các hướng đông, tây, nam, bắc. Mỗi ô là một ngôi nhà, một nhà thờ hoặc một khu đất trống. Trong thị trấn có đúng một nhà thờ. Ông già Noel và tuần lộc xuất phát từ nhà thờ, phát quà cho mỗi ngôi nhà đúng một lần rồi trở về nhà thờ, theo các quy tắc sau:

• Vì hơi kém định hướng, chú tuần lộc năm nay chỉ có thể bay thẳng theo một trong bốn hướng đông, tây, nam, bắc và không thể đổi hướng trên không.
• Có thể tự do bay qua phía trên những ngôi nhà chưa được phát quà và có thể hạ xuống những ngôi nhà ấy. Mỗi khi hạ xuống một ngôi nhà, ông già Noel bắt buộc phải phát quà, rồi bay đi theo một trong bốn hướng đông, tây, nam, bắc.
• Vào đêm Giáng sinh, các nhà trong thị trấn JOI không đốt lò sưởi cho đến khi ông già Noel đến, và chỉ đốt lò sau khi ông bay đi. Khi lò sưởi được đốt, khói sẽ thoát ra từ ống khói, nên không thể bay qua phía trên một ngôi nhà đã được phát quà.
• Có thể tự do bay qua phía trên nhà thờ. Tuy nhiên, vì nhà thờ đang có buổi lễ, không được hạ xuống nhà thờ cho đến khi phát hết quà.
• Có thể tự do bay qua phía trên các khu đất trống, nhưng không được hạ xuống đó.

Yêu cầu

Cho cấu trúc của thị trấn. Hãy viết chương trình tính số đường đi mà ông già Noel và tuần lộc có thể sử dụng để phát quà.

Dữ liệu vào

Dữ liệu vào gồm \(n+1\) dòng.

• Dòng đầu tiên chứa hai số nguyên \(m,n\), cách nhau bởi một dấu cách.
• Mỗi dòng từ \(2\) đến \(n+1\) chứa \(m\) số, cách nhau bởi dấu cách; mỗi số là \(0\), \(1\) hoặc \(2\) và biểu diễn trạng thái của một ô.

Ký hiệu \((i,j)\) là ô ở hàng thứ \(i\) tính từ phía bắc và cột thứ \(j\) tính từ phía tây (\(1\le i\le n\), \(1\le j\le m\)). Giá trị thứ \(j\) trên dòng \(i+1\) mô tả ô \((i,j)\):

• \(0\) nếu đó là khu đất trống.
• \(1\) nếu đó là ngôi nhà.
• \(2\) nếu đó là nhà thờ.

Dữ liệu ra

In ra một dòng chỉ chứa một số nguyên là số đường đi để phát quà.

Ràng buộc

• \(1\le m\le 10\).
• \(1\le n\le 10\).
• Có đúng \(1\) nhà thờ.
• Số ngôi nhà từ \(1\) đến \(23\).
• Trong các bộ dữ liệu chấm, số đường đi để phát quà không vượt quá \(2\,000\,000\).

Ví dụ

3 2
1 0 1
1 0 2

2

3 3
1 1 1
1 0 1
1 1 2

6