Tài liệu 100 đề Toán Tin - Phạm Duy Sinh

100 đề Toán Tin - Phạm Duy SinhTin học & Nhà trường
Phần 1: ĐỀ BÀI
Phần II: LỜI GIẢI


Bài 1/1999 - Trò chơi cùng nhau qua cầu
(Dành cho học sinh Tiểu học)
Bốn người cần đi qua một chiếc cầu. Do cầu yếu nên mỗi lần đi không quá hai người, và vì trời tối nên phải cầm đèn mới đi được. Bốn người đi nhanh chậm khác nhau, qua cầu với thời gian tương ứng là 10 phút, 5 phút, 2 phút và 1 phút. Vì chỉ có một chiếc đèn nên mỗi lần qua cầu phải có người mang đèn trở về cho những người kế tiếp. Khi hai người đi cùng nhau thì qua cầu với thời gian của người đi chậm hơn. Ví dụ sau đây là một cách đi:
- Người 10 phút đi với người 5 phút qua cầu, mất 10 phút.
- Người 5 phút cầm đèn quay về, mất 5 phút.
- Người 5 phút đi với người 2 phút qua cầu, mất 5 phút.
- Người 2 phút cầm đèn quay về, mất 2 phút.
- Người 2 phút đi với người 1 phút qua cầu, mất 2 phút.
Thời gian tổng cộng là 10+5+5+2+2 = 24 phút.
Em hãy tìm cách đi khác với tổng thời gian càng ít càng tốt, và nếu dưới 19 phút thì thật tuyệt vời! Lời giải ghi trong tệp văn bản có tên là P1.DOC

Bài 2/1999 - Tổ chức tham quan
(Dành cho học sinh THCS)
Trong đợt tổ chức đi tham quan danh lam thắng cảnh của thành phố Hồ Chí Minh, Ban tổ chức hội thi Tin học trẻ tổ chức cho N đoàn ( đánh từ số 1 đến N) mỗi đoàn đi thăm quan một địa điểm khác nhau. Đoàn thứ i đi thăm địa điểm ở cách Khách sạn Hoàng Đế di km (i=1,2, , N). Hội thi có M xe taxi đánh số từ 1 đến M (M³N) để phục vụ việc đưa các đoàn đi thăm quan. Xe thứ j có mức tiêu thụ xăng là vj đơn vị thể tích/km.
Yêu cầu: Hãy chọn N xe để phục vụ việc đưa các đoàn đi thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.
Dữ liệu: File văn bản P2.INP:
- Dòng đầu tiên chứa hai số nguyên dương N, M (N£M£200);
- Dòng thứ hai chứa các số nguyên dương d[SUB]1[/SUB], d[SUB]2[/SUB], ., dN;
- Dòng thứ ba chứa các số nguyên dương v[SUB]1[/SUB], v[SUB]2[/SUB], ., vM.
- Các số trên cùng một dòng được ghi khác nhau bởi dấu trắng.
Kết quả: Ghi ra file văn bản P2.OUT:
- Dòng đầu tiên chứa tổng lượng xăng dầu cần dùng cho việc đưa các đoàn đi thăm quan (không tính lượt về);
- Dòng thứ i trong số N dòng tiếp theo ghi chỉ số xe phục vụ đoàn i (i=1, 2, ., N).

Ví dụ:
[TABLE]
[TR]
[TD]P2.INP[/TD]
[TD][/TD]
[TD]P2.OUT[/TD]
[/TR]
[TR]
[TD]3 4
7 5 9
17 13 15 10[/TD]
[TD][/TD]
[TD]256
2
3
4[/TD]
[/TR]
[/TABLE]

Bài 3/1999 - Mạng tế bào
(Dành cho học sinh THPT)
Mạng tế bào có dạng một lưới ô vuông hình chữ nhật. Tại mỗi nhịp thời gian: mỗi ô của lưới chứa tín hiệu là 0 hoặc 1 và có thể truyền tín hiệu trong nó cho một số ô kề cạnh theo một qui luật cho trước. Ô ở góc trên bên trái có thể nhận tín hiệu từ bên ngoài đưa vào. Sau nhịp thời gian đó, tín hiệu ở một ô sẽ là 0 nếu tất cả các tín hiệu truyền đến nó là 0, còn trong trường hợp ngược lại tín hiệu trong nó sẽ là 1. Một ô không nhận được tín hiệu nào từ các ô kề cạnh với nó sẽ giữ nguyên tín hiệu đang có trong nó. Riêng đối với ô trên trái, sau khi truyền tín hiệu chứa trong nó đi, nếu có tín hiệu vào thì ô trên trái sẽ chỉ nhận tín hiệu này, còn nếu không có tín hiệu nào thì ô trên trái cũng hoạt động giống như các ô khác. ở trạng thái đầu tín hiệu trong tất cả các ô là 0.
Yêu cầu: Cho trước số nhịp thời gian T và dãy tín hiệu vào S là một dãy gồm T ký hiệu S[SUB]1[/SUB], ., ST, trong đó Si là 0 hoặc 1 thể hiện có tín hiệu vào, ngược lại Si là X thể hiện không có tín hiệu vào tại nhịp thời gian thứ i (1£ i £T), hãy xác định trạng thái của lưới sau nhịp thời gian thứ T.
Dữ liệu: vào từ file văn bản P3.INP:
- Dòng đầu tiên chứa 3 số nguyên M, N, T theo thứ tự là số dòng, số cột của lưới và số nhịp thời gian (1<M, N £ 200; T £ 100);
- Dòng thứ hai chứa xâu tín hiệu vào S;
- M dòng tiếp theo mô tả qui luật truyền tin. Dòng thứ i trong số M dòng này chứa N số ai[SUB]1[/SUB], ai[SUB]2[/SUB], ., aiN, trong đó giá trị của aij sẽ là 1, 2, 3, 4, 5, 6, 7, 8 tương ứng lần lượt nếu ô (i, j) phải truyền tin cho ô kề cạnh bên trái, bên phải, bên trên, bên dưới, bên trên và bên dưới, bên trái và bên phải, bên trên và bên trái, bên dưới và bên phải (xem hình vẽ); còn nếu ô (i, j) không phải truyền tín hiệu thì aij = 0.

