List 150+ bài toán tin – Lê Minh Hoàng

pdf

166 trang phuongnguyen 1891

Download

Bạn đang xem 20 trang mẫu của tài liệu "List 150+ bài toán tin – Lê Minh Hoàng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

list_150_bai_toan_tin_le_minh_hoang.pdf

Nội dung text: List 150+ bài toán tin – Lê Minh Hoàng

150+Bài Toán Tin
Lê Minh Hoàng 150 +Bài Toán Tin Đạọạộ 2004 – 2006 1
LIST 150 + BÀI TOÁN TIN – LÊ MINH HOÀNG 001. TÍNH TOÁN SONG SONG 9 002. B NG S 10 003. CARGO 11 004. DÃY CON 12 005. XÂU FIBINACCI 13 006. VÒNG S NGUYÊN T 14 007. ÔI B N 15 008. C A S V N B N 16 009. VÒNG TRÒN CON 17 010. B TRÍ PHÒNG H P 18 011. MUA VÉ TÀU HO 19 012. XIN CH KÝ 21 013. L C N M KIM C Ư NG 22 014. R I S I 23 015. IP VIÊN 24 016. KHO NG CÁCH GI A HAI XÂU 25 017. X P L I B NG S 26 018. TH M KHU TRI N LÃM 27 019. DÒ MÌN 29 020. X P L I DÃY S 30 2
021. CO DÃY BÁT PHÂN 31 022. TUY N BAY 32 023. MÔ PH NG CÁC PHÉP TOÁN 33 024. DÃY CON C A DÃY NH PHÂN 34 025. T NG CÁC CH S 35 026. ƯNG I NHI U IM NH T 36 027. K HO CH THUÊ NHÂN CÔNG 37 028. DÃY CÁC HÌNH CH NH T 38 029. S N C T 39 030. C T V I 40 031. CHIA K O 41 032. B NG QUAN H 42 033. ONG N ƯC 43 034. TR TI N 44 035. HOÁN V CH CÁI 45 036. D TI C BÀN TRÒN 46 037. TRÁO BÀI 47 038. I X NG HOÁ 48 039. M NG MÁY TÍNH 49 040. L T Ô MI NÔ 50 041. S NH PHÂN L N NH T 51 042. S N CÁC HÌNH CH NH T 52 043. PHÂN HO CH TAM GIÁC 53 3
044. CÁC THÀNH PH N LIÊN THÔNG M NH 54 045. MÃ GRAY 55 046. D ÁN XÂY C U 56 047. B O T N NG V T HOANG DÃ 57 048. PHÁ T ƯNG 58 049. TRUY N TIN TRÊN M NG 59 050. HÌNH VUÔNG C C I 60 051. OÀN XE QUA C U 61 052. S L ƯNG 62 053. THÁM HI M LÒNG T 63 054. TH T T IN 64 055. DÃY L CH 65 056. RÚT G N DÃY S 66 057. BUÔN TI N 67 058. DÃY NGO C 68 059. TH NG B M VÀ PHÚ ÔNG 69 060. S TH P PHÂN 70 061. DANH SÁCH VÒNG 71 062. TÍNH DI N TÍCH 72 063. THANG MÁY 73 064. TR NG S XÂU 74 065. PH MAY M N 75 066. TÍN HI U GIAO THÔNG 76 4
067. PHÂN NHÓM 77 068. TUA DU L CH R NH T 78 069. DU L CH NHI U TUA NH T 79 070. PHÂN CÔNG 80 071. NH N TIN 81 072. CÁC S IN THO I 82 073. GIÁ TR L N NH T 83 074. NÚT GIAO THÔNG TR NG IM 84 075. T P K T 85 076. M I KHÁCH D TI C 86 077. KHÔI PH C NGO C 87 078. DÂY XÍCH 88 079. PHÂN CÔNG 89 080. DÂY CUNG 90 081. MÊ CUNG 91 082. DU L CH KI U ÚC 92 083. S A ƯNG 93 084. I THI 94 085. MÈO KI U ÚC 95 086. THÀNH PH TRÊN SAO HO 96 087. RÔ B T XÂY NHÀ 97 088. T Ư DUY KI U ÚC 98 089. 8-3, T NG HOA KI U ÚC 99 5
090. MÃ HOÁ BURROWS WHEELER 100 091. BAO L I 101 092. GIAI TH A 102 093. PH SÓNG 103 094. DÃY NGH CH TH 104 095. MUA HÀNG 105 096. XÂU CON CHUNG DÀI NH T 106 097. DÃY CON NG N NH T 107 098. BI N I DÃY S 108 099. GIÁ TR NH NH T 109 100. N I DÂY 110 101. GHI A 111 102. ƯNG I THOÁT MÊ CUNG 112 103. CHU TRÌNH C B N 113 104. C T CÂY S 114 105. L CH S A CH A Ô TÔ 115 106. KH P VÀ C U 116 107. HÀNG I V I ƯU TIÊN 117 108. H I CH 118 109. SERIE A 119 110. S HI U VÀ GIÁ TR 120 111. PHÉP CO 121 112. CH A NGO C 122 6
113. MÃ HOÁ BURROWS WHEELER 123 114. M NG RÚT G N 124 115. DÃY NGO C 125 116. L P RÁP MÁY TÍNH 126 117. ƯNG M T CHI U 127 118. PH 128 119. THÁP G CH 129 120. THU THU 130 121. PHÂN CÔNG 131 122. XÂU CON 132 123. L N SÚC S C 133 124. V S 134 125. GIAO L ƯU 135 126. GIAO L ƯU 136 127. I DI N 137 128. H I CH 138 129. L CH H C 139 130. MÃ LIÊN HOÀN 140 131. TUY N NHÂN CÔNG 141 132. ƯNG TRÒN 142 133. ON 0 143 134. H C B NG 144 135. ON D Ư NG 145 7
136. TÍN HI U GIAO THÔNG 146 137. PH 147 138. DI CHUY N RÔ-BT 148 139. TR M NGH 149 140. CHIA CÂN B NG 151 141. L N XÚC X C 152 142. CHUY N HÀNG 153 143. GHÉT NHAU NÉM Á 154 144. N I DÂY 155 145. MY LAST INVENTION 156 146. CÂY KHUNG NH NHT 158 147. M NG MÁY TÍNH 159 148. D Y N IU T NG DÀI NH T 160 149. LU NG C C I TRÊN M NG 161 150. B GHÉP C C I 162 151. B GHÉP Y TR NG S C C TI U 163 152. TUY N NHÂN CÔNG 164 153. DÀN ÈN 165 8
001. TÍNH TOÁN SONG SONG Bi ểu th ức đủ là m ột dãy ký t ự g ồm các bi ến ký hi ệu b ằng ch ữ cái th ường ti ếng Anh: a z, các phép toán c ộng ký hi ệu +, nhân ký hi ệu * và các d ấu ngo ặc (,). Được đị nh ngh a nh ư sau: i) M ỗi bi ến a,b, ,z là m ột bi ểu th ức đủ ii) N ếu X và Y là bi ểu th ức đủ thì (X+Y) và (X*Y) c ng là bi ểu th ức đủ . iii) Nh ững bi ểu th ức nào không xây d ựng được theo 2 nguyên t ắc trên không là bi ểu th ức đủ . VD: Theo cách định ngh a trên thì (a+(b+(c+d))) ho ặc ((a+b)+(c*d)) là các bi ểu th ức đủ . Cho bi ết th ời gian tính phép + là P, th ời gian tính phép * là Q, ng ời ta đị nh ngh a th ời gian tính toán m ột bi ểu th ức đủ nh sau: • Nếu bi ểu th ức đủ ch ỉ g ồm 1 bi ến (a z) thì th ời gian tính toán là 0 • Nếu X và Y là 2 bi ểu th ức đủ ; th ời gian tính X là TX th ời gian tính Y là TY thì th ời gian tính (X+Y) là max(TX,TY)+P th ời gian tính (X*Y) là max(TX,TY)+Q Từ 1 bi ểu th ức đủ ng ời ta có th ể bi ến đổ i v ề m ột bi ểu th ức t ơ ng đơ ng b ằng các lu ật: • Giao hoán: (X+Y) ⇔ (Y+X); (X*Y) ⇔ (Y*X) • Kết h ợp: (X+(Y+Z)) ⇔ ((X+Y)+Z); (X*(Y*Z)) ⇔ ((X*Y)*Z) Yêu c ầu: Cho tr ớc m ột bi ểu th ức đủ E d ới d ạng xâu ký t ự hãy vi ết ch ơ ng trình: 1. Tìm th ời gian tính toán biểu th ức E 2. Hãy bi ến đổ i bi ểu th ức E thành bi ểu th ức E' t ươ ng đươ ng v ới nó sao cho th ời gian tính E' là ít nh ất có th ể. Dữ li ệu vào đợc đặ t trong file v n b ản PO.INP nh sau: • Dòng th ứ nh ất ghi 2 s ố P, Q cách nhau 1 d ấu cách (P,Q ≤100) • Ti ếp theo là m ột s ố dòng, m ỗi dòng ghi 1 bi ểu th ức đủ . Kết qu ả ra đặ t trong file v n b ản PO.OUT nh ư sau: Với m ỗi bi ểu th ức E trong file PO.INP ghi ra file PO.OUT 3 dòng • Dòng th ứ nh ất: Ghi th ời gian tính toán E • Dòng th ứ hai: Ghi bi ểu th ức E' • Dòng th ứ ba: Ghi th ời gian tính toán E' Chú ý: Để cho g ọn, m ỗi bi ểu th ức đủ trong input/output file có th ể vi ết mà không c ần đế n c ặp dấu ngo ặc ngoài cùng, d ữ li ệu vào đợc coi là đúng đắn và không c ần ki ểm tra Ví d ụ: PO.INP PO.OUT 1 1 7 a+(a+(a+(a+(a+(a+(a+a)))))) ((a+a)+(a+a))+((a+a)+(a+a)) (((a+(b+(c+d)))*e)*f) 3 (((((a*b)*c)*d)+e)+(f*g)) 5 (e*f)*((a+b)+(c+d)) 3 5 ((a*b)*(c*d))+(e+(f*g)) 3 9
002. B NG S Cho m ột b ảng hình ch ữ nh ật kích th ước M x N v ới M, N nguyên d ươ ng. M, N ≤ 50. Hình ch ữ nh ật này được chia thành M x N ô vuông b ằng nhau v ới kích th ước đơn v ị b ởi các đường song song v ới các c ạnh, trên ô vuông [i, j] ghi s ố nguyên A[i, j] (2 ≤ A[i, j] ≤ 50). Từ m ảng A ta l ập m ảng B mà B[i, j] được xây d ựng nh ư sau: Bi ểu di ễn s ố A[i, j] thành t ổng các s ố nguyên t ố v ới ràng bu ộc: trong bi ểu di ễn đó có nhi ều nh ất ch ỉ một s ố nguyên t ố xu ất hi ện hai l ần. Trong các cách bi ểu di ễn, ch ọn ra bi ểu di ễn nhi ều h ạng t ử nh ất thì B[i, j] b ằng s ố s ố h ạng c ủa bi ểu di ễn này k ể c ả b ội (n ếu có). Ví d ụ: Nếu A[i, j] = 10 = 2 + 3 + 5 thì B[i, j] = 3; Nếu A[i, j] = 12 = 2 + 2 + 3 + 5 thì B[i, j] = 4; Chú ý: Không được bi ểu di ễn A[i, j] = 10 = 2 + 2 + 2 + 2 + 2 để có B[i, j] = 5 vì nh ư v ậy không tho ả mãn ràng bu ộc a) D ữ li ệu vào được cho b ởi Text file TABLE.INP trong đó: • Dòng đầu ghi hai s ố M, N • M dòng sau, dòng th ứ i ghi N ph ần t ử trên dòng i c ủa b ảng A: A[i, 1], A[i, 2], , A[i, N] hai ph ần t ử liên ti ếp cách nhau ít nh ất m ột d ấu tr ống. b) K ết qu ả ghi ra Text file TABLE.OUT Giá tr ị b ảng B, m ỗi dòng c ủa b ảng ghi trên m ột dòng c ủa file, hai ph ần t ử liên ti ếp cách nhau ít nh ất một d ấu tr ống. c) Hãy tìm hình ch ữ nh ật l ớn nh ất được t ạo b ởi các ô mang giá tr ị b ằng nhau c ủa b ảng B. Ghi ti ếp ra file OUT.B1 m ột dòng g ồm 5 s ố là: di ện tích l ớn nh ất tìm được, to ạ độ trên trái và d ưới ph ải c ủa hình ch ữ nh ật có di ện tích lớn nh ất đó. 10
003. CARGO Bản đồ m ột kho hàng hình ch ữ nh ật kích th ước mxn được chia thành các ô vuông đơ n v ị (m hàng, n cột: các hàng đánh s ố t ừ trên xu ống d ưới, các c ột đánh s ố t ừ trái qua ph ải). Trên các ô c ủa b ản đồ có một s ố ký hi ệu: • Các ký hi ệu # đánh d ấu các ô đã có m ột ki ện hàng x ếp s ẵn, • Một ký hi ệu *: Đánh d ấu ô đang có m ột xe đ y • Một ký hi ệu $: Đánh d ấu ô ch ứa ki ện hàng c ần x ếp • Một ký hi ệu @: Đánh d ấu v ị trí ô mà c ần ph ải x ếp ki ện hàng B vào ô đó • Các ký hi ệu d ấu ch ấm ".": Cho bi ết ô đó tr ống Cần phải dùng xe đy ở * để đ y ki ện hàng ở $ đế n v ị trí @ sao cho trong quá trình di chuy ển cng nh đy hàng, không ch ạm vào nh ững ki ện hàng đã đợc x ếp s ẵn. (Xe đ y có th ể di chuy ển sang m ột trong 4 ô chung c ạnh v ới ô đang đứ ng). N ếu có nhi ều ph ơ ng án thì chỉ ra m ột ph ơ ng án sao cho xe đy ph ải di chuy ển qua ít b ớc nh ất. Các h ướng di chuy ển được ch ỉ ra trong hình d ưới đây # # # # # # # # N # @ # # # WE # # # # # # * $ S Dữ li ệu: Vào t ừ file v n b ản CARGO.INP • Dòng 1: Ghi hai s ố nguyên d ươ ng m, n cách nhau m ột d ấu cách (m, n ≤ 80) • m dòng ti ếp theo, dòng th ứ i ghi đủ n ký hi ệu trên hàng th ứ i c ủa b ản đồ theo đúng th ứ t ự t ừ trái qua ph ải. Các ký hi ệu được ghi li ền nhau Kết qu ả: Ghi ra file v n b ản CARGO.OUT • Dòng 1: Ghi s ố b ước di chuy ển xe đ y để th ực hi ện m ục đích yêu c ầu, n ếu không có ph ươ ng án kh ả thi thì dòng này ghi s ố -1 • Dòng 2: N ếu có ph ươ ng án kh ả thi thì dòng này ghi các ký t ự li ền nhau th ể hi ện h ướng di chuy ển c ủa xe đ y R ( East , West , South , North). Các ch ữ cái th ường (e,w,s,n) th ể hi ện b ước di chuy ển không đ y hàng, các ch ữ cái in hoa (E,W,S,N) th ể hi ện b ước di chuy ển có đ y hàng. Ví d ụ: CARGO.INP CARGO.OUT CARGO.INP CARGO.OUT 8 8 23 5 9 22 ######## sswwwwwwNNNwnEseNwnEEEE @ eeNNNssseeeennnnwwwWWW # @. .##.###.# ### # .##$###.# #.#####* .* .$ 11
004. DÃY CON Cho m ột dãy g ồm n ( n ≤ 1000) s ố nguyên d ươ ng A 1, A 2, , A n và s ố nguyên d ươ ng k (k ≤ 50). Hãy tìm dãy con g ồm nhi ều ph ần t ử nh ất c ủa dãy đã cho sao cho t ổng các ph ần t ử c ủa dãy con này chia h ết cho k. Dữ li ệu vào: file v n b ản DAY.INP • Dòng đầu tiên ch ứa hai s ố n, k ghi cách nhau b ởi ít nh ất 1 d ấu tr ống. • Các dòng ti ếp theo ch ứa các s ố A 1, A 2, , A n được ghi theo đúng th ứ t ự cách nhau ít nh ất m ột dấu tr ống ho ặc xu ống dòng (CR-LF). Kết qu ả: ghi ra file v n b ản DAY.OUT • Dòng đầu tiên ghi m là s ố ph ần t ử c ủa dãy con tìm được. • Các dòng ti ếp theo ghi dãy m ch ỉ s ố các ph ần t ử c ủa dãy đã cho có m ặt trong dãy con tìm được. Các chỉ s ố ghi cách nhau ít nh ất m ột d ấu tr ắng ho ặc m ột d ấu xu ống dòng. Ví d ụ: DAY.INP DAY.OUT 10 3 9 2 3 5 7 1 3 2 4 5 9 6 12 7 6 7 10 8 11 15 12
005. XÂU FIBINACCI Xét dãy các xâu F 1, F 2, F 3, , F N, trong đó: F1 = 'A' F2 = 'B' FK+1 = F K + F K-1 (K ≥ 2). Ví d ụ: F1 = 'A' F2 = 'B' F3 = 'BA' F4 = 'BAB' F5 = 'BABBA' F6 = 'BABBABAB' F7 = 'BABBABABBABBA' F8 = 'BABBABABBABBABABBABAB' F9 = 'BABBABABBABBABABBABABBABBABABBABBA' Cho xâu S độ dài không quá 25, ch ỉ bao g ồm các ký t ự 'A' và 'B'. Hãy xác định s ố l ần xu ất hi ện xâu S trong xâu F N, N ≤ 35. Chú ý: hai l ần xu ất hi ện c ủa S trong FN không nh ất thi ết ph ải là các xâu r ời nhau hoàn toàn. Dữ li ệu: vào t ừ file v n b ản FIBISTR.INP, bao g ồm nhi ều dòng, m ỗi dòng có d ạng N S. Gi ữa N và S có đúng 1 d ấu cách. D ữ li ệu vào là chu n, không c ần ki ểm tra. Kết qu ả: Đư a ra file v n b ản FIBISTR.OUT, m ỗi dòng d ữ li ệu ứng v ới m ột dòng k ết qu ả ra Ví d ụ: FIBISTR.INP FIBISTR.OUT 3 A 1 3 AB 0 8 BABBAB 4 13
006. VÒNG S NGUYÊN T Một vòng tròn ch ứa 2n vòng tròn nh ỏ (Xem hình v ẽ). Các vòng tròn nh ỏ được đánh s ố t ừ 1 đế n n theo chi ều kim đồ ng h ồ. C ần điền các s ố t ự nhiên t ừ 1 đế n 2n m ỗi s ố vào m ột vòng tròn nh ỏ sao cho tổng c ủa hai s ố trên hai vòng tròn nh ỏ liên ti ếp là s ố nguyên t ố. S ố điền ở vòng tròn nh ỏ 1 luôn là s ố 1. 1 6 4 5 3 2 Dữ li ệu: Vào t ừ file v n b ản CIRCLE.INP ch ứa s ố nguyên d ươ ng n (1 < n < 10) Kết qu ả: Ghi ra file v n b ản CIRCLE.OUT: • Dòng đầu tiên ghi s ố l ượng các cách điền s ố tìm được (k). • Dòng th ứ i trong s ố k dòng ti ếp theo ghi các s ố trong các vòng tròn nh ỏ b ắt đầ u t ừ vòng tròn nh ỏ 1 đọ c theo th ứ t ự c ủa các vòng tròn nh ỏ Ví d ụ: CIRCLE.INP CIRCLE.OUT CIRCLE.INP CIRCLE.OUT 3 2 4 4 1 4 3 2 5 6 1 2 3 8 5 6 7 4 1 6 5 2 3 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2 14
007. ÔI B N Tr ước kia Tu ấn và Mai là hai b ạn cùng l ớp còn bây gi ờ hai b ạn h ọc khác tr ường nhau. C ứ m ỗi sáng, đúng 6 gi ờ c ả hai đề u đi t ừ nhà t ới tr ường c ủa mình theo con đường m ất ít th ời gian nh ất (có th ể có nhi ều con đường đi m ất th ời gian b ằng nhau và đều ít nh ất). Nh ưng hôm nay, hai b ạn mu ốn g ặp nhau để bàn vi ệc h ọp l ớp c nhân ngày 20-11. Cho bi ết s ơ đồ giao thông c ủa thành ph ố g ồm N nút giao thông được đánh s ố t ừ 1 đế n N và M tuy ến đường ph ố (m ỗi đường ph ố n ối 2 nút giao thông). V ị trí nhà c ủa Mai và Tu ấn c ng nh ư tr ường c ủa hai b ạn đề u n ằm ở các nút giao thông. C ần xác đị nh xem Mai và Tu ấn có cách nào đi tho ả mãn yêu cầu nêu ở trên, đồng th ời h ọ l ại có th ể g ặp nhau ở nút giao thông nào đó trên con đường t ới tr ường hay không ? (Ta nói Tu ấn và Mai có th ể g ặp nhau t ại m ột nút giao thông nào đó n ếu h ọ đế n nút giao thông này t ại cùng m ột th ời điểm). N ếu có nhi ều ph ươ ng án thì hãy ch ỉ ra ph ươ ng án để Mai và Tu ấn g ặp nhau s ớm nh ất. Dữ li ệu vào đợc đặ t trong t ệp FRIEND.INP: • Dòng đầu tiên ch ứa 2 s ố nguyên d ươ ng N, M (1 ≤ N ≤ 100); • Dòng ti ếp theo ch ứa 4 s ố nguyên d ươ ng Ha, Sa, Hb, Sb l ần l ượt là s ố hi ệu các nút giao thông tươ ng ứng v ới: Nhà Tu ấn, tr ường c ủa Tu ấn, nhà Mai, tr ường c ủa Mai. • Dòng th ứ i trong s ố M dòng ti ếp theo ch ứa 3 s ố nguyên d ươ ng A, B, T. Trong đó A & B là hai đầu c ủa tuy ến đường ph ố i. Còn T là thời gian (tính b ằng giây ≤ 1000) c ần thi ết để Tu ấn (ho ặc Mai) đi t ừ A đế n B c ng nh ư t ừ B đế n A. Gi ả thi ết là s ơ đồ giao thông trong thành ph ố đả m b ảo để có th ể đi t ừ m ột nút giao thông b ất k đế n tất c ả các nút còn l ại. Kết qu ả : Ghi ra t ệp v n b ản FRIEND.OUT • Dòng 1: Ghi t ừ YES hay NO tu theo có ph ươ ng án giúp cho hai b ạn g ặp nhau hay không. Trong tr ường h ợp có ph ươ ng án: ♦ Dòng 2: Ghi th ời gian ít nh ất để Tu ấn t ới tr ường ♦ Dòng 3: Ghi các nút giao thông theo th ứ t ự Tu ấn đi qua ♦ Dòng 4: Ghi th ời gian ít nh ất để Mai t ới tr ường ♦ Dòng 5: Ghi các nút giao thông theo th ứ t ự Mai đi qua ♦ Dòng 6: Ghi s ố hi ệu nút giao thông mà hai b ạn g ặp nhau ♦ Dòng 7: Th ời gian s ớm nh ất tính b ằng giây k ể t ừ 6 gi ờ sáng mà hai b ạn có th ể g ặp nhau. Các s ố trên m ột dòng c ủa Input/Output file ghi cách nhau ít nh ất m ột d ấu cách. Ví d ụ : V ới s ơ đồ giao thông sau: (N=6,M=7, Ha=1, Sa=6, Hb=2, Sb=5) Dòng FRIEND.INP FRIEND.OUT 1 6 7 YES 1 5 2 1 6 2 5 25 10 20 3 1 3 10 1 4 6 4 1 4 10 30 10 4 5 2 3 5 2 3 4 5 5 15 6 3 4 5 4 5 3 15 6 7 3 6 15 10 2 8 4 5 20 9 4 6 15 15
008. C A S V N B N Xét v n b ản T g ồm N ký t ự (N ≤ 1000000, N không cho tr ước) và v n b ản P g ồm M ký t ự (0 < M ≤ 100). C ửa s ổ độ dài W là m ột đoạn v n b ản g ồm W ký t ự liên ti ếp c ủa T (M < W ≤ 1000). Nói c ửa sổ W ch ứa m ẫu P n ếu t ồn t ại m ột cách xoá m ột s ố ký t ự liên ti ếp c ủa W để nh ận được P. Hai c ửa s ổ c ủa T g ọi là khác nhau n ếu chúng b ắt đầ u t ừ nh ững v ị trí khác nhau trong T. Hãy xác định s ố c ửa s ổ khác nhau trong v n b ản T ch ứa P. Dữ li ệu: • File v n b ản WINDOWP.INP ♦ Dòng đầu ch ứa hai s ố nguyên W, M ♦ Dòng th ứ hai ch ứa M ký t ự c ủa v n b ản P; • File WINDOWT.TXT ch ứa v n b ản T Kết qu ả: Đư a ra file WINDOW.OUT m ột s ố nguyên xác định s ố c ửa s ổ tìm được theo yêu c ầu. Lưu ý: Đa s ố tr ường h ợp, file WINDOWT.TXT không ph ải là Text file, có ngh a là nó ch ứa các ký tự trong kho ảng #0 #255 (file of Char). Nh ư v ậy tính c ả CR(#13) và LF(#10) Ví d ụ: WINDOWP.INP WINDOWT.TXT WINDOW.OUT 4 2 This is a sample text for the 8 is first task on the contest 16
009. VÒNG TRÒN CON Cho hai dãy s ố nguyên a 1, a 2, , a m và b 1, b 2, , b n (2 ≤ m, n ≤ 100) Các s ố này được x ếp quanh hai vòng tròn A và B: các s ố a i quanh vòng tròn A và các s ố b j quanh vòng tròn B. Vòng tròn C được g ọi v ới các s ố quanh nó c 1, c 2, , c p được g ọi là vòng tròn con c ủa A (ho ặc c ủa B) n ếu t ồn t ại m ột cách xoá b ớt các s ố c ủa A (ho ặc c ủa B) để được vòng tròn C. Hãy tìm vòng tròn C là vòng tròn con c ủa c ả A và B v ới s ố ph ần t ử (p) l ớn nh ất có th ể. Chú ý: Các s ố trên 3 vòng tròn A, B, C đợc x ếp theo đúng th ứ t ự trong dãy theo cùng m ột chi ều kim đồng h ồ. Dữ li ệu: Vào t ừ file v n b ản CIRCLE.INP • Dòng đầu ch ứa hai s ố nguyên m, n cách nhau ít nh ất m ột d ấu cách. • m dòng ti ếp theo, dòng th ứ i ghi s ố a i • n dòng ti ếp theo, dòng th ứ j ghi s ố bj Kết qu ả: Đư a ra file v n b ản CIRCLE.OUT • Dòng đầu ghi s ố nguyên p • p dòng sau, dòng th ứ k ghi s ố ck. Ví d ụ: CIRCLE.INP CIRCLE.OUT 8 7 6 1 1 4 2 6 2 2 3 8 8 4 1 4 5 2 3 6 3 7 3 8 7 2 6 4 6 2 8 1 6 8 2 1 4 3 5 17
010. 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 được b ắt đầu ngay sau th ời điểm s i và k ết thúc t ại th ời điểm f i. H ỏi có th ể b ố trí phòng h ội th ảo ph ục v ụ được nhi ều nh ất bao nhiêu cu ộc h ọp, sao cho kho ảng th ời gian làm vi ệc c ủa hai cu ộc h ọp b ất k là không giao nhau. Dữ li ệu vào t ừ file v n b ản ACTIVITY.INP • Dòng đầu tiên ch ứa s ố nguyên d ươ ng n ( n ≤ 10000) • Dòng th ứ i trong s ố n dòng ti ếp theo ch ứa hai s ố nguyên d ươ ng s i, f i (s i < f i ≤ 32000) ( ∀i: 1 ≤ i ≤ n). Kết qu ả: Ghi ra file ACTIVITY.OUT • Dòng đầu tiên ghi s ố K là s ố các cu ộc h ọp được ch ấp nh ận ph ục v ụ • K dòng ti ếp theo li ệt kê s ố hi ệu các cu ộc h ọp được ch ấp nh ận theo th ứ t ự t ừ cu ộc h ọp đầ u tiên tới cu ộc h ọp cu ối cùng , m ỗi dòng ghi s ố hi ệu m ột cu ộc h ọp. Ví d ụ: 0 1 2 3 4 5 6 7 8 9 10 11 12 2 3 5 1 4 ACTIVITY.INP ACTIVITY.OUT 5 3 7 9 3 2 4 5 1 3 1 1 6 3 7 18
011. MUA VÉ TÀU HO Tuy ến đường s ắt t ừ thành ph ố A đế n thành ph ố B đi qua m ột s ố nhà ga. Tuy ến đường có th ể bi ểu di ễn b ởi m ột đoạn th ẳng, các nhà ga là các điểm trên đó. Tuy ến đường b ắt đầ u t ừ A và k ết thúc ở B, vì th ế các nhà ga s ẽ được đánh s ố b ắt đầ u t ừ A (có s ố hi ệu là 1) và B là nhà ga cu ối cùng. Giá vé đi l ại gi ữa hai nhà ga ch ỉ ph ụ thu ộc vào kho ảng cách gi ữa chúng. Cách tính giá vé được cho trong b ảng sau đây: Kho ảng cách gi ữa hai nhà ga (X) Giá vé 0 < X ≤ L 1 C1 L1 < X ≤ L 2 C2 L2 < X ≤ L 3 C3 Vé để đi th ẳng t ừ nhà ga này đến nhà ga khác ch ỉ có th ể đặ t mua n ếu kho ảng cách gi ữa chúng không v ượt quá L 3. Vì th ế nhi ều khi để đi t ừ nhà ga này đến nhà ga khác ta ph ải đặ t mua m ột s ố vé. Hơn th ế n ữa, nhân viên đường s ắt yêu c ầu hành khách ch ỉ được gi ữ đúng m ột vé khi đi trên tàu và vé đó s ẽ b ị hu ỷ khi hành khách xu ống tàu. Ví d ụ, trên tuy ến đường s ắt cho nh ư sau: 1 2 3 4 5 6 7 A L1 = 3 B L2 = 6 L3 = 8 Để đi t ừ ga 2 đế n ga 6 không th ể mua vé đi th ẳng. Có nhi ều cách mua vé để đi t ừ ga 2 đế n ga 6: Ch ẳng h ạn đặ t mua vé t ừ ga 2 đế n ga 3 m ất chi phí C 2 sau đó mua vé t ừ ga 3 đế n ga 6 m ất chi phí C3, và chi phí t ổng c ộng khi đi theo cách này là C 2 + C 3. Ho ặc mua vé t ừ ga 2 đế n ga 4 m ất chi phí C2, sau đó mua vé t ừ ga 4 đế n ga 5 m ất chi phí C 2 và mua vé t ừ ga 5 đế n ga 6 m ất chi phí C1, nh ư vậy chi phí t ổng c ộng là 2C 2 + C 1. L ưu ý r ằng m ặc dù kho ảng cách gi ữa ga 2 và ga 6 b ằng 12 = 2 L 2 nh ưng không được phép mua 2 vé v ới giá C 2 để đi th ẳng t ừ ga 2 đế n ga 6. Yêu c ầu: Tìm cách đặt mua vé để đi l ại gi ữa hai nhà ga cho tr ước v ới chi phí mua vé là nh ỏ nh ất. Dữ li ệu vào t ừ file v n b ản RTICKET.INP 9 • Dòng đầu tiên ghi các s ố nguyên L 1, L 2, L 3, C 1, C 2, C 3 (1 ≤ L 1 < L 2 < L 3 ≤ 10 ; 1 ≤ C 1 < C 2 < C 3 ≤ 10 9) theo đúng th ứ t ự li ệt kê ở trên. • Dòng th ứ hai ch ứa s ố l ượng nhà ga N ( 2 ≤ N ≤ 10000). • Dòng th ứ ba ghi hai s ố nguyên s, f là các ch ỉ s ố c ủa hai nhà ga c ần tìm cách đặt mua vé v ới chi phí nh ỏ nh ất để đi l ại gi ữa chúng. • Dòng th ứ i trong s ố N - 1 dòng ti ếp theo ghi s ố nguyên là kho ảng cách t ừ nhà ga A (ga 1) đến nhà ga th ứ i + 1. Chi phí ít nh ất t ừ nhà ga đầu tiên A đến nhà ga cu ối cùng B không v ượt quá 10 9. Kết qu ả ghi ra file v n b ản RTICKET.OUT chi phí nh ỏ nh ất tìm đợc. Ví d ụ: RTICKET.INP RTICKET.OUT 3 6 8 20 30 40 70 19
7 2 6 3 7 8 13 15 23 20
012. XIN CH KÝ Giám đốc m ột công ty trách nhi ệm h ữu h ạn mu ốn xin ch ữ ký c ủa ông Ki ến trúc s ư tr ưởng thành ph ố phê duy ệt d ự án xây d ựng tr ụ s ở làm vi ệc c ủa công ty. Ông ki ến trúc s ư tr ưởng ch ỉ ký vào gi ấy phép khi bà th ư ký c ủa ông ta đã ký duy ệt vào gi ấy phép. Bà th ư ký làm vi ệc t ại t ầng th ứ M c ủa toà nhà tr ụ s ở làm vi ệc g ồm M t ầng c ủa V n phòng Ki ến trúc s ư tr ưởng thành ph ố. Các t ầng c ủa toà nhà được đánh s ố t ừ 1 đế n M, t ừ th ấp đế n cao. M ỗi t ầng c ủa toà nhà có N phòng được đánh s ố t ừ 1 đến N t ừ trái qua ph ải. Trong m ỗi phòng ch ỉ có m ột nhân viên làm vi ệc. Gi ấy phép ch ỉ được bà th ư ký ký duy ệt khi đã có ít nh ất m ột nhân viên ở t ầng M đã ký xác nh ận. Ngoài bà th ư ký, m ột nhân viên b ất k ch ỉ ký xác nh ận vào gi ấy phép khi có ít nh ất m ột trong các điều ki ện sau được tho ả mãn: a) Nhân viên đó làm vi ệc ở t ầng 1 b) Gi ấy phép đã được ký xác nh ận b ởi nhân viên làm vi ệc ở cùng s ố phòng trong t ầng sát d ưới c) Gi ấy phép đã được ký xác nh ận b ởi nhân viên làm vi ệc ở cùng s ố phòng trong t ầng sát trên d) Gi ấy phép đã được ký xác nh ận b ởi nhân viên làm vi ệc ở phòng bên c ạnh Mỗi m ột nhân viên (k ể c ả bà th ư ký) khi ký xác nh ận đề u đòi m ột kho ản l ệ phí. Hãy ch ỉ ra cách xin được ch ữ ký c ủa Ki ến trúc s ư tr ưởng đòi h ỏi t ổng l ệ phí ph ải tr ả là nh ỏ nh ất (gi ả thi ết r ằng riêng ch ữ ký c ủa Ki ến trúc s ư tr ưởng không m ất l ệ phí). Dữ li ệu vào t ừ file v n b ản SIGN.INP • Dòng đầu tiên ch ứa ba s ố M, N, P (1 ≤ M ≤ 50; 1 ≤ N ≤ 100; 1 ≤ P ≤ N) ở đây P là s ố phòng bà th ư ký. • Dòng th ứ i trong s ố M dòng ti ếp theo ch ứa N s ố nguyên d ươ ng theo th ứ t ự là l ệ phí ph ải tr ả cho các nhân viên ở các phòng 1, 2, , N trên t ầng i. Các s ố này không v ượt quá 10 9 và gi ả thi ết rằng t ổng chi phí c ần tr ả c ng không v ượt quá 10 9. Kết qu ả: Ghi ra file v n b ản SIGN.OUT Dòng đầu tiên ghi 2 s ố F, K theo th ứ t ự là chi phí c ần tr ả và s ố l ượng phòng c ần đi qua. K dòng ti ếp theo, m ỗi dòng ghi s ố t ầng và s ố phòng c ủa m ột phòng theo th ứ t ự c ần đi qua. (Các s ố trên 1 dòng c ủa input/output file cách nhau ít nh ất 1 d ấu tr ống) Ví d ụ: SIGN.INP SIGN.OUT 3 4 4 9 6 10 10 1 10 1 3 2 2 2 10 2 3 1 10 10 1 2 2 2 1 3 1 3 4 21
013. L C N M KIM C Ư NG Lắc là m ột đồ trang s ức r ất được các cô gái ưa chu ộng. Chính vì v ậy mà chúng ph ải được ch ế t ạo th ật đẹ p và đa d ạng. Xét vi ệc ch ế t ạo l ắc có m m ắt xích, m ỗi m ắt được n ạp m ột viên kim c ươ ng. Có n lo ại viên kim c ươ ng khác nhau, n ≤ 7; 2 ≤ m ≤ 2 7-n + 19. Hai l ắc được g ọi là khác nhau n ếu ta không th ể tìm cách đặt sao cho các m ắt t ươ ng ứng có kim cươ ng cùng lo ại. L ưu ý r ằng l ắc có hình vòng. Với m và n cho tr ước, hãy xác định xem có th ể t ồn t ại bao nhiêu lo ại l ắc khác nhau. Các lo ại kim c ươ ng được ký hi ệu là A, B, C, M ột c ấu hình l ắc được xác đị nh b ởi m ột xâu m ký tự A, B, C, và b ắt đầ u b ằng ký t ự nh ỏ nh ất. Cho s ố th ứ t ự l, hãy xác định c ấu hình t ươ ng ứng (Các c ấu hình được s ắp x ếp theo th ứ t ự t ừ điển). Dữ li ệu: Vào t ừ file BRASLET.INP có d ạng m n l1 l2 Kết qu ả: Đa ra file BRASLET.OUT K - S ố l ượng l ắc khác nhau s1 s2 (si xác định c ấu hình l ắc t ươ ng ứng v ới l i) Ví d ụ: BRASLET.INP BRASLET.OUT 4 3 21 2 AAAB 21 CCCC 22
014. R I S I Xét trò ch ơi r ải s ỏi v ới m ột ng ười ch ơi nh ư sau: Cho cây T và m ột đố ng s ỏi g ồm K viên ở m ỗi b ước ng ười ta l ấy 1 viên s ỏi t ừ đố ng s ỏi và đặt vào m ột nút lá tu ch ọn Nếu nút p có r nút lá và t ất c ả và t ất c ả các nút lá đề u có s ỏi thì ng ười ta gom t ất c ả các viên s ỏi ở lá lại, đặ t 1 viên ở nút p, xoá các nút lá c ủa nó và hoàn tr ả r - 1 viên s ỏi còn l ại vào đống s ỏi. Trò ch ơi k ết thúc khi đã đặt được 1 viên s ỏi vào nút g ốc Nhi ệm v ụ đặ t ra là theo c ấu trúc c ủa cây T, xác đị nh s ố viên s ỏi t ối thi ểu ban đầ u để trò ch ơi có th ể kết thúc bình th ường. Cây có n nút ( N ≤ 400), nút g ốc được đánh s ố là 1. Dữ li ệu: vào t ừ file v n b ản STONE.INP • Dòng đầu: s ố n • Dòng th ứ i trong s ố n dòng ti ếp theo có d ạng: i m i 1 i 2 i m. Trong đó m là s ố nút con c ủa nút i; i1, i 2, , i m: Các nút con c ủa nút i. Kết qu ả: đa ra file STONE.OUT s ố l ượng viên s ỏi t ối thi ểu c ần thi ết Ví d ụ STONE.INP STONE.OUT 7 3 1 2 2 3 2 2 5 4 3 2 6 7 23
015. IP VIÊN Địa bàn ho ạt độ ng c ủa m ột điệp viên là m ột khu ph ố mà ở đó ch ỉ có các đường ph ố ngang, d ọc t ạo thành m ột l ưới ô vuông. V ới m ục đích b ảo m ật, thay vì tên đường ph ố, điệp viên đánh s ố các ph ố ngang t ừ 0 đến m và các ph ố d ọc t ừ 0 đế n n. ở m ột s ố ngã ba ho ặc ngã t ư có các tr ạm ki ểm soát. Anh ta đang đứng ở nút giao c ủa hai đường (i 1, j 1) (j 1 - đường ngang; i 1 - đường d ọc) và c ần t ới điểm h ẹn ở giao c ủa hai đường (i 2, j 2). Để tránh b ị theo dõi, đường đi ph ải không qua các tr ạm ki ểm soát và c ứ t ới ch ỗ r ẽ thì nh ất thi ết ph ải đổ i h ướng đi, th ậm chí có th ể sang đường và đi ng ược tr ở l ại. Vi ệc đổ i h ướng ch ỉ được th ực hi ện ở ngã ba ho ặc ngã t ư. Hãy xác định đường đi ng ắn nh ất tới điểm h ẹn ho ặc cho bi ết không có đường đi đáp ứng được yêu c ầu đã nêu. Dữ li ệu: vào t ừ file SPY.INP Dòng đầu: m n i 1 j 1 i 2 j 2 ( 0 ≤ m, n ≤ 100) Các dòng sau: m ỗi dòng 2 s ố i, j (to ạ độ tr ạm ki ểm soát). Kết qu ả: đa ra file SPY.OUT Dòng đầu: độ dài đường đi ng ắn nh ất ho ặc thông báo NO n ếu không có đường đi. Các dòng sau: m ỗi dòng 2 s ố i, j ch ỉ nút ti ếp theo c ần t ới theo đường đi tìm được, b ắt đầ u là i 1 j 1 và kết thúc là i 2 j 2. Ví d ụ: SPY.INP SPY.OUT 4 5 0 0 5 4 13 0 1 0 0 0 4 1 0 2 2 1 1 2 3 1 0 4 0 2 0 5 2 2 1 5 3 3 1 -1 3 2 4 2 4 3 3 3 4 3 4 4 5 4 24
016. KHO NG CÁCH GI A HAI XÂU Cho hai xâu ký t ự S 1 và S 2, m ỗi xâu có độ dài không quá 100 ký t ự. Cho phép th ực hi ện các phép bi ến đổ i sau đây đố i v ới xâu ký t ự: 1. Thay th ế m ột ký t ự nào đó b ởi ký t ự khác 2. Đổi ch ỗ hai ký t ự li ền nhau 3. Chèn m ột ký t ự vào sau v ị trí nào đó 4. Xoá b ớt 1 ký t ự Ta g ọi kho ảng cách gi ữa hai xâu S 1 và S 2 là s ố ít nh ất các phép bi ến đổ i nêu trên c ần áp d ụng đố i với xâu S 1 để bi ến nó thành xâu S 2. Yêu c ầu: Tính kho ảng cách gi ữa 2 xâu S 1, S 2 cho tr ớc và ch ỉ ra th ứ t ự các phép bi ến đổ i. Ví d ụ: Gi ả s ử S1 = 'Barney'; S2 = 'brawny'. Kho ảng cách gi ữa 2 xâu là 4. Dãy các phép bi ến đổ i cần th ực hi ện là: 1. Thay ký t ự 1 c ủa S 1 (B) b ởi b 2. Đổi ch ỗ ký t ự th ứ 2 (a) và th ứ 3 (r) c ủa S 1. 3. Chèn ký t ự w vào S 1 sau ký t ự th ứ 3. 4. Xoá ký t ự th ứ 5 c ủa S 1. Dãy các phép bi ến đổ i có th ể mô t ả nh ư sau: 'Barney' → 'barney' → 'braney' → 'brawney' → 'brawny' Dữ li ệu: vào t ừ file v n b ản STREDIT.INP có c ấu trúc nh sau: • Dòng đầu tiên ch ứa xâu S 1 • Dòng th ứ hai ch ứa xâu S 2 Kết qu ả: Ghi ra file v n b ản STREDIT.OUT • Dòng đầu tiên ghi s ố l ượng các phép bi ến đổ i c ần s ử d ụng K • Mỗi dòng i trong s ố K dòng ti ếp theo mô t ả phép bi ến đổ i được s ử d ụng ở l ần th ứ i g ồm các tham s ố sau: các tham s ố ghi trên 1 dòng ghi cách nhau 1 d ấu cách. ♦ 1, P, C (n ếu là phép thay ký t ự t ại v ị trí P b ằng ký t ự C) ♦ 2, I, I + 1 (n ếu là phép đổi ch ỗ 2 ký t ự th ứ I và th ứ I + 1) ♦ 3, P, C (n ếu là phép chèn ký t ự C vào sau v ị trí P) ♦ 4, P (n ếu là phép xoá ký t ự th ứ P) Ví d ụ: STREDIT.INP STREDIT.OUT Barney 4 brawny 1 1 b 2 2 3 3 3 w 4 5 25
017. X P L I B NG S Cho m ột b ảng ô vuông g ồm m hàng và n c ột. Các ô được đánh ch ỉ s ố theo (hàng, c ột) t ừ (0, 0) đế n (m - 1, n - 1). Trên m x n ô ng ười ta vi ết các s ố t ự nhiên t ừ 0 đế n m x n - 1 theo m ột th ứ t ự tu ý. Cho phép đổi ch ỗ hai s ố đặ t trong hai ô ở th ế mã giao chân. C ần tìm cách đổi ch ỗ các s ố sao cho thu được b ảng có tính ch ất: Số ở ô (i, j) là n x i + j . Dữ li ệu vào t ừ file v n b ản BOARD.INP: các s ố ghi trên 1 dòng cách nhau ít nh ất 1 d ấu tr ống. • Dòng đầu ghi 2 s ố m, n (5 ≤ m, n ≤ 80) • m dòng ti ếp theo, dòng th ứ i ghi n s ố t ự nhiên theo đúng th ứ t ự các s ố ghi trên hàng i c ủa bảng. Kết qu ả đa ra file BOARD.OUT • Dòng th ứ i ch ứa 4 s ố X 1, Y 1, X 2, Y 2 cho bi ết t ại b ước th ứ i c ần đổ i ch ỗ 2 s ố t ại hai ô (X 1, Y1) và (X 2, Y 2) Ví d ụ: (n = m = 8) Bảng ban đầ u Bảng c ần t ạo 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 10 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 8 9 0 16 12 13 14 15 1 8 9 10 11 12 13 14 15 2 11 17 18 19 20 21 22 23 2 16 17 18 19 20 21 22 23 3 24 25 26 27 28 29 30 31 3 24 25 26 27 28 29 30 31 4 32 33 34 35 36 37 38 39 4 32 33 34 35 36 37 38 39 5 40 41 55 43 44 45 46 47 5 40 41 42 43 44 45 46 47 6 48 49 50 51 52 53 54 42 6 48 49 50 51 52 53 54 55 7 56 57 58 59 60 61 62 63 7 56 57 58 59 60 61 62 63 Input/Output File: BOARD.INP BOARD.OUT 8 8 1 2 0 0 10 1 2 3 4 5 6 7 2 0 3 2 8 9 0 16 12 13 14 15 3 2 1 3 11 17 18 19 20 21 22 23 3 2 2 0 24 25 26 27 28 29 30 31 6 7 7 5 32 33 34 35 36 37 38 39 7 5 6 3 40 41 55 43 44 45 46 47 6 3 7 1 48 49 50 51 52 53 54 42 7 1 5 2 56 57 58 59 60 61 62 63 7 1 6 3 6 3 7 5 7 5 6 7 26
018. TH M KHU TRI N LÃM Một khu tri ển lãm ngh ệ thu ật có mxn phòng được b ố trí trong m ột hình ch ữ nh ật kích th ước mxn (2 ≤m,n ≤ 20). M ỗi phòng bi ểu di ễn b ởi m ột ô và đều có c ửa thông v ới các phòng chung c ạnh v ới nó. Với m ỗi m ột phòng, ta đánh ch ỉ s ố theo to ạ độ (x, y) c ủa ô (1 ≤hàng x ≤m; 1 ≤cột y ≤n) và gán cho nó m ột ch ữ cái in hoa ('A' 'Z') th ể hi ện lo ại ngh ệ thu ật tr ưng bày t ại phòng đó. Có th ể vào khu tri ển lãm ở các phòng có to ạ độ (x b ất k , y = 1) và có th ể đi ra ở các phòng có to ạ độ (x b ất k , y = n) Ví d ụ v ới m=10 và n=11: 1 2 3 4 5 6 7 8 9 10 11 1 B B B B B B F F F F F 2 A A A A A B D C C F F 3 A F F F A B A A C F C 4 B F E F A B B B B B D 5 F F D E A B A A A B A 6 E E D E E E E E A B B 7 D D D E E E E E A A B 8 D C C F F F C C A B A 9 D C C F F F C C A A A 10 C C C C C C C C C C C Một v ị th ủ t ướng đi th m tri ển lãm có s ở thích đặ c bi ệt v ới m ột lo ại ngh ệ thu ật. Yêu c ầu c ủa ông ta "r ất đơn gi ản" là không nh ất thi ết ph ải đi th m t ất c ả các phòng ch ứa lo ại ngh ệ thu ật mà ông ta thích nh ưng không được đi qua các phòng ch ứa lo ại ngh ệ thu ật khác. Ví d ụ: Để đi th m lo ại ngh ệ thu ật B, Th ủ t ớng có th ể đi: (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,6), (3,6), (4,6), (4,7), (4,8), (4,9), (4,10), (5,10), (6,10), (6,11). Nh ng không ph ải luôn t ồn t ại đờng đi nh v ậy, ví d ụ : n ếu Th ủ t ớng mu ốn đi th m lo ại ngh ệ thu ật A thì không th ể tìm đợc m ột đờng đi (B ởi c ột 6 c ủa b ảng không có m ột ch ữ A nào). Để có đường đi c ủa v ị th ủ t ướng đi th m lo ại nghệ thu ật A thì nh ững ng ười qu ản lý tri ển lãm ph ải tìm cách đổi lo ại ngh ệ thu ật t ại hai phòng nào đó. Trong ví d ụ này thì để có đường đi chúng ta có th ể đổ i lo ại ngh ệ thu ật B ở phòng (5,6) cho lo ại ngh ệ thu ật A ở phòng (3,1) ho ặc phòng (3,7), (3,8), Trong nh ững cách đổ i đó, ng ười ta th ường quan tâm đế n vi ệc ph ải đổ i sao cho t ổng s ố phòng ph ải đổi là ít nh ất có th ể được. Trong nh ững cách đổ i v ới s ố c ặp phòng ph ải đổ i ít nh ất hãy ch ỉ ra cách đổi mà con đường th ủ t ướng ph ải đi là ng ắn nh ất có th ể được. Có thể có nhi ều nghi ệm thì ch ỉ c ần ch ỉ ra m ột nghi ệm. Dữ li ệu vào t ừ file v n b ản TL.INP bao g ồm: • Dòng đầu tiên ghi s ố m, n • Dòng th ứ hai ghi m ột ch ữ cái in hoa th ể hi ện lo ại ngh ệ thu ật th ủ t ướng mu ốn th m. • m dòng ti ếp theo, dòng th ứ i là m ột xâu ký t ự độ dài n bi ểu di ễn các lo ại ngh ệ thu ật trong các phòng trên hàng i theo đúng th ứ t ự t ừ c ột 1 đế n c ột n. Kết qu ả cho ra file v n b ản TL.OUT bao g ồm: • Dòng đầu tiên là s ố c ặp phòng c ần đổ i (p). • p dòng ti ếp theo m ỗi dòng g ồm 4 s ố a, b, c, d có ngh a là ta c ần đổ i lo ại ngh ệ thu ật t ại phòng (a,b) cho phòng (c,d). • Dòng ti ếp theo ghi s ố phòng trên con đường đi ng ắn nh ất tìm được (q). • q dòng ti ếp theo, m ỗi dòng ghi to ạ độ x,y th ể hi ện cho con đường ng ắn nh ất đó theo đúng th ứ t ự phòng đi qua. • Nếu không t ồn t ại ph ươ ng án đổi phòng để có đường đi thì ghi vào file TL.OUT m ột dòng: NO SOLUTION Ví d ụ: V ới khu tri ển lãm nh trên: 27
TL.INP TL.OUT 10 11 0 B 16 BBBBBBFFFFF 1 1 AAAAABDCCFF 1 2 AFFFABAACFC 1 3 BFEFABBBBBD 1 4 FFDEABAAABA 1 5 EEDEEEEEABB 1 6 DDDEEEEEAAB 2 6 DCCFFFCCABA 3 6 DCCFFFCCAAA 4 6 CCCCCCCCCCC 4 7 4 8 4 9 4 10 5 10 6 10 6 11 TL.INP TL.OUT 10 11 1 A 5 6 3 1 BBBBBBFFFFF 18 AAAAABDCCFF 2 1 AFFFABAACFC 2 2 BFEFABBBBBD 2 3 FFDEABAAABA 2 4 EEDEEEEEABB 2 5 DDDEEEEEAAB 3 5 DCCFFFCCABA 4 5 DCCFFFCCAAA 5 5 CCCCCCCCCCC 5 6 5 7 5 8 5 9 6 9 7 9 8 9 9 9 9 10 9 11 28
019. DÒ MÌN Cho m ột bãi mìn kích th ước mxn ô vuông, trên m ột ô có th ể có ch ứa m ột qu ả mìn ho ặc không, để bi ểu di ễn b ản đồ mìn đó, ng ười ta có hai cách: • Cách 1: dùng b ản đồ đánh d ấu: s ử d ụng m ột l ưới ô vuông kích th ước mxn, trên đó t ại ô (i, j) ghi số 1 n ếu ô đó có mìn, ghi s ố 0 n ếu ô đó không có mìn • Cách 2: dùng b ản đồ m ật độ : s ử d ụng m ột l ưới ô vuông kích th ước mxn, trên đó t ại ô (i, j) ghi một s ố trong kho ảng t ừ 0 đế n 8 cho bi ết t ổng s ố mìn trong các ô lân c ận v ới ô (i, j) (ô lân c ận với ô (i, j) là ô có chung v ới ô (i, j) ít nh ất 1 đỉ nh). Gi ả thi ết r ằng hai b ản đồ được ghi chính xác theo tình tr ạng mìn trên hi ện tr ường. Ví d ụ: B ản đồ đánh d ấu và b ản đồ m ật độ t ơ ng ứng: (m = n = 10) Bản đồ đánh d ấu Bản đồ m ật độ 1 0 1 0 1 0 1 0 0 0 1 3 1 2 1 3 1 2 2 2 0 1 0 0 0 1 0 0 1 1 2 3 3 4 3 3 2 2 2 2 0 0 1 0 1 0 0 0 0 1 2 4 4 5 3 3 2 3 5 3 0 1 1 1 1 0 0 1 1 0 2 4 6 6 3 2 2 2 4 3 0 1 1 1 0 0 0 1 0 1 2 3 6 5 5 2 4 3 5 1 0 0 0 1 0 1 0 1 0 0 3 5 6 3 4 2 5 3 5 3 1 1 1 0 0 1 1 0 1 1 2 3 3 3 5 3 5 4 4 2 1 0 0 1 0 1 0 1 0 1 2 5 4 3 5 5 7 5 6 3 0 0 1 0 1 1 1 1 1 0 2 3 1 3 4 4 5 3 3 2 1 0 0 0 0 1 0 0 0 0 0 2 1 2 3 3 4 3 2 1 Về nguyên t ắc, lúc cài bãi mìn ph ải v ẽ c ả b ản đồ đánh d ấu và b ản đồ m ật độ , tuy nhiên sau m ột th ời gian dài, khi ng ười ta mu ốn g ỡ mìn ra kh ỏi bãi thì v ấn đề h ết s ức khó kh n b ởi b ản đồ đánh d ấu đã bị th ất l ạc !!. Công vi ệc c ủa các l ập trình viên là: T ừ b ản đồ m ật độ , hãy tái t ạo l ại b ản đồ đánh dấu c ủa bãi mìn. Dữ li ệu: Vào t ừ file v n b ản MINE.INP, các s ố trên 1 dòng cách nhau ít nh ất 1 d ấu cách • Dòng 1: Ghi 2 s ố nguyên d ươ ng m, n (2 ≤ m, n ≤ 80) • m dòng ti ếp theo, dòng th ứ i ghi n s ố trên hàng i c ủa b ản đồ m ật độ theo đúng th ứ t ự t ừ trái qua ph ải. Kết qu ả: Ghi ra file v n b ản MINE.OUT, các s ố trên 1 dòng ghi cách nhau ít nh ất 1 d ấu cách • Dòng 1: Ghi t ổng s ố l ượng mìn trong bãi • m dòng ti ếp theo, dòng th ứ i ghi n s ố trên hàng i c ủa b ản đồ đánh d ấu theo đúng th ứ t ự t ừ trái qua ph ải. Ví d ụ: MINE.INP MINE.OUT 10 15 80 0 3 2 3 3 3 5 3 4 4 5 4 4 4 3 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 4 3 5 5 4 5 4 7 7 7 5 6 6 5 0 0 1 0 0 1 1 1 0 1 1 1 0 1 1 1 4 3 5 4 3 5 4 4 4 4 3 4 5 5 0 0 1 0 0 1 0 0 1 1 1 0 0 1 1 1 4 2 4 4 5 4 2 4 4 3 2 3 5 4 1 0 1 1 1 0 0 1 0 0 0 0 0 1 1 1 3 2 5 4 4 2 2 3 2 3 3 2 5 2 1 0 0 0 1 1 1 0 0 1 0 0 1 0 1 2 3 2 3 3 5 3 2 4 4 3 4 2 4 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 2 3 2 4 3 3 2 3 4 6 6 5 3 3 1 0 1 1 0 0 1 0 0 1 1 0 0 1 0 0 2 6 4 5 2 4 1 3 3 5 5 5 6 4 3 1 0 1 0 1 0 1 0 1 1 1 1 0 1 0 4 6 5 7 3 5 3 5 5 6 5 4 4 4 3 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 2 4 4 4 2 3 1 2 2 2 3 3 3 4 2 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 29
020. X P L I DÃY S Cho dãy A = (a 1, a 2, , an) là dãy các s ố nguyên d ươ ng đôi m ột khác nhau. Hãy li ệt kê t ất c ả các cách hoán v ị ph ần t ử c ủa dãy A tho ả mãn: gi ữa hai giá tr ị M và N b ất k trong hoán v ị đó, không t ồn t ại giá tr ị P nào để: 2P = M + N. Ví d ụ: V ới dãy A là (11, 22, 33, 44) thì Hoán v ị (11, 44, 33, 22) là tho ả mãn điều ki ện trên Hoán v ị (11, 44, 22, 33) không tho ả mãn vì có giá tr ị P = 22 n ằm gi ữa hai giá tr ị M = 11 và N = 33 mà: 22 * 2 = 11 + 33. Dữ li ệu: Vào t ừ file v n b ản SORT.INP. Các s ố trên 1 dòng cách nhau ít nh ất 1 d ấu tr ống • Dòng 1: Ghi s ố n (2 ≤ n ≤ 11) • Dòng 2: Ghi đủ giá tr ị n ph ần t ử c ủa dãy A (1 ≤ ai ≤ 100). Kết qu ả: Ghi ra file v n b ản SORT.OUT. Các s ố trên 1 dòng cách nhau ít nh ất 1 d ấu tr ống • Dòng cu ối cùng ghi s ố l ượng hoán v ị tìm được (K) • K dòng tr ước dòng cu ối cùng, m ỗi dòng ghi 1 hoán v ị tìm được Ví d ụ: SORT.INP SORT.OUT 4 11 33 22 44 11 22 33 44 11 33 44 22 22 11 44 33 22 44 11 33 22 44 33 11 33 11 22 44 33 11 44 22 33 44 11 22 44 22 11 33 44 22 33 11 10 30
021. CO DÃY BÁT PHÂN Cho m ột b ảng A kích th ước 8x8; Các dòng và các c ột được đánh s ố t ừ 0 đế n 7. Trên m ỗi ô c ủa b ảng ch ứa m ột s ố nguyên trong kho ảng t ừ 0 đế n 7. Cho dãy X = (x 1, x 2, , xn), có các ph ần t ử xi ∈ N; 0 ≤ xi ≤ 7. (2 ≤ n ≤ 200). Với ∀i: 1 ≤ i < n. Phép co R(i) th ực hi ện trên dãy X: Xoá hai ph ần t ử xi và xi +1 và thay vào đó giá tr ị n ằm trên hàng xi, c ột xi +1 c ủa b ảng A, sau đó dãy X được đánh ch ỉ s ố l ại t ừ trái qua ph ải b ắt đầ u t ừ 1. Ví d ụ: A 0 1 2 3 4 5 6 7 0 0 1 2 3 0 0 0 0 1 3 2 3 0 0 0 0 0 2 5 3 0 1 0 0 0 0 3 7 0 1 2 0 0 0 0 4 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 Ví d ụ: V ới b ảng A nh ư trên và dãy X = (0, 1, 2, 3, 1, 2) n ếu ta th ực hi ện phép co R(3) thì ta s ẽ được dãy (0, 1, 1, 1, 2). N ếu th ực hi ện ti ếp R(4) thì ta s ẽ được dãy (0, 1, 1, 3). Th ực hi ện ti ếp R(2) thì s ẽ được dãy (0, 2, 3). Th ực hi ện ti ếp R(1) thì s ẽ còn (2, 3) và th ực hi ện R(1) m ột l ần n ữa s ẽ được (1). Yêu c ầu: cho tr ớc m ột giá tr ị V (0 ≤≤≤ V ≤≤≤ 7), hãy tìm m ột th ứ t ự th ực hi ện n - 1 phép co trên dãy X để giá tr ị còn l ại cu ối cùng là V. N ếu có nhi ều ph ơ ng án thì ch ỉ c ần cho bi ết m ột. Dữ li ệu vào t ừ file v n b ản OCT.INP • 8 dòng đầu tiên, dòng th ứ i ghi 8 s ố trên hàng th ứ i - 1 c ủa b ảng A theo đúng th ứ t ự t ừ trái qua ph ải • Dòng th ứ 9 ghi s ố n • Dòng th ứ 10 ghi đủ n s ố: x 1, x 2, , xn theo đúng th ứ t ự. • Dòng th ứ 11 ghi giá tr ị V. Kết qu ả ghi ra file v n b ản OCT.INP, ch ỉ g ồm 1 dòng, trên đó: • Ghi s ố 0 n ếu không t ồn t ại ph ươ ng án s ử d ụng n - 1 phép co để cho giá tr ị V. Ho ặc ghi (theo đúng th ứ t ự thực hi ện) đủ n - 1 v ị trí c ủa các phép co trên dãy X để cho giá tr ị V. Chú ý: Các s ố trên 1 dòng c ủa Input/Output File ghi cách nhau ít nh ất 1 d ấu cách. Ví d ụ: OCT.INP OCT.OUT 5 7 2 1 7 1 4 0 13 13 10 10 10 9 7 7 6 5 3 3 2 1 0 6 0 0 1 3 1 6 0 4 5 1 3 6 6 1 2 5 6 5 5 3 2 5 2 7 1 3 7 3 5 1 2 5 2 4 6 0 4 5 6 3 5 6 7 6 0 2 0 6 0 1 3 3 4 4 15 5 2 3 0 1 6 1 0 4 2 4 3 2 4 4 6 31
022. TUY N BAY Có N thành ph ố và M đường hàng không hai chi ều gi ữa m ột s ố c ặp thành ph ố nào đó, các đường bay được qu ản lý b ởi 16 hãng hàng không. Các thành ph ố được đánh s ố t ừ 1 t ới N (N ≤ 100) và các hãng được đánh s ố t ừ 1 t ới 16. Được bi ết chi phí bay tr ực ti ếp gi ữa hai thành ph ố i, j b ất k (n ếu nh ư có đường bay ) là C. N ếu đang đi máy bay c ủa m ột hãng đến sân bay nào đó r ồi chuy ển sang máy bay c ủa hãng khác thì s ẽ ph ải m ất thêm m ột kho ản ph ụ phí A. Yêu c ầu: Cho tr ớc hai thành ph ố S và F, hãy tìm hành trình bay t ừ thành ph ố S đế n thành ph ố F v ới chi phí ít nh ất. V ới gi ả thi ết r ằng luôn luôn t ồn t ại cách bay t ừ S t ới F. Dữ li ệu: Vào t ừ file v n b ản AIRLINES.INP. Trong đó: • Dòng 1 ghi sáu s ố nguyên d ươ ng N, M, C, A, S, F. (1 ≤ A, C ≤ 100) • M dòng ti ếp theo, m ỗi dòng có d ạng u v k 1 k 2 cho bi ết r ằng gi ữa thành ph ố u và thành ph ố v có đường bay và k 1, k 2, là s ố hi ệu các hãng s ở h ữu đường bay đó Kết qu ả: Ghi ra file v n b ản AIRLINES.OUT. Trong đó: • Dòng 1: Ghi chi phí t ối thi ểu ph ải tr ả • Các dòng ti ếp theo, m ỗi dòng ghi m ột b ộ ba i, j, k. Th ể hi ện t ại b ước đó s ẽ bay t ừ thành ph ố i đến thành ph ố j b ởi máy bay c ủa hãng k. Thứ t ự các dòng ph ải theo đúng th ứ t ự bay trong hành trình. Các s ố trên m ột dòng c ủa Input/Output file ghi cách nhau ít nh ất m ột d ấu cách. Ví d ụ: Với m ạng l ưới đường không nh ư d ưới đây: c ần đi t ừ thành ph ố 1 đế n thành ph ố 5. Chi phí đường bay tr ực ti ếp gi ữa hai thành ph ố b ất k C = 3, ph ụ phí chuy ển tuy ến A = 2. Các s ố ghi bên cạnh các đường bay tr ực ti ếp là tên các hãng s ở h ữu đường bay đó. AIRLINES.INP AIRLINES.OUT 15 16 3 2 1 5 37 1 1 1 & 2 1 2 1 1 2 1 1 2 3 4 5 2 3 1 2 3 1 3 4 1 2 3 4 1 2 1 1 & 3 3 9 2 4 9 1 4 9 1 9 8 1 1 1 1 6 7 8 9 10 5 10 1 3 8 7 1 6 7 1 7 13 2 2 6 11 1 13 14 3 1 3 7 8 1 14 15 3 1 1 1 & 3 1 & 3 7 13 2 15 10 3 11 12 13 14 15 8 9 1 10 5 3 10 15 3 11 12 1 12 13 1 13 14 1 3 14 15 1 3 32
023. MÔ PH NG CÁC PHÉP TOÁN Cho hai s ố nguyên d ươ ng a và b (1 ≤ b ≤ a < 10 1000 ), hãy tính a + b, a - b, a * b, a div b, a mod b. Dữ li ệu: Vào t ừ file v n b ản OPT.INP • Dòng 1: Ch ứa s ố a • Dòng 2: Ch ứa s ố b Kết qu ả: Ghi ra file v n b ản OPT.OUT • Dòng 1: Ghi giá tr ị a + b • Dòng 2: Ghi giá tr ị a - b • Dòng 3: Ghi giá tr ị a * b • Dòng 4: Ghi giá tr ị a div b • Dòng 5: Ghi giá tr ị a mod b Ví d ụ: OPT.INP OPT.OUT OPT.INP OPT.OUT 56 106 987111 1055001 50 6 67890 919221 2800 67014965790 1 14 6 36651 33
024. DÃY CON C A DÃY NH PHÂN Xét dãy B 0, B 1, B 2, , Bn là các dãy các xâu nh ị phân, được xây d ựng nh ư sau: B0 = '1' Với ∀i: (i ≥ 1) thì Bi là ghép c ủa Bi -1 v ới ¬(Bi -1). Trong đó ¬(S) là xâu được t ạo thành t ừ xâu S bằng cách đả o t ất c ả các s ố 1 thành 0 và s ố 0 thành 1 B0 = 1 B1 = 10 B2 = 1001 B3 = 10010110 B4 = 1001011001101001 B5 = 10010110011010010110100110010110 B6 = 1001011001101001011010011001011001101001100101101001011001101001 Yêu c ầu: Cho tr ước s ố nguyên d ươ ng n ≤ 30 và m ột s ố k ≤ 2 n. hãy cho bi ết ký t ự th ứ k c ủa Bn là ký tự 0 hay 1. 34
025. T NG CÁC CH S Cho tr ước hai s ố nguyên d ươ ng n và k (n ≤ 20, k ≤ 30). Yêu c ầu 1: Hãy cho bi ết có bao nhiêu s ố có ≤ n ch ữ s ố mà t ổng các ch ữ s ố đúng b ằng k Yêu c ầu 2: Cho s ố nguyên d ươ ng p, h ỏi n ếu đem các s ố tìm được s ắp x ếp theo th ứ t ự t ng d ần thì số th ứ p là s ố nào. (p không l ớn h ơn s ố l ượng các s ố tìm được) Dữ li ệu: Vào t ừ file v n b ản DIGITSUM.INP g ồm 1 dòng ch ứa ba s ố n, k, p theo đúng th ứ t ự cách nhau 1 d ấu cách. Kết qu ả: Ghi ra file v n b ản DIGITSUM.OUT g ồm 2 dòng • Dòng 1: Ghi s ố l ượng các s ố tìm được trong yêu c ầu 1 • Dòng 2: Ghi s ố th ứ p trong yêu c ầu 2 tìm được Ví d ụ: DIGITSUM.INP DIGITSUM.OUT 3 8 10 45 107 35
026. ƯNG I NHI U IM NH T Cho m ột b ảng A kích th ước m x n (1 ≤ m, n ≤ 100), trên đó ghi các s ố nguyên a ij ( aij  ≤ 100). M ột ng ười xu ất phát t ại ô nào đó c ủa c ột 1, c ần sang c ột n (t ại ô nào c ng được). Quy t ắc đi: T ừ ô (i, j) ch ỉ được quy ền sang m ột trong 3 ô (i, j + 1); (i - 1, j + 1); (i + 1, j + 1). Xem hình v ẽ: 1 2 6 7 9 7 6 5 6 7 1 2 3 4 2 4 7 8 7 6 Yêu c ầu: Hãy tìm v ị trí ô xu ất phát và m ột hành trình đi t ừ c ột 1 sang c ột n sao cho t ổng các s ố ghi trên đờng đi là l ớn nh ất. Dữ li ệu: Vào t ừ file v n b ản MAX.INP. Trong đó: • Dòng 1: Ghi hai s ố m, n là s ố hàng và s ố c ột c ủa b ảng. • m dòng ti ếp theo, dòng th ứ i ghi đủ n s ố trên hàng i c ủa b ảng theo đúng th ứ t ự t ừ trái qua ph ải. Kết qu ả: Ghi ra file v n b ản MAX.OUT. Trong đó: • Dòng 1: Ghi s ố điểm t ối đa có được • n dòng ti ếp theo, dòng th ứ i ghi ch ỉ s ố hàng c ủa ô th ứ i trong hành trình. Các s ố trên 1 dòng trong Input/ Output file cách nhau ít nh ất 1 d ấu cách Ví d ụ: 1 2 3 4 5 6 7 1 9 -2 6 2 1 3 4 2 0 -1 6 7 1 3 3 3 8 -2 8 2 5 3 2 4 1 -1 6 2 1 6 1 5 7 -2 6 2 1 3 7 MAX.INP MAX.OUT 5 7 41 9 -2 6 2 1 3 4 1 0 -1 6 7 1 3 3 2 8 -2 8 2 5 3 2 3 1 -1 6 2 1 6 1 2 7 -2 6 2 1 3 7 3 4 5 36
027. K HO CH THUÊ NHÂN CÔNG Giám đốc điều hành c ủa m ột Công ty tin h ọc c ần xác đị nh s ố l ượng nhân công c ần s ử d ụng trong mỗi tháng để th ực hi ện m ột d ự án phát tri ển tin h ọc. Ông giám đố c n ắm được s ố l ượng nhân công tối thi ểu c ần cho m ỗi tháng. Mỗi l ần thuê ho ặc sa th ải m ột nhân công luôn m ất thêm m ột kho ản chi phí. M ỗi khi m ột th ợ nào đó được thuê, anh ta luôn nh ận được ti ền l ươ ng ngay c ả khi không làm vi ệc. Giám đố c n ắm được chi phí để thuê m ột nhân công m ới, chi phí sa th ải m ột nhân công, l ươ ng tháng c ủa m ột nhân công. V ấn đề đặ t ra cho giám đố c là ph ải xác đị nh s ố l ượng nhân công c ần thuê hay sa th ải trong m ỗi tháng để cho chi phí th ực hi ện d ự án là t ối thi ểu. Dữ li ệu: Vào t ừ file v n b ản PROJECT.INP. • Dòng đầu tiên ghi th ời gian th ực hi ện d ự án n ( đơ n v ị tính: tháng, n ≤ 12) • Dòng th ứ hai ch ứa ba s ố nguyên d ươ ng theo th ứ t ự là chi phí thuê m ột nhân công m ới, l ươ ng tháng c ủa m ột nhân công, chi phí sa th ải m ột nhân công. • Dòng cu ối cùng ghi n s ố nguyên d ươ ng d 1, d 2, , dn, trong đó di là s ố l ượng nhân công c ần s ử dụng trong tháng i. Kết qu ả: Ghi ra file v n b ản PROJECT.OUT • Dòng đầu tiên ghi chi phí t ối thi ểu tìm được • Mỗi dòng th ứ i trong s ố n dòng ti ếp theo ghi s ố si. Được hi ểu là: ♦ Nếu s i > 0 thì nó là s ố l ượng nhân công c ần thuê thêm ở tháng i. ♦ Nếu si < 0 thì si  là s ố l ượng nhân công c ần sa th ải ở tháng i ♦ Nếu si = 0 thì không có bi ến độ ng nhân s ự trong tháng i c ủa d ự án Ví d ụ: PROJECT.INP PROJECT.OUT 3 199 4 5 6 10 10 9 11 0 1 37
028. DÃY CÁC HÌNH CH NH T Gi ả s ử ABCD là m ột hình ch ữ nh ật trên m ặt ph ẳng to ạ độ có các đỉ nh: A (0, 0); B(0, 1); C(K, 1) và D(K, 0). Ta xem hình này là hình có s ố hi ệu 1. Hình có s ố hi ệu 2 xây d ựng trên c ạnh B ắc c ủa hình 1 và c ạnh kia g ấp K l ần. Hình có s ố hi ệu 3 xây dựng trên c ạnh tây c ủa hình ch ữ nh ật hợp các hình 1 và 2 và c ạnh kia g ấp K l ần. Hình có s ố hi ệu 4 xây d ựng trên c ạnh nam c ủa h ợp các hình 1,2,3 và c ạnh kia g ấp K l ần. Hình có s ố hi ệu 5 xây d ựng trên c ạnh đông c ủa h ợp các hình 1,2,3,4 và c ạnh kia g ấp K l ần. T ươ ng t ự quy lu ật đó v ới các hình mang th ứ t ự 6,7 Bài toán đặt ra là cho tr ước 3 s ố th ực K,X,Y, hãy cho bi ết s ố hi ệu nh ỏ nh ất c ủa hình ch ữ nh ật ch ứa điểm có to ạ độ (X,Y) Dữ li ệu: Vào t ừ b ởi file v n b ản REC.INP g ồm 1 s ố dòng. Mỗi dòng g ồm 3 s ố K,X,Y v ới ý ngh a nêu trên. Kết qu ả: Ghi ra file v n b ản REC.OUT nh ư sau: Với m ỗi dòng c ủa file d ữ li ệu ghi trên 1 dòng s ố hi ệu c ủa điểm đã cho: Chú ý: K, X, Y có th ể có t ới 100 ch ữ s ố. Ví d ụ: REC.INP REC.OUT 3 0 1 1 2 7 -2 5 4 1 17 2 N W E S 38
029. S N C T Trên m ột n ền ph ẳng đã được chia thành các l ưới ô vuông đơn v ị g ồm mxn ô (m, n ≤ 100), ng ười ta đặt ch ồng khít lên nhau các kh ối l ập ph ươ ng đơ n v ị thành nh ững c ột. Kh ối d ưới cùng c ủa c ột chi ếm tr ọn m ột ô c ủa l ưới. Chi ều cao c ủa m ỗi c ột được tính b ằng s ố kh ối l ập ph ươ ng đơ n v ị t ạo thành c ột đó. Sau khi x ếp xong toàn b ộ các c ột, ng ười ta ti ến hành sơn các m ặt nhìn th ấy được c ủa các c ột. Yêu c ầu: Bi ết chi ều cao c ủa m ỗi c ột, hãy tính s ố đơn v ị di ện tích c ần s ơn. Dữ li ệu vào đặt trong file v n b ản PAINT.INP. Trong đó: Dòng đầu tiên ghi hai s ố nguyên d ươ ng m, n là kích th ước c ủa l ưới n ền (m hàng, n c ột) m dòng ti ếp theo, dòng th ứ i ghi n s ố nguyên không âm, s ố nguyên th ứ j bi ểu th ị chi ều cao c ủa c ột dựng t ại ô (i, j) c ủa l ưới. Các s ố cách nhau ít nh ất m ột d ấu cách. Kết qu ả ra đặt trong file v n b ản PAINT.OUT, ghi s ố di ện tích c ần s ơn. Ví d ụ: Với hình v ẽ bên, các c ột được xây trên n ền kích th ước 2x3. Các file d ữ li ệu vào và k ết qu ả ra s ẽ là: PAINT.INP PAINT.OUT 2 3 42 4 3 4 1 2 1 39
030. C T V I Một c ơ s ở may m ặc chuyên s ản xu ất kh n vuông đủ m ọi kích c ỡ, nguyên li ệu là các t ấm v ải. V ới một t ấm v ải hình ch ữ nh ật chi ều dài m đơ n v ị và chi ều r ộng n đơn v ị (m, n nguyên d ươ ng không quá 100), ng ười ta có hai cách c ắt, c ắt ngang và c ắt d ọc. Đặc điểm c ủa m ỗi thao tác c ắt là: m ỗi l ần c ắt b ắt bu ộc ph ải c ắt r ời m ột m ảnh v ải hình ch ữ nh ật thành hai m ảnh khác c ng hình ch ữ nh ật và kích th ước hai m ảnh c ắt r ời đó c ng ph ải là s ố nguyên. Yêu c ầu: Cho tr ớc t ấm v ải kích th ớc m x n. Hãy tìm cách c ắt t ấm v ải đó thành nh ững m ảnh vuông ( không đợc để l ại m ột m ảnh nào không vuông) sao cho s ố m ảnh vuông c ắt ra là ít nh ất. Dữ li ệu: Vào t ừ file v n b ản CUT.INP g ồm 1 dòng ch ứa hai s ố m, n cách nhau 1 d ấu cách Kết qu ả: Ghi ra file v n b ản CUT.OUT. Trong đó: • Dòng 1: Ghi s ố K là s ố m ảnh vuông t ối thi ểu có th ể c ắt ra được • K dòng ti ếp theo, m ỗi dòng ghi 3 s ố X, Y, d. ở đây (X, Y) là to ạ độ ô vuông ở góc trái trên c ủa một hình vuông c ắt ra được và d là độ dài c ạnh hình vuông đó. Quy ước to ạ độ c ủa ô ở góc trái trên hình ch ữ nh ật ban đầ u là (1, 1). To ạ độ c ủa ô ở góc ph ải d ưới hình ch ữ nh ật ban đầ u là (m, n). Ba s ố X, Y, d ghi cách nhau ít nh ất 1 d ấu cách. Ví d ụ: 1 2 3 4 5 6 1 2 3 4 CUT.INP CUT.OUT 4 6 3 1 1 4 1 5 2 3 5 2 40
031. CHIA K O Cho n gói k ẹo đánh s ố t ừ 1 đế n n, gói k ẹo th ứ i có A i viên k ẹo. Gi ả thi ết 2 ≤ n ≤ 200 và 1 ≤ A i ≤ 200 v ới ∀i: 1 ≤ i ≤ n. Yêu c ầu: Chia n gói k ẹo đã cho làm hai nhóm sao cho hi ệu s ố k ẹo c ủa hai nhóm chênh l ệch nhau ít nh ất, n ếu có nhi ều cách chia thì ch ỉ c ần ch ỉ ra m ột cách. Dữ li ệu: Vào t ừ file v n b ản CANDY.INP. Trong đó: • Dòng đầu tiên ghi s ố n • n dòng ti ếp theo, dòng th ứ i ghi s ố A i Kết qu ả: Ghi ra file v n b ản CANDY.OUT. Trong đó: • Dòng đầu tiên ghi hai s ố m 1 và c 1 cách nhau ít nh ất m ột d ấu cách, m 1 là s ố gói nhóm I, c 1 là số kẹo nhóm I. • m1 dòng ti ếp theo, m ỗi dòng ghi ch ỉ s ố m ột gói k ẹo được ch ọn vào nhóm I • Dòng m 1+2 ghi hai s ố m 2 và c 2 cách nhau ít nh ất m ột d ấu cách, m 2 là s ố gói nhóm II, c 2 là số kẹo nhóm II. • m2 dòng ti ếp theo, m ỗi dòng ghi ch ỉ s ố m ột gói k ẹo được ch ọn vào nhóm II Ví d ụ: CANDY.INP CANDY.OUT CANDY.INP CANDY.OUT 6 3 111 10 6 27 100 1 1 2 4 4 2 3 9 5 3 4 5 3 111 4 5 6 2 5 6 98 3 6 7 6 7 4 28 8 1 9 8 10 9 10 41
032. B NG QUAN H Cho b ảng vuông A, kích th ước nxn, các ph ần t ử là s ố nguyên ∈ {-2, -1, 0, 1, 2, 3}. Gi ả thi ết 2 ≤ n ≤ 200. Bảng A g ọi là t ươ ng thích v ới dãy T = (t 1, t 2, , t n), hay dãy T t ươ ng thích v ới b ảng A n ếu: • Aij = 0 ⇒ ti = t j • Aij = 1 ⇒ ti t j • Aij = 2 ⇒ ti ≤ t j • Aij = -2 ⇒ ti ≥ t j • Aij = 3 ⇒ ti ≠ t j (V ới m ọi i, j: 1 ≤ i, j ≤ n) Ví d ụ: Dãy T = (1, 4, 5, 4, 5, 9) t ươ ng thích v ới b ảng: A 1 2 3 4 5 6 1 0 1 1 1 2 2 2 -2 0 1 0 2 2 3 -2 -1 0 3 0 1 4 -2 -2 3 0 1 1 5 -1 -2 0 -1 0 1 6 -1 -2 -1 -1 -1 0 Dãy T = (10, 20, 30, 20, 30, 40) c ng t ươ ng thích v ới b ảng Yêu c ầu, cho tr ớc b ảng quan h ệ A, hãy tìm dãy s ố nguyên d ơ ng T = (t 1, t 2, , t n) t ơ ng thích với b ảng A mà max(T) là bé nh ất có th ể. Bi ết r ằng luôn t ồn t ại m ột dãy nh v ậy Dữ li ệu: Vào t ừ file v n b ản REL.INP: • Dòng 1: Ch ứa s ố n • n dòng ti ếp theo, dòng th ứ i ghi n s ố trên dòng i c ủa b ảng A theo đúng th ứ t ự t ừ A i1 đến A in Kết qu ả: Ghi ra file v n b ản REL.OUT: Ch ỉ g ồm 1 dòng ghi n s ố c ủa dãy T tìm được theo đúng th ứ t ự t ừ t 1 đến t n. Các s ố trên m ột dòng c ủa Input/ Output File cách nhau ít nh ất 1 d ấu cách Ví d ụ: REL.INP REL.OUT 6 1 2 3 2 3 4 0 1 1 1 2 2 -2 0 1 0 2 2 -2 -1 0 3 0 1 -2 -2 3 0 1 1 -1 -2 0 -1 0 1 -1 -2 -1 -1 -1 0 42
033. ONG N ƯC Nền ph ẳng c ủa m ột công tr ường xây dựng đã được chia thành l ưới ô vuông đơn v ị kích th ước mxn ô. Trên m ỗi ô (i, j) c ủa l ưới, ng ười ta d ựng m ột c ột bê tông hình h ộp có đáy là ô (i, j) và chi ều cao là Hij đơ n v ị. Sau khi d ựng xong, thì tr ời đổ m ưa to và đủ lâu. Gi ả thi ết r ằng n ước không th m th ấu qua các c ột bê tông c ng nh ư không rò r ỉ qua các đường ghép gi ữa chúng. Yêu c ầu: Xác đị nh l ợng n ớc đọ ng gi ữa các c ột Chú ý k ỹ thu ật: m, n, H ij là các s ố nguyên d ươ ng. 1 ≤ m, n ≤ 100. 1 ≤ H ij ≤ 1000 Dữ li ệu: Vào t ừ file v n b ản WATER.INP được ghi d ưới khuôn d ạng sau: Dòng 1: m n Dòng 2: H11 H 12 H 1n Dòng 3: H21 H 22 H 2n Dòng m + 1: Hm1 H m2 H mn Các s ố trên 1 dòng các nhau ít nh ất 1 d ấu cách K ết qu ả: Ghi ra file v n b ản WATER.OUT ch ứa s ố đơn v ị kh ối n ước đọ ng Ví d ụ: WATER.INP WATER.OUT WATER.INP WATER.OUT 5 5 64 5 7 27 9 9 9 9 9 3 3 3 3 3 3 3 9 2 2 2 9 3 1 1 1 1 1 3 9 2 1 2 9 3 1 2 2 2 1 3 9 2 2 2 9 3 1 1 1 1 1 3 9 9 9 9 9 3 3 3 3 3 3 3 WATER.INP WATER.OUT 10 10 128 9 9 9 9 9 9 9 9 9 9 9 1 1 1 1 9 1 1 1 9 9 1 1 1 1 1 1 1 1 9 9 1 1 1 1 9 1 1 1 9 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 9 1 1 1 9 9 1 1 1 1 9 1 1 1 9 9 1 1 1 1 9 1 1 1 9 9 1 1 1 1 9 1 1 1 9 9 9 9 9 9 9 9 1 9 9 43
034. TR TI N Nước Silverland s ử d ụng h ệ th ống 20 lo ại ti ền xu, trong đó các xu có m ệnh giá là m ột s ố chính ph ươ ng t ừ 1 2 đến 20 2: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400. Với h ệ th ống này, để tr ả 10 xu ta có 4 cách: 1. Tr ả 10 đồ ng 1 xu 2. Tr ả 6 đồ ng 1 xu và 1 đồng 4 xu 3. Tr ả 2 đồ ng 1 xu và 2 đồng 4 xu 4. Tr ả 1 đồ ng 1 xu và 1 đồng 9 xu Nhi ệm v ụ c ủa b ạn là xác định xem có bao nhiêu cách tr ả m ột s ố ti ền cho tr ớc ở Silverland và cho bi ết m ột cách tr ả ph ải dùng ít đồng xu nh ất. Dữ li ệu vào t ừ file v n b ản COIN.INP Ghi s ố ti ền nguyên d ươ ng không l ớn h ơn 666 xu. Kết qu ả: Đưa ra file v n b ản COIN.OUT • Dòng 1: Ghi s ố cách tr ả s ố ti ền ghi trong file d ữ li ệu • Dòng 2: Ghi s ố đồ ng xu t ối thi ểu ph ải tr ả • Các dòng ti ếp theo, m ỗi dòng ghi hai s ố a, b cách nhau ít nh ất m ột d ấu cách: cho bi ết s ẽ có a đồng xu lo ại m ệnh giá b 2 trong ph ươ ng án t ối ưu (dùng ít đồng xu nh ất) Ví d ụ: COIN.INP COIN.OUT COIN.INP COIN.OUT COIN.INP COIN.OUT 10 4 19 10 499 9508585 2 3 3 1 3 1 1 2 15 1 1 2 3 1 7 44
035. HOÁN V CH CÁI Cho m ột xâu S ch ỉ g ồm các ch ữ cái in hoa, 1 ≤ độ dài ≤ 9. Hãy l ập ch ơ ng trình tr ả l ời hai câu h ỏi sau: • Có bao nhiêu cách hoán v ị các ch ữ cái c ủa xâu S • Li ệt kê các hoán v ị đó theo th ứ t ự t ừ điển. Dữ li ệu: Vào t ừ file v n bản PERMUTE.INP g ồm 1 dòng ch ứa xâu S Kết qu ả: Ghi ra file v n b ản PERMUTE.OUT. • Dòng 1: Ghi s ố l ượng hoán v ị tìm được (K) • K dòng ti ếp theo, m ỗi dòng ghi m ột xâu hoán v ị c ủa xâu S (ph ải li ệt kê theo đúng th ứ t ự t ừ điển) PERMUTE.INP PERMUTE.OUT ABAB 6 AABB ABAB ABBA BAAB BABA BBAA 45
036. D TI C BÀN TRÒN Có n nhà khoa h ọc đánh s ố 1, 2, , n và 26 l nh v ực khoa h ọc ký hi ệu A, B, C, , Z. Thông tin v ề ng ười th ứ i được cho b ởi m ột xâu ký t ự Si g ồm các ch ữ cái in hoa th ể hi ện nh ững l nh v ực khoa h ọc mà ng ười đó bi ết. Ví d ụ: S 2 = 'ABCXYZ' cho bi ết nhà khoa h ọc th ứ 2 có hi ểu bi ết v ề các l nh v ực A, B, C, X, Y, Z. Một l ần c ả n nhà khoa h ọc đế n d ự m ột b ữa ti ệc. Ch ủ nhân c ủa b ữa ti ệc đị nh x ếp n nhà khoa h ọc ng ồi quanh m ột bàn tròn, nh ưng m ột v ấn đề khi ến chủ nhân r ất khó x ử là các nhà khoa h ọc c ủa chúng ta có hi ểu bi ết xã h ội t ươ ng đối kém, nên n ếu nh ư ph ải ng ồi c ạnh m ột ai đó không hi ểu bi ết gì v ề các l nh v ực c ủa mình thì r ất khó nói chuy ện. Vậy hãy giúp ch ủ nhân x ếp n nhà khoa h ọc ng ồi quanh bàn tròn sao cho hai ng ười b ất k ng ồi c ạnh nhau ph ải có ít nh ất m ột l nh v ực hi ểu bi ết chung, để các nhà khoa h ọc c ủa chúng ta không nh ững n ngon mà còn có th ể trò chuy ện rôm r ả. Dữ li ệu: Vào t ừ file v n b ản PARTY.INP. Trong đó: • Dòng 1: Ghi s ố n • n dòng ti ếp theo, dòng th ứ i ghi xâu ký t ự Si Kết qu ả: Ghi ra file v n b ản PARTY.OUT g ồm n dòng. • Dòng th ứ i ghi nhà khoa h ọc ng ồi t ại v ị trí i c ủa bàn (Các v ị trí trên bàn tròn được đánh s ố t ừ 1 đến n theo chi ều kim đồ ng h ồ) Lưu ý: • n ≤ 20 • Nếu có nhi ều cách x ếp thì ch ỉ c ần ch ỉ ra m ột cách • Nếu không có cách x ếp thì ghi vào file PARTY.OUT m ột dòng: NO SOLUTION Ví d ụ: PARTY.INP PARTY.OUT PARTY.INP PARTY.OUT PARTY.INP PARTY.OUT 6 1 10 1 6 NO SOLUTION AV 3 AX 3 AB DIQR 6 BI 2 BC DV 2 ABTX 5 CD CQ 4 AS 6 DE AC 5 IK 4 EF DR KS 8 FG BE 7 AB 9 EK 10 AK 46
037. TRÁO BÀI Có 2n lá bài, trên đó ghi l ần l ượt các s ố t ừ 1 đế n 2n (m ỗi lá bài ghi m ột s ố và không có hai lá bài nào trùng s ố). Ban đầ u các lá bài được x ếp ch ồng nhau theo th ứ t ự t ừ lá bài ghi s ố 1 đế n lá bài ghi số 2n từ d ưới lên trên. Sau đó ng ời ta ti ến hành tráo các lá bài theo cách: • Nếu th ứ t ự các lá bài t ừ d ưới lên đang là: (1, 2, 3 , n, n + 1, n + 2, n + 3, , 2n) • Sẽ tráo thành th ứ t ự m ới: (n + 1, 1, n + 2, 2, n + 3, 3, , 2n, n). Bằng cách đổ i vai trò các lá bài cho nhau, ta có th ể hình dung ra được cách tráo trong các l ần ti ếp theo. Ví d ụ: n = 3 Tr ạng thái ban đầ u: (1, 2, 3, 4, 5, 6) Sau l ần tráo th ứ nh ất: (4, 1, 5, 2, 6, 3) (Xem hình v ẽ) Sau l ần tráo th ứ hai: (2, 4, 6, 1, 3, 5) Sau l ần tráo th ứ ba: (1, 2, 3, 4, 5, 6) 6 5 3 4 6 2 5 3 1 2 4 1 Cách tráo bài này r ất hay được s ử d ụng, t ưởng r ằng nó s ẽ t ạo ra m ột hoán v ị hoàn toàn "vô t ư" đối với các quân bài nh ưng th ực ra không ph ải nh ư v ậy, sau m ột s ố h ữu h ạn l ần tráo, t ập bài l ại tr ở về tr ạng thái ban đầ u nh ư ch ưa tráo . Ví d ụ nh ư b ộ bài có 52 quân (n = 26) thì ch ỉ qua 52 l ần tráo là đâu v ẫn hoàn đấy, hay b ộ bài có 104 quân (n = 52) thì ch ỉ qua có 12 l ần tráo là s ẽ tr ở v ề tr ạng thái ban đầ u. Nhi ệm v ụ c ủa b ạn là khi bi ết đợc s ố n là m ột n ửa s ố quân bài, hãy tính xem sau ít nh ất bao nhiêu l ần tráo thì t ập bài s ẽ tr ở v ề tr ạng thái ban đầ u. Dữ li ệu: Vào t ừ file v n b ản CARD.INP ch ỉ g ồm 1 dòng ghi s ố nguyên d ươ ng n ( n ≤ 10000) Kết qu ả: Ghi ra file v n b ản CARD.OUT c ng ch ỉ g ồm 1 dòng ghi m ột s ố nguyên d ươ ng, là s ố l ần tráo tối thi ểu để t ập bài tr ở l ại tr ạng thái ban đầ u. Ví d ụ: CARD.INP CARD.OUT CARD.INP CARD.OUT CARD.INP CARD.OUT 999 333 26 52 9875 9875 47
038. I X NG HOÁ Định ngh a: • Một xâu ký t ự X g ọi là ch ứa xâu ký t ự Y n ếu nh ư có th ể xoá b ớt m ột s ố ký t ự trong xâu X để được xâu Y: Ví d ụ: Xâu '1a2b3c45d' ch ứa xâu '12345'. • Một xâu ký t ự g ọi là đối x ứng n ếu nó không thay đổ i khi ta vi ết các ký t ự trong xâu theo th ứ t ự ng ược l ại: Ví d ụ: 'abcABADABAcba', 'MADAM' là các xâu đối x ứng Cho tr ớc m ột xâu ký t ự S có độ dài không quá 128. Hãy tìm xâu ký t ự T tho ả mãn c ả 3 điều ki ện: 1. Đối x ứng 2. Ch ứa xâu S 3. Có ít ký t ự nh ất (có độ dài ng ắn nh ất) Lưu ý r ằng v ới m ột xâu S, n ếu có nhi ều xâu T tho ả mãn đồng th ời 3 điều ki ện trên thì ch ỉ c ần cho bi ết m ột. Ch ẳng h ạn v ới S = 'a_101_b' thì ch ọn T = 'ab_101_ba' hay T = 'ba_101_ab' đề u đúng. Dữ li ệu: Vào t ừ file v n b ản STR.INP ch ỉ g ồm 1 dòng ch ứa xâu ký t ự S Kết qu ả: Ghi ra file v n b ản STR.OUT c ng ch ỉ g ồm 1 dòng ghi xâu ký t ự T Ví d ụ: Một vài file d ữ li ệu vào và file k ết qu ả t ươ ng ứng: STR.INP STR.OUT STR.INP STR.OUT MADAM MADAM edbabcd edcbabcde STR.INP STR.OUT 00_11_22_33_222_1_000 000_11_222_33_222_11_000 STR.INP STR.OUT abcdefg_hh_gfe_1_d_2_c_3_ba ab_3_c_2_d_1_efg_hh_gfe_1_d_2_c_3_ba 48
039. M NG MÁY TÍNH Trên m ột n ền ph ẳng v ới h ệ to ạ độ Decattes vuông góc đặ t n máy tính và m cáp m ạng n ối chúng. Các máy tính được đánh s ố 1, 2, , n và các cáp m ạng được đánh s ố 1, 2, , m. V ị trí c ủa máy tính th ứ i được cho b ởi to ạ độ (X i, Y i), cáp m ạng th ứ j được cho n ối gi ữa hai máy tính (p j, q j). Hai máy tính b ất k có th ể chuy ển thông tin cho nhau b ằng m ột trong hai cách: Truy ền tr ực ti ếp qua cáp n ối chúng (n ếu có) ho ặc truy ền qua m ột s ố máy trung gian. Yêu c ầu: Ng ời ta mu ốn n ối thêm các dây cáp m ạng sau cho hai máy b ất k trong c ả h ệ th ống n máy tính đều có th ể chuy ển thông tin cho nhau. Hãy ch ỉ ra cách n ối thêm các dây cáp m ạng sao cho t ổng độ dài các dây cáp n ối thêm là ít nh ất, gi ả thi ết r ằng các dây cáp m ạng đợc n ối theo đờng th ẳng gi ữa hai máy. Dữ li ệu: Vào t ừ file v n b ản NET.INP theo khuôn d ạng sau: Dòng Nội dung 1 n m 2 x1 y 1 3 x2 y 2 n + 1 xn y n n + 2 p1 q 1 n + 3 p2 q 2 n + m + 1 pm q m Kết qu ả: Ghi ra file v n b ản NET.OUT. Trong đó: • Dòng 1: Ghi s ố nguyên d ươ ng K và s ố th ực L. K là s ố dây cáp m ạng ph ải n ối thêm và L là t ổng độ dài các dây cáp m ạng n ối thêm (L l ấy chính xác t ới 6 ch ữ s ố sau d ấu ch ấm th ập phân). • K dòng ti ếp theo, m ỗi dòng ghi s ố hi ệu hai máy tính, cho bi ết s ẽ đặ t thêm dây cáp m ạng n ối hai máy tính đó Lưu ý: 1. Các s ố trên m ột dòng c ủa Input/ Output file cách nhau ít nh ất m ột d ấu cách 2. 1 ≤ n ≤ 1000; 0 ≤ m ≤ 10000 và to ạ độ c ủa các máy tính là s ố nguyên có giá tr ị tuy ệt đố i không quá 1000. Ví d ụ: NET.INP NET.OUT 9 5 3 3.000000 1.0 1.0 1 2 2.0 1.0 4 5 4.0 1.0 3 6 1.0 2.0 7 8 9 2.0 2.0 4.0 2.0 4 5 6 1.0 3.0 2.0 3.0 1 2 3 4.0 3.0 1 4 2 3 4 7 5 8 6 9 49
040. L T Ô MI NÔ Cho n quân đô-mi-nô x ếp d ựng đứ ng theo hàng ngang và được đánh s ố t ừ 1 đế n n. Quân đô-mi-nô th ứ i có s ố ghi ở ô trên là a i và s ố ghi ở ô d ưới là b i. Xem hình v ẽ: 1 2 3 4 5 6 1 1 4 4 0 6 6 3 1 1 6 1 Bi ết r ằng 1 ≤ n ≤ 100 và 0 ≤ a i, b i ≤ 6 v ới ∀i: 1 ≤ i ≤ n. Cho phép l ật ng ược các quân đô-mi-nô. Khi m ột quân đô-mi-nô th ứ i b ị l ật, nó s ẽ có s ố ghi ở ô trên là b i và s ố ghi ở ô d ưới là a i. Vấn đề đặ t ra là hãy tìm cách l ật các quân đô-mi-nô sao cho chênh l ệch gi ữa t ổng các s ố ghi ở hàng ô trên và t ổng các s ố ghi ở hàng ô d ới là t ối thi ểu. N ếu có nhi ều ph ơ ng án l ật t ốt nh nhau, thì ch ỉ ra ph ơ ng án ph ải l ật ít quân nh ất. Dữ li ệu: Vào t ừ file v n b ản DOMINO.INP. Trong đó: • Dòng 1 ghi s ố n • Dòng 2 ghi n s ố a 1, a 2, , a n theo đúng th ứ t ự. • Dòng 3 ghi n s ố b 1, b 2, , b n theo đúng th ứ t ự. Kết qu ả: Ghi ra file v n b ản DOMINO.OUT. Trong đó: • Dòng 1: Ghi s ố quân Đô-mi-nô b ị l ật (C) • Dòng 2: Ghi ch ỉ s ố c ủa C quân Đô-mi-nô b ị l ật • Dòng 3: Ghi độ chênh l ệch gi ữa t ổng các s ố hàng trên và t ổng các s ố hàng d ưới sau khi l ật. Các s ố trên m ột hàng c ủa Input/ Output File cách nhau ít nh ất m ột d ấu cách. Ví d ụ: DOMINO.INP DOMINO.OUT 6 2 1 1 4 4 0 6 6 5 6 3 1 1 6 1 0 50
041. S NH PHÂN L N NH T Xâu nh ị phân là xâu ký t ự ch ỉ g ồm các ch ữ s ố 0 và 1. Ng ười ta nói xâu nh ị phân X là xâu con c ủa xâu nh ị phân Y n ếu có th ể xóa b ớt m ột s ố ký t ự trong xâu Y để được xâu X. Ví d ụ: Xâu '0101' là xâu con c ủa xâu '000111000111'. Lưu ý r ằng n ếu nh ư xâu X = xâu Y thì xâu X c ng được coi là xâu con c ủa xâu Y. Nếu coi xâu nh ị phân là bi ểu di ễn nh ị phân c ủa m ột s ố nguyên thì s ố nguyên đó g ọi là tr ị s ố c ủa xâu nh ị phân. Yêu c ầu: Cho tr ớc hai xâu nh ị phân A và B, hãy tìm m ột xâu nh ị phân C là xâu con c ủa c ả A và B mà tr ị s ố c ủa C là l ớn nh ất có th ể đợc. Dữ li ệu: Nh ập t ừ file v n b ản BSTR.INP g ồm 2 dòng: • Dòng 1: Ghi xâu nh ị phân A • Dòng 2: Ghi xâu nh ị phân B Kết qu ả: T ạo file v n b ản BSTR.OUT g ồm 1 dòng ghi xâu nh ị phân C tìm được. Ví d ụ: BSTR.INP BSTR.OUT BSTR.INP BSTR.OUT 00000000101000101010 1000010101 110011001100 1100110011 1000000000000010101 001100110011 51
042. S N CÁC HÌNH CH NH T Một b ảng hình ch ữ nh ật ph ẳng đã được chia thành các y mi ền hình ch ữ nh ật không giao nhau và có c ạnh song 6 song v ới c ạnh c ủa b ảng. Ng ười ta mu ốn s ơn các mi ền 4 ( Đỏ) ch ữ nh ật này, m ỗi mi ền s ẽ được s ơn b ằng m ột màu 6 (xanh) định s ẵn. 5 Vì khi s ơn có hi ện t ượng s ơn ch ảy xu ống phía d ưới 3 (xanh) nên m ột mi ền ch ữ nh ật phía d ưới ch ỉ được phép s ơn 4 5 ( Đỏ) khi mà các mi ền trên, có ảnh h ưởng t ới nó đã được 7 (xanh) sơn. 3 Theo hình bên thì mi ền 2 ch ỉ được s ơn sau khi mi ền 5 2 1 ( Đỏ) và mi ền 7 đã s ơn xong. Nói m ột cách chính xác: Mi ền 2 (xanh) A b ắt bu ộc ph ải s ơn sau mi ền B n ếu c ả hai điều ki ện 1 sau th ỏa mãn: 1. Hình chi ếu c ủa mi ền A và mi ền B trên tr ục hoành 0 1 2 3 4 5 6 x có ít nh ất hai điểm chung 2. Tung độ tâm mi ền B l ớn h ơn tung độ tâm mi ền A Để s ơn t ất c ả các mi ền, ng ười ta s ử d ụng m ột h ệ th ống ch ổi s ơn đủ màu s ắc, hai ch ổi s ơn khác nhau có màu khác nhau. Hãy tìm th ứ t ự s ơn các mi ền ch ữ nh ật sao cho s ố l ần ph ải thay ch ổi là ít nh ất. Dữ li ệu: Vào t ừ file v n b ản PAINT.INP. Trong đó: • Dòng đầu tiên ghi s ố mi ền ch ữ nh ật trong b ảng (n) • n dòng ti ếp theo, Dòng th ứ i ghi thông tin v ề mi ền th ứ i g ồm 5 s ố nguyên X 1 Y 1 X 2 Y 2 C theo đúng th ứ t ự đó. (X 1, Y 1) là t ọa độ đỉ nh trái d ưới, (X 2, Y 2) là t ọa độ đỉ nh ph ải trên, C là mã màu cần tô cho mi ền. Kết qu ả: Ghi ra file v n b ản PAINT.OUT. Trong đó • Dòng 1: Ghi s ố l ần thay ch ổi ít nh ất (tính c ả l ần đầ u tiên khi b ắt đầ u s ơn) • Dòng 2: Ghi s ố hi ệu các mi ền ch ữ nh ật theo đúng th ứ t ự s ẽ tô. Các s ố trên m ột dòng c ủa Input/ Output file ghi cách nhau ít nh ất m ột d ấu cách. Gi ới h ạn: 1 ≤ n ≤ 20; 1 ≤ mã màu ≤ 15; 0 ≤ các t ọa độ ≤ 100; Ví d ụ: V ới hình v ẽ trong bài, s ố 2 là mã màu đỏ và s ố 1 là mã màu xanh. PAINT.INP PAINT.OUT 7 3 4 0 6 3 2 4 5 3 6 7 2 1 0 0 4 2 1 4 3 6 5 1 2 5 6 6 2 2 2 4 5 2 0 4 2 6 1 0 2 2 4 1 52
043. PHÂN HO CH TAM GIÁC Xét m ột đa giác l ồi v ới n c ạnh, các đỉ nh được đánh s ố theo th ứ t ự t ừ 1 t ới n. M ột b ộ n - 3 đường chéo đôi m ột không c ắt nhau sẽ chia đa giác đã cho thành n - 2 tam giác. Ta g ọi b ộ g ồm n - 3 đường chéo đó là m ột phép tam giác phân c ủa đa giác l ồi ban đầ u. Tr ọng s ố c ủa m ột phép tam giác phân là tổng độ dài các đường chéo được s ử d ụng trong phép phân ho ạch. Yêu c ầu: Cho tr ớc m ột đa giác l ồi, hãy tìm m ột phép tam giác phân nh ỏ nh ất (có tr ọng s ố nh ỏ nh ất) Dữ li ệu: Vào t ừ file v n b ản POLYGON.INP. Trong đó: • Dòng 1: Ghi s ố đỉ nh n c ủa đa giác đã cho • n dòng ti ếp theo, dòng th ứ i g ồm 2 s ố th ực Xi, Yi theo th ứ t ự là hoành độ và tung độ c ủa đỉnh th ứ i. (Các đỉnh được li ệt kê theo đúng th ứ t ự g ọi tên đa giác) Kết qu ả: Ghi ra file v n b ản POLYGON.OUT. Trong đó: • Dòng 1: Ghi tr ọng s ố c ủa phép tam giác phân nh ỏ nh ất • n - 3 dòng ti ếp theo, m ỗi dòng ghi hai s ố nguyên d ươ ng i, j cho bi ết có s ử d ụng đường chéo nối đỉnh i v ới đỉ nh j trong phép phân ho ạch tìm được Các s ố trên m ột dòng c ủa Input/Output file được ghi cách nhau ít nh ất m ột d ấu cách. Gi ới h ạn: 1. n nguyên d ươ ng, 4 ≤ n ≤ 100 2. Các to ạ độ đỉ nh là s ố th ực: Xi , Yi  ≤ 10 6 3. Tr ọng s ố c ủa phép tam giác phân nh ỏ nh ất được ghi d ưới d ạng s ố th ực làm tròn l ấy 6 ch ữ s ố sau dấu ch ấm th ập phân. Ví d ụ: POLYGON.INP POLYGON.OUT 6 12.000000 y 4 0 2 6 5 1 2 4 6 4 4 6 2 4 0 3 2 1 0 x 53
044. CÁC THÀNH PH N LIÊN THÔNG M NH Cho đồ th ị có h ướng G = (V, E) g ồm n đỉ nh và m cung. Một đồ th ị con G' c ủa G được g ọi là m ột thành ph ần liên thông m ạnh n ếu hai điều ki ện sau tho ả mãn: 1. Ho ặc G' ch ỉ g ồm 1 đỉ nh, ho ặc v ới hai đỉ nh i, j b ất k c ủa G' luôn t ồn t ại đường đi t ừ đỉ nh i tới đỉ nh j. 2. Vi ệc thêm vào G' m ột đỉ nh b ất k s ẽ làm h ỏng tính chất 1 Yêu c ầu: Cho bi ết s ố thành ph ần liên thông m ạnh c ủa đồ th ị đã cho và li ệt kê t ất c ả các thành ph ần liên thông m ạnh. Dữ li ệu: Vào t ừ file v n b ản GRAPH.INP, trong đó: • Dòng 1: Ghi hai s ố n, m • m dòng ti ếp theo, m ỗi dòng ghi hai s ố nguyên d ươ ng x, y th ể hi ện có cung n ối t ừ đỉ nh x t ới đỉ nh y Kết qu ả: Ghi ra file v n b ản GRAPH.OUT, trong đó: • Dòng 1: Ghi s ố thành ph ần liên thông m ạnh (K) • K dòng ti ếp theo, dòng th ứ i, ghi các đỉ nh thu ộc thành ph ần liên thông m ạnh th ứ i tìm được Các s ố trên m ột dòng c ủa Input/ Output file đợc ghi cách nhau ít nh ất m ột d ấu cách Gi ới h ạn: 1 ≤ n ≤ 1000; 1 ≤ m ≤ 3000 Ví d ụ: GRAPH.INP GRAPH.OUT 4 4 2 1 1 2 1 2 3 2 2 3 4 3 1 3 4 4 3 54
045. MÃ GRAY Một hình tròn được chia làm 2 n hình qu ạt đồ ng tâm, các hình qu ạt được đánh s ố từ 1 t ới 2 n theo chi ều kim đồ ng h ồ. Hãy ch ỉ ra một cách x ếp t ất c ả s ố t ừ 0 t ới 2 n - 1 vào các hình qu ạt, m ỗi s ố vào một hình qu ạt sao cho b ất c ứ hai s ố nào ở hai hình qu ạt c ạnh nhau đề u ch ỉ khác nhau đúng 1 bít trong bi ểu di ễn nh ị phân c ủa nó. Ví d ụ: V ới n = 4: 0 = 0000 6 4 1 = 0001 14 12 2 = 0010 3 = 0011 10 8 4 = 0100 5 = 0101 6 = 0110 2 0 7 = 0111 8 = 1000 3 1 9 = 1001 10 = 1010 11 11 = 1011 9 12 = 1100 13 = 1101 15 13 14 = 1110 7 5 15 = 1111 Dữ li ệu: Nh ập t ừ bàn phím s ố nguyên d ươ ng n. Gi ới h ạn (1 ≤ n ≤ 20). Kết qu ả: Ghi ra File (of LongInt) GRAYCODE.OUT g ồm 2 n s ố nguyên ki ểu LongInt theo đúng th ứ t ự t ừ s ố ghi trên hình qu ạt 1 t ới s ố ghi trên hình qu ạt 2 n. 55
046. D ÁN XÂY C U Trong m ột khu công viên n ước có n hòn đảo nh ỏ và m ột s ố c ầu n ối gi ữa chúng. Gi ả thi ết r ằng các cầu được n ối theo đường th ẳng. Hai câu h ỏi đặ t ra là: 1. Có t ồn t ại m ột đường đi qua t ất c ả các đả o m ỗi đả o đúng m ột l ần hay không ? 2. Nếu không t ồn t ại đường đi nh ư v ậy, hãy ch ỉ ra các xây thêm các cây c ầu để th ực hi ện được điều đó sao cho t ổng độ dài nh ững cây c ầu xây thêm là ít nh ất. Dữ li ệu: Vào t ừ file v n b ản WPARK.INP • Dòng 1: Ghi s ố đả o n ( ≤ 16) và s ố c ầu đã có m • n dòng ti ếp theo, dòng th ứ i g ồm 2 s ố th ực x[i] y[i] là to ạ độ c ủa hòn đảo i. • m dòng ti ếp theo, dòng th ứ j ghi s ố hi ệu hai đả o t ươ ng ứng v ới chi ếc c ầu th ứ j. Kết qu ả: Ghi ra file v n b ản WPARK.OUT • Dòng 1: ghi s ố k là s ố c ầu c ần xây thêm và s ố th ực T (l ấy t ới 6 ch ữ s ố sau d ấu ch ấm th ập phân) là t ổng độ dài các cây c ầu xây thêm • k dòng ti ếp theo, m ỗi dòng ghi s ố hi ệu hai đả o t ươ ng ứng v ới m ột cây c ầu xây thêm • Dòng k + 2 ghi s ố hi ệu các đả o trên đường đi tìm được (sau khi đã xây thêm c ầu) Các s ố trên m ột dòng c ủa Input/ Output file được ghi cách nhau ít nh ất m ột d ấu cách. Ví d ụ: WPARK.INP WPARK.OUT 10 11 1 1.000000 y 3.0 3.0 4 5 6.0 3.0 7 8 3 1 4 5 2 6 9 10 2.0 2.0 1 2 4.0 2.0 5.0 2.0 3 4 5 6 7.0 2.0 1.0 1.0 3.0 1.0 7 8 9 10 6.0 1.0 8.0 1.0 0 x 1 3 1 4 2 5 2 6 3 8 4 8 5 9 6 9 7 8 8 9 9 10 56
047. B O T N NG V T HOANG DÃ Một khu b ảo t ồn độ ng v ật có n đị a điểm và các đường đi hai chi ều n ối các đị a điểm đó, đị a điểm th ứ i có nhi ệt độ là t i, gi ữa hai đị a điểm b ất k có nhi ều nh ất là m ột đường đi n ối chúng. Ng ười ta mu ốn di chuy ển m ột loài động v ật quý hi ếm t ừ đị a điểm A t ới đị a điểm B, tuy nhiên n ếu chênh l ệch v ề nhi ệt độ gi ữa hai đị a điểm liên ti ếp trên đường đi là quá cao thì loài động v ật này r ất có th ể b ị ch ết. Yêu c ầu: Hãy ch ỉ ra m ột hành trình mà độ l ệch nhi ệt độ l ớn nh ất gi ữa hai đị a điểm liên ti ếp b ất k trên đờng đi là c ực ti ểu. Dữ li ệu: Vào t ừ file v n b ản MOVE.INP • Dòng 1: Ch ứa ba s ố n, A, B (2 ≤ n ≤ 200; A ≠ B) • Dòng 2: Ch ứa n s ố t ự nhiên t 1, t 2, , t n ( ∀i: 0 ≤ t i ≤ 20000) • Các dòng ti ếp theo, m ỗi dòng ch ứa hai s ố nguyên d ươ ng u, v cho bi ết gi ữa hai đị a điểm u và v có đường đi n ối chúng. Kết qu ả: Ghi ra file v n b ản MOVE.OUT • Dòng 1: Ghi độ l ệch nhi ệt độ l ớn nh ất gi ữa hai địa điểm liên ti ếp b ất k trên đường đi tìm được, nếu không t ồn t ại đường đi thì dòng này ghi s ố -1. • Trong tr ường h ợp tìm được đường đi thì dòng 2 ghi hành trình tìm được, b ắt đầ u t ừ đị a điểm A, ti ếp theo là nh ững đị a điểm đi qua, k ết thúc là địa điểm B. Các địa điểm ph ải được li ệt kê theo đúng th ứ t ự đi qua trên hành trình Các s ố trên m ột dòng c ủa Input/ Output file đợc ghi cách nhau ít nh ất m ột d ấu cách. Ví d ụ: MOVE.INP MOVE.OUT 7 1 4 2 22 24 20 22 29 30 24 27 26 1 2 5 7 6 3 4 2 5 1 2 1 3 1 4 30 2 4 20 1 4 7 26 2 5 3 4 3 6 3 6 4 5 29 27 4 6 5 7 6 7 57
048. PHÁ T ƯNG Có m ột toà lâu đài hình ch ữ nh ật v ới hai c ạnh là m, n nguyên d ươ ng không l ớn h ơn 50. Lâu đài được chia thành các ô vuông đơ n v ị. Các dòng ô vuông được đánh s ố t ừ 1 t ới m t ừ trên xu ống d ưới, trên m ỗi dòng, các ô được đánh s ố theo th ứ t ự t ừ 1 t ới n t ừ trái qua ph ải. Quanh m ỗi ô có th ể có t ừ 0 tới 4 b ức t ường, tuy nhiên tình tr ạng có t ường t ại các ô k ề c ạnh là không mâu thu ẫn nhau. Để th ể hi ện tình tr ạng t ường quanh m ột ô, ta gán cho m ỗi ô m ột s ố nguyên, mà trong bi ểu di ễn nh ị phân c ủa s ố nguyên đó: • Bít 0 (Bít đơ n v ị) b ằng 1 hay 0 tu theo ô đó có t ường hay không có t ường h ướng Tây • Bít 1 b ằng 1 hay 0 tu theo ô đó có t ường hay không có t ường h ướng B ắc • Bít 2 b ằng 1 hay 0 tu theo ô đó có t ường hay không có t ường h ướng Đông • Bít 3 b ằng 1 hay 0 tu theo ô đó có t ường hay không có t ường h ướng Nam Quanh lâu đài có t ường bao b ọc. Ví d ụ trong hình v ẽ d ưới, ta có m ột lâu đài 4 x 7. Tình tr ạng t ường c ủa ô (2, 2) được th ể hi ện b ởi s ố 9 = 1001 Tình tr ạng t ường c ủa ô (3, 5) được th ể hi ện b ởi s ố 13 = 1101 1 2 3 4 5 6 7 N 1 2 9 W E 3 13 S 4 Lâu đài được chia thành các phòng, các phòng phân cách nhau b ởi các b ức t ường. Hãy l ập ch ươ ng trình tr ả l ời các câu h ỏi sau: 1. Cho bi ết lâu đài có bao nhiêu phòng 2. Cho bi ết s ố ô c ủa phòng r ộng nh ất 3. Hãy tìm cách phá đi m ột và ch ỉ m ột b ức t ường để được m ột phòng r ộng nh ất có th ể Dữ li ệu: Vào t ừ file v n b ản DWALL.INP • Dòng 1: Ghi hai s ố m, n • m dòng ti ếp theo, dòng th ứ i ghi n s ố nguyên, s ố th ứ j th ể hi ện tình tr ạng t ường quanh ô (i, j) Kết qu ả: Ghi ra file v n b ản DWALL.OUT • Dòng 1: Ghi s ố phòng • Dòng 2: Ghi s ố ô c ủa phòng r ộng nh ất • Dòng 3: Ghi hai s ố P, Q và ký t ự c ∈ {W, N, E, S} v ới ý ngh a phá t ường ở h ướng c c ủa ô (P, Q) • Dòng 4: Ghi s ố ô c ủa phòng r ộng nh ất thu được sau khi phá t ường Các s ố trên m ột dòng c ủa Input/Output file được ghi cách nhau ít nh ất m ột d ấu cách Ví d ụ: DWALL.INP DWALL.OUT 4 7 5 11 06 11 06 03 10 06 9 07 09 06 13 05 14 05 3 2 S 01 10 12 07 13 07 05 16 13 11 10 08 10 12 13 58
049. 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 m kênh n ối tr ực ti ếp gi ữa m ột s ố c ặp máy 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 máy D (S ≠ D). Để đả m b ảo an toàn, ng ười ta mu ốn chuy ển b ức thông điệp này theo hai đường truy ền tin khác nhau (t ức là không có kênh nào của m ạng được s ử d ụng trong c ả hai đường truy ền tin). Chi phí c ủa m ột đường truy ền tin được hi ểu là t ổng chi phí trên các kênh c ủa nó. Chi phí truy ền thông điệp b ằng t ổng chi phí c ủa hai đường truy ề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 truy ền thông điệp t ừ s đến t sao cho chi phí truy ền thông điệp là nh ỏ nh ất Dữ li ệu: Nh ập t ừ file vn b ản MESSAGE.INP v ới c ấu trúc nh ư sau: • Dòng đầu tiên ghi b ốn s ố n, m, S, D (n ≤100); • Mỗi dòng th ứ i trong s ố m dòng ti ếp theo ghi thông tin v ề kênh n ối th ứ i c ủa m ạng g ồm ba s ố a i, bi, c i, trong đó a i, b i là ch ỉ s ố c ủa hai máy t ươ ng ứng v ới kênh này và c i (nguyên d ươ ng ≤ 200) là chi phí để truy ền m ột đơn v ị thông tin t ừ máy ai đế n máy b i (và ng ược l ại) theo kênh này (i=1,2, ,m). Kết qu ả: Ghi ra file v n b ản MESSAGE.OUT theo c ấu trúc sau: • Dòng đầu tiên ghi chi phí truy ền thông điệp theo cách truy ền tin tìm được. • Dòng th ứ hai ghi đường truy ền tin th ứ nh ất 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 D. • Dòng th ứ ba ghi đường truy ền tin th ứ hai 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 D. Nếu không t ồn t ại cách truy ền thì ch ỉ c ần ghi vào file MESSAGE.OUT m ột dòng: NO SOLUTION Các s ố trên m ột dòng c ủa Input/ Output file ghi cách nhau ít nh ất m ột d ấu cách. Ví d ụ: 8 3 5 8 3 1 2 3 4 5 4 5 MESSAGE.INP MESSAGE.OUT 5 7 1 5 24 1 2 3 1 2 3 5 1 4 8 1 4 5 2 3 5 2 4 4 3 5 5 4 3 8 4 5 3 59
050. HÌNH VUÔNG C C I Cho m ột b ảng kích th ước mxn, được chia thành l ưới ô vuông đơn v ị m dòng n c ột. Trên các ô c ủa bảng ghi s ố 0 ho ặc 1. Các dòng c ủa b ảng được đánh s ố 1, 2 m theo th ứ t ự t ừ trên xu ống d ưới và các c ột c ủa b ảng được đánh s ố 1, 2 , n theo th ứ t ự t ừ trái qua ph ải. Hãy tìm m ột hình vuông g ồm các ô c ủa b ảng tho ả mãn các điều ki ện sau: 1. Hình vuông là đồng nh ất: t ức là các ô thu ộc hình vuông đó ph ải ghi các s ố gi ống nhau (0 ho ặc 1) 2. Cạnh hình vuông song song v ới c ạnh b ảng. 3. Kích th ớc hình vuông là l ớn nh ất có th ể. Dữ li ệu: Vào t ừ file v n b ản SQUARE.INP • Dòng 1: Ghi hai s ố m, n • m dòng ti ếp theo, dòng th ứ i ghi n s ố mà s ố th ứ j là s ố ghi trên ô (i, j) c ủa b ảng Kết qu ả: Ghi ra file v n b ản SQUARE.OUT • Dòng 1: Ghi kích th ước c ạnh hình vuông tìm được • Dòng 2: Ghi 4 s ố nguyên r 1, c 1, r 2, c 2. ở đây (r 1, c 1) là ch ỉ s ố hàng và ch ỉ s ố c ột c ủa ô thu ộc góc trên bên trái, (r 2, c 2) là ch ỉ s ố hàng và ch ỉ s ố c ột c ủa ô thu ộc góc d ưới bên ph ải hình vuông tìm được. Các s ố trên m ột dòng c ủa Input/ Output file ghi cách nhau ít nh ất m ột d ấu cách. Ví d ụ: SQUARE.INP SQUARE.OUT 11 13 7 0 0 0 0 0 1 0 0 0 0 0 0 0 3 3 9 9 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 60
051. OÀN XE QUA C U Cho m ột đoàn xe g ồm n chi ếc đi trên m ột đường m ột chi ều và đoàn xe đã được b ố trí theo th ứ t ự t ừ 1 đến n. M ỗi m ột xe trong đoàn có v ận t ốc là vi và tr ọng l ượng wi. Khi đi qua m ột chi ếc c ầu có tr ọng t ải gi ới h ạn là P thì đoàn xe ph ải chia thành các nhóm sao cho tổng tr ọng l ượng c ủa m ỗi nhóm không quá P (L ưu ý r ằng không được đả o th ứ t ự đoàn xe). Các nhóm ph ải đi tu ần t ự có ngh a là nhóm th ứ i ch ỉ được kh ởi hành khi mà toàn b ộ xe c ủa nhóm th ứ i - 1 đã qua c ầu. Gi ả thi ết r ằng P > wi v ới ∀i: 1 ≤ i ≤ n. Rõ ràng khi đó th ời gian để m ột nhóm xe qua c ầu ph ụ thu ộc vào xe ch ậm nh ất trong nhóm đó n ếu coi nh ư chi ều dài c ng nh ư kho ảng cách c ủa các xe là không đáng k ể. Hãy tìm cách chia đoàn xe thành các nhóm sao cho th ời gian mà đoàn xe sang đợc c ầu là nh ỏ nh ất có th ể đợc. Dữ li ệu: Vào t ừ file v n b ản CARGROUP.INP • Dòng đầu là 3 s ố nguyên d ươ ng n, P và L (n, P, L ≤ 1000) th ể hiện cho s ố xe, tr ọng l ượng gi ới hạn c ủa c ầu và độ dài c ủa c ầu. • Dòng th ứ i trong n dòng k ế ti ếp g ồm 2 s ố nguyên d ươ ng wi và vi (wi, vi ≤ 100) Kết qu ả: Ghi ra file v n b ản CARGROUP.OUT • Dòng đầu ghi m ột s ố th ực là t ổng th ời gian nh ỏ nh ất để xe qua c ầu, cho phép làm tròn l ấy 2 ch ữ số sau d ấu ch ấm th ập phân. • Dòng k ế ti ếp g ồm các s ố x 1, x 2, , xk th ể hi ện: nhóm 1 g ồm các xe t ừ 1 đế n xe th ứ x 1, nhóm 2 gồm các xe th ứ x 1+1 đến xe th ứ x 2 , nhóm k t ừ xe th ứ x[k - 1] t ới x[k] Các s ố trên m ột dòng c ủa Input / Output file ghi cách nhau ít nh ất m ột d ấu cách. Ví d ụ: P = 100 25 20 20 10 50 70 30 25 50 70 (km / h) 100 km 40 50 50 70 12 9 49 38 27 19 4h 5h 10h 4h 2h CARGROUP.INP CARGROUP.OUT 10 100 100 25.00 40 25 1 3 6 8 10 50 20 50 20 70 10 12 50 09 70 49 30 38 25 27 50 19 70 61
052. S L ƯNG Cho s ố nguyên d ươ ng n (n ≤ 2 000 000 000). Hãy xác định xem trong ph ạm vi t ừ 1 t ới n có bao nhiêu s ố mà trong d ạng bi ểu di ễn nh ị phân c ủa nó có đúng K ch ữ s ố 0 có ngh a. Ví d ụ: n = 18, k = 3 có 3 s ố: 1. 8 = 1000 2. 17 = 10001 3. 18 = 10010 Dữ li ệu: Vào t ừ file v n b ản NUMBER.INP, g ồm m ột dòng ch ứa hai s ố nguyên N và K cách nhau một d ấu cách. Kết qu ả: Đư a ra file NUMBER.OUT, ghi s ố l ượng các s ố tìm được Ví d ụ: NUMBER.INP NUMBER.OUT 18 3 3 62
053. THÁM HI M LÒNG T Một nhà kh ảo c ổ nghiên c ứu nh ững di s ản v n hoá c ổ đạ i ở m ột thành ph ố b ị chôn vùi d ưới lòng đất. Để thám hiểm thành ph ố đó, nhà kh ảo c ổ c ủa chúng ta bu ộc ph ải đào các đường ng ầm. Bắt đầ u t ại v ị trí xu ất phát, ông ta đào theo m ột trong 4 h ướng Đông (E), Tây (W), Nam (S), B ắc (N), m ỗi l ần đào m ột đơn v ị độ dài. Sau đó có th ể đào ti ếp theo h ướng đó ho ặc đổ i h ướng theo m ột trong 4 h ướng trên. Gi ả s ử r ằng đường kính c ủa đường ng ầm đào được là không đáng k ể. Để tránh b ị l ạc, ông ta ghi l ại vào file v n b ản MAP.INP trong máy tính xách tay c ủa mình m ột trong 4 ký t ự E, W, S, N t ươ ng ứng v ới m ột trong b ốn h ướng mà ông ta s ẽ đào t ới m ỗi l ần. Ví d ụ v ới điểm xu ất phát và quy trình đào h ầm d ưới đây, s ơ đồ các đường ng ầm s ẽ là: Finish Start Sau khi đã kh ảo sát xong, nhà kh ảo c ổ mu ốn quay tr ở l ại điểm xu ất phát b ằng đờng h ầm đã đào. Hãy d ựa vào thông tin trong máy tính xách tay c ủa nhà kh ảo c ổ để ch ỉ cho ông ta đờng đi ng ắn nh ất quay tr ở l ại. Dữ li ệu: Vào t ừ file v n b ản MAP.INP c ủa nhà kh ảo c ổ g ồm 1 dòng không quá 5000 ký t ự ∈ {E, W, N, S} Kết qu ả: Ghi ra file v n b ản MAP.OUT g ồm 1 dòng ch ứa các ký t ự ch ỉ h ướng đi d ẫn v ề n ơi xu ất phát. Ví d ụ: MAP.INP MAP.OUT EEEENNNWWWSSSSSSSEEEEENNNNNWW SWWWW 63
054. TH T T IN Một b ảng danh m ục g ồm các t ừ đã đợc s ắp x ếp theo m ột tr ật t ự t ừ điển nào đấy (không nh ất thi ết là t ừ điển thông th ờng). Yêu c ầu t ừ b ảng danh m ục, hãy khôi ph ục l ại tr ật t ự t ừ điển đã dùng. • Dữ li ệu vào được cho b ởi file v n b ản NOTE.INP. Dòng đầu là s ố l ượng t ừ, các dòng ti ếp, (theo th ứ t ự) m ỗi dòng là m ột t ừ trong b ảng danh m ục. Gi ả thi ết r ằng m ỗi t ừ đề u không quá 20 ký t ự được l ấy trong b ảng ch ữ cái nh ỏ ti ếng Anh (t ừ 'a' đế n 'z'). S ố l ượng t ừ trong b ảng danh m ục không quá 10000. • Kết qu ả đư a ra file v n b ản NOTE.OUT g ồm m ột dòng là xâu g ồm các ch ữ cái đã xu ất hi ện trong b ảng danh m ục. Các ch ữ cái trong xâu vi ết li ền nhau và theo th ứ t ự phù h ợp v ới tr ật t ự từ điển đã dùng. Ví d ụ: NOTE.INP NOTE.OUT 10 gsvqnx svxngqqnsnvqv snngg qsqsqvgsqq qqns qnvq nsxnxnvsqsvvs nqg nn xsgvsgggqvsqqsxgv xxgxxggsvnxsnxsnqq 64
055. DÃY L CH Cho hai dãy s ố nguyên: • A = (a 1, a 2, , an) • B = (b 1, b 2, , b n) (n ≤ 100; -10000 ≤ ai, bj ≤ 10000 v ới ∀i, j : 1 ≤ i, j ≤ n ) Hãy tìm m ột hoán v ị σσσ = ( σσσ1, σσσ2, , σσσn) c ủa dãy s ố (1, 2, , n) Để c ực ti ểu hoá bi ểu th ức: F( σσσ) := 1 - a σσσ1 + bσσσ1 - a σσσ2 + bσσσ2 - a σσσ3 + + bσσσn-1 - aσσσn + bσσσn - 1  Dữ li ệu: Vào t ừ file v n b ản SLANTING.INP • Dòng 1: Ghi s ố n • n dòng ti ếp theo, Dòng th ứ i ghi 2 s ố nguyên ai và bi cách nhau ít nh ất 1 d ấu cách Kết qu ả: Ghi ra file v n b ản SLANTING.OUT • Dòng 1: Ghi giá tr ị c ực ti ểu F( σ) tìm được • n Dòng ti ếp theo, dòng th ứ i ghi giá tr ị σi Ví d ụ: 65
056. RÚT G N DÃY S Cho dãy g ồm n s ố nguyên d ươ ng a = (a 1, a 2, , an). Trên dãy s ố này ta có th ể th ực hi ện phép rút gọn t ại v ị trí i: R(i): thay hai s ố h ạng liên ti ếp a i và a i+1 b ằng hi ệu c ủa chúng a i - a i+1 . Sau n - 1 l ần rút g ọn, v ới dãy a, ta thu được duy nh ất m ột s ố nguyên. Ví d ụ: Th ực hi ện l ần l ượt các phép rút g ọn 2, 3, 2 và 1 đối v ới dãy s ố (12, 10, 4, 3, 5) ta s ẽ thu được kết qu ả nh ư sau: 1. Ban đầu: (12, 10, 4, 3, 5) 2. Rút g ọn R(2): (12, 6, 3, 5) 3. Rút g ọn R(3): (12, 6, -2) 4. Rút g ọn R(2): (12, 8) 5. Rút g ọn R(1): (4) Yêu c ầu cho dãy s ố a = (a 1, a 2, , an) và s ố T, hãy tìm th ứ t ự th ực hi ện N - 1 phép rút g ọn đố i v ới dãy đã cho để thu được T. Dữ li ệu: Vào t ừ file v n b ản SUBTRACT.INP • Dòng đầu tiên ch ứa hai s ố n và T các nhau m ột d ấu cách (1 ≤ n ≤ 100; -10000 ≤ T ≤ 10000) • Dòng th ứ i trong s ố n dòng ti ếp theo ghi s ố ai. (1 ≤ ai ≤ 100). Kết qu ả: Ghi ra file v n b ản SUBTRACT.OUT • Gồm n - 1 dòng, dòng th ứ i ghi v ị trí th ực hi ện phép rút g ọn th ứ i. Gi ả thi ết r ằng các d ữ li ệu đề u có ít nh ất m ột l ời gi ải Ví d ụ: SUBTRACT.INP SUBTRACT.OUT 4 5 3 10 1 2 1 5 2 66
057. BUÔN TI N Một ng ười làm vi ệc ở m ột ngân hàng ngo ại t ệ theo dõi t ỉ giá h ối đoái phát hi ện ra là: N ếu khôn khéo, thì t ừ m ột l ượng ngo ại t ệ ban đầ u, nh ờ chuy ển đổ i sang các lo ại ngo ại t ệ khác, anh ta có th ể thu được l ợi nhu ận đáng k ể. Ví d ụ: N ếu anh ta có 1 USD và t ỉ giá h ối đoái gi ữa các ngo ại t ệ nh ư sau: • 1 USD = 0.7 b ảng Anh • 1 b ảng Anh = 9.5 Franc Pháp • 1 Franc Pháp = 0.16 USD Khi đó v ới 1 USD anh ta có th ể mua được 0.7 * 9.5 * 0.16 = 1.064 USD nh ờ vi ệc chuy ển đổ i ti ền qua b ảng Anh, r ồi t ừ b ảng Anh sang Franc Pháp, và cu ối cùng l ại quay v ề USD. Nh ờ đó m ỗi USD đã đem l ại cho anh ta l ợi nhu ận là 0.064USD. Gi ả s ử trong nhà b ng qu ản lý n lo ại ngo ại t ệ đánh s ố 1, 2, , n. Bi ết b ảng t ỉ giá h ối đoái R[i, j] (1 ≤ i, j ≤ n). (T ức là 1 đơ n v ị ngo ại h ối i mua được R[i, j] đơn v ị ngo ại h ối j). C ần xác đị nh xem có cách đổi ti ền đem l ại l ợi nhu ận hay không ? Dữ li ệu: Vào t ừ file v n b ản MONEY.INP • Dòng đầu tiên ch ứa s ố n (n ≤ 100) • Dòng th ứ i trong s ố n dòng ti ếp theo ch ứa n s ố th ực d ươ ng R[i, 1], R[i, 2], , R[i, n]. Kết qu ả: Ghi ra file v n b ản MONEY.OUT Dòng đầu tiên ghi YES ho ặc NO t ươ ng ứng v ới vi ệc có ho ặc không có cách đổ i ti ền sinh l ợi nhu ận Nếu dòng đầu tiên là YES thì dòng th ứ hai ghi hai s ố u và s. Trong đó u là lo ại ti ền xu ất phát, còn s là l ợi nhu ận thu được nh ờ cách đổ i 1 đơn v ị ti ền u. Dòng th ứ ba ghi trình t ự c ần ti ến hành đổi ti ền để thu l ại được l ợi nhu ận b ắt đầ u t ừ lo ại ti ền xu ất phát Các s ố trên m ột dòng c ủa Input/Output File đợc ghi cách nhau ít nh ất m ột d ấu cách Lợi nhu ận (n ếu có) trong Output File có th ể ch ỉ c ần làm tròn gi ữ l ại 6 ch ữ s ố sau d ấu ch ấm th ập phân. Ví d ụ: MONEY.INP MONEY.OUT 5 YES 1.00 1.10 0.83 0.81 0.85 1 0.007160 0.83 1.00 0.86 1.09 0.81 1 2 4 0.89 0.84 1.00 0.83 1.02 0.84 0.83 1.01 1.00 0.84 1.09 0.84 0.87 0.90 1.00 67
058. DÃY NGO C Một dãy d ấu ngo ặc h ợp l ệ là m ột dãy các ký t ự "(" và ")" được đị nh ngh a nh ư sau: i. Dãy r ỗng là m ột dãy d ấu ngo ặc h ợp l ệ độ sâu 0 ii. Nếu A là dãy d ấu ngo ặc h ợp l ệ độ sâu k thì (A) là dãy d ấu ngo ặc h ợp l ệ độ sâu k + 1 iii. Nếu A và B là hai dãy d ấu ngo ặc h ợp l ệ v ới độ sâu l ần l ượt là p và q thì AB là dãy d ấu ngo ặc hợp l ệ độ sâu là max(p, q) Độ dài c ủa m ột dãy ngo ặc là t ổng s ố ký t ự "(" và ")" Ví d ụ: Có 5 dãy d ấu ngo ặc h ợp l ệ độ dài 8 và độ sâu 3: ((()())) ((())()) ((()))() (()(())) ()((())) Bài toán đặt ra là khi cho bi ết tr ớc hai s ố nguyên d ơ ng n và k. Hãy cho bi ết có bao nhiêu dãy ngo ặc h ợp l ệ có độ dài là n và độ sâu là k. N ếu có không quá 100 dãy thì hãy li ệt kê h ết các dãy, nếu có nhi ều h ơn 100 dãy thì hãy ch ỉ ra 100 dãy ngo ặc phân bi ệt. Dữ li ệu: Vào t ừ file v n b ản NGOAC.INP g ồm 1 dòng ghi hai s ố nguyên d ươ ng n và k cách nhau một d ấu cách (n ≤ 64, k ≤ 32). Kết qu ả: Ghi ra file v n b ản NGOAC.OUT • Dòng 1: Ghi s ố C là s ố l ượng dãy ngo ặc h ợp l ệ có độ dài là n và độ sâu là k. • Nếu C ≤ 100, thì C dòng ti ếp theo m ỗi dòng ghi m ột dãy ngo ặc tìm được. N ếu C > 100, thì 100 dòng ti ếp theo m ỗi dòng ghi m ột dãy ngo ặc. Các dãy ngo ặc được li ệt kê đôi m ột khác nhau. Ví d ụ: NGOAC.INP NGOAC.OUT NGOAC.INP NGOAC.OUT 8 3 5 10 2 15 ((()())) (()()()()) ((())()) (()()())() ((()))() (()())(()) (()(())) (()())()() ()((())) (())(()()) (())(())() (())()(()) (())()()() ()(()()()) ()(()())() ()(())(()) ()(())()() ()()(()()) ()()(())() ()()()(()) 68
059. TH NG B M VÀ PHÚ ÔNG Bờm th ắng phú ông trong m ột cu ộc đánh c ược và bu ộc phú ông ph ải đãi r ượu. Phú ông bèn bày ra một dãy n chai ch ứa đầ y r ượu, và nói v ới B ờm r ằng có th ể u ống bao nhiêu tu ý, nh ưng đã ch ọn chai nào thì ph ải u ống h ết và không được u ống ở ba chai li ền nhau b ởi đó là điều xui x ẻo. Bạn hãy ch ỉ cho B ờm cách u ống đợc nhi ều r ợu nh ất. Dữ li ệu: Vào t ừ file v n b ản BOTTLES.INP • Dòng 1: Ghi s ố nguyên d ươ ng n (n ≤ 10000) • Các dòng ti ếp ghi các s ố nguyên d ươ ng ( ≤ 10000) là dung tích c ủa các chai r ượu phú ông bày ra, theo th ứ t ự li ệt kê t ừ chai th ứ nh ất t ới chai th ứ n, các s ố được ghi cách nhau b ởi d ấu cách ho ặc d ấu xu ống dòng. Kết qu ả: Ghi ra file v n b ản BOTTLES.OUT • Dòng 1: Ghi s ố chai được ch ọn và l ượng r ượu t ối đa có th ể u ống cách nhau m ột d ấu cách. • Các dòng ti ếp theo, m ỗi dòng ghi ch ỉ s ố c ủa m ột chai ch ọn ra được Ví d ụ: BOTTLES.INP BOTTLES.OUT 6 4 40 6 10 10 13 2 10 10 3 5 6 69
060. S TH P PHÂN Kết qu ả c ủa phép chia: a/b v ới a và b là hai s ố nguyên (b ≠ 0) có th ể bi ểu di ễn d ưới d ạng m ột s ố th ập phân h ữu h ạn ho ặc s ố th ập phân vô h ạn tu ần hoàn. Ví d ụ: 6/25 = 0.24 1/3 = 0.(3) -17/140 = -0.12(142857) Vấn đề đặ t ra là khi bi ết hai s ố nguyên a, b (-10 9 ≤≤≤ a ≤≤≤ 10 9; -10 7 ≤≤≤ b ≤≤≤ 10 7; b ≠≠≠ 0). Hãy tìm bi ểu di ễn th ập phân c ủa phép chia a/b. Dữ li ệu: Vào t ừ file v n b ản DECIMAL.INP Input file g ồm nhi ều dòng, m ỗi dòng ghi m ột b ộ d ữ li ệu là c ặp s ố nguyên a, b cách nhau m ột d ấu cách. Kết qu ả: Ghi ra file v n b ản DECIMAL.OUT Output file có s ố dòng b ằng s ố dòng c ủa input file, ch ươ ng trình ph ải ghi k ết qu ả t ươ ng ứng v ới b ộ dữ li ệu th ứ i trong input file vào dòng th ứ i c ủa output file. Chú ý: • Trong tr ường h ợp a/b là s ố nguyên thì ch ỉ ghi k ết qu ả ph ần nguyên, không có ph ần th ập phân và dấu ch ấm th ập phân. • Tr ường h ợp a/b là s ố th ập phân h ữu h ạn, không được ghi th ừa s ố 0 ở cu ối. • Tr ường h ợp a/b là s ố th ập phân vô h ạn tu ần hoàn, ph ần th ập phân đứ ng tr ước chu k ph ải là ng ắn t ối ti ểu. Ví d ụ: DECIMAL.INP DECIMAL.OUT DECIMAL.OUT d ưới đây tuy giá tr ị đúng nh ưng là sai khuôn d ạng 100 10 10 10.00 6 25 0.24 0.240 1 3 0.(3) 0.33(3) 99 101 0.(9801) 0.98(0198) 431 3500 0.123(142857) 0.123142(857142) 70
061. DANH SÁCH VÒNG Để làm vi ệc v ới m ột danh sách g ồm N s ố nguyên c ần ph ải có hai thao tác. • Thao tác Top chuy ển ph ần t ử đầ u tiên c ủa danh sách xu ống v ị trí cu ối cùng c ủa danh sách. • Thao tác Bottom chuy ển ph ần t ử cu ối cùng c ủa danh sách lên v ị trí đầ u tiên c ủa danh sách. Một phép bi ến đổ i danh sách đã cho là vi ệc th ực hi ện K l ần thao tác Top, r ồi sau đó đế n L l ần thao tác Bottom. Do s ố l ần th ực hi ện phép bi ến đổ i trên là r ất l ớn nên đòi h ỏi ph ải có nh ững th ủ t ục th ực hi ện hi ệu qu ả để th ực hi ện liên ti ếp X phép bi ến đổ i đưa danh sách v ề tr ạng thái cu ối cùng. Yêu c ầu: Vi ết ch ươ ng trình cho phép v ới m ột danh sách và ba s ố K, L, X cho tr ước, xác đị nh tr ạng thái c ủa danh sách sau X l ần th ực hi ện phép bi ến đổ i. Dữ li ệu: Vào t ừ file v n b ản CLIST.INP • Dòng đầu tiên ch ứa ba s ố nguyên d ươ ng N, K, L (1 ≤ N, K, L ≤ 10000). • Dòng th ứ hai ch ứa N s ố nguyên, m ỗi s ố có giá tr ị tuy ệt đố i không quá 10000, được s ắp x ếp theo th ứ t ự t ươ ng ứng v ới tr ạng thái kh ởi đầ u c ủa danh sách. • Dòng th ứ ba ch ứa s ố nguyên X (0 ≤ X ≤ 2.10 9). Kết qu ả: Ghi ra file v n b ản CLIST.OUT Ghi ra trên m ột dòng c ủa file v n b ản CLIST.OUT các ph ần t ử c ủa danh sách sau X phép bi ển đổ i. Các ph ần t ử ph ải được ghi đúng th ứ t ự t ừ ph ần t ử đầ u tiên đến ph ần t ử cu ối cùng. Các s ố trên m ột dòng c ủa Input/Output File ghi cách nhau ít nh ất m ột d ấu cách. Ví d ụ: CLIST.INP CLIST.OUT 5 2 1 7 3 5 2 4 3 5 2 4 7 9 71
062. TÍNH DI N TÍCH Cho m ột l ưới ô vuông kích th ước MxN. M ỗi ô ch ứa m ột s ố 0 ho ặc 1. Các s ố 1 trên l ưới t ạo thành một đường kín (t ức là dãy các ô mà hai ô liên ti ếp có chung c ạnh ho ặc đỉ nh và ô cu ối cùng c ủa dãy có chung c ạnh ho ặc đỉ nh v ới ô đầ u tiên) b ọc được m ột vùng c ủa l ưới mà ta s ẽ g ọi là m ột hình. Di ện tích c ủa hình là s ố ô ch ứa s ố 0 n ằm trong đó. Yêu c ầu: Vi ết ch ơ ng trình tính di ện tích c ủa hình trong m ột l ới ô vuông cho tr ớc. Gi ả thi ết là di ện tích c ủa m ột hình khác 0. Dữ li ệu: Vào t ừ file v n b ản SZERO.INP: Dòng đầu tiên ch ứa hai s ố nguyên d ươ ng M, N (5 ≤ M, N ≤ 100) M dòng ti ếp theo mô t ả b ảng cho tr ước, m ỗi dòng ch ứa dãy g ồm N s ố 0 ho ặc 1 được ghi li ền nhau Kết qu ả: Ghi ra trên m ột dòng c ủa file v n b ản SZERO.OUT di ện tích c ủa hình trên l ưới đã cho. Ví d ụ: SZERO.INP SZERO.OUT SZERO.INP SZERO.OUT 6 8 7 5 5 3 01000000 00000 10100000 01111 10010000 10010 10001000 01010 01010000 00100 00100000 72
063. THANG MÁY Trong toà nhà c ủa m ột trung tâm th ươ ng m ại g ồm 101 t ầng (các t ầng được đánh s ố t ừ 0 đế n 100) khách hàng có th ể s ử d ụng hai lo ại thang máy: • Thang máy lo ại I: cho phép di chuy ển đế n b ất k t ầng nào v ới th ời gian di chuy ển qua m ột t ầng là E 1 giây. • Thang máy lo ại II (siêu t ốc) ch ỉ d ừng l ại ở các t ầng có ch ỉ s ố chia h ết cho 10, th ực hi ện vi ệc di chuy ển qua 10 t ầng v ới th ời gian là E 2 giây. Bất k ể thang máy đang ở đâu, th ời gian ch ờ đợ i thang máy I và II ( để chuy ển thang máy ho ặc vào thang máy) là W 1 và W 2 giây t ươ ng ứng. Ngoài ra t ại m ỗi t ầng, khách hàng còn có th ể di chuy ển t ừ tầng này lên t ầng trên ho ặc xu ống t ầng d ưới theo c ầu thang c ố đị nh v ới th ời gian là S giây. Yêu c ầu: Xác định th ời gian nh ỏ nh ất T c ần thi ết để m ột khách hàng có th ể di chuy ển t ừ t ầng X đến t ầng Y. Gi ả thi ết là 1 ≤ E 1, E 2, W 1, W 2, S ≤ 1000. Dữ li ệu: Vào t ừ file v n b ản LMOVE.INP • Dòng đầu tiên ch ứa hai s ố E 1, W 1. • Dòng th ứ hai ch ứa hai s ố E 2, W 2. • Dòng th ứ ba ch ứa s ố S • Dòng th ứ t ư ch ứa hai s ố X, Y. Kết qu ả: Ghi ra file v n b ản LMOVE.OUT th ời gian T tìm được Các s ố trên m ột dòng c ủa input file được ghi cách nhau ít nh ất m ột d ấu cách. Ví d ụ: LMOVE.INP LMOVE.OUT 2 25 96 4 15 10 85 43 Cách di chuy ển t ối ưu v ới d ữ li ệu trên nh ư sau: Đang ở t ầng 85, ch ờ thang lo ại I: 25 giây Tụt xu ống t ầng 80: 2giây x 5 = 10 giây Ch ờ thang lo ại II: 15 giây Tụt xu ống t ầng 40: 4giây x 4 = 16 giây Di chuy ển theo c ầu thang lên t ầng 43: 10giây x 3 = 30 giây Tổng c ộng: 96 giây 73
064. TR NG S XÂU Xét t ập ch ữ cái A = {I, W, N}. M ột t ừ là m ột dãy liên ti ếp không quá 6 ký t ự c ủa A. Cho m ột danh sách L g ồm m t ừ phân bi ệt. • Mỗi t ừ trong danh sách được gán m ột tr ọng s ố d ươ ng ≤ 60000. • Nh ững t ừ không có trong danh sách mang tr ọng s ố 0. Xét m ột xâu S ch ỉ g ồm các ký t ự trong A. Tr ọng s ố c ủa xâu S được tính b ằng t ổng tr ọng s ố các t ừ trong S. (Các t ừ trong S được li ệt kê d ưới d ạng các đoạn ký t ự liên ti ếp c ủa S tính c ả vi ệc giao nhau và ch ứa nhau) Yêu c ầu: Cho tr ớc danh sách L và độ dài n ≤≤≤ 100. Hãy tìm xâu S = S 1S2 S n có tr ọng s ố nh ỏ nh ất. N ếu có nhi ều xâu S đề u có tr ọng s ố nh ỏ nh ất thì ch ỉ c ần ch ỉ ra m ột xâu. Dữ li ệu: Vào t ừ file v n b ản STR.INP • Dòng 1: Ghi hai s ố n, m cách nhau m ột d ấu cách. • m c ặp dòng ti ếp theo, c ặp dòng th ứ i g ồm 2 dòng: ♦ Dòng th ứ nh ất ghi t ừ th ứ i trong danh sách L ♦ Dòng th ứ hai ghi tr ọng s ố c ủa t ừ đó Kết qu ả: Ghi ra file v n b ản STR.OUT g ồm 2 dòng: • Dòng 1: Ghi tr ọng s ố c ủa t ừ S tìm được • Dòng 2: Ghi xâu ký t ự S Ví d ụ: STR.INP STR.OUT STR.INP STR.OUT 8 10 62 8 8 98 I WWIWWIWW W IWIWIWIW 13 10 W I 6 10 N N 12 30 II WI 6 1 NI WW 6 10 IIN II 13 11 WWW WIW 7 2 WNN IWI 23 3 NWW 18 NWN 0 74
065. PH MAY M N Ng ười dân thành ph ố Byteland có r ất nhi ều điều kiêng k ỵ trong cu ộc s ống. Theo quan điểm c ủa h ọ, các s ố 2, 6, 13 và nhi ều s ố khác không mang l ại điều may m ắn. Trong khi đó, các s ố 3, 5, 7 l ại r ất được ưa chu ộng. Nh ững ngôi nhà có s ố mà khi phân tích ra th ừa s ố nguyên t ố ch ỉ ch ứa các th ừa s ố 3, 5, 7 được coi là may m ắn và được mua r ất nhanh. Sau m ột th ời gian dài th ảo lu ận, H ội đồ ng thành ph ố quy ết đị nh đánh s ố t ất c ả các ngôi nhà trên m ột đường ph ố m ới m ở b ằng các s ố may m ắn liên ti ếp nhau, bi ến ph ố đó thành m ột ph ố may m ắn. Ký hi ệu dãy các s ố may m ắn là X 1, X 2, X 3, X 4, Khi đó các nhà bên trái s ẽ mang s ố X 1, X 3, X 5. Còn dãy nhà bên ph ải s ẽ mang s ố X 2, X 4, X 6, Toàn b ộ đường ph ố có không quá 4000 nhà. Hãy xác định xem m ột s ố cho tr ớc có ph ải là m ột s ố nhà ở ph ố may m ắn không. N ếu đúng thì cho bi ết nhà đó n ằm ở bên ph ải hay bên trái c ủa ph ố. Dữ li ệu: Vào t ừ file v n b ản STREET.INP g ồm không quá 100000 dòng, m ỗi dòng ch ứa m ột s ố nguyên d ươ ng không quá 18 ch ữ s ố. Kết qu ả: Ghi ra file v n b ản STREET.OUT, g ồm nhi ều dòng, m ỗi dòng t ươ ng ứng v ới m ột s ố ở file d ữ li ệu vào và ch ứa m ột trong ba ch ữ cái L, R, N t ươ ng ứng v ới nhà bên trái, bên ph ải hay không ph ải s ố nhà ở ph ố may m ắn. Lưu ý: Dãy s ố may m ắn được tính b ắt đầu t ừ X 1=3. Ví d ụ: STREET.INP STREET.OUT 5 R 3 L 4 N 98415 R 12814453125 L 75
066. TÍN HI U GIAO THÔNG Trong m ột thành ph ố có: • m đường ph ố (hai chi ều) song song ch ạy th ẳng d ọc theo h ướng Tây ↔Đông, để ti ện, ta g ọi các đường ph ố đó là H 1, H 2, , Hm theo th ứ t ự t ừ B ắc xu ống Nam. • n đường ph ố (hai chi ều) song song ch ạy th ẳng theo h ướng B ắc↔Nam, ta g ọi các đường ph ố đó là V 1, V 2, , Vn theo th ứ t ự t ừ Tây sang Đông Hai đường ph ố vuông góc b ất k c ắt nhau t ạo thành m ột nút giao thông. Ngo ại tr ừ hai nút giao thông n ằm ở v ị trí góc Đông-Nam và góc Tây-Bắc nh ững nút giao thông khác có th ể g ắn đèn tín hi ệu giao thông hai tr ạng thái: 0. Tr ạng thái EW: Xanh h ướng Đông và Tây, Đỏ h ướng B ắc và Nam. 1. Tr ạng thái NS: Xanh h ướng B ắc và Nam, Đỏ h ướng Đông và Tây. Mỗi đèn tín hi ệu có m ột chu k th ời gian riêng, c ứ sau m ỗi chu k th ời gian đó, đèn đổi tr ạng thái một l ần. T ại th ời điểm 0, các đèn tín hi ệu đề u ở tr ạng thái 0 (EW). Để gi ữ an toàn, lu ật giao thông quy đị nh: Khi xe t ới m ột nút giao thông t ừ m ột h ướng nào đó đúng vào th ời điểm đèn tín hi ệu theo h ướng đó đang Đỏ hay chuy ển sang Đỏ thì bu ộc ph ải d ừng l ại, đúng vào th ời điểm đèn tín hi ệu theo h ướng đó đang Xanh hay chuy ển sang Xanh thì có th ể đi th ẳng, r ẽ ph ải hay r ẽ trái tu ý. Trên m ột đường ph ố, th ời gian xe đi gi ữa hai nút giao thông liên ti ếp c ố đị nh là 1 đơ n v ị th ời gian. Yêu c ầu: Cho bi ết s ơ đồ giao thông và các đèn tín hi ệu. Cho m ột xe xu ất phát t ại th ời điểm 0 t ừ nút giao thông ở góc Tây-Bắc. Tìm hành trình và th ời điểm s ớm nh ất để xe t ới nút giao thông ở góc Đông-Nam. Dữ li ệu: Vào t ừ file v n b ản TRAFFIC.INP • Dòng 1: Ghi hai s ố nguyên d ươ ng m, n (m, n ≤ 100) • Dòng 2: Ghi s ố k là s ố đèn hi ệu giao thông • k dòng ti ếp theo, dòng th ứ i g ồm 3 s ố nguyên d ươ ng x, y, t cho bi ết đèn hi ệu th ứ i n ằm ở giao điểm c ủa đường Hx và Vy có chu k là t (t ≤ 10000). Kết qu ả: Ghi ra file v n b ản TRAFFIC.OUT • Dòng 1: Ghi th ời điểm s ớm nh ất để xe ch ạy t ừ góc Tây-Bắc t ới góc Đông-Nam • Dòng 2: Ghi m ột dãy ký t ự, ký t ự th ứ p ∈ {w, E, W, S, N} cho bi ết trong kho ảng th ời gian t ừ p- 1 t ới p, xe trong tr ạng thái đứ ng đợ i hay ch ạy theo h ướng Đông, Tây, Nam hay B ắc (theo th ứ t ự w, E, W, S, N đó). Các s ố trên m ột dòng c ủa Input File được ghi cách nhau ít nh ất m ột d ấu cách. Ví d ụ: TRAFFIC.INP TRAFFIC.OUT 3 4 6 9 ESEwSE 2 2 3 N 1 2 2 1 3 2 w W E 1 4 3 4 2 1 2 2 1 4 2 2 2 S 2 3 1 10 4 2 4 2 3 1 10 3 3 4 76