T
tmb12
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Sau đây là đề
Bài 1: Có 16 đồng xu xếp thành bảng 4x4, mỗi đồng xu có thể úp hoặc ngửa. Tại mỗi bước ta có phép biến đổi sau: chọn một đồng xu và thay đổi trạng thái của đồng xu đó và tất cả các đồng xu nằm ở ô chung cạnh (úp thành ngửa, ngửa thành úp). Cho trước trạng thái các đồng xu, hãy lập trình tìm số phép biến đổi ít nhất để đưa về trạng thái tất cả các đồng xu hoặc đều úp hoặc đều ngửa.
Bài 2: Cho N (N≤1000) đoạn số [ai, bi], hãy chọn một tập hợp gồm ít số nhất mà mỗi đoạn số nguyên trên đều có ít nhất 2 số trong tập đó.
vd: có 5 đoạn [0,10] [2,3] [4,7][3,5][5,8] ta chọn tập gồm 4 số {2,3,5,7}
Bài 3: Stones: Có N đống sỏi, đống thứ i có Ai viên sỏi. Ta có thể ghép hai đống sỏi kề nhau thàh một đống và mật một chi phí bằng tổng số sỏi của hai đống. Hãy tìm cách ghép N đống sỏi thành một đống với chi phí là nhỏ nhất.
Bài 4: Cắt hình 1: Có một hình chủ nhật MxN ô vuông, mỗi lần ta được cắt một hình chủ nhật thành hai hình chủ nhật con theo chiều ngang hoặc chiều dọc và lại tiệp tục cắt các hình chữ nhật con cho đến khi được hình vuông thì dừng lại. Hỏi có thể cắt hình chủ nhật MxN thành ít nhất bao nhiêu hình vuông.
Bài 5: Cắt hình 2:
Cho một bảng số gồm M dòng, N cột, các giá trị của bảng A chỉ là 0 hoặc 1. Ta muốn cắt bảng A thành các hình chữ nhật con sao cho các hình chữ nhật con có giá trị toàn bằng 1 hay toàn bằng 0. Một lần cắt là một nhát cắt thẳng theo dòng hoặc theo cột của một hình chữ nhật thành hai hình chữ nhật riêng biệt. Cứ tiếp tục cắt cho đên khi hình chữ nhật có các giá trị taòn ằng 1 hay toàn bằng 0. Hãy tìm cách cắt để số hình chữ nhật con nhận được, có giá trị toàn là 1 hay toàn bằng 0, là nhỏ nhất.
Bài 6: Phân trang
Văn bản là một dãy gồm N từ đánh số từ 1 đến N. Từ i có độ dài là wi (i=1..N). Phân trang là một cáh xếp lần lượt các từ của văn bản vào các dòng, mỗi dòng có đội dài L, sao cho tổng độ dài của các từ trên cùng một dòng không vượt quá L. Ta gọi hệ số phạt của mỗi dòng trong cách phân trang là hiệu số L-S, trong đó S là tổng độ dài của các từ xếp trên dòng đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong số các hệ số phạt của các dòng.
Tìm cách phân trang với hệ số phạt nhỏ nhất.
input: tệp văn bản PTRANG.INP
-Dòng 1 chứa 2 số nguyên dương N<L(N<=4000,L<=70)
-Dòng thứ i tỏng số N dòng tiếp theo chứa số nguyên dương wi(wi <=L)
i= 1, 2, ..., N
output: Tệp văn bản PTRANG.OUT
-Dòng đầu ghi hai số P,Q theo thứ tự là hệ số phạt và số dòng theo cách phân trang tìm được.
-Dòng thứ i trong số Q dòng tiếp theo ghi chỉ số của các từ trong dòng thứ i của cách phân trang.
Bài 7: Chọn số
Cho mảng A có kích thước NxN gồm các số nguyên không âm. Hãy chọn ra K số sao cho mỗi dòng có nhiều nhất 1 số được chọn, mỗi cột có nhiều nhất 1 số được chọn để tổng K số đó là lớn nhất.
Bài 1: Có 16 đồng xu xếp thành bảng 4x4, mỗi đồng xu có thể úp hoặc ngửa. Tại mỗi bước ta có phép biến đổi sau: chọn một đồng xu và thay đổi trạng thái của đồng xu đó và tất cả các đồng xu nằm ở ô chung cạnh (úp thành ngửa, ngửa thành úp). Cho trước trạng thái các đồng xu, hãy lập trình tìm số phép biến đổi ít nhất để đưa về trạng thái tất cả các đồng xu hoặc đều úp hoặc đều ngửa.
Bài 2: Cho N (N≤1000) đoạn số [ai, bi], hãy chọn một tập hợp gồm ít số nhất mà mỗi đoạn số nguyên trên đều có ít nhất 2 số trong tập đó.
vd: có 5 đoạn [0,10] [2,3] [4,7][3,5][5,8] ta chọn tập gồm 4 số {2,3,5,7}
Bài 3: Stones: Có N đống sỏi, đống thứ i có Ai viên sỏi. Ta có thể ghép hai đống sỏi kề nhau thàh một đống và mật một chi phí bằng tổng số sỏi của hai đống. Hãy tìm cách ghép N đống sỏi thành một đống với chi phí là nhỏ nhất.
Bài 4: Cắt hình 1: Có một hình chủ nhật MxN ô vuông, mỗi lần ta được cắt một hình chủ nhật thành hai hình chủ nhật con theo chiều ngang hoặc chiều dọc và lại tiệp tục cắt các hình chữ nhật con cho đến khi được hình vuông thì dừng lại. Hỏi có thể cắt hình chủ nhật MxN thành ít nhất bao nhiêu hình vuông.
Bài 5: Cắt hình 2:
Cho một bảng số gồm M dòng, N cột, các giá trị của bảng A chỉ là 0 hoặc 1. Ta muốn cắt bảng A thành các hình chữ nhật con sao cho các hình chữ nhật con có giá trị toàn bằng 1 hay toàn bằng 0. Một lần cắt là một nhát cắt thẳng theo dòng hoặc theo cột của một hình chữ nhật thành hai hình chữ nhật riêng biệt. Cứ tiếp tục cắt cho đên khi hình chữ nhật có các giá trị taòn ằng 1 hay toàn bằng 0. Hãy tìm cách cắt để số hình chữ nhật con nhận được, có giá trị toàn là 1 hay toàn bằng 0, là nhỏ nhất.
Bài 6: Phân trang
Văn bản là một dãy gồm N từ đánh số từ 1 đến N. Từ i có độ dài là wi (i=1..N). Phân trang là một cáh xếp lần lượt các từ của văn bản vào các dòng, mỗi dòng có đội dài L, sao cho tổng độ dài của các từ trên cùng một dòng không vượt quá L. Ta gọi hệ số phạt của mỗi dòng trong cách phân trang là hiệu số L-S, trong đó S là tổng độ dài của các từ xếp trên dòng đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong số các hệ số phạt của các dòng.
Tìm cách phân trang với hệ số phạt nhỏ nhất.
input: tệp văn bản PTRANG.INP
-Dòng 1 chứa 2 số nguyên dương N<L(N<=4000,L<=70)
-Dòng thứ i tỏng số N dòng tiếp theo chứa số nguyên dương wi(wi <=L)
i= 1, 2, ..., N
output: Tệp văn bản PTRANG.OUT
-Dòng đầu ghi hai số P,Q theo thứ tự là hệ số phạt và số dòng theo cách phân trang tìm được.
-Dòng thứ i trong số Q dòng tiếp theo ghi chỉ số của các từ trong dòng thứ i của cách phân trang.
Bài 7: Chọn số
Cho mảng A có kích thước NxN gồm các số nguyên không âm. Hãy chọn ra K số sao cho mỗi dòng có nhiều nhất 1 số được chọn, mỗi cột có nhiều nhất 1 số được chọn để tổng K số đó là lớn nhất.
