Bài tập HSG Tin học THPT

Bài tập HSG Tin học THPT

Chúng tôi xin giới thiệu 16 Bài tập HSG Tin học THPT gồm các bài tập: Điệp viên, Trư bát giới, Bàn cờ 4 * 4, Đội cờ, Hệ thống xe buýt, Bố trí phòng họp, Phân phối kênh, Trò chơi với ô chữ, Công việc, Mã hoá Burrows wheeler, Mặt phẳng, Truyền tin ngắn nhất, Robot quét vôi, Vườn Táo, Dãy lồi.

Quý thầy cô và các em học sinh có thể tham khảo thêm Giải thuật Đệ quy là gì?

1. Bài tập HSG Tin học THPT: Điệp viên

Một điệp viên trưởng phụ trách một nước nọ trước khi về nước muốn gặp nhân viên của mình để nghe báo cáo. Hai người đang ở hai thành phố khác nhau vì vậy họ phải di chuyển để gặp nhau. Quy tắc di chuyển như sau:

  • Họ di chuyển vào ban ngày và nghỉ tại một thành phố vào buổi tối.
  • Trong ngày, họ chỉ có thể di chuyển từ một thành phố tới thành phố bên cạnh (có đường đi trực tiếp và các đường đi này là 1 chiều).
  • Để bảo đảm an toàn, các điệp viên luôn luôn di chuyển (không dừng tại một thành phố quá một đêm).
  • Hai người có thể gặp nhau nếu họ ở cùng1 thành phố vào buổi tối.

Yêu cầu: Lập chương trình kiểm tra xem hai người có gặp nhau không.

Dữ liệu: agent.inp

  • Dòng đầu ghi 2 số: n là số thành phố, m là số các đường đi trực tiếp giữa các thành phố (n <=50, m<=100).
  • Dòng tiếp theo là 2 số p, q là vị trí hiện thời của hai điệp viên.
  • M dòng tiếp theo mỗi dòng chứa 2 số ai, aj là số hiêu các thành phố và từ ai có đường đi trực tiếp (một chiều) đến aj.

Kết quả: agent.out

  • Nếu 2 người không gặp nhau in ra từ “No”
  • Nếu 2 người gặp nhau in ra t là số ngày ngắn nhất mà hai người có thể gặp nhau.

Ví dụ:

Agent.in1 Agent.ou1 Agent.in2 Agent.ou2 Agent.in3 Agent.ou3 Agent.in4 Agent.ou4
6 7

1 5

1 2

4 5

2 3

3 4

4 1

5 4

5 6

3 3 3

1 3

1 2

2 3

3 1

No 8 9

1 8

1 2

2 3

3 4

4 1

1 5

5 6

6 7

7 8

8 1

5 8 9

2 8

1 2

2 3

3 4

4 1

1 5

5 6

6 7

7 8

8 1

11

Hướng dẫn: Sử dụng thuật toán: Loang theo lớp

Bài toán này là một điển hình cho thuật toán “loang theo lớp”. Ta loang theo chiều rộng đường đi của 2 điệp viên theo trình tự: loang đường đi của người thứ nhất tại thời điểm i một lần rồi loang đường đi của người thứ hai tại thời điểm đó một lần. Lặp lại việc loang  đó cho đến khi không thể loang được tiếp hoặc kiểm tra thấy 2 người gặp nhau (tức cả 2 bên loang cùng đến được một địa điểm) hoặc kiểm tra thấy một đỉnh nào đó lặp lại quá nhiều một số lần cho phép (tức người đó rơi vào một chu trình mà không thể gặp được người kia) hay nếu queue vơi giới hạn cao cũng không thể chứa được nữa.

Giả mã

While Not Stop Do
   Begin
   Loangr1(đau1, cuoi1, Stop1);
   Loangr2(đau2,cuoi2, Stop2);
   If  kiemtra (dau1, cuoi1, dau2, cuoi2) then begin found := true; break end;
   Stop := Stop 1 or Stop2;
End;

Trong chương trình con Loangr1(dau1, cuoi1, Stop1) đó biến stop1 trả giá trị true nếu chưa vượt quá giới hạn queue1solanlaplai[i] < Ghanchophep (co the là 10000 – tuy theo ban thich đo chinh xac nao).

Hàm Loangr2(đau2,cuoi2, Stop2) cũng tương tự.

