TRẦN SĨ TÙNG –«— BÀI TẬP TIN HỌC Tin học & Nhà trường Tập III 151 – 200 2013 Tin hoïc & Nhaø tröôøng 1 Phần 1: ĐỀ BÀI Bài 151/2003 – Người nông dân và những quả táo Một người nông dân đến gặp đức vua và nói: ″Xin đức vua ban cho tôi 1 quả táo trong vườn Thượng uyển của ngài″. Nhà vua đồng ý. Người nông dân đi đến vườn và thấy muốn vào vườn phải lần lượt qua 3 cổng gác và ở mỗi cổng đều có một người lính canh. Người nông dân tiến đến người lính canh thứ nhất và nói: – ″Đức vua cho tôi lấy một quả táo ở trong vườn″ – ″Được, anh hái đi, nhưng khi đi ra phải đưa cho tôi một nửa số táo anh hái và thêm một quả nữa″, người lính canh trả lời.
Hai người lính canh kia cũng nói như vậy với người nông dân. Hỏi người nông dân phải hái bao nhiêu quả táo để khi ra khỏi vườn và đưa cho những người lính canh số táo đúng như họ yêu cầu, anh ta còn lại một quả? Bài 152/2003 – Chia kẹo Có N gói kẹo, gói thứ i có A[i] cái kẹo. Yêu cầu: Hãy tìm cách chia các gói kẹo này thành 2 phần sao cho độ chênh lệch giữa tổng số kẹo ở hai phần là ít nhất có thể được 0 <A[i] <1000, 2≤N≤10000 Dữ liệu vào: Cho trong file Chiakeo.inp: Một dòng duy nhất gồm các giá trị là số kẹo trong mỗi gói, các số cách nhau bởi một dấu cách (N = số gói kẹo đọc được) Dữ liệu ra: Ghi ra file Chiakeo.out – Dòng 1 lần lượt ghi 3 số: tổng số kẹo ở phần 1, phần 2 và độ chênh lệch giữa hai phần. – Dòng 2,3 là giá trị các gói kẹo ở mỗi phần được chia.
Ví dụ: Nguyễn Duy Phi Bài 153/2003 – Phân phối hàng Có N công trường cần vật liệu thi công. Công trường i cần cung cấp D[i] đơn vị hàng. Hàng được cung cấp từ hai kho A và B. Cước vận chuyển một đơn vị hàng từ kho A đến công trường i là A[i].
Cước vận chuyển một đơn vị hàng từ kho B đến công trường i là B[i]. Biết rằng kho A có R đơn vị hàng và tổng số hàng của hai kho đủ cung cấp cho N công trường. Yêu cầu: Hãy phân phối hàng từ hai kho đến các công trường sao cho tổng cước phí vận chuyển là ít nhất. Dữ liệu vào: File HANG.INP có cấu trúc như sau: Dòng 1: Ghi 2 số N, R (N≤ 10000) Dòng 2: Ghi N số D[1], D[2], …,D[N].
Dòng 3: Ghi N số A[1], A[2], …,A[N]. Dòng 4: Ghi N số B[1], B[2], …,B[N]. Dữ liệu ra: File HANG.OUT có cấu trúc như sau: Dòng 1: Ghi một số nguyên dương là tổng chi phí vận chuyển ít nhất. Dòng 2: Ghi N số nguyên không âm tương ứng số đơn vị hàng mà kho A cung cấp cho các 2 Tin hoïc & Nhaø tröôøng công trường 1,2…N.
Dòng 3: Ghi N số nguyên không âm tương ứng số đơn vị hàng mà kho B cung cấp cho các công trường 1,2…N. Ví dụ: Trần Đức Thiện − Xóm Chùa − Xã Hương Lạc − Huyện Lạng Giang − Bắc Giang. Bài 154/2003 – Tuổi cha và con Hai người đàn ông gặp nhau trên đường, một người hỏi ″Cậu đi đâu đấy″? − Mình đến trường mẫu giáo đón con, người kia trả lời − Cậu có mấy con và các con cậu mấy tuổi? − Mình có hai đứa. Tuổi của mình gấp 4 lần tuổi đứa lớn và gấp 7 lần tuổi đứa nhỏ, người bạn trả lời.
Bạn hãy cho biết người thứ hai và các con anh ta bao nhiêu tuổi? Bài 155/2003 – Bố trí phòng họp Có N cuộc họp đánh số từ 1 đến N đăng ký làm việc tại một phòng hội thảo. Cuộc họp i cần bắt đầu vào thời điểm Ai và kết thúc vào thời điểm Bi (i=1,2,…,N). Hai cuộc họp có thể nhận phục vụ nếu các khoảng thời gian làm việc tương ứng của chúng chỉ có thể giao nhau tại đầu mút hoặc tách rời nhau. Hãy tìm một lịch cho phòng hội thảo để có thể phục vụ nhiều cuộc họp nhất.
Dữ liệu vào từ file Activity.Inp gồm: – Dòng đầu tiên ghi giá trị N (N≤1000000) – Dòng thứ i trong N dòng tiếp theo ghi 2 số Ai và Bi cách nhau ít nhất một dấu cách. (A[i], B[i]≤ 32000 nguyên dương) Kết quả: Ghi ra file Activity.out gồm – Dòng đầu tiên ghi k là số cuộc họp tối đa có thể bố trí – Dòng tiếp theo ghi số hiệu của cuộc họp được phục vụ theo trình tự lịch bố trí Ví dụ: ACTIVITY.OUT 5 3 1 3 1 4 5 2 4 1 6 3 5 7 9 (Đề ra của Trần Quang Đức) Bài 156/2003 – Bày tranh Cho n bức tranh mã số từ 1. Người ta cần chọn ra một bức để đặt ở cửa phòng tranh, số còn lại được treo thẳng hàng trong phòng trên m vị trí định sẵn có mã số 1.m từ trái qua phải. Các bức tranh phải được treo theo trật tự nghiêm ngặt sau đây: tranh có số hiệu nhỏ phải treo ở trên tranh có số hiệu lớn.
Biết các thông tin sau về mỗi bức tranh: Tin hoïc & Nhaø tröôøng 3 – Tranh thứ i treo tại cửa sẽ đạt trị thẩm mỹ c[i]; – Tranh thứ i treo tại vị trí j sẽ đạt trị thẩm mỹ v[i,j]. – Các giá trị thẩm mỹ là những số tự nhiên không vượt quá 50. Yêu cầu: Hãy xác định một phương án treo tranh để có tổng trị thẩm mỹ là lớn nhất. Dữ liệu vào: Tệp văn bản ′ Picture.INP ′ – Dòng thứ nhất ghi n, m (cách nhau 1 dấu cách) – Dòng tiếp theo là n giá trị c.
– Tiếp đến là n dòng, dòng i gồm m vị trí v[i,1], v[i,2],. Dữ liệu ra: Tệp văn bản ′ Picture.OUT′ – Dòng thứ nhất ghi giá trị thẩm mỹ lớn nhất tìm được – Dòng thứ hai: ghi mã số hiệu bức tranh treo ở cửa phòng tranh. – Dòng thứ 3 ghi n–1 số tự nhiên sắp tăng chặt cho biết mã số các vị trí được chọn để treo tranh Ví dụ: Vũ Mạnh Hùng − lớp 10 A (Tin) − Trường THPTNK Ngô Sỹ Liên − tx Bắc Giang − Tỉnh Bắc Giang) Bài 157/2003 – Biến đổi xâu (Dành cho học sinh THPT) Với một xâu ký tự S cho trước, ta có thể thực hiện các phép biến đổi sau: − D: xoá một ký tự của xâu S. Ký hiệu D i trong đó i là vị trí ký tự cần xoá.
− I: chèn trước vị trí t của xâu S một ký tự c nào đó. Quy định thêm về vị trí chèn: nếu S có độ dài k, vị trí chèn có thể là 1, 2, 3,…,k+1, chèn ở vị trí k+1 có nghĩa là viết thêm vào cuối xâu S. − R: thay ký tự thứ t của S bởi ký tự c nào đó. Giả sử X và Y là hai xâu ký tự.
Độ dàu xâu X là n, độ dài xâu Y là m. Yêu cầu: Hãy tìm một dãy gồm ít nhất các phép biến đổi xâu X thành xâu Y. Dữ liệu vào ghi trong file ′XAU.INP′ gồm hai dòng: − Dòng thứ nhất là xâu X. − Dòng thứ hai là xâu Y.
Kết quả ghi ra file ′XAU. OUT′ − Dòng thứ nhất là K, đó là khoảng cách hai xâu. − K dòng tiếp theo mỗi dòng ghi ký hiệu một phép biến đổi theo trình tự thực hiện để biến xâu X thành xâu Y. Ví dụ: 4 Tin hoïc & Nhaø tröôøng Bài 158/2003 – Tuổi của hai anh em Các em nhỏ bắt đầu đi học khi được 6 tuổi (tính theo năm âm lịch).
Sơn học ở lớp mà số của lớp bằng tuổi của em Dũng. Hỏi khi anh Sơn học xong phổ thông (hết lớp 12) thì em Dũng học xong lớp mấy? Bài 159/2003 – Dãy con lồi Dãy giá trị nguyên A=(A1, A2, …, AN) được gọi là lồi, nếu nó giảm dần từ A1 đến một Ai nào đó, rồi tăng dần tới AN. Ví dụ dãy lồi: 10 5 4 2 −1 4 6 8 12 Yêu cầu: Lập trình nhập vào một dãy số nguyên, bằng cách xóa bớt một số phần tử của dãy và giữ nguyên trình tự các phần tử còn lại, ta nhận được dãy con lồi dài nhất. Dữ liệu vào trong file: Dayloi.inp có dạng – Dòng đầu là N (N≤2000) – Dòng tiếp theo là N số nguyên của dãy số (các số kiểu integer) Kết quả ra file: Dayloi.out gồm: – Dòng đầu tiên ghi số phần tử lớn nhất của dãy con tìm được – Dòng tiếp theo ghi các số thuộc dãy con (không thay đổi trật tự các phần tử trong dãy ban đầu) Ví dụ Bài 160/2003 – Truyền tin trên mạng Trong một mạng gồm n máy tính đánh số từ 1 đến N.
Sơ đồ nối mạng đựơc cho bởi hệ thống gồm M kênh nối trực tiếp giữa một số cặp máy tính trong mạng. Biết chi phí truyền một đơn vị thông tin theo mỗi kênh nối của mạng. Người ta cần chuyển một bức thông điệp từ máy S đến T. Để đảm bảo an toàn, người ta muốn chuyển bức thông điệp này theo K đường truyền tin khác nhau.
Hai đường truyền tin được gọi là khác nhau nếu không có bất cứ kênh nối trực tiêp nào được dùng chung trên cả hai đường truyền tin. Chi phí của một đường truyền tin được hiểu là chi phí trên các kênh của nó. Yêu cầu : Giả sử bức thông điệp có độ dài là 1 đơn vị thông tin, hãy tìm cách chuyển thông tin từ S đến T sao cho tổng chi phí chuyển thông tin (bằng tổng chi phí theo cả K đường truyền tin) là nhỏ nhất. Dữ liệu: Vào từ file văn bản Ttin.INP: – Dòng đầu tiên ghi năm số N,M,S,T,K cách nhau bởi dấu cách (N≤100).
– M dòng sau mỗi dòng ghi ba số di, ci, gi: trong đó di, ci là chỉ số của hai máy tương ứng có kênh nỗi và gi (nguyên dương) là chi phí để truyền một đơn vị thông tin từ máy di đến máy ci và ngựơc lại (i=1. Kết quả: Ghi ra file văn bản TTIN.OUT: – Dòng đầu tiên ghi chi phí truyền thông điệp theo cách tìm đựơc – K dòng tiếp theo, mỗi dòng ghi đường truyền tin dưới dạng dãy có thứ tự các máy bắt đầu từ máy S và kết thúc ở máy T. – Nếu không tìm đủ K đường đưa ra một dòng duy nhất: NO SOLUTION. Ví dụ: Tin hoïc & Nhaø tröôøng 5 Bài 161/2003 – Người bạn cũ Gặp lại người bạn cũ đã có hai đứa con, tôi hỏi tuổi ba mẹ con.
Là một nhà toán học, bạn tôi trả lời rằng tích của tuổi bạn tôi với tuổi hai đứa nhỏ là 2. Sau khi suy nghĩ một lát, tôi nói "Điều bạn nói đưa ra quá nhiều khả năng.
