1. Đề bài Quy hoạch động Đường đi có tổng lớn nhất Cho ma trận A hình vuông có kích thước n*n. Đầu tiên bạn ở ô có tọa độ [1,1], bạn được phép đi sang phải và đi xuống dưới ô kề cạnh. Hãy tìm đường đi có tổng lớn nhất khi đi đến ô […]
Author: Đặng Minh Tiến
LIQ spoj – Dãy con tăng dài nhất
Nguồn đề bài: http://vn.spoj.com/problems/LIQ/ 1. Đề bài LIQ Dãy con tăng dài nhất Cho một dãy số nguyên gồm N phần tử A[1], A[2], … A[N]. Biết rằng dãy con tăng đơn điệu là 1 dãy A[i1],… A[ik] thỏa mãn i1 < i2 < … < ik và A[i1] < A[i2] < .. < A[ik]. Hãy cho […]
[Tin học] Xây dựng trường Chuyên Bến Tre
2. Đề bài về cặp ghép cực đại có trọng số nhỏ nhất Trường THPT Chuyên Bến Tre ra quyết định xây dựng trường chuyên mới. Ban giám hiệu quyết định trả tiền ngay trong ngày cho các nhà thầu. Có n công trình và n nhà thầu tham gia đấu thầu công trình. Biết […]
PTIT123C spoj PTIT – chứng khoán
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT123C/ 1. Đề bài PTIT123C spoj Cho trước lịch sử giao dịch của một mã chứng khoán trong n ngày. Hãy xác định k1 ngày có giá thấp nhất và k2 ngày có giá cao nhất. Input Mỗi bộ test gồm 2 dòng Dòng 1 ghi 3 số n, k1, k2 với n<=106. k1+k2<=n […]
Hungari Cặp ghép cực đại có trọng số cực tiểu
Nguồn đề bài: http://vn.spoj.com/problems/MATCH2/ 1. Đề bài Cặp ghép cực đại có trọng số cực tiểu Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, …, xn, các đỉnh của Y ký hiệu là y1, y2, …, yn. Mỗi cạnh của G được gán một trọng […]
PTIT123B spoj PTIT – Đếm số lần lặp
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT123B/ 1. Đề bài PTIT123B spoj Cho trước n số nguyên không âm a1, a2, …, an. Mỗi lần lặp, bạn thay đổi dãy này thành một dãy mới theo cách: phần tử thứ k trong dãy mới bằng trị tuyệt đối của ak – ak+1. Phần tử cuối cùng sẽ là an – […]
PTIT122F spoj PTIT – Số siêu tự nhiên
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT122F/ 1. Đề bài PTIT122F spoj Một số siêu tự nhiên là một chuỗi chứa các chữ số và dấu hỏi (ví dụ như 36?1?8). Một số X phù hợp với một số siêu tự nhiên W nếu X có thể được tạo thành từ W bằng cách thay thế dấu hỏi bằng các […]
PTIT121K spoj PTIT – Đường đi lớn nhất
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT121K/ 1. Đề bài PTIT121K spoj Sau những tiết học ban đầu hứng thú với môn Điện tử số về hệ cơ số, MĐ dần thấy nản khi phải đối mặt với các loại mạch và cổng @@. Đầu óc cứ nghĩ đến mấy cái hệ cơ số, MĐ lại nghĩ ra một bài […]
PTIT121I spoj PTIT – Lặp lại các kí tự
Nguồn đề bài: http://www.spoj.com/PTIT12R1/problems/PTIT121I/ 1. Đề bài PTIT121I spoj Với một xâu ký tự S, và một số nguyên R, hãy tạo ra một xâu T bằng cách mỗi ký tự trong S được lặp lại R lần. Các ký tự trong S có thể nằm trong dãy: 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ$%*+-./: Input Dòng 1 ghi số bộ test (không […]
PTIT121G spoj PTIT – Quan hệ
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT121G/ 1. Đề bài PTIT121G spoj Có N người mang tên tương ứng là 1, 2, …, N và tình trạng quen biết của N người này được cho bởi mảng đối xứng A[1..N][1..N] trong đó A[i][j] = A[j][i] = 1 nếu i quen j và bằng 0 nếu i không quen j (quy […]