Hàm Kiemtra (dau1, cuoi1, dau2, cuoi2) tra gia tri true nếu với các đỉnh được đi đến (vừa kết nạp vào queue1 và queue 2) trong lần loangr1 (co cuoi1 – dau1 đỉnh) và trong lần loangr2 (có cuoi2 – dau2 đỉnh) có một đỉnh chung.

2. Bài tập HSG Tin học THPT: Trư bát giới

Trên đường đi thỉnh kinh, một lần Bát Giới được Tôn Ngộ Không giao cho nhiệm vụ đi hầu Tam Tạng. Tam Tạng đi với tốc độ không đổi và đường đi của ông là đường gấp khúc (có thể tự cắt) gồm n điểm gãy. Mỗi điểm gãy được cho bởi cặp số nguyên (xi, yi) là toạ độ trên mặt phẳng xoy. Theo hầu Tam Tạng, Bát Giới đi chơi theo con đường riêng của mình nhưng luôn gặp Tam Tạng tại n điểm gãy nói trên. Hai người bắt đầu xuất phát từ điểm (x1, y1) và kết thúc chuyến đi đồng thời tại điểm (xn, yn) để chờ Tôn Ngộ Không và Sa Tăng. Bát Giới có thể đi với tốc độ không vượt quá hai lần tốc độ của Tam Tạng. Khi Tam Tạng đi theo đường thẳng từ điểm gãy này đến điểm gãy kế tiếp, Bát Giới có thể chạy đến các điểm hấp dẫn được cho bởi m cặp số nguyên (x’i, y’i). Tuy nhiên, sau khi tách rời Sư phụ tại điểm (xi, yi) Bát Giới chỉ có thể thăm không quá một điểm hấp dẫn ông để rồi gặp lại Sư phụ tại điểm (xi+1, yi+1).

Yêu cầu:

Tìm đường đi của Bát Giới thoả mãn các điều kiện nêu trên và sao cho số điểm hấp dẫn của Bát Giới thăm được là nhiều nhất.

Dữ liệu: Bg.inp.

  • Dòng đầu tiên chứa hai số nguyên dương n và m (2n100, 0m100)
  • Dòng thứ hai chứa n cặp số nguyên: x1, y1, …, xn, yn.
  • Dòng thứ ba chứa m cặp số nguyên: x’1, y’1, …, x’m, y’m.

Các điểm trong file dữ liệu là khác nhau từng đôi một và toạ độ của chúng là các số nguyên có trị tuyệt đối không vượt quá 1000. Các số ghi cách nhau bởi dấu cách.

Kết quả: Bg.out.

  • Dòng đầu tiên ghi số nguyên dương k là số điểm gãy trên đường đi của Bát Giới.
  • Dòng thứ hai ghi cặp toạ độ u1, v1, …, uk, vk biểu diễn đường đi của Bát Giới. Các toạ độ ghi cách nhau bởi dấu cách..

Ví dụ:

Bg.INP Bg.OUT
4 5

1 4 5 7 5 2 -2 4

-4 -2 3 9 1 2 -1 3 8 -3

6

1 4 3 9 5 7 5 2 1 2 -2 4

Hướng dẫn:

Dùng cặp ghép

  • Xây dựng tập X: tập các gồm n – 1 phần tử. Với các phần tử đó là các cạnh trên đường đi của Bát Giới.
  • Xây dựng tập Y: tập gồm m phần tử. Các phần tử là các điểm hấp dẫn.
  • Xây dựng ma trận quan hệ giữa X và Y. Nếu ở phần tử i (i của tập X – tức là các cạnh trên đường đi của Tam Tạng), Bát Giới có thể đi đến điểm hấp dẫn j (j thuộc Y) thì a[i,j] = true và ngược lại. Tức là a[i,j] = true ó kc(xi, yi, x’j, y’j) + kc(xi+1, yi+1, x’j, y’j) 2kc(xi, yi, xi+1, yi+1).
  • Dùng thuật toán cặp ghép tối đa để giải.

3. Bài tập HSG Tin học THPT: Bàn cờ 4 * 4

Một bàn cờ có dạng bảng vuông kích thước 4 * 4, trên đó có một số quân cờ. Một quân cờ chỉ có thể di chuyển sang 1 ô kề cạnh còn trống, mỗi di chuyển như vậy được gọi là 1 bước di chuyển. Cho hai trạng thái của bàn cờ, hãy chỉ ra một dãy các bước di chuyển để đưa bảng từ trạng thái xuất phát đến trạng thái đích với số phép di chuyển là ít nhất. Mỗi trạng thái được mô tả là một ma trận 4 * 4 trong đó số ô ở hàng I, cột j là 1 nếu tại vị trí (i,j) tương ứng có quân cờ đang đứng hoặc bằng 0 nếu không có.

