Tuyển tập đề thi tin học quốc gia

Chia sẻ: Rose_12 Rose_12 | Ngày: | Loại File: PDF | Số trang:50

Thêm vào BST

Báo xấu

126
lượt xem 27
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài 1. Phân đoạn Tên file chương trình: SEGPAR.PAS Cho dãy số nguyên a1, a2, …, an và số nguyên dương k. Ta gọi k-phân đoạn của dãy số đã cho là cách chia dãy số đã cho ra thành k đoạn, mỗi đoạn là một dãy con gồm các phần tử liên tiếp của dãy. Chính xác hơn, một k-phân đoạn được xác định bởi dãy chỉ số 1 ≤ n1

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tuyển tập đề thi tin học quốc gia

http://vnoi.info Olympic tin học Việt Nam Tuyển tập đề thi tin học quốc gia (2005-2008)
http://vnoi.info Olympic tin học Việt Nam Đề thi vòng I quốc gia
http://vnoi.info Olympic tin học Việt Nam Năm 2005 Bảng A Bài 1. Phân đoạn Tên file chương trình: SEGPAR.PAS Cho dãy số nguyên a1, a2, …, an và số nguyên dương k. Ta gọi k-phân đoạn của dãy số đã cho là cách chia dãy số đã cho ra thành k đoạn, mỗi đoạn là một dãy con gồm các phần tử liên tiếp của dãy. Chính xác hơn, một k-phân đoạn được xác định bởi dãy chỉ số 1 ≤ n1 < n 2 < ... < n k = n . a ni −1 +1 , a ni −1 + 2 ,..., a ni , i = 1,2,..., k . Ở đây quy ước n0 = 0. Đoạn thứ i là dãy con Yêu cầu: Hãy xác định số M nhỏ nhất để tồn tại k-phân đoạn sao cho tổng các phần tử trong mỗi đoạn đều không vượt quá M. Dữ liệu: Vào từ file văn bản SEGPAR.INP. • Dòng đầu tiên chứa hai số nguyên n và k (1≤ k ≤ n ≤ 15000); • Dòng thứ i trong số n dòng tiếp theo chứa số nguyên ai (|ai| ≤ 30000), i =1, 2, …, n. Các số cạnh nhau trên một dòng trong file dữ liệu cách nhau ít nhất một dấu cách. Kết quả: Ghi ra file SEGPAR.OUT một số nguyên duy nhất là giá trị M tìm được. Ví dụ: SEGPAR.INP SEGPAR.OUT 94 5 1 1 1 3 2 2 1 3 1
http://vnoi.info Olympic tin học Việt Nam Bài 2: Pháo hoa Tên chương trình: FIREWK.PAS Nhằm chào mừng các ngày lễ lớn trong năm 2005 người ta đã chế tạo một loại đạn pháo hoa mới, khi bắn, đạn nổ thành bông hoa 2n cánh màu ( 1 ≤ n ≤ 30). Nguyên vật liệu cho phép tạo được m màu khác nhau, đánh số từ 1 đến m (2 ≤ m ≤ 32). Để đảm bảo tính mỹ thuật, việc chuyển tiếp màu giữa 2 cánh hoa kề nhau phải tuân theo quy tắc chuyển màu cầu vồng sau đây: • Bên cạnh cánh hoa màu i phải là cánh hoa màu i-1 hoặc i+1, với 1 < i < m, • Bên cạnh cánh hoa màu 1 chỉ có thể là cánh hoa màu 2, • Bên cạnh cánh hoa màu m chỉ có thể là cánh hoa màu m-1. Một bông hoa không nhất thiết phải có đầy đủ m màu. Mỗi bông hoa tương ứng với một vòng tròn 2n số thể hiện màu của các cánh hoa. Ví dụ, hình 1 là bông hoa 24 cánh (n = 12) và hình 2 là vòng tròn số tương ứng với nó. Mỗi bông hoa được mô tả bằng dãy 2n số nguyên liệt kê các chỉ số màu của các cánh hoa theo chiều kim đồng hồ. Ví dụ, bông hoa ở hình 1 có thể được mô tả bằng dãy số 3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 4 3 2. Dãy có thứ tự từ điển nhỏ nhất trong các dãy có thể dùng để mô tả hoa được gọi là mã hoa. Khi đó, mã hoa của bông hoa ở hình 1 sẽ là 1 2 3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 4 3 2 3 4 3 2. Trong các ngày lễ, Ban tổ chức yêu cầu bắn các đạn pháo hoa 2n cánh có đúng k cánh màu C (0 ≤ k ≤ 2). Các mã hoa thỏa mãn yêu cầu vừa nêu cũng được sắp xếp theo thứ tự từ điển và đánh số bắt đầu từ 1. Hơn nữa, nhằm tạo ra các hoa không giống nhau, đội bắn pháo hoa cần đảm bảo hai viên đạn pháo hoa bắn liên tiếp phải có mã khác nhau. Do vậy, người ta đã thiết kế một Hệ thống chụp ảnh và phân tích tự động để báo cho đội bắn pháo hoa biết số thứ tự của viên đạn pháo hoa vừa nổ trên trời. Em được giao viết chương trình giải quyết nhiệm vụ chính trong phần mềm phân tích tự động này. Yêu cầu: Cho biết n, m, k và C. Gọi X là tập tất cả các mã hoa 2n cánh có đúng k cánh màu C. • Hãy xác định số lượng p các phần tử của X; • Cho một mã hoa nào đó trong tập X. Hãy xác định số thứ tự từ điển của nó trong X. Dữ liệu: Vào từ file văn bản FIREWK.INP. Dòng đầu tiên chứa 4 số nguyên n, m, k, C; dòng tiếp theo chứa 2n số nguyên mô tả một mã hoa. Các số trên một dòng của file dữ liệu cách nhau ít nhất một dấu cách. Kết quả: Đưa ra file văn bản FIREWK.OUT. Dòng đầu tiên ghi số nguyên p; dòng tiếp theo ghi số thứ tự tìm được của mã hoa. Ví dụ: FIREWK.INP FIREWK.OUT 3401 4 234343 3
http://vnoi.info Olympic tin học Việt Nam Bài 3. Bộ sưu tập Tên chương trình: COLLECT.PAS Một bộ sưu tập tiền xu cổ được coi là có giá trị phải gồm không ít hơn Z 0 đồng tiền vàng, S 0 đồng tiền bạc và M 0 đồng tiền đồng. Bộ sưu tập ban đầu của Alibaba có một số lượng nhất định các đồng tiền vàng, bạc và đồng nhưng chưa phải là một bộ sưu tập có giá trị. Tại Trụ sở của Hiệp hội những người sưu tầm tiền cổ có đặt một máy đổi tiền để giúp hội viên đổi được các bộ sưu tập có giá trị. Tuy nhiên, máy đổi chỉ hỗ trợ việc đổi tiền trọn gói theo quy tắc đổi gói ( Z 1 , S1 , M 1 ) lấy gói ( Z 2 , S 2 , M 2 ) đồng tiền. Các quy tắc đổi tiền khác nhau từng đôi một, được gán số hiệu tuần tự 1,2,3, . . . và được công bố trước. Hội viên có thể tạo gói tiền thích hợp từ bộ sưu tập của mình để thực hiện việc đổi tiền. Các đồng tiền nhận được sau mỗi lần đổi được gộp lại với các đồng tiền mà hội viên đang có để thành một bộ sưu tập mới và có thể được sử dụng để đổi trong những lần sau nếu cần. Số lần đổi không hạn chế, tuy nhiên, là người thực dụng, Alibaba luôn cố gắng giảm tới mức tối đa số lần đổi tiền. Mặt khác, để ngăn chặn việc đầu cơ, Hiệp hội quy định, trong mọi thời điểm, mỗi hội viên không được giữ quá 4 đồng tiền mỗi loại và không được phép đổi tiếp khi đã đổi được một bộ sưu tập có giá trị. Yêu cầu: Cho biết số lượng Z , S , M các đồng tiền vàng, bạc, đồng mà Alibaba có ban đầu và các quy tắc đổi tiền. Hãy chỉ ra tất cả các bộ sưu tập tiền cổ có giá trị mà Alibaba có thể có được sau một số lần đổi không vượt quá k cho trước. Dữ liệu: Vào từ file văn bản COLLECT.INP. • Dòng đầu ghi số nguyên dương k (k ≤ 1000) ; dòng thứ 2 ghi 6 số nguyên không âm Z , S , M , Z 0 , S 0 , M 0 ( 0 ≤ Z , S , M , Z 0 , S 0 , M 0 ≤ 4) ; • Các dòng tiếp theo mỗi dòng ghi 6 số nguyên không âm Z 1 , S1 , M 1 , Z 2 , S 2 , M 2 xác định một quy tắc đổi tiền ( 0 ≤ Z 1 , Z 2 , S1 , S 2 , M 1 , M 2 ≤ 4 ). Kết quả: Đưa ra file văn bản COLLECT.OUT. Nếu không tồn tại cách đổi để có được bộ sưu tập có giá trị, file kết quả chỉ gồm một số -1. Trong trường hợp ngược lại, dòng đầu ghi số v là số các bộ tiền cổ có giá trị mà Alibaba có thể đổi được. Dòng thứ i trong v dòng tiếp theo ghi 4 số nguyên Z i , S i , M i , k i mô tả bộ sưu tập có giá trị thứ i và số lần đổi k i ít nhất không vượt quá k cần thực hiện để có được bộ sưu tập ấy. Các số trên một dòng của file dữ liệu và file kết quả đặt cách nhau ít nhất một dấu cách. Ví dụ: COLLECT.INP COLLECT.OUT 2 1 401333 3331 101111 201133
http://vnoi.info Olympic tin học Việt Nam Bài 4. Khuôn thép Tên chương trình: STEEL.PAS Để chuNn bị cho Lễ hội kỷ niệm 30 năm ngày Chiến dịch Hồ Chí Minh toàn thắng, giải phóng miền Nam, thống nhất đất nước, người ta cần gia công các loại khuôn thép có hình dạng là các hình đa giác lồi M đỉnh. Mỗi khuôn thép được thiết kế trên một tấm thép cũng có hình dạng là một hình đa giác lồi N đỉnh, không có cạnh nào của khuôn thép nằm gọn trên một cạnh của tấm thép. Để tiện cho việc gia công, khuôn thép được vẽ sao cho hai đường thẳng chứa hai cạnh không kề nhau của nó không cắt nhau ở bên trong tấm thép. Công việc chính cần làm trong quá trình gia công là sử dụng máy cắt để cắt được khuôn thép từ tấm thép ra. Rõ ràng là cần phải thực hiện M nhát cắt. Mỗi nhát cắt được thực hiện bằng cách chọn một cạnh nào đó của khuôn thép và cắt theo đường thẳng chứa cạnh ấy chia tấm thép thành hai phần, một phần chứa khuôn thép cần gia công. Chi phí cắt khuôn thép là tổng chiều dài của các đường cắt. Trên hình 1 và 2, tấm thép là tứ giác được tô nhạt, khuôn thép là hình vuông được tô bằng các gạch đậm. Các nét gạch đứt là các đường cắt với tổng chi phí bằng 6.5 đơn vị. Yêu cầu: Cho biết hình dạng tấm thép và khuôn thép cần gia công. Hãy tìm phương án cắt khuôn thép có chi phí nhỏ nhất. Dữ liệu: Vào từ file văn bản STEEL.INP: Dòng đầu ghi số N (3 ≤ N ≤ 2000) là số đỉnh của tấm thép; N dòng tiếp theo, mỗi dòng ghi 2 số thực x và y (−10 4 < x, y < 10 4 ) , là toạ độ N đỉnh của tấm thép được liệt kê theo chiều kim đồng hồ bắt đầu từ một đỉnh nào đó; dòng tiếp theo ghi số M (3 ≤ M ≤ 2000) là số đỉnh của khuôn thép; cuối cùng là M dòng, mỗi dòng ghi 2 số thực x và y (−10 4 < x, y < 10 4 ) là toạ độ M đỉnh của khuôn thép được liệt kê theo chiều kim đồng hồ bắt đầu từ một đỉnh nào đó. Các số trên một dòng cách nhau ít nhất một dấu cách. Kết quả: Đưa ra file văn bản STEEL.OUT chi phí nhỏ nhất tìm được với độ chính xác tới 4 chữ số sau dấu chấm thập phân. Ví dụ: STEEL.INP STEEL.OUT 4 6.5000 2 1 2 5 5 3.5 5 2 4 3 3 3 4 4 4 4 3
http://vnoi.info Olympic tin học Việt Nam Bảng B Bài 1. Đóng gói sản ph m Tên file chương trình: ZXY.PAS Ở đầu ra của một dây chuyền sản xuất trong nhà máy ZXY có một máy xếp tự động. Sau khi kết thúc việc gia công trên dây chuyền, các sản phNm sẽ được xếp vào các hộp có cùng dung lượng M. Sản phNm rời khỏi dây chuyền được xếp vào hộp đang mở (khi bắt đầu ca làm việc có một hộp rỗng được mở sẵn) nếu như dung lượng của hộp còn đủ để chứa sản phNm. Trong trường hợp ngược lại, máy sẽ tự động đóng nắp hộp hiện tại, cho xuất xưởng rồi mở một hộp rỗng mới để xếp sản phNm vào. Trong một ca làm việc có n sản phNm đánh số từ 1 đến n theo đúng thứ tự mà chúng rời khỏi dây chuyền. Sản phNm thứ i có trọng lượng là ai, i = 1, 2, …, n. Ban Giám đốc nhà máy qui định rằng sản phNm xuất xưởng của mỗi ca làm việc phải được xếp vào trong không quá k hộp. Yêu cầu: Hãy giúp người quản đốc của ca làm việc xác định giá trị M nhỏ nhất sao cho số hộp mà máy tự động cần sử dụng để xếp dãy n sản phNm xuất xưởng của ca không vượt quá số k cho trước. Dữ liệu: Vào từ file văn bản ZXY.INP: • Dòng đầu tiên chứa hai số nguyên n và k, (1≤ k ≤ n ≤ 15000); • Dòng thứ i trong n dòng tiếp theo chứa số nguyên dương ai (ai ≤30000), i =1, 2, …, n. Các số trên một dòng cách nhau ít nhất một dấu cách. Kết quả: Ghi ra file ZXY.OUT một số nguyên duy nhất là dung lượng của hộp. Ví dụ: ZXY.INP ZXY.OUT 94 5 1 1 1 3 2 2 1 3 1
http://vnoi.info Olympic tin học Việt Nam Bài 2. Chữ số Tên chương trình: DIGIT.PAS Cho xâu M không quá 127 ký tự lấy từ tập F = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}và không bắt đầu bằng ký tự 0. Gọi S là xâu với giá trị ban đầu là xâu M. Người ta biến đổi M theo quy tắc sau: đếm số lần xuất hiện các ký tự 0, 1, 2, . . . , F, gọi Ki là số lần xuất hiện ký tự i (với i lần lượt là 0, 1, 2, . . . F). Với các Ki ≠ 0 người ta viết liên tiếp xâu biểu diễn số Ki trong cơ số 16 và ký tự i. Xâu kết quả thu được là giá trị mới của M. Sau mỗi lần biến đổi người ta lại viết tiếp M vào sau S. Ví dụ, với M = '150A', S nhận giá trị ban đầu là '150A'. Sau lần biến đổi thứ nhất ta có M là '1011151A' và S ='150A1011151A'. Sau lần biến đổi thứ 2 ta có M là '1051151A' và S ='150A1011151A1051151A'. Sau lần biến đổi thứ 3 ta có M là '1041251A' và S = ‘150A1011151A1051151A1041251A’. Yêu cầu: Cho xâu M, số lần biến đổi L ( 0 ≤ L ≤ 107) và X là một ký tự từ tập F. Hãy đếm số lần xuất hiện X trong S thu được sau L lần biến đổi M. Dữ liệu: Vào từ file văn bản DIGIT.INP : • Dòng thứ nhất chứa xâu M, • Dòng thứ 2 chứa số nguyên L • Dòng thứ 3 chứa ký tự X. Kết quả: Đưa ra file văn bản DIGIT.OUT một số nguyên - số lần xuất hiện X. Ví dụ: DIGIT.INP DIGIT.OUT 150A 1 3 2
http://vnoi.info Olympic tin học Việt Nam Bài 3. Đổi đất Tên file chương trình: LAND.PAS Hai bộ lạc Anpha và Bêta sống rất hoà thuận với nhau. Một phần ranh giới của hai bộ lạc là một đường gấp khúc không tự cắt. Đường gấp khúc nhận được bằng cách lần lượt nối N điểm đôi một khác nhau A1 , A2 ,..., AN . Điểm Ai được xác định bởi hoành độ xi và tung độ yi ( xi là các số nguyên thoả mãn điều kiện: xi ≤ xi +1 ). Phần đất của bộ lạc Anpha nằm ở phía trên đường gấp khúc. Nhân dịp năm mới, tù trưởng hai bộ lạc quyết định thay đổi đường ranh giới cũ bằng cách xây dựng một đường cao tốc là làm đường nối thẳng từ A1 tới AN và lấy đường cao tốc này ranh giới mới. Dĩ nhiên, sự thay đổi này sẽ chuyển một số phần đất của bộ lạc Anpha cho bộ lạc Bêta và ngược lại. Hai tù trưởng thoả thuận phần diện tích chênh lệch do việc thay đổi đường ranh giới sẽ được điều chỉnh trong tương lai bằng m ột cách khác. Anpha Yêu cầu: Hãy tính diện tích phần đất SA của bộ lạc trở thành đất của bộ lạc Bêta và diện tích phần đất khi SB của bộ lạc Bêta trở thành đất của bộ lạc Anpha sau thay đổi đường ranh giới giữa hai bộ lạc. Dữ liệu: Vào từ file văn bản LAND.INP trong đó : Dòng đầu chứa số N ( N ≤ 10000) ; Dòng thứ i trong N dòng tiếp theo chứa hai số nguyên xi và yi đặt cách nhau ít nhất 1 dấu cách (−32000 ≤ xi , yi ≤ 32000) . Kết quả: Đưa ra file văn bản LAND.OUT trong đó dòng thứ nhất chứa SA , dòng thứ hai chứa SB . Kết quả được lấy chính xác với 4 chữ số sau dấu chấm thập phân. Ví dụ : LAND.INP LAND.OUT 6 8.0000 0 0 9.0000 2 4 5 1 7 11 10 8 11 11
http://vnoi.info Olympic tin học Việt Nam Bài 4. Bộ sưu tập Tên chương trình: COLLECT.PAS Một bộ sưu tập tiền xu cổ được coi là có giá trị phải gồm không ít hơn Z 0 đồng tiền vàng, S 0 đồng tiền bạc và M 0 đồng tiền đồng. Bộ sưu tập ban đầu của Alibaba có một số lượng nhất định các đồng tiền vàng, bạc và đồng nhưng chưa phải là một bộ sưu tập có giá trị. Tại Trụ sở của Hiệp hội những người sưu tầm tiền cổ có đặt một máy đổi tiền để giúp hội viên đổi được các bộ sưu tập có giá trị. Tuy nhiên, máy đổi chỉ hỗ trợ việc đổi tiền trọn gói theo quy tắc đổi gói ( Z 1 , S1 , M 1 ) lấy gói ( Z 2 , S 2 , M 2 ) đồng tiền. Các quy tắc đổi tiền khác nhau từng đôi một, được gán số hiệu tuần tự 1,2,3, . . . và được công bố trước. Hội viên có thể tạo gói tiền thích hợp từ bộ sưu tập của mình để thực hiện việc đổi tiền. Số lần đổi tiền là không hạn chế, tuy nhiên, để ngăn chặn việc đầu cơ, Hiệp hội quy định mỗi hội viên không được giữ quá 4 đồng tiền mỗi loại. Các đồng tiền nhận được sau mỗi lần đổi được gộp lại với các đồng tiền mà hội viên đang có để thành một bộ sưu tập mới và có thể được sử dụng để đổi trong những lần sau nếu cần. Yêu cầu: Cho biết số lượng Z , S , M các đồng tiền vàng, bạc, đồng mà Alibaba có ban đầu và các quy tắc đổi tiền. Hãy chỉ ra một phương án đổi tiền nào đó để Alibaba có được bộ sưu tập có giá trị. Dữ liệu vào đảm bảo luôn có phương án. Dữ liệu: Vào từ file văn bản COLLECT.INP: Dòng đầu ghi 6 số nguyên không âm Z , S , M , Z 0 , S 0 , M 0 (0 ≤ Z , S , M , Z 0 , S 0 , M 0 ≤ 4) ; • Các dòng tiếp theo mỗi dòng ghi 6 số nguyên không âm Z 1 S1 M 1 Z 2 S 2 M 2 xác định một quy tắc đổi • tiền. Kết quả: Đưa ra file văn bản COLLECT.OUT một dòng ghi dãy số hiệu các quy tắc theo thứ tự đã sử dụng trong phương án đổi tiền. Các số trên một dòng của file dữ liệu và file kết quả đặt cách nhau ít nhất một dấu cách. Ví dụ: COLLECT.INP COLLECT.OUT 401333 34 101022 011003 201123 100110
http://vnoi.info Olympic tin học Việt Nam Năm 2006 Bảng A Bài 1. Dãy con dài nhất Cho dãy số nguyên a1, a2, ..., an. Dãy số ai, ai+1, ..., aj với 1≤ i ≤ j ≤ n được gọi là dãy con của dãy số đã cho và khi đó, j-i+1 được gọi là độ dài, còn j ∑a được gọi là trọng lượng của dãy con này. k k =i Yêu cầu: Cho số nguyên p, trong số các dãy con của dãy số đã cho có trọng lượng không nhỏ hơn p hãy tìm dãy con có độ dài lớn nhất. Dữ liệu: Vào từ file văn bản MAXSEQ.INP: • Dòng đầu tiên ghi hai số nguyên n và p cách nhau bởi dấu cách; • Dòng thứ i trong số n dòng tiếp theo chứa số nguyên ai là số hạng thứ i của dãy số đã cho, i = 1, 2, ..., n. Kết quả: Ghi ra file văn bản MAXSEQ.OUT số nguyên k là độ dài của dãy con tìm được (qui ước: nếu không có dãy con nào thoả mãn điều kiện đặt ra thì k = -1) . Ví dụ: MAXSEQ.INP MAXSEQ.OUT MAXSEQ.INP MAXSEQ.OUT 56 4 49 -1 -2 2 3 3 2 2 -2 -2 3 Hạn chế: Trong tất cả các test: 1 ≤ n ≤ 20000; | ai | ≤ 20000; | p | ≤ 109. Có 50% số lượng test với n ≤ 1000.
http://vnoi.info Olympic tin học Việt Nam Bài 2. Đường đi trên lưới Cho một lưới ô vuông gồm m dòng và n cột. Các dòng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm ở vị trí dòng i và cột j của lưới được gọi là ô (i,j) và khi đó, i được gọi là toạ độ dòng còn j được gọi là toạ độ cột của ô này. Trên ô (i,j) của lưới ghi số nguyên dương aij, i = 1, 2, ..., m; j = 1, 2, ..., n. Trên lưới đã cho, từ ô (i,j) ta có thể di chuyển đến ô (p,q) nếu các điều kiện sau đây được thoả mãn: j < n; i ≤ p; j ≤ q v à i + j < p + q; • aij và apq có ước số chung lớn hơn 1. • Ta gọi một cách di chuyển từ mép trái sang mép phải của lưới là cách di chuyển bắt đầu từ một ô có toạ độ cột bằng 1 qua các ô của lưới tuân theo qui tắc di chuyển đã nêu và kết thúc ở một ô có toạ độ cột bằng n. Yêu cầu: Tính số cách di chuyển từ mép trái sang mép phải của lưới. Dữ liệu: Vào từ file văn bản NETPATH.INP: Dòng đầu tiên ghi 2 số nguyên dương m, n. • Dòng thứ i trong số m dòng tiếp theo ghi n số nguyên dương ai1, ai2, ..., ain là các số trên dòng • thứ i của lưới, i = 1, 2, ..., m. Hai số liên tiếp trên cùng một dòng được ghi cách bởi ít nhất một dấu cách. Kết quả: Ghi ra file văn bản NETPATH.OUT số nguyên k là số lượng cách di chuyển tìm được, biết rằng dữ liệu đảm bảo k < 109. Ví dụ: NETPATH.INP NETPATH.OUT NETPATH.INP NETPATH.OUT 22 4 22 0 24 25 68 67 Hạn chế: Trong tất cả các test: 1 < m, n ≤ 100; aij ≤ 30000, i=1,2,...,m; j=1,2,...,n. Có 50% số lượng test với m, n ≤ 50.
http://vnoi.info Olympic tin học Việt Nam Bài 3. Mạng máy tính Một hệ thống n máy tính (các máy tính được đánh số từ 1 đến n) được nối lại thành một mạng bởi m kênh nối, mỗi kênh nối hai máy nào đó và cho phép truyền tin một chiều từ máy này đến máy kia. Giả sử s và t là hai máy tính trong mạng. Ta gọi đường truyền tin từ máy s đến máy t là một dãy các máy tính và các kênh nối chúng có dạng: s = u1, e1, u2, ...,ui, ei, ui+1, ..., uk-1, ek-1, uk= t, trong đó u1, u2, ..., uk là các máy tính trong mạng, ei – kênh truyền tin từ máy ui đến máy ui+1 (i = 1, 2, ..., k-1). Mạng máy tính được gọi là thông suốt nếu như đối với hai máy u, v bất kỳ ta luôn có đường truyền tin từ u đến v và đường truyền tin từ v đến u. Mạng máy tính được gọi là hầu như thông suốt nếu như đối với hai máy u, v bất kỳ, hoặc là có đường truyền tin từ u đến v hoặc là có đường truyền tin từ v đến u. Biết rằng mạng máy tính đã cho là hầu như thông suốt nhưng không là thông suốt. Yêu cầu: Hãy xác định xem có thể bổ sung đúng một kênh truyền tin để biến mạng đã cho trở thành thông suốt được hay không? Dữ liệu: Vào từ file văn bản ONEARC.INP: • Dòng đầu tiên chứa 2 số nguyên dương n và m. • Dòng thứ i trong số m dòng tiếp theo mô tả kênh nối thứ i bao gồm hai số nguyên dương ui, vi cho biết kênh nối thứ i cho phép truyền tin từ máy ui đến máy vi, i=1,2,...,m. Các số trên cùng một dòng được ghi cách nhau bởi dấu cách. Kết quả: Ghi ra file văn bản ONEARC.OUT: • Dòng đầu tiên ghi ‘YES’ nếu câu trả lời là khẳng định, ghi ‘NO’ nếu câu trả lời là phủ định. • Nếu câu trả lời là khẳng định thì dòng thứ hai ghi hai số nguyên dương u, v cách nhau bởi dấu cách cho biết cần bổ sung kênh truyền tin từ máy u đến máy v để biến mạng thành thông suốt. Ví dụ: ONEARC.INP ONEARC.OUT 32 YES 12 31 23 Hạn chế: Trong tất cả các test: n ≤ 2000, m ≤ 30000.Có 50% số lượng test với n ≤ 200.
http://vnoi.info Olympic tin học Việt Nam Bài 4. Xoá cặp ô Cho một bảng hình chữ nhật kích thước m×n ô vuông kích thước đơn vị. Các dòng được đánh số từ 1 đến m, từ trên xuống dưới. Các cột được đánh số từ 1 đến n, từ trái qua phải. Ô nằm ở vị trí dòng i và cột j của bảng được gọi là ô (i,j). Mỗi ô của bảng hoặc được số t ừ 0 để trống hoặc chứa một ký tự lấy từ tập Σ gồm các chữ đến 9 và các chữ cái la tinh in hoa từ A đến Z. Mỗi ký tự của 1 A B D cùng tập Σ xuất hiện ở không quá 4 ô trong bảng. Hai ô chứa 2 C 1 2 một ký tự được gọi là giống nhau. Hai ô giống nhau có thể 2 1 C 3 xoá được nếu chúng có cạnh chung hoặc tâm (giao điểm của hai đường chéo) của 2 ô này có thể nối với nhau 4 A bằng B D một đường gấp khúc gồm không quá 3 đoạn thẳng độ dài 1 2 3 4 5 6 nguyên, mỗi đoạn song song với cạnh của bảng, và ngoại m = 4, n = 6 trừ hai ô cần xoá, đường gấp khúc này chỉ qua các ô trống hay nằm ngoài bảng. Các ô bị xoá trở thành ô trống. Mỗi lần xoá một cặp ô của bảng được gọi là một bước. Hình bên nêu ví dụ với trường hợp m = 4 và n = 6. Bước đầu tiên có thể xoá hai ô chứa ký tự ‘A’ hoặc 2 ô chứa ký tự ‘B’ hay 2 ô chứa ký tự ‘D’. Hai ô chứa ký tự ‘C’ chỉ có thể xoá sớm nhất ở bước thứ 2, sau khi đã xoá các ô chứa ‘A’. Như vậy, để xoá trống 2 ô (2, 1) và (1,2) cần thực hiện tối thiểu 3 bước xoá. Yêu cầu: Cho hai số m, n và m xâu độ dài n mô tả các dòng của bảng và hai ô khác trống (r1, c1), (r2, c2). Hãy xác định số bước ít nhất cần thực hiện để biến đổi các ô (r1, c1) và (r2, c2) trở thành ô trống. Dữ liệu: Vào từ file văn bản DEL.INP: • Dòng đầu tiên chứa 6 số nguyên m, n, r1, c1, r2, c2, hai số liên tiếp được ghi cách nhau bởi dấu cách. • Dòng thứ i +1 chứa xâu n ký tự mô tả dòng thứ i của bảng (i = 1, 2, ..., m). Các ô trống được thể hiện bằng dấu chấm (‘.’). Kết quả: Đưa ra file văn bản DEL.OUT số nguyên k là số bước ít nhất tìm được (qui ước: nếu không tồn tại cách biến đổi thoả mãn yêu cầu đặt ra thì k=-1). Ví dụ: DEL.INP DEL.OUT DEL.INP DEL.OUT 452112 3 464246 3 ABD... ABCDUV C.12.. BADCVU ..21C. ABCDUV A.B.D. BADCVU Hạn chế: Trong tất cả các test: 0 < m ≤ 10, 0 < n ≤ 20. Có 60% số lượng test có m ≤ 8, n ≤ 10 và số lượng m×n các ô khác trống không quá . 2
http://vnoi.info Olympic tin học Việt Nam Bảng B Bài 1. Chọn ô Cho một bảng hình chữ nhật kích thước 4×n ô vuông. Các dòng được đánh số từ 1 đến 4, từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên mỗi ô (i,j) có ghi một số nguyên aij , i =1, 2, 3, 4; j =1, 2, ..., n. Một cách chọn ô là việc xác định một tập con khác rỗng S của tập tất cả các ô của bảng sao cho không có hai ô nào trong S có chung cạnh. Các ô trong tập S được gọi là ô được chọn, tổng các số trong các ô được chọn được gọi là trọng lượng của cách chọn. Ví dụ: Xét bảng với n=3 trong hình vẽ dưới đây 1 2 3 1 -1 9 3 2 -4 5 -6 3 7 8 9 4 9 7 2 Cách chọn cần tìm là tập các ô S = {(3,1), (1,2), (4,2), (3,3)} với trọng lượng 32. Yêu cầu: Hãy tìm cách chọn ô với trọng lượng lớn nhất. Dữ liệu: Vào từ file văn bản SELECT.INP: • Dòng đầu tiên chứa số nguyên dương n là số cột của bảng. • Dòng thứ j trong số n dòng tiếp theo chứa 4 số nguyên a1j, a2j, a3j, a4j, hai số liên tiếp cách nhau ít nhất một dấu cách, là 4 số trên cột j của bảng. Kết quả: Ghi ra file văn bản SELECT.OUT trọng lượng của cách chọn tìm được. Ví dụ: SELECT.INP SELECT.OUT SELECT.INP SELECT.OUT 3 32 3 30 -1 -4 7 9 5555 9587 5555 3 -6 9 2 5555 Hạn chế: Trong tất cả các test: n ≤ 10000, |aij|≤ 30000. Có 50% số lượng test với n ≤ 1000.
http://vnoi.info Olympic tin học Việt Nam Bài 2. Quân tượng Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (ri, ci), i = 1,2,..., m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân. Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t). Giả thiết là ở ô đích không có quân cờ. Nếu ngoài quân tượng không có quân nào khác trên bàn cờ thì chỉ có 2 trường hợp: hoặc là không thể tới được ô đích, hoặc là tới được sau không quá 2 nước đi (hình trái). Khi trên bàn cờ còn có các quân cờ khác, vấn đề sẽ không còn đơn giản như vậy. Yêu cầu: Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được. Dữ liệu: Vào từ file văn bản BISHOP.INP: • Dòng đầu tiên chứa 6 số nguyên n, m, p, q, s, t; • Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i. Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách. Kết quả: Đưa ra file văn bản BISHOP.OUT một số nguyên là số nước đi tìm được. Ví dụ: BISHOP.INP BISHOP.OUT 8 37214 3 5 4 3 4 4 7 Hạn chế: Trong tất cả các test: 1 ≤ n ≤ 200. Có 60% số lượng test với n ≤ 20.
http://vnoi.info Olympic tin học Việt Nam Bài 3. Kênh xung yếu Một hệ thống n máy tính (các máy tính được đánh số từ 1 đến n) được nối lại thành một mạng bởi m kênh nối, mỗi kênh nối hai máy nào đó và cho phép truyền tin một chiều từ máy này đến máy kia. Ta gọi một mạch vòng của mạng đã cho là một dãy các máy tính và các kênh nối chúng có dạng: u1, e1, u2, ...,ui, ei, ui+1, ..., uk-1, ek-1, uk, ek, u1 trong đó u1, u2, ..., uk là các máy tính khác nhau trong mạng, ei – kênh truyền tin từ máy ui đến máy ui+1 (i = 1, 2, ..., k-1), ek là kênh truyền tin từ máy uk đến máy u1. Một kênh truyền tin trong mạng được gọi là kênh xung yếu nếu như bất cứ mạch vòng nào của mạng cũng đều chứa nó. Yêu cầu: Hãy xác định tất cả các kênh xung yếu của mạng đã cho. Dữ liệu: Vào từ file văn bản CIRARC.INP: Dòng đầu tiên chứa 2 số nguyên dương n và m. • Dòng thứ i trong số m dòng tiếp theo mô tả kênh nối thứ i bao gồm hai số nguyên dương ui, vi • cho biết kênh nối thứ i cho phép truyền tin từ máy ui đến máy vi. Các số trên cùng một dòng được ghi cách nhau bởi dấu cách. Kết quả: Ghi ra file văn bản CIRARC.OUT: Dòng đầu tiên ghi số nguyên k là số lượng kênh xung yếu trong mạng đã cho. Ghi k = -1 nếu • mạng không chứa kênh xung yếu. Nếu k>0 thì mỗi dòng trong số k dòng tiếp theo ghi thông tin về một kênh xung yếu tìm được • theo qui cách mô tả giống như trong file dữ liệu vào. Ví dụ: CIRARC.INP CIRARC.OUT CIRARC.INP CIRARC.OUT 22 2 3 3 -1 12 12 1 2 21 21 2 3 1 3 Hạn chế: Trong tất cả các test: n ≤ 1000, m ≤ 20000. Có 50% số lượng test với n ≤ 200.
http://vnoi.info Olympic tin học Việt Nam Bài 4. Biến đổi bảng Cho một bảng hình chữ nhật kích thước m×n ô vuông kích thước đơn vị. Các dòng được đánh số từ 1 đến m, từ trên xuống dưới. Các cột được đánh số từ 1 đến n, từ trái qua phải. Mỗi ô của bảng hoặc chữ được để trống hoặc chứa một ký tự lấy từ tập Σ gồm các số từ 0 đến 9 và các chữ cái la tinh in hoa từ A đến Z. Hai ô chứa cùng một ký tự được gọi là giống nhau. Mỗi ký tự của 1 A B D tập Σ xuất hiện ở không quá 4 ô trong bảng. Hai ô giống 2 C 1 2 nhau có thể xoá được nếu chúng có cạnh chung hoặc có thể 2 1 C 3 nối các tâm (giao điểm của hai đường chéo) của chúng vớ i nhau bằng một đường gấp khúc gồm không quá 3 đoạn 4 A B D thẳng độ dài nguyên, mỗi đoạn song song với cạnh của 1 2 3 4 5 6 bảng và ngoại trừ hai ô cần xoá, đường gấp khúc chỉ qua các m = 4, n = 6 ô trống hay nằm ngoài bảng. Các ô bị xoá trở thành ô trống. Mỗi lần xoá một cặp ô của bảng được gọi là một bước. Hình bên nêu ví dụ với trường hợp m = 4 và n = 6. Bước đầu tiên có thể xoá hai ô chứa ký tự ‘A’, tiếp theo, lần lượt xoá các cặp ô chứa ‘B’, chứa ‘C’ và cặp ô chứa ‘D’. Ở ví dụ này, sau khi thực hiện 4 bước xoá có thể, trong bảng còn lại 4 ô không thể xoá được. Yêu cầu: Cho m, n và m xâu độ dài n mô tả các dòng của bảng. Hãy xác định số lượng ô lớn nhất có thể xoá được. Dữ liệu: Vào từ file văn bản CHANGE.INP: • Dòng đầu tiên chứa 2 số nguyên m, n được ghi cách nhau bởi dấu cách. • Dòng thứ i+1 chứa xâu n ký tự mô tả dòng thứ i của bảng (i = 1, 2, ..., m). Các ô trống được thể hiện bằng dấu chấm (‘.’). Kết quả: Đưa ra file văn bản CHANGE.OUT một số nguyên là số lượng ô lớn nhất có thể xoá được. Ví dụ: CHANGE.INP CHANGE.OUT CHANGE.INP CHANGE.OUT 45 8 46 24 ABD... ABCDUV C.12.. BADCVU ..21C. ABCDUV A.B.D. BADCVU Hạn chế: Trong tất cả các test: 0 < m ≤ 10, 0 < n ≤ 10. Có 60% số lượng test có m ≤ 5, n ≤ 6 và số m×n lượng các ô khác trống không quá . 2
http://vnoi.info Olympic tin học Việt Nam Năm 2007 Bài 1. Dãy con không giảm dài nhất (6 điểm) Cho dãy số nguyên dương a1, a2, ..., an. Dãy số ai, ai+1, ..., aj thỏa mãn ai ≤ ai+1 ≤ ... ≤ aj, với 1 ≤ i ≤ j ≤ n được gọi là dãy con không giảm của dãy số đã cho và khi đó số j-i+1 được gọi là độ dài của dãy con này. Yêu cầu: Trong số các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy số {uk} xác định bởi u1 = 1, uk = uk-1 + k (k ≥ 2), hãy tìm dãy con có độ dài lớn nhất. Dữ liệu: Vào từ file văn bản MAXISEQ.INP • Dòng đầu tiên chứa một số nguyên dương n (n ≤ 104); • Dòng thứ i trong n dòng tiếp theo chứa một số nguyên dương ai (ai ≤ 108) là số hạng thứ i của dãy số đã cho, i = 1, 2, ..., n. Kết quả: Ghi ra file văn bản MAXISEQ.OUT số nguyên d là độ dài của dãy con không giảm tìm được (quy ước rằng nếu không có dãy con nào thỏa mãn điều kiện đặt ra thì d = 0). Ví dụ: Cho dãy số có 8 phần tử: 2, 2007, 6, 6, 15, 16, 3, 21. Các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy {uk} là: 6, 6, 15 và 3, 21 (vì u2 = 3, u3 = 6, u5 = 15, u6 = 21). Dãy cần tìm là 6, 6, 15 có độ dài là 3. MAXISEQ.INP MAXISEQ.OUT 8 3 2 2007 6 6 15 16 3 21
http://vnoi.info Olympic tin học Việt Nam Bài 2. Siêu thị may mắn (7 điểm) An được mời tham gia trò chơi “Siêu thị may mắn” do đài truyền hình ZTV tổ chức. Siêu thị được đặt trong trường quay truyền hình có n mặt hàng được đánh số từ 1 đến n và mặt hàng thứ i được niêm yết giá là ci đồng, i = 1, 2, ..., n. Theo thể lệ của trò chơi, An được ban tổ chức tặng một thẻ mua hàng có giá trị là s đồng và phải dùng hết số tiền trong thẻ này để mua hàng trong siêu thị với điều kiện mặt hàng thứ i chỉ được mua với số lượng nhiều nhất là mi, i = 1, 2, …, n. An sẽ là người thắng cuộc nếu tìm được tổng số cách mua hàng thỏa mãn yêu cầu đặt ra và chỉ ra một cách mua hàng nếu có. Yêu cầu: Hãy giúp An trở thành người thắng cuộc khi cho bạn biết trước các giá trị n, s, ci và mi (1 ≤ n ≤ 500; 1 ≤ s ≤ 105; 1 ≤ ci ≤ 104; 1 ≤ mi ≤ 100) với i = 1, 2, …, n. Dữ liệu: Vào từ file văn bản SMARKET.INP • Dòng đầu tiên chứa hai số nguyên dương s và n; • Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên dương ci và mi với i = 1, 2, …, n. Kết quả: Ghi ra file văn bản SMARKET.OUT • Dòng đầu tiên ghi số nguyên d là tổng số cách mua hàng tìm được; • Nếu d ≥ 1 thì dòng thứ hai ghi một cách mua hàng tìm được là một dãy n số nguyên, trong đó số hạng thứ i là số lượng mặt hàng thứ i mua được trong cách mua hàng này, i = 1, 2, …, n. Hai số liên tiếp trên một dòng trong file dữ liệu và file kết quả cách nhau ít nhất một dấu cách. Ví dụ: SMARKET.INP SMARKET.OUT 12 3 2 41 020 62 21