[Bài tập] Kho bài tập Pascal Tin Học Việt

Trên mặt phẳng tạo độ cho N hình chữ nhật với các cạnh song song với hệ trục toạ độ, các hình chữ nhật được đánh số từ 1 đến N. Hình chữ nhật thứ i được cho bởi 4 số nguyên dương x_i1, y_i1, x_i2, y_i2, trong đó (x_i1,y_i1) là toạ độ đỉnh trái dưới, còn (x_i2,y_i2) là toạ độ đỉnh phải trên. Ta nói rằng hình chữ nhật thứ i nằm trong hình chữ nhật thứ j nếu trên mặt phẳng toạ độ mọi điểm của hình thứ i đều thuộc hình thứ j.
Yêu cầu: Với N hình chữ nhật cho trước hãy tìm K hình chữ nhật với chỉ số i₁, i₂,...., i_k,sao cho hình i₁ nằm trong hình i₂, hình i₂ nằm trong hình i₃,......, hình i_k-1 nằm trong hình i_k và K là lớn nhất. Biết rằng 2 hình chữ nhật bất kì trong N hình chữ nhật đã cho hoặc rời nhau hoặc một trong hai hình nằm trong hình còn lại.

Dữ liệu: Vào từ file văn bản HCN.INP:
Dòng đầu tiên chứa số nguyên dương N (N từ 1 đến 100)
N dòng tiếp theo, mỗi dòng thứ i chứa 4 số nguyên dương x_i1, y_i1, x_i2, y_i2
Kết quả: Ghi ra file HCN.OUT số K tìm được.

Thời xa xưa, để đề phòng và chống lại sự tấn công của các bộ tộc khác, tù trưởng bộ tộc Fladland đã quyết định cho xây các thành luỹ quanh các điểm dân cư đông đúc của mình. Theo lời khuyên của thầy phù thuỷ, tên các thành luỹ phải được chọn là một xâu con các kí tự liên tiếp nhau của một ten thiêng nào đó. Ví dụ, nếu tên thiêng đó là 'baobaab' thì tên thành luỹ có thể là 'ba', 'oba', ..., còn 'bab' hoặc 'bob' không thể được dùng để đặt tên. Dĩ nhiên, các thành luỹ phải đặt tên khác nhau không được trùng nhau.
Tù trưởng muốn biết là có thể xây được tối đa bao nhiêu thành luỹ dựa vào số tên có thể đặt.

Dữ liệu: Vào từ file văn bản BASTION.INP gồm một dòng chứa tên thiêng, trong đó chì có các chữa cái latin thường (độ dài không quá 255 chữ)
Kết quả: Ghi ra file BASTION.OUT số lượng tên thành luỹ có thể đặt

Có n gói kẹo (n<=20), các gói kẹo được đánh số từ 1 đến n. Gói kẹo thứ i có A_i cái kẹo (1<= i <= n, 0 < A₁ <= 200) Hãy sắp xếp các gói kẹo thành 2 phần sao cho tổng số kẹo của 2 phần chênh nhau ít nhất.

Dữ liệu: Vào file văn bản CHIAKEO.INP:
Dòng thứ 1 ghi số n
Các dòng sau, mỗi dòng 10 số, ghi lần lượt các giá trị từ A₁ đến A_n
Kết quả: Ghi ra file CHIAKEO.OUT:
Dòng thứ 1 ghi số kẹo chênh lệch giữa 2 phần
Dòng thứ 2 ghi số hiệu các gói kẹo thuộc phần I
Dòng thứ 3 ghi số hiệu các gói kẹo thuộc phần II

Cho một dãy các phân số với tử số và mẫu số là các số nguyên.Hãy tối giản và sắp xếp các phân số đã cho theo giá trị tuyệt đối của chúng theo thứ tự tăng dần.

Dữ liệu: Đọc từ file văn bản PHANSO.INP gồm:
Dòng đầu là số lượng phân số trong dãy;
Dòng thứ hai ghi tử số của các phân số trong dãy;
Dòng thứ ba ghi mẫu số của các phân số tương ứng với tử số ở dòng trên.
Kết quả: Ghi ra file văn bản PHANSO.OUT gồm:
Dòng đầu ghi số lượng phân số trong dãy;
Dòng thứ hai ghi tử số của các phân số sau khi sắp xếp và tối giản
Dòng thứ ba ghi mẫu số của các phân số sau khi sắp xếp và tối giản

Cho trước một chuỗi ký tự chiều dài N, không chứa khoảng trắng. Hãy đếm và in ra tất cả các hoán vị khác nhau của chuỗi ký tự đã cho.
Dữ liệu: Đọc từ file văn bản HOANVI.INP gồm một chuỗi ký tự.
Kết quả: ghi ra file văn bản HOANVI.OUT có cấu trúc
Dòng thứ nhất ghi số lượng hoán vị tìm được;
Từ dòng thứ hai trở đi, liệt kê các hoán vị tìm được của chuỗi đã cho.