Dữ liệu: chess.inp

  • Gồm 2 * 4 dòng thể hiện ma trận mô tả trạng thái xuất phát và trạng thái đích. 4 dòng đầu tiên thể hiện ma trận xuất phát, 4 dòng tiếp theo là ma trận đích.
  • Input luôn đảm bảo là có nghiệm.

Kết quả: chess.out

  • Dòng đầu tiên ghi k là số ít nhất các phép biến đổi tìm được.
  • K dòng tiếp, mỗi dòng mô tả 1 phép biến đổi, theo đúng trình tự biến đổi, gồm 4 số nguyên dương u, v, x, y thể hiện di chuyển quân cờ ở vị trí (u, v) sang vị trí (x, y).

Ví dụ:

Chess.inp Chess.out
1111

1111

0000

0000

0000

0000

1111

1111

16

2 1 3 1

1 1 2 1

2 2 3 2

1 2 2 2

2 3 3 3

1 3 2 3

2 4 3 4

1 4 2 4

3 1 4 1

2 1 3 1

3 2 4 2

2 2 3 2

3 3 4 3

2 3 3 3

3 4 4 4

2 4 3 4

4. Bài tập HSG Tin học THPT: Đội cờ             

Có hai đội cờ vua A và B thi đấu với nhau. Mỗi đội cử ra n kì thủ, mỗi kì thủ của đội B chỉ đấu một trận và đấu với 1 kì thủ của đội A và ngược lại. Vậy có tất cả n trận đấu. Đội nào thắng được 2 điểm, hoà được 1 điểm và thua không được điểm nào.

Cho đội B được quyền chọn cặp thi đấu.

Yêu cầu: lập trình để đội B chọn được các cặp thi đấu sao cho tổng số điểm của đội B là cao nhất. Cho biết trình độ của kì thủ thứ i của hai đội A và B là ai và bi (I = 1, 2, …, n) và giả sử trong thi đấu, hai kì thủ có trình độ bằng nhau sẽ hoà và cầu thủ nào có trình độ cao hơn sẽ thắng.

Dữ liệu: Doico.inp

  • Dòng đầu ghi số nguyên dương n (1n10000).
  • Trên dòng thứ I trong số n dòng tiếp theo ghi hai số nguyên dương ai, bi (1ai, bi1000), cách nhau một khoảng trắng.

Kết quả: Doico.out

  • Dòng đầu là số nguyên t là tổng số điểm cao nhất mà đội B có thể đạt được.
  • Trên dòng thứ hai là n số nguyên dương xi, trong đó xi là số thứ tự của kì thủ đội B phải đấu với kì thủ thứ i của đội A để tổng số điểm đội B đạt được là lớn nhất.

Ví dụ:

Doico.inp Doico.out
4

7 8

5 6

4 3

9 4

5

1 2 4 3

Hướng dẫn thuật giải:

  • Sắp xếp hai mảng A, B theo thứ tự không giảm, nhớ lưu vị trí cũ của A, B vào hai mảng chỉ số.
  • Ta thực hiện phương pháp tối ưu từng bước, cụ thể:
  • Ở chương trình này cần chú ý khi sắp xếp 2 dãy A, B thì vị trí các kì thủ đã đổi, do đó mảng x là mảng ứng với vị trí mới của mảng A và B ta cần đổi về vị trí cũ.

5. Bài tập HSG Tin học THPT: Hệ thống xe buýt.

Một hệ thống các xe buýt có nhiệm vụ chuyên chở hành khách đi lại giữa một số ga sao cho đảm bảo tính liên thông hai chiều giữa các ga này. Hệ thống bao gồm một số tuyến đường, mỗi tuyến đường gồm một số ga khác nhau theo thứ tự mà xe buýt đi qua. Xe buýt thuộc tuyến đường nào chỉ chạy trên tuyến đường đó, lần lượt qua các ga thuộc tuyến cho đến hết, sau đó lại quay đầu chạy theo hướng ngược lại. Có thể có một số ga chung cho một số tuyến đường. Một hành khách muốn đi từ ga đầu đến ga cuối, có thể đi trên một tuyến hoặc phải chuyển tuyến một số lần ở những nơi có ga chung. Bài toán đặt ra là, cần tìm một hành trình cho phép đi từ ga đầu đến ga cuối sao cho số lần phải chuyển tuyến là ít nhất. Nếu tồn tại nhiều phương án như vậy, hãy tìm phương án đi qua ít ga nhất.

