Giáo án cả năm

NTSEQS2 - Dãy có tổng bằng S

Cho N  số nguyên dương tạo thành dãy A={A1, A2, ..., AN}. Tìm ra một dãy con của dãy A (không nhất thiết là các phần tử liên tiếp trong dãy) có tổng bằng S cho trước.
Input
Dòng đầu tiên ghi hai số nguyên dương N và S (0Các dòng tiếp theo lần lượt ghi N số hạng của dãy A là các số A1, A2, ..., AN (0Output
Nếu bài toán vô nghiệm thì in ra “NO”
Nếu bài toán có nghiệm thì in ra “YES”
Example
Input:
5 6 1 2 4 3 5
Output:
YES
QBSEQ2 - Dãy con dài nhất có tổng chia hết cho K

Cho một dãy gồm n ( n <= 1000) số nguyên dương A1, A2, ..., An 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.
Input
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ố A1, A2, ..., An được ghi theo đúng thứ tự cách nhau ít nhất một dấu trống hoặc xuống dòng
Output
Gồm 1 dòng duy nhất ghi số lượng phần tử của dãy con dài nhất thoả mãn
Example
Input:
10 3 2 3 5 7 9 6 12 7 11 15
Output:
9
 Submit solution!
BCPALIN2 - Chuỗi đối xứng

Một chuỗi được gọi là đối xứng (palindrome) nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu.
Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi s cho trước. Chuỗi con là chuỗi thu được khi xóa đi một số ký tự từ chuỗi ban đầu.
Input
Gồm một dòng duy nhất chứa chuỗi s (có độ dài không quá 2000 kí tự), chỉ gồm những chữ cái in thường.
Output
Gồm một dòng duy nhất là độ dài xâu con đối xứng dài nhất của xâu s. 
Example
Input:
lmevxeyzl

Output:
5
BCATM3 - ATM 3

Máy ATM tại cổng trường Học viện Công nghệ Bưu chính viễn thông hiện chứa tiền có 9 mệnh giá: 500, 200, 100, 50, 20, 10, 5, 2, 1 (đơn vị Nghìn đồng). Mỗi mệnh giá có vô số tờ tiền.
Khi bạn rút một lượng tiền X (đơn vị Nghìn đồng), máy ATM sẽ tính toán để đưa ra các tờ tiền sao cho tổng tiền là X và số tờ tiền là ít nhất có thể. Bạn hãy viết chương trình giúp ATM giải bài toán này nhé.
Input
Dòng đầu tiên nhập N là số bộ test (0 < N <= 50 000)
N dòng sau, mỗi dòng tương ứng với 1 bộ test, bao gồm số tiền X (0 < X <= 10 000) – là lượng tiền bạn cần rút.
Output
In kết quả trên N dòng, dòng thứ i là tổng số tờ tiền mà máy ATM sẽ đưa ra tương ứng với test thứ i.
Example
Input:
2
560
732

Output:
3
5
BCTSP2 - Travelling Salesman Problem 2

Một người du lịch muốn tham quan n thành phố T1, …, Tn. Xuất phát từ 1 thành phố nào đó, người du lịch muốn đi qua tất cả thành phố còn lại, mỗi thành phố đi qua đúng một lần rồi quay trở lại thành phố xuất phát.
Gọi C[i][j] là chi phí đi từ thành phố Ti đến Tj. Hãy tìm một hành trình thỏa mãn yêu cầu của bài toán sao cho chi phí là nhỏ nhất.
 
Lưu ý: Bài TSP 2 nhằm mục đích luyện tập cho thuật toán tham lam, thuật toán này không đảm bảo luôn tìm ra đáp án tối ưu, tuy nhiên với mục đích luyện tập test của TSP 2 được chọn để tham lam cũng tìm ra được đáp án tối ưu.
Input
Dòng đầu tiên gồm số nguyên n (0 < n <= 1000) – là số thành phố
N dòng tiếp theo, dòng thứ i nhập n số nguyên C[i][j] (0 <= j < n, 0 < C[i][j] <= 10^9) – là chi phí đi từ thành phố Ti đến Tj và ngược lại
Output
In ra chi phí nhỏ nhất có thể đạt được
Example
Input:
 
4
4
0 20 35 42
20 0 34 30
35 34 0 12
42 30 12 0
0 20 35 42

20 0 34 30
35 34 0 12
42 30 12
 
Output:
97
BCTSP - Travelling Salesman