Lâu đài ma có dạng một hình chữ nhật được chia ra làm N x M phòng (xem hình vẽ). Nếu một phòng nằm ở giao của cột j và dòng i thì ta nói nó là phòng (j, i). Các quy tắc sau đây phải được tuân thủ khi di chuyển trong lâu đài:
1. Người lữ hành chỉ có thể thâm nhập lâu đài từ phòng (1,1).
2. Chỉ có thể thoát khỏi lâu đài từ phòng (N, M).
3. Trên cánh cửa của mỗi phòng có ghi một con số huyền bí, là một số nguyên trong khoảng từ 1 đến 13.
4. Người lữ hành có thể ước muốn đi về một trong 8 hướng (song song với các bức tường hoặc các đường chéo) và lập tức anh ta sẽ được di chuyển theo hướng mong muốn xuyên qua một số lượng phòng đúng bằng con số huyền bí ghi trên cánh cửa phòng nơi anh ta đang đứng. Nếu như điều đó không thể thực hiện được (khi số phòng theo hướng này nhỏ hơn số ghi trên cánh cửa) thì không xảy ra bất kỳ sự kiện nào và anh ta buộc phải nghĩ về một hướng di chuyển khác.
5. Không được phép di chuyển hai lần liên tiếp theo cùng một hướng.
Ví dụ: nếu người lữ hành đang đứng ở phòng (3, 3) trong lâu đài được cho trong hình vẽ thì sau một lần di chuyển anh ta có thể đến được các phòng (1, 1), (3, 1), (1, 3), (5, 1) và (5, 3). Để đến được phòng (5, 4) từ phòng (3, 2) bằng hai lần di chuyển, anh ta không được đến (4, 3) rồi tiếp đó là (5, 4) vì như vậy là đã thực hiện hai lần di chuyển liên tiếp theo cùng một hướng mà có thể đến (2, 1) rồi sau đó đến (5, 4).

Yêu cầu: Xác định cách di chuyển tuân thủ các quy tắc đã nêu để thoát khỏi lâu đài sao cho số lần di chuyển là ít nhất.

Dữ liệu: tệp văn bản GPALACE.INP mà:
• Dòng đầu ghi hai số N và M ( 2≤ N, M ≤ 200) theo tứ tự là số cột và dòng của lâu đài.
• Dòng thứ i trong M dòng tiếp chứa N số nguyên dương (thuộc đoạn [1, 13]) là các số ghi trên cánh cửa của các phòng tương ứng trên dòng i của lâu đài.

Kết quả: Ghi ra tệp văn bản GPALACE.OUT số nguyên dương duy nhất là số lần di chuyển ít nhất tìm được. Nếu không tìm được cách di chuyển thì ghi số -1.

Ví dụ:

GPALACE.INP	GPALACE.OUT
5 4 3 3 6 7 11 3 2 1 1 3 3 2 2 1 1 2 1 2 2 1	4

Cho dãy số nguyên a1, a2, ..., aN. Mỗi số hạng của dãy này thuộc một trong hai loại khác nhau. Xét tất cả các dãy con của dãy đã cho có tính chất: hai số hạng liên tiếp của dãy con không thuộc cùng một loại. Mỗi dãy con như vậy, được gọi là một dãy con xen kẽ.

Yêu cầu: Tìm giá trị lớn nhất của tổng các số hạng của dãy con xen kẽ.
Dữ liệu: Đọc từ file văn bản XENKE.INP có:
• Dòng đầu chứa số nguyên N (1 ≤ N ≤ 106),
• Dòng thứ i trong N dòng tiếp theo chứa hai số nguyên: ai và li (|ai| <= 104, li <= {1, 2}, trong đó li là loại của ai.
Kết quả: Ghi ra file văn bản XENKE.OUT một số nguyên, là tổng lớn nhất tìm được.

Ví dụ:

XENKE.INP	XENKE.OUT
10 -2 2 -1 1 5 2 1 2 -4 1 5 2 6 1 -3 1 2 2 4 2	7

Với x nguyên dương, gọi f(x,k) là số cách phân tích x thành tổng các số nguyên tố mà mỗi số nguyên tố có trong tổng không quá k lần.

f(12,6)=7 với 7 cách phân tích:
12= 2+2+2+2+2+2
12= 2+2+2+3+3
12= 2+2+3+5
12= 2+3+7
12= 2+5+5
12= 3+3+3+3
12= 5+7

f(12,3)=5 vì có 5 cách phân tích:
12= 2+2+2+3+3
12= 2+2+3+5
12= 2+3+7
12= 2+5+5
12= 5+7

f(12,1)=2 vì có 2 cách phân tích
12= 2+3+7
12= 5+7

Cho một mảng hai chiều A[1..m,1..n] có m dòng, n cột, mỗi phần tử là số nguyên dương không quá 100 và cho số nguyên dương k. Hãy lập mảng hai chiều B gồm m dòng, n cột sao cho B[i,j]=f(A[i,j],k).
Dữ liệu: vào từ file văn bản PTS.INP gồm:
• Dòng thứ nhất là 3 số m,n,k.(m,n<=100)
• m dòng tiếp theo là mảng A, mỗi dòng n số, hai số trên một dòng cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản PTS.OUT: m dòng là mảng B[1..m,1..n], mỗi dòng n số, hai số cách nhau ít nhất một dấu cách.

Ví dụ:

PTS.INP	PTS.OUT
2 3 3 1 3 5 7 100 12	0 1 2 3 4752 5