Dữ liệu: busway.inp

  • Dòng đầu là số tuyến đường.
  • Các dòng tiếp mỗi dòng mô tả một tuyến đường, gồm một chuỗi các kí tự viết liền nhau, mỗi kí tự mô tả một tên ga theo đúng thứ tự các ga tren tuyến (chú ý các ga trên cùng một tuyến là khác nhau, nhưng các ga trên các tuyến khác nhau có thể trùng nhau, tên ga có thể là một kí tự bất kì hiển thị được trong bảng mã ACSII)
  • Dòng tiếp theo là số hành trình cần tìm.
  • Các dòng tiếp theo, mỗi dòng mô tả một hành trình cần tìm, gồm cặp kí tự viết liền nhau, xác định các tên ga đầu và ga cuối.

Giả thiết các dữ liệu là hợp lệ, không cần kiểm tra. Giới hạn kích thước 100 cho số các tuyên đường và 50 cho số các ga trên cùng một tuyến đường.

Kết quả: busway.out

  • Mỗi hành trình được viết trên một dòng, gồm các kí tự biểu diễn tên ga viết theo thứ tự đi được. Các tên ga này được viết thành từng nhóm theo tuyến đường: nếu thuộc cùng một tuyến thì viết liền nhau, nếu sang tuyến khác thì viết cách nhau một dấu cách (space), tên ga chung được viết lặp lại.

Ví dụ

Busway.inp Busway.out
3

ABC

DBE

GAEH

2

HC

GB

HEA ABC

GA AB

Hướng dẫn:

  • Xây dựng đồ thị đường đi giữa các ga là ma trận hai chiều (lưu vào mảng trọng số a). Coi mỗi kí tự là một đỉnh của đồ thị (dùng hàm ord(kítự) lấy giá trị là số). a[i,j] = 0 nếu các kí tự “chr(i)”, “ chr(j)” (cũng là các ga) không thuộc cùng một tuyến đường nào cả. a[i,j] > 0 và là giá trị nhỏ nhất của đoạn đường đi giữa hai ga (chr(i), chr(j)).
  • Dùng thuật toán Dijstra để tìm đường đi ngắn nhất từ ga đầu tới ga cuối. Trong thuật toán ta có hai ưu tiên sau:
    • Số ga giữa đường đi là ít nhất (ưu tiên cao nhất).
    • Tổng đường đi giữa các ga là nhỏ nhất.
  • Với ưu tiên thứ nhất ta có thể coi đồ thị vừa lập là một đồ thị mới: đồ thị quan hệ: a[i,j] = 0 tức không có đường đi từ i tới j và a[i,j] > 0 tức có đường đi giữa i và j. Với ưu tiên thứ nhất ta coi a[i,j] > 0 thì a[i,j] = 1 trong đồ thị mới lập.
  • Khi ưu tiên thứ nhất được thoả mãn ta xét đến ưu tiên thứ hai, khi đó coi như thuật toán Dijstra dùng cho đồ thị cũ đã lập lúc đầu – đồ thị trọng số.

6. Bài tập HSG Tin học THPT: Bố trí phòng họp.

Có n cuộc họp được đánh số từ 1 đến n đăng kí làm việc tại một phòng hội thảo. Cuộc họp i cần bắt đầu vào thời điểm ai và kết thúc vào thời điểm bi (i = 1..n). Hai cuộc họp có thể nhận phục vụ nếu các khoảng thời gian làm việc tương ứng chỉ có thể giao nhau tại đầu mút hoặc tách rời nhau.

Yêu cầu: Hãy tìm một lịch cho phòng hội thảo để có thể phục vụ nhiều cuộc họp nhất.

Dữ liệu:  Activity.inp.

  • Dòng đầu tiên là giá trị n (n <= 1000000).
  • Dòng thứ i trong n dòng tiếp theo ghi 2 số ai và bi cách nhau ít nhất một dấu cách. (ai, bi <=32000 và là các số nguyên dương).

