Codeptit - Tài liệu tổng hợp

LCM & GCD 1 Bài làm t t nh ố t ấ Cho hai s nguyên a, b. Nhi ố m v ệ c ụ a b ủ n là tìm b ạ i s ộ chung nh ố nh ỏ t và ấ ư c s ớ ố chung lớn nh t c ấ a a và b. B ủ i s ộ chung nh ố nh ỏ t c ấ a a và b ký hi ủ u là LCM(a, b) ệ và ư c s ớ chung l ố ớn nh t c ấ a a và b ký hi ủ u là GCD(a,b). ệ Input: Dòng đ u tiên đ ầ ưa vào T là s l ố ượng b test. ộ T dòng ti p theo m ế i dòng đ ỗ ưa vào m t b ộ test. M ộ i b ỗ test là m ộ t c ộ p s ặ a, b đ ố ược vi t cách nhau m ế t vào kho ộ ng tr ả ng. ố T, a, b th a mãn ràng bu ỏ
c: 1≤T≤100; 1≤a, b≤108; ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input Output 2 5 10 14 8 10 5 56 2 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb LCM & GCD 2 Bài làm t t nh ố t ấ Cho s t ố ự nhiên n. Nhi m v ệ c ụ a b ủ n là tìm s ạ nguyên nh ố nh ỏ t chia h ấ t cho 1, ế 2, .., n. Input: Dòng đ u tiên đ ầ ưa vào T là s l ố ượng b test. ộ T dòng ti p theo m ế i dòng đ ỗ ưa vào m t b ộ test. M ộ i b ỗ test là m ộ t s ộ t ố ự nhiên n. T th a mãn ràng bu ỏ c: 1≤T≤104; ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input Output 2 3 5 6 60 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb PRIME 1 Bài làm t t nh ố t ấ Cho s nguyên d ố ương N. Hãy đưa ra t t c ấ các ả ư c s ớ nguyên t ố c ố a N. ủ Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test là m ộ t s ộ nguyên d ố ương N được ghi trên m t dòng. ộ T, N th a mãn ràng bu ỏ c: 1≤T≤100; 2≤N≤1010. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 315 31 3 3 5 7 31 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb PRIME 2 Bài làm t t nh ố t ấ Cho s nguyên d ố ương N. Hãy đưa ra ư c s ớ nguyên t ố l ố ớn nh t c ấ a N. ủ Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test là m ộ t s ộ nguyên d ố ương N được ghi trên m t dòng. ộ T, N th a mãn ràng bu ỏ c: 1≤T≤100; 2≤N≤1010. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 315 31 7 31 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb PRIME 3 Bài làm t t nh ố t ấ Cho s nguyên d ố ương N. Hãy đưa ra t t c ấ các s ả nguyên t ố nh ố h ỏ ơn ho c b ặ ng N. ằ Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test là m ộ t s ộ nguyên d ố ương N được ghi trên m t dòng. ộ T, N th a mãn ràng bu ỏ c: 1≤T≤100; 2≤N≤104. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 10 35 2 3 5 7 2 3 5 7 11 13 17 19 23 29 31 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb PRIME 9 Bài làm t t nh ố t ấ Cho s t ố ự nhiên N. Nhi m v ệ c ụ a b ủ n là hãy đ ạ ưa ra t t c ấ các ả ước số nguyên t c ố a ủ
N cùng lũy thừa c a nó. Ví d ủ
N=100 = 22 × 52. N = 35 =51 × 71. ụ Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng test T. Những dòng k ti ế p đ ế ưa vào các b test. M ộ i b ỗ test là m ộ t s ộ nguyên N. ố T, N th a mãn ràng bu ỏ c 1≤T≤100; 1≤N≤10000. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 100 35 2 2 5 2 5 1 7 1 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb PRIME 12 Bài làm t t nh ố t ấ Cho s t ố ự nhiên N. Nhi m v ệ c ụ a b ủ n là hãy đ ạ
ưa ra ước số nguyên tố thứ k của N. Đưa ra -1 n u không t ế n t ồ i ạ ước s th ố ứ k c a N. Ví d ủ N = 225, k =2 ta có k ụ t qu ế ả
là 3 vì 225 = 3×3×5×5. Với N = 81, k = 5 ta có k t qu ế -1 vì 81 = 3×3×3×3. ả Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng test T. Những dòng k ti ế p đ ế ưa vào các b test. M ộ i b ỗ test là m ộ t b ộ đôi N và k. ộ T, N th a mãn ràng bu ỏ c 1≤T≤100; 1≤N, k≤104. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 225 2 81 5 3 -1 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb PRIME 14 Bài làm t t nh ố t ấ Cho s t ố ự nhiên N. Nhi m v ệ c ụ a b ủ n là hãy li ạ t kê t ệ t c ấ các s ả có đúng ba ố ước s . Ví d ố n=100, ta có các s ụ 4, 9, 25, 49. ố Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng test T. Những dòng k ti ế p đ ế ưa vào các b test. M ộ i b ỗ test là m ộ t s ộ N. ố T, N th a mãn rang bu ỏ c 1≤T≤100; 1≤N ≤106. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 50 200 4 9 25 49 4 9 25 49 121 169 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Large Number 1 Bài làm t t nh ố t ấ Cho hai s r ố t l ấ ớn X và Y được bi u di ể n nh ễ ư hai xâu ký tự. Nhi m v ệ c ụ a b ủ n là ạ tìm |X-Y|? Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng test T. Những dòng k ti ế p đ ế ưa vào các b test. M ộ i test g ỗ m hai dòng: dòng th ồ ứ nh t đ ấ ưa xâu X; dòng ti p theo đ ế ưa vào xâu Y. T, X, Y th a mãn ràng bu ỏ
c : 1≤T≤100; 0≤length(X), length(Y)≤103. ộ Output: Đưa ra s k ố t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 978 12977 100 1000000 11999 0999900 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Large Number 2 Bài làm t t nh ố t ấ Cho hai s r ố t l ấ ớn X và Y được bi u di ể n nh ễ ư hai xâu ký tự. Nhi m v ệ c ụ a b ủ n là ạ tìm X+Y? Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng test T. Những dòng k ti ế p đ ế ưa vào các b test. M ộ i test g ỗ m hai dòng: dòng th ồ ứ nh t đ ấ ưa xâu X; dòng ti p theo đ ế ưa vào xâu Y. T, X, Y th a mãn ràng bu ỏ
c : 1≤T≤100; 0≤length(X), length(Y)≤103. ộ Output: Đưa ra s k ố t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 1 12 198111 198123 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Lo i b ạ xâu con ỏ Bài làm t t nh ố t ấ Vi t ch ế
ương trình cho phép nh p vào m ậ t chu ộ i và t ỗ ừ c n lo ầ i b ạ kh ỏ i chu ỏ i. Th ỗ ực hi n lo ệ i b ạ t ỏ ừ và in ra k t qu ế ả Trong đó: INPUT - Hàng thứ nh t là chu ấ i ban đ ỗ u ầ - Hàng ti p theo là t ế ừ c n lo ầ i b ạ ỏ OUTPUT - Chu i k ỗ t qu ế ả Input Output Toi Yeu PTIT Toi Yeu PTIT Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Đ a ch ị email PTIT ỉ Bài làm t t nh ố t ấ Đ a ch ị email c ỉ a cán b ủ PTIT đ ộ ược c p theo nguyên t ấ c ghép tên v ắ ới chữ cái đ u ầ tiên c a h ủ và tên đ ọ m. Vi ệ t ch ế
ương trình cho phép t o các đ ạ a ch ị email theo tên ỉ cán bộ Input Output Nguyen vAn nAM namnv@ptit.edu.vn Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Chu n hóa tên ẩ Bài làm t t nh ố t ấ Tên người dùng s đ ẽ
ược chu n hóa theo nguyên t ẩ c tên đ ắ
ược viết sau cùng, phân tách với ph n tên đ ầ m và tên b ệ ởi d u ph ấ y. Các ch ẩ ữ cái n m trong tên đ ằ u đ ề ược vi t hoa; ch ế ữ cái đ u tiên c ầ a tên đ ủ m và h ệ đ ọ ược vi t hoa, các ch ế ữ cái còn l i ạ vi t th ế ường. Input Output ngUyeN vAN Nam Nguyen Van, NAM Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Tìm s nguyên t ố trong kho ố ng ả Bài làm t t nh ố t ấ Vi t ch ế
ương trình cho phép nh p vào hai s ậ nguyên d ố
ương và tìm tất cả các s ố nguyên t n ố m trong kho ằ ng đó ả Input Output 10 50
11 13 17 19 23 29 31 37 41 43 47 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb MODULO 1 Bài làm t t nh ố t ấ Cho ba s nguyên d ố ương x, y, p. Nhi m v ệ c ụ a b ủ n là tính (xy) %p. Ví d ạ v ụ ới x = 2, y = 3, p = 5 thì (23)%5=3. Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng test T. Những dòng k ti ế p m ế i dòng đ ỗ ưa vào m t test. M ộ i test là b ỗ ba x, y, p đ ộ ược vi t ế cách nhau m t vài kho ộ ng tr ả ng. ố T, x, y, p th a mãn ràng bu ỏ
c : 1≤T≤100; 1≤x, y≤106; 1≤P≤109+7. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 2 3 5 3 2 4 3 1 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb MODULO 2 Bài làm t t nh ố t ấ Cho hai s nguyên d ố ương a và m. Nhi m v ệ c ụ a b ủ n là tìm x nh ạ nh ỏ t trong kho ấ ng ả
[0,m-1] sao cho a * x ≡ 1( mod m). Ví d a = 3, m=11 ta tìm đ ụ ược x = 4 vì 4*3%11=1. Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng test T. Những dòng k ti ế p m ế i dòng đ ỗ ưa vào m t test. M ộ i test là b ỗ đôi a, m đ ộ ược vi t ế cách nhau m t vài kho ộ ng tr ả ng. ố T, a, m th a mãn ràng bu ỏ
c : 1≤T≤100; 1≤a ≤m≤100. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. N u ph ế
ương trình đồng dư không có nghiệm, hày đưa ra -1 Input: Output: 2 3 11 10 17 4 12 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb MODULO 3 Bài làm t t nh ố t ấ
Cho hai s nguyên không âm N và K. Nhi ố m v ệ c ụ a b ủ
n là tìm S = 1%K + 2%K + ..+ N%K. ạ Ví d v ụ
ới N = 10, K=2 ta có S = 1%2 + 2%2+3%2 + 4%2+5%2+6%2+7%2+8%2+9%2+10%2 = 5. Yêu c u đ ầ ph ộ ức t p thu ạ t toán là h ậ ng s ằ ố Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng test T. Những dòng k ti ế p m ế i dòng đ ỗ ưa vào m t test. M ộ i test là b ỗ đôi N, K đ ộ ược vi t ế cách nhau m t vài kho ộ ng tr ả ng. ố T, N, K th a mãn ràng bu ỏ
c : 1≤T≤100; 0≤N ≤1000; 0≤K ≤1012. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 10 55 1 11 55 1 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb MODULO 4 Bài làm t t nh ố t ấ
Cho hai s nguyên không âm N và K. Nhi ố m v ệ c ụ a b ủ n là ki ạ m tra xem K = 1%K + 2%K + ể
..+ N%K hay không. Đưa ra 1 ho c 0 n ặ u c ế p N, K th ặ a mãn ho ỏ c không th ặ a mãn yêu ỏ c u bài toán. Ví d ầ v ụ
ới N = 10, K=55 ta có k t qu ế
là 1 vì 55= 1%55 + 2%55+3%55 ả
+ ..+ 10%55. Ngược l i, N=4, K=11 có k ạ t qu ế
là 0 vì 11≠1%11+ 2%11+3%11+4%11. ả Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng test T. Những dòng k ti ế p m ế i dòng đ ỗ ưa vào m t test. M ộ i test là b ỗ đôi N, K đ ộ ược vi t ế cách nhau m t vài kho ộ ng tr ả ng. ố T, N, K th a mãn ràng bu ỏ
c : 1≤T≤100; 0≤N ≤1000; 0≤K ≤1012. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 10 55 1 11 1 0 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb FIBONACCI 1 Bài làm t t nh ố t ấ Dãy s Fibonacci đ ố
ược đ nh nghĩa Fn = Fn-1 + Fn-2, n>1 và F0 = 0, F1 = 1. D ị ưới đây là m t s ộ s ố
Fibonacci : 0, 1, 1, 2, 3, 5, 8, 13, 21… ố Nhi m v ệ c ụ a b ủ n là tìm s ạ Fibonacci th ố ứ n. Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào các b test. M ộ i b ỗ test là m ộ t s ộ nguyên d ố ương n. T, n th a mãn ràng bu ỏ
c :1 ≤ T ≤ 100; 1≤n≤1000. ộ Output: Đưa ra k t qu ế m ả
i test theo modulo 109 + 7 theo t ỗ ừng dòng. Input Output 2 2 5 1 5 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb COMINATION 1 Bài làm t t nh ố t ấ Cho s t ố
ự nhiên N. Hãy đưa ta các xâu nh phân có đ ị dài N. ộ Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào các b test. M ộ i b ỗ test là m ộ t s ộ N đ ố ược vi t trên 1 ế dòng. T, N th a mãn ràng bu ỏ c :1 ≤ T, N ≤ 20. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input Output 2 2 3 00 01 10 11
000 001 010 011 100 101 110 111 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Re-arrang Array 1 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n ph ồ n t ầ ử. Nhi m v ệ c ụ a b ủ n là hãy s ạ p đ ắ t l ặ i các ph ạ n t ầ ử c a ủ m ng sao cho A[i] = i. N ả u ph ế n t ầ ử A[j] c a có giá tr ủ khác j, hãy đ ị ưa ghi vào -1. Ví d v ụ
ới m ng A[] = {-1,-1,6,1,9, 3, 2, -1, 4, -1} ta có k ả t qu ế A[] = {-1, 1, 2, ả 3, 4, -1, 1, -1, -1, 9}. Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m hai dòng: dòng đ ồ u tiên đ ầ ưa vào n là s ph ố n t ầ ử c a m ủ ng A[]; dòng k ả ti ế p đ ế ưa vào n s A[i] c ố a m ủ ng; các s ả ố được vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố T, n, A[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n ≤107; 1≤ A[i] ≤1018; ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 10 -1 -1 6 1 9 3 2 -1 4 -1 6 0 -3 1 -2 3 - 4 -1 1 2 3 4 -1 6 -1 -1 9 0 1 -1 3 -1 -1 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Re-arrang Array 2 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n ph ồ n t ầ ử. Nhi m v ệ c ụ a b ủ n là hãy s ạ p đ ắ t l ặ i các ph ạ n t ầ ử c a ủ m ng sao cho các s ả 0 đ ố ể ở cu i cùng, các ph ố n t ầ
ử khác không được bảo toàn thứ tự trước sau. Ví d v ụ
ới m ng A[] = {1, 2, 0, 0, 0, 3, 6} ta có k ả t qu ế A[] = {1, 2, ả 3, 6, 0, 0, 0}. Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m hai dòng: dòng đ ồ u tiên đ ầ ưa vào n là s ph ố n t ầ ử c a m ủ ng A[]; dòng k ả ti ế p đ ế ưa vào n s A[i] c ố a m ủ ng; các s ả ố được vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố T, n, A[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n ≤107; 0≤ A[i] ≤1018; ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 7 1 2 0 0 0 3 6 6 0 1 0 2 0 3 1 2 3 6 0 0 0 1 2 3 0 0 0 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Re-arrang Array 14 Bài làm t t nh ố t ấ Cho k m ng m ả i m ỗ ng g ả m n ph ồ n t ầ ử đã được s p x ắ p. Hãy đ ế ưa ra k t qu ế là m ả t dãy ộ đã được s p x ắ p. Ví d ế v ụ ới k = 3, n=4 và m ng ả A[] = { {1, 3, 5, 7}, {2, 4, 6, 8}, {0, 9, 10, 11} }; s cho ta k ẽ t qu ế
A[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ả 11}. Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m hai ph ồ n: ph ầ n th ầ ứ nh t dòng ấ thứ nh t đ ấ ưa là hai s k, n; k dòng ti ố p, m ế i dòng g ỗ m n s ồ c ố a m ủ ng A[k][n]. Các ả s đ ố ược vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố
T, n, k, A[i][j] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n ≤103; 1≤ k ≤10; 1≤ A1[i][j] ộ ≤106. Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 1 3 4 1 3 5 7 2 4 6 8 0 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Order Statistics 1 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n s ồ và s ố k. Hãy tìm ph ố n t ầ ử nh nh ỏ t th ấ ứ k c a m ủ ng. Ví d ả v ụ ới
m ng A[] = {7, 10, 4, 3, 20, 15 }, k=3 ta nh ả n đ ậ ược s nh ố nh ỏ t th ấ ứ k là 7. Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m hai dòng: dòng đ ồ u tiên đ ầ ưa vào n là s ph ố n t ầ ử c a m ủ ng A[] và s ả k; dòng k ố ti ế p đ ế ưa vào n s A[i] c ố a m ủ ng; ả các s đ ố ược vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố
T, n, k, A[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ k≤n ≤105; 1≤ A[i] ≤105; ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 6 3 7 10 4 3 20 15 6 4 9 7 12 8 6 5 7 8 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Order Statistics 2 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n ph ồ n t ầ ử. Hãy tìm ph n t ầ ử lớn nh t c ấ a m ủ ng. Ví d ả v ụ ới m ng A[] ả
= {7, 10, 4, 3, 20, 15 } ta nh n đ ậ ược k t qu ế là 20. ả Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m hai dòng: dòng đ ồ u tiên đ ầ ưa vào n là s ph ố n t ầ ử c a m ủ ng A[]; dòng k ả ti ế p đ ế ưa vào n s A[i] c ố a m ủ ng; các s ả ố được vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố T, n, A[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n ≤105; 1≤ A[i] ≤105; ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 6 7 10 4 3 20 15 6 9 7 12 8 6 5 20 12 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Order Statistics 8 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n s ồ đ ố ược thi t l ế p theo nguyên t ậ c n ắ ửa đ u tăng d ầ n n ầ ửa sau gi m d ả n. Hãy tìm s ầ l ố ớn nh t c ấ a m ủ ng. Ví d ả v ụ
ới m ng A[] = {1, 2, 3, 4, 5, 2, ả 1}, ta có k t qu ế 5. ả Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m hai dòng: dòng đ ồ u tiên đ ầ ưa vào n là s ph ố n t ầ ử c a m ủ ng A[]; dòng k ả ti ế p đ ế ưa vào n s A[i] c ố a m ủ ng; các s ả ố được vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố T, n, A[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n ≤107; 0≤ A[i] ≤107; ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 1 5 1 2 7 4 3 7 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Order Statistics 12 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n s ồ nguyên bao g ố m c ồ s ả 0. Nhi ố m v ệ c ụ a b ủ n là tìm s ạ nguyên ố dương nh nh ỏ t không có m ấ t trong m ặ ng. Ví d ả v ụ
ới m ng A[] = {5, 8, 3, 7, 9, 1}, ả ta có k t qu ế là 2. ả Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m hai dòng: dòng đ ồ u tiên đ ầ ưa vào n là s ph ố n t ầ ử c a m ủ ng A[]; dòng k ả ti ế p đ ế ưa vào n s A[i] c ố a m ủ ng; các s ả ố được vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố T, n, A[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n ≤106; 10-6≤ A[i] ≤106; ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 5 1 2 3 4 5 5 0 -10 1 3 -20 6 2 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Range Query 1 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n ph ồ n t ầ ử và Q câu h i. M ỏ i câu h ỗ i Q là b ỏ đôi hai s ộ L và R. ố Nhi m v ệ c ụ a b ủ n là tìm t ạ ng các ph ổ n t ầ ử c a m ủ ng A[] c ả a m ủ i câu h ỗ i Q. Ví d ỏ v ụ ới
m ng A[] = {1, 1, 2, 1, 3, 4, 5, 2, 8}, các câu h ả
i Q: [1, 5], [2, 4], [3, 5] ta s ỏ ẽ có các câu tr l ả ời : 8 , 4, 6. Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m ba ph ồ n: ph ầ n th ầ ứ nh t đ ấ ưa vào n, Q là s ph ố n t ầ ử c a m ủ ng A[] và s ả l ố ượng câu h i Q; ph ỏ n ti ầ p theo đ ế ưa vào n s A[i] c ố a m ủ ng; ph ả n cu ầ i cùng đ ố ưa vào Q câu h i, m ỏ i câu h ỗ i là m ỏ t b ộ đôi L, ộ R; các s đ ố ược vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố
T, n, Q, L, R, A[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ L≤ R ≤n, Q, ≤104; 1≤ A[i] ộ ≤103; Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 1 9 3 1 1 2 1 3 4 5 2 8 1 5 2 4 3 5 8 4 6 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Range Query 11 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n s ồ ch ố ưa được s p x ắ
p. Hãy tìm Min(A[i]-A[j]) : i ≠j và i, j =0, ế 1, 2, .., n-1. Ví d v ụ
ới A[] = {1, 5, 3, 19, 18, 25} ta có k t qu ế là 1 = 19-18. ả
với A[] = {1, 19, -4, 31, 28, 35, 100} ta có k t qu ế là 3 = 31-28. ả Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m hai dòng: dòng đ ồ u tiên là ầ s ph ố n t ầ ử c a m ủ ng n; dòng ti ả p theo là n s ế A[i] c ố a m ủ ng A[]; các s ả đ ố ược viết cách nhau m t vài kho ộ ng tr ả ng. ố T, n, A[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n ≤103; -103≤ A[i] ≤103. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 5 2 4 5 7 9 10 87 32 99 75 56 43 21 10 68 49 1 6 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Range Query 12 Bài làm t t nh ố t ấ Cho m ng các s ả nh ố phân A1[] và A2[] g ị m n 0, 1. Hãy tìm kho ồ ng chung dài nh ả t ấ
th a mãn: j ≥i và span(i, j) = A1[i] + A1[i+1] + …+A1[j] = A2[i] + A2[i+1] + … ỏ +A2[j]. Ví d v ụ
ới A1[] = {0, 1, 0, 0, 0, 0}, A2[] = {1, 0, 1, 0, 0, 1} ta có k t ế qu là 4 t ả
ương ứng với A1[1]+ A1[2]+ A1[3]+ A1[4] = A2[1]+ A2[2]+ A2[3]+ A2[4] = 1. Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m ba dòng: dòng đ ồ u tiên là s ầ ố ph n t ầ ử c a m ủ ng n; dòng ti ả p theo là n s ế A1[i] c ố a m ủ ng A1[];dòng ti ả p theo là n ế s A2[i] c ố a m ủ ng A2[];các s ả đ ố ược vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố T, n th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n ≤103. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 1 6 0 1 0 0 0 0 1 0 1 0 0 1 4 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Sorting 1 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n s ồ nguyên khác nhau. Hãy đ ố ưa ra các ph n t ầ ử c a m ủ ng theo khuôn ả d ng l ạ ớn nh t, nh ấ nh ỏ t, l ấ ớn thứ hai, nh th ỏ ứ 2, … Ví d v ụ ới A[] = {9, 7, 12, 8,
6, 5} ta đưa ra : 12, 5, 9, 6, 8, 7. Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m hai dòng: dòng đ ồ u tiên là ầ s ph ố n t ầ ử c a m ủ ng n; dòng ti ả p theo là n s ế A [i] c ố a m ủ ng A [];các s ả đ ố ược viết cách nhau m t vài kho ộ ng tr ả ng. ố T, n th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n ≤103. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 7 7 1 2 3 4 5 6 8 1 6 9 4 3 7 8 2 7 1 6 2 5 3 4 9 1 8 2 7 3 6 4 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Sorting 6 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n ph ồ n t ầ ử. Các ph n t ầ ử c a m ủ ng A[] ch ả bao g ỉ m các s ồ 0, 1, 2. ố Hãy s p x ắ p m ế ng A[] theo th ả ứ tự tăng d n. Ví d ầ v ụ
ới A[] = {0, 2, 1, 2, 0} ta k t ế qu A[] = {0, 0, 1, 2, 2}. ả Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m hai dòng: dòng đ ồ u tiên đ ầ ưa vào n là s ph ố n t ầ ử c a m ủ ng A[]; dòng ti ả p theo là n s ế A [i] c ố a m ủ ng A []các s ả ố được vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố T, n, A[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 0≤ A[i] ≤2; 1≤ n ≤106. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 5 0 2 1 2 0 3 0 1 0 0 0 1 2 2 0 0 1 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Sorting 9 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n ph ồ n t ầ ử và s k. Đ ố m t ế t c ấ các c ả p ph ặ n t ầ ử c a m ủ ng có t ả ng ổ b ng k. Ví d ằ
A[] = {1, 5, 3, 4, 2 }, k = 7 ta có k ụ t qu ế là 2 c ả p (3, 4), (5, 2). ặ Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m hai dòng: dòng đ ồ u tiên đ ầ ưa vào n là s ph ố n t ầ ử c a m ủ ng A[] và k; dòng ti ả p theo là n s ế A[i] c ố a m ủ ng A[]các ả s đ ố ược vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố
T, n, k, A[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n ≤100; 0≤ k ≤100, 0≤ A[i] ≤103. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 5 0 1 5 4 1 2 3 2 1 1 1 0 3 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Sorting 12 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n ph ồ n t ầ ử và m ng B[] g ả m m ph ồ n t ầ ử. Nhi m v ệ c ụ a b ủ n là tìm tích ạ giữa ph n t ầ ử lớn nh t c ấ a m ủ ng A[] và ph ả n t ầ ử nh nh ỏ t c ấ a m ủ ng B[]. Ví d ả A[] = ụ
{5, 7, 112, 9, 3, 6, 2 }, B[] = {1, 2, 6, -1, 0, 9} ta có k t qu ế là -9 = 9*(-1). ả Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m ba dòng: dòng đ ồ u tiên đ ầ ưa
vào n, m tương ứng với s ph ố n t ầ ử c a m ủ ng A[] và B[]; dòng ti ả p theo là n s ế ố
A[i] ; dòng cu i cùng là m s ố B[i]; các s ố đ ố ược vi t cách nhau m ế t vài kho ộ ng ả tr ng. ố
T, n, m, A[i], B[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n, m ≤106; -108≤ A[i] ≤108. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 6 6 5 7 9 3 6 2 1 2 6 -1 0 9 6 6 1 4 2 3 10 2 4 2 6 5 2 9 -9 20 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Sorting 13 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n ph ồ n t ầ ử và m ng B[] g ả m m ph ồ n t ầ ử. Nhi m v ệ c ụ a b ủ n là h ạ ợp nh t ấ hai m ng A[] và B[] đ ả đ ể ược m t m ộ ng m ả ới đã được s p x ắ p. Ví d ế A[] = {10, 5, ụ
15}, B[] = {20, 3, 2} ta có k t qu ế
là C[] = {2, 3, 5, 10, 15, 20}. ả Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m ba dòng: dòng đ ồ u tiên đ ầ ưa
vào n, m tương ứng với s ph ố n t ầ ử c a m ủ ng A[] và B[]; dòng ti ả p theo là n s ế ố
A[i] ; dòng cu i cùng là m s ố B[i]; các s ố đ ố ược vi t cách nhau m ế t vài kho ộ ng ả tr ng. ố
T, n, m, A[i], B[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n, m ≤106; -108≤ A[i] ≤108. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 1 3 3 10 5 15 20 3 2 2 3 5 10 15 20 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Sorting 14 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n s ồ nguyên d ố
ương. G i L, R là max và min các ph ọ n t ầ ử c a A[]. ủ Nhi m v ệ c ụ a b ủ n là tìm s ạ ph ố n t ầ ử c n thi ầ t c ế n thêm vào m ầ ng đ ả m ể ng có đ ả y đ ầ ủ các s trong kho ố ng [L, R]. Ví d ả
A[] = {5, 7, 9, 3, 6, 2 } ta nh ụ n đ ậ ược k t qu ế ả
là 2 tương ứng với các s còn thi ố u là 4, 8. ế Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào T b test. M ộ i b ỗ test g ộ m hai dòng: dòng đ ồ u tiên đ ầ ưa
vào n, tương ứng với s ph ố n t ầ ử c a m ủ ng A[]; dòng ti ả p theo là n s ế A[i] ; các ố s đ ố ược vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố T, n, A[i] th a mãn ràng bu ỏ
c: 1≤ T ≤100; 1≤ n, A[i] ≤103. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 5 4 5 3 8 6 3 2 1 3 1 0 Giới h n th ạ ời gian: 2s Giới h n b ạ nh ộ ớ: 65536 Kb Searching 1 Bài làm t t nh ố t ấ Cho m ng A[] g ả m n ph ồ n t ầ ử. Hãy tìm v trí c ị a ph ủ n t ầ ử đ u tiên có giá tr ầ X trong ị m ng A[]. N ả u không tìm th ế y X hãy đ ấ ưa ra -1. Input: Dòng đ u tiên đ ầ ưa vào s l ố ượng b test T. ộ Những dòng k ti ế p đ ế ưa vào các b test. M ộ i b ỗ test g ộ m hai dòng: dòng th ồ ứ nh t ấ đưa vào n, X là s các ph ố n t ầ ử c a m ủ ng A[] và s ả X c ố n tìm; dòng ti ầ p theo đ ế ưa
vào n s A[i] (1≤i≤n) các s ố đ ố ược vi t cách nhau m ế t vài kho ộ ng tr ả ng. ố T, n, A, X th a mãn ràng bu ỏ
c: 1≤T≤100; 1≤N, X, A[i] ≤106. ộ Output: Đưa ra k t qu ế m ả i test theo t ỗ ừng dòng. Input: Output: 2 5 16 9 7 2 16 4 7 98 1 22 57 47 34 18 66 4