[TABLE=align: left]
[TR]
[TD][/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]






Kết quả: Ghi ra file văn bản P3.OUT gồm M dòng, mỗi dòng là một xâu gồm N ký tự 0 hoặc 1 mô tả trạng thái của lưới sau nhịp thời gian thứ T.
Ví dụ:
[TABLE]
[TR]
[TD]P3.INP[/TD]
[TD][/TD]
[TD]P3.OUT[/TD]
[/TR]
[TR]
[TD]2 2 5
101XX
2 4
2 1[/TD]
[TD][/TD]
[TD]11
01[/TD]
[/TR]
[/TABLE]

Quá trình biến đổi trạng thái được diễn tả trong hình dưới đây:

[TABLE]
[TR]
[TD]0[/TD]
[TD]0[/TD]
[TD][/TD]
[TD][/TD]
[TD]1[/TD]
[TD]0[/TD]
[TD][/TD]
[TD][/TD]
[TD]0[/TD]
[TD]1[/TD]
[TD][/TD]
[TD][/TD]
[TD]1[/TD]
[TD]0[/TD]
[TD][/TD]
[TD][/TD]
[TD]1[/TD]
[TD]1[/TD]
[TD][/TD]
[TD][/TD]
[TD]1[/TD]
[TD]1[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]0[/TD]
[TD]0[/TD]
[TD][/TD]
[TD][/TD]
[TD]0[/TD]
[TD]0[/TD]
[TD][/TD]
[TD][/TD]
[TD]0[/TD]
[TD]0[/TD]
[TD][/TD]
[TD][/TD]
[TD]0[/TD]
[TD]1[/TD]
[TD][/TD]
[TD][/TD]
[TD]1[/TD]
[TD]0[/TD]
[TD][/TD]
[TD][/TD]
[TD]0[/TD]
[TD]1[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[/TABLE]
Bài 4/1999 - Trò chơi bốc sỏi
(Dành cho học sinh Tiểu học)
Trên mặt đất có một đống sỏi có 101 viên. Hai em học sinh Hoàng và Huy chơi trò chơi như sau: Mỗi em đến lượt đi phải bốc ra từ đống sỏi trên tối thiểu là 1 viên và tối đa là 4 viên. Người thua là người phải bốc viên sỏi cuối cùng. Giả sử Hoàng là người được bốc trước, Huy bốc sau. Các em thử nghĩ xem ai là người thắng cuộc, Hoàng hay Huy? Và người thắng cuộc phải suy nghĩ gì và thực hiện các bước đi của mình ra sao?


Bài 5/1999 - 12 viên bi
(Dành cho học sinh THCS)
Có 12 hòn bi giống hệt nhau về kích thước, hình dáng và khối lượng. Tuy nhiên trong chúng lại có đúng một hòn bi kém chất lượng: hoặc nhẹ hơn hoặc nặng hơn bình thường. Dùng một cân bàn hai bên, bạn hãy dùng 3 lần cân để tìm ra được viên bi đó. Cần chỉ rõ rằng viên bi đó là nặng hơn hay nhẹ hơn.
Viết chương trình mô phỏng việc tổ chức cân các hòn bi trên. Dữ liệu về hòn bi kém chất lượng do người sử dụng chương trình nắm giữ. Yêu cầu trình bày chương trình đẹp và mỹ thuật.

Bài 6/1999 - Giao điểm các đường thẳng
(Dành cho học sinh THPT)
Trên mặt phẳng cho trước n đường thẳng. Hãy tính số giao điểm của các đường thẳng này. Yêu cầu tính càng chính xác càng tốt.
Các đường thẳng trên mặt phẳng được cho bởi 3 số thực A, B, C với phương trình Ax + By + C = 0, ở đây các số A, B không đồng thời bằng 0.
Dữ liệu vào của bài toán cho trong tệp B6.INP có dạng sau:
- Dòng đầu tiên ghi số n
- n dòng tiếp theo, mỗi dòng ghi 3 số thực A, B, C cách nhau bởi dấu cách.
Kết quả của bài toán thể hiện trên màn hình.
Bài 7/1999 - Miền mặt phẳng chia bởi các đường thẳng
(Dành cho học sinh THPT)
Xét bài toán tương tự như bài 6/1999 nhưng yêu cầu tính số miền mặt phẳng được chia bởi n đường thẳng này:
Trên mặt phẳng cho trước n đường thẳng. Hãy tính số miền mặt phẳng được chia bởi các đường thẳng này. Yêu cầu tính càng chính xác càng tốt.
Các đường thẳng trên mặt phẳng được cho bởi 3 số thực A, B, C với phương trình Ax + By + C = 0, ở đây các số A, B không đồng thời bằng 0.
Dữ liệu vào của bài toán cho trong tệp B7.INP có dạng sau:
- Dòng đầu tiên ghi số n
- n dòng tiếp theo, mỗi dòng ghi 3 số thực A, B, C cách nhau bởi dấu cách.
Kết quả của bài toán thể hiện trên màn hình.