Kết quả: Activity.out.

  • Dòng đầu tiên ghi số k là số cuộc họp tối đa có thể bố trí.
  • Dòng tiếp theo ghi số hiệu của cuộc họp được phục vụ theo trình tự lịch bố trí.

Ví dụ:

Activity.inp Activity.out
5

1 3

2 4

1 6

3 5

7 9

3

1 4 5

Hướng dẫn:

Do n lớn nên ta cần lưu dữ liệu theo mảng thời gian.

Khai báo:        tr: array [1..32000] of integer;

Dùng mảng trước đánh dấu thời gian cuối của cuộc họp. Tức là nếu tr[c]  <> 0 thì tồn tại cuộc họp có thời điểm kết thúc là c và tr[c] mang ý nghĩa là thời điểm ban đầu của cuộc họp. Đọc dữ liệu và đánh dấu mảng tr sao cho tr[c] gần c nhất có thể.

Với cuộc họp có thời điểm kết thúc c mà ta chọn, ta cần lưu chỉ số của cuộc họp đó.

Khai báo:        Cs: array [1..32000] of longint; {vì n lớn}.

Do mảng này không thể khai báo được -> lưu chỉ số theo 2 giá trị: n div 32, n mod 32 -> thay mảng cs bằng hai mảng sau:

Khai báo:        Trx, try: array [1..32000] off integer

Ý nghĩa  :        trx[c] = I div 32; try[c] := I mod 32.

Mảng try có thể khai báo bằng kiểu byte. Hai mảng này dùng mảng động.

Xử lí: Gọi max là thời gian kết thúc lớn nhất trong các cuộc họp. Duyệt từ 1 đến max, nếu có cuộc họp i nào có tr[i] >= cuối thì kết nạp vào mảng lưu. Với cuoi là giá trị thời gian kết thúc của cuộc họp được chọn trước đó (đầu tiên cuối = 0).

7. Bài tập HSG Tin học THPT: Phân phối kênh

Công ty dịch vụ mạng máy tính cần phân phối kênh hoạt động phục vụ n yêu cầu của khách hàng (n <= 5000) đánh số thứ tự từ 1 tới n. Với mỗi khách hàng thứ i ta biết khoảng thời gian yêu cầu sử dụng kênh là (si, ti), i =1, 2, …, n (khách hàng sẽ sử dụng kênh từ thời điểm si tới thời điểm ti). Thời gian chuyển giao kênh từ khách hàng này tới khách hàng khác là không đáng kể. Như vậy, nếu hai khách hàng nào đó được bố trí làm việc trên cùng một kênh thì các khoảng thời gian sử dụng của họ chỉ có thể có nhiều nhất là một điểm chung.

Yêu cầu: hãy tìm cách phân phối sử dụng ít kênh nhất.

Dữ liệu: Chanel.inp

  • Dòng đầu tiên ghi số n.
  • Dòng thứ i trong số n dòng tiếp theo mỗi dòng ghi 2 số nguyên dương si, ti (i =1, 2, …, n).

Kết quả: Chanel.out

  • Dòng đầu tiên ghi số lượng kênh cần sử dụng p.
  • Mỗi dòng thứ i trong số p dòng tiếp theo chứa các chỉ số của mỗi khách hàng sử dụng kênh thứ i, i = 1, 2, …, p.

Ví dụ:

Chanel.inp Chanel.out
7

0 3

3 5

6 8

0 7

7 8

0 2

2 6

3

4 5

1 2 3

6 7

Hướng dẫn.

Ở bài này ta cần xác định các khách hàng với khoảng thời gian (si, ti) đó vào các tập sao cho các khoảng thời gian trong mỗi tập chỉ có thể có duy nhất là một điểm chung và số tập là ít nhất có thể được. Ta sắp xếp lại các khoảng thời gian đó theo thứ tự tăng dần của si, nếu si, sj bằng nhau thì sắp xếp theo thứ tự tăng dần của ti, tj … Khi đó ta duyệt các khách hàng theo thứ tự từ 1 tới n, với mỗi khách hàng thì ta duyệt các tập đã xây dựng được, nếu có thể kết nạp khách hàng này vào tập hợp nào thì ta kết nạp vào (và có thể thấy đó là cách kết nạp tối ưu do hiệu quả của sắp xếp), nếu không thì cho khách hàng này vào tập hợp mới. Ta thấy độ phức tạp của thuật toán chỉ cỡ .

8. Bài tập HSG Tin học THPT: Trò chơi với ô chữ.

Tiếp tục phát triển trò chơi với ô chữ, người ta đã đánh số cho các từ có độ dài từ 1 đến 26 theo quy tắc là ưu tiên độ dài từ, sau đó là theo vần ABC. Với:

a                      1

b                      2

z                      26

aa                    27

snowfall          157.118.051.752

Như vậy, mỗi một số ta có tương ứng là một từ gồm các chữ cái thường và ngược lại ứng với mỗi từ ta có một số tương ứng. Công việc đặt ra là: giả sử ta có một số hãy tìm từ tương ứng với nó, và cho một từ hãy cho biết từ đó ứng với số bao nhiêu.

Dữ liệu: Game.inp.

  • Dòng đầu là một số nguyên.
  • Dòng thứ hai là một xâu kí tự (gồm các kí tự thường).

Kết quả: Game.out.

  • Dòng thứ nhất là một từ tương ứng với số trong file input.
  • Dòng thứ hai là một số tương ứng với từ trong file input.

Ví dụ:

Game.inp Game.out
157118051752

snowfall

snowfall

157118051752

9. Bài tập HSG Tin học THPT: Công việc

Có n công viêc đánh số từ 1 đến n, n <= 10000. Mỗi việc làm đều phải làm liên tục trong một giờ mới xong. Việc u nếu làm không muộn hơn giờ thứ du sẽ thu được một giá trị nguyên dương gu; các giá trị du, gu nguyên dương và không lớn hơn 60000. Tại mỗi thời điểm không được làm hơn một việc và bắt đầu từ thời điểm 0, giờ thứ I xem như bắt đầu từ thời điểm I – 1.

Yêu cầu: Hãy chọn một số việc làm sao cho tổng giá trị thu được là lớn nhất. Các số phát sinh trong phạm vi longint.

Dữ liệu: Job.inp

  • Dòng thứ nhất ghi số n.
  • N dòng tiếp theo, dòng thứ u ghi hai số du, gu.

Kết quả: Job.out

  • Dòng thứ nhất ghi tổng giá trị thu được.
  • Tiếp theo là các dòng, mỗi dòng ghi hai số x, y với ý nghĩa việc x làm trong giờ thứ y.

Ví dụ:

Job.inp Job.out
6

3 7

3 20

1 10

1 15

1 5

3 3

42

3

2 3

4 1

1 2

10. Bài tập HSG Tin học THPT: Mã hoá Burrows wheeler.

Burrows Wheeler đề xuất phương pháp mã hóa thông tin như sau: ví dụ cần mã hóa BANANA, các bước tiến hành là:

  • Bước 1: Từ cần mã hóa được dịch chuyển vòng tròn và tạo thành một ma trận l * l kí tự, trong đó l là độ dài của từ.
  • Bước 2: Sắp xếp lại các dòng của ma trận theo thứ tự từ điển.
  • Bước 3: trích xâu từ các kí tự cuối của cột, thông báo xâu này và cho biết từ gốc là thứ mấy trong ma trận nhận được ở bước 2. Ta có: (NNBAAA, 4).

BANANA                               ABANAN

ANANAB                               ANABAN

NANABA                               ANANAB

ANABAN                               BANANA

NABANA                               NABANA

ABANAN                               NANABA.

Yêu cầu: cho kết quả mã hóa (kết quả bước 3). Hãy xác định từ ban đầu.

Dữ liệu: mahoa.inp:

  • Bao gồm một hoặc nhiều nhóm 2 dòng , dòng đầu là xâu kí tự độ dài không quá 100, dòng sau là số nguyên dương cho biết vị trí từ gốc.

Kết quả: mahoa.out:

  • Xuất ra các từ ban đầu, mỗi từ trên 1 dòng.

Ví dụ:

Mahoa.inp Mahoa.out
NNBAAA

4

OMOEULCG

1

BANANA

COGUMELO

11. Bài tập HSG Tin học THPT: Mặt phẳng

Trên mặt phẳng cho n hình chữ nhật có cạnh song song với trục toạ độ. Hãy đếm số miền mặt phẳng được tạo ra bởi các cạch của hình chữ nhật. Một miền mặt phẳng là một vùng liên tục khép kín giới hạn bởi các cạnh của hình chữ nhật và không chứa một miền mặt phẳng nào khác.

Dữ liệu: Matphang.inp.

Dòng đầu là số nguyên dương n (<30) là số hình chữ nhật.

N dòng tiếp theo, mỗi dòng chứa 4 số nguyên dương lần lượt là toạ độ theo hai trục toạ độ của hai đỉnh đối của hình chữ nhật.

Kết quả: Matphang.out.

Số miền mặt phẳng tìm được.

Ví dụ:

Matphang.inp Matphang.out
2

10 10 30 30

20 20 40 40

3

 

Matphang.inp Matphang.out
2

20 10 30 40

10 20 40 30

5

12. Bài tập HSG Tin học THPT: Truyền tin ngắn nhất.

Trong một mạng gồm n máy tính đánh số từ 1 đến n. Sơ đồ nối mạng được cho bởi hệ thống gồm m kênh nối trực tiếp giữa một số cặp máy trong mạng. Biết chi phí truyền cho 1 đơn vị thông tin theo mỗi kênh nối của mạng.

Người ta cần chuyển 1 bức thông điệp từ máy s -> t. Để đảm bảo an ninh, người ta muốn chuyển bức thông điệp này theo 2 đườ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ả 2 đường truyền tin). Chi phí của 1 đường truyền được hiểu là tổng chi phí trên các kênh của nó.

Yêu cầu: giả sử bức thông điệp có độ dài một đơn vị thông tin, hãy tìm cách chuyển thông điệp từ s -> t sao cho tổng chi phí chuyển thông tin ( bằng tổng chi phí theo cả hai đường truyền tin) là nhỏ nhất.

Dữ liệu: May.inp

  • Dòng đầu ghi n, m, s, t cách nhau bởi dấu cách (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 3 số di, ci, gi: di, ci là chỉ số 2 máy tương ứng và gi là chi phí để truyền theo kênh này (đường truyền là hai chiều).

Kết quả: May.out

  • Dòng đầu ghi tổng chi phí.
  • Dòng thứ hai ghi đường truyền 1: s-> t.
  • Dòng thứ ba ghi đường truyền 2: s ->t.

Ví dụ:

May.inp May.out
5 7 15

1 2 3

1 4 8

2 3 5

2 4 4

3 5 5

4 3 8

4 5 3

24

1 2 3 5

1 4 5

13. Bài tập HSG Tin học THPT: Robot quét vôi

Có 9 căn phòng (đánh số từ 1 đến 9) đã được quét vôi với mầu trắng, xanh hoặc vàng. Có 9 rôbôt (đánh số từ 1 đến 9) phụ trách việc quét vôi các phòng. Mỗi rôbôt chỉ quét vôi một số phòng nhất định. Việc quét vôi được thực hiện nhờ một chương trình cài sẵn theo qui tắc:

  • nếu phòng đang có mầu trắng thì quét mầu xanh,
  • nếu phòng đang có mầu xanh thì quét mầu vàng,
  • nếu phòng đang có mầu vàng thì quét mầu trắng.

Cần phải gọi lần lượt một số các rôbôt ra quét vôi (mỗi lần một rôbôt, một rôbôt có thể gọi nhiều lần và có thể có rôbôt không được gọi. Rôbôt được gọi sẽ quét vôi tất cả các phòng mà nó phụ trách) để cuối cùng các phòng đều có mầu trắng. Hãy tìm một phương án như vậy sao cho lượng vôi phải quét là ít nhất. Giả thiết rằng luợng vôi cho mỗi lượt quét đối với các phòng là như nhau.

Dữ liệu: đọc từ file văn bản ROBOT.INP gồm các dòng:

  • 9 dòng đầu, mỗi dòng mô tả danh sách các phòng được quét vôi bởi một rôbôt theo thứ tự từ rôbôt 1 đến rôbôt 9. Mỗi dòng như vậy gồm các số hiệu phòng viết sát nhau. Chẳng hạn dòng thứ 2 có nội dung:
    3578 mô tả rôbôt 2 phụ trách việc quét vôi các phòng 3, 5, 7, 8.
  • dòng cuối mô tả mầu vôi ban đầu của các phòng. Dòng gồm 9 ký tự viết sát nhau, ký tự thứ i biểu diễn mầu vôi của phòng i với quy ước: ký tự T chỉ mầu trắng, ký tự X chỉ mầu xanh, ký tự V chỉ mầu vàng.

Kết quả: đưa ra file văn bản ROBOT.OUT gồm một dòng dưới dạng:

  • nếu không có phương án thì ghi một chữ số 0,
  • trái lại ghi dãy thứ tự các rôbôt được gọi (các số hiệu rôbôt viết sát nhau).

Thí dụ: 

ROBOT.INP   ROBOT.OUT
159

123

357

147

5

369

456

789

258

XVXVXVTXT

2455688

14. Bài tập HSG Tin học THPT

Cho 2 xâu:

X = x1x2..xM. (Với xi là các kí tự số từ ‘0’ đến ‘9’)

Y = y1y2..yN.( Với yi là các kí tự số từ ‘0’ đến ‘9’)

(M, N <= 250)

Ta gọi: Z = z1z2..zk là xâu chung của 2 xâu X, Y nếu xâu Z nhận đ­ợc từ xâu X bằng cách xoá đi một số kí tự và cũng nhận được từ xâu Y bằng cách xoá đi một số kí tự.

Yêu cầu: Tìm một xâu chung của 2 xâu X, Y sao cho xâu nhận được tạo thành một số lớn nhất có thể được.

Dữ liệu vào file: String.inp

Gồm 2 dòng, dòng 1 là xâu X, dòng 2 là xâu Y.

Kết quả ra file: String.out

Gồm 1 dòng duy nhất là số lớn nhất có thể nhận được.

Ví dụ:

String.inp String.out
19012304 034012 34

15. Bài tập HSG Tin học THPT: Vườn Táo

Trong một mảnh vờn hình vuông cạnh 1000 m có trồng N cây táo . Vị trí mỗi cây táo đợc xác định bởi toạ độ (x,y) trong hệ toạ độ vuông góc với gốc toạ đọ là góc trái dới của vờn và các trục toạ độ song song với các cạnh vờn . Hãy tìm hình chữ nhật lớn nhất sao cho các cạnh song song với các cạnh của vờn , và trong nó không chứa cây táo nào ( mà chỉ có thể chứa trên biên ) .

Dữ Liệu vào từ file     Tao.Inp

  • Dòng thứ nhất ghi N số từ 1 đến 600 .
  • Trong N dòng sau mỗi dòng ghi hai số nguyên dơng x,y ,0<x,y<1000 là toạ độ của các cây táo .

Kết Quả ghi ra file   Tao.Out

  • Dòng thứ nhất ghi diện tích hình chữ nhật
  • Dòngthứ hai ghi số hai số là toạ độ của đỉnh trái dới
  • Dòng thứ ba ghi hai số là toạ độ của đỉnh trên phải của hình chữ nhật .

Ví Dụ:

TAO.INP

7 280 100 200 600 400 200 135 800 800 400 600 800 900 210

TAO.OUT

360000 200 200 800 800

Hướng dẫn.

Ta thêm vào tập các cây những cây giả là hình chiếu của các cây thật trên bốn cạnh của khu vờn . Sắp xếp lại các cây theo thứ tự tăng dần của hoành độ . Thực chất ta đã chia chúng thành các hình nhỏ hơn . Sau đó tìm từng hình một thoả mãn điều kiện của hình chữ nhật ( không chứa táo , diện tích lớn nhất ) .

16. Bài tập HSG Tin học THPT Dãy lồi

Dãy giá trị nguyên A=(a1, a2, …, an) được gọi là dãy lồi nếu nó giảm dần từ a1 tới ai nào đó, rồi tăng dần tới an. Ví dụ: dãy 10 5 4 2 -1 4 6 8 12 là dãy lồi.

Yêu cầu: lập trình nhập vào một dãy số nguyên, bằng cách xoá bớt một số phần tử của dãy và giữ nguyên trình tự các phần tử còn lại, ta nhận được dãy con lồi dài nhất.

Dữ liệu: dayloi.inp.

  • Dòng đầu là số tự nhiên n (n<=5000).
  • Dòng tiếp theo là n số nguyên của dãy số(các số kiểu integer).

Kết quả: dayloi.out.

  • Dòng đầu tiên ghi số phần tử lớn nhất của dãy con tìm được (ghi ra 0 nếu không tồn tại dãy lồi).
  • Dòng tiếp theo ghi các số thuộc dãy con (không thay đổi trật tự các phần tử trong dãy ban đầu).

Ví dụ:

Dayloi.inp Dayloi.out
10

1 2 3 4 2 5 1 2 3 4

6

4 2 1 2 3 4