Bài tập C++ có lời giải/Một số bài tập nâng cao

Tủ sách mở Wikibooks
Buớc tưới chuyển hướng Bước tới tìm kiếm

Bài 1:

Một công ty quyết định sản xuất lại Ti vi để tung ra thị trường và màn hình Ti vi có chính xác n pixel.

Nhiệm vụ của bạn là xác định kích thước của màn hình Ti vi sao cho chiều rộng và chiều dài chênh lệch nhau ít nhất.

Input Output
8 2 4
64 8 8
5 1 5
 1 #include "iostream"
 2 using namespace std;
 3 
 4 typedef struct tagRongDai {
 5 	long r, d, min;
 6 } rd;
 7 
 8 int main()
 9 {
10 	long n;
11 	cin >> n;
12 	long m = n;
13 	rd a[100];
14 	int t = 0;
15 	int i = 1;
16 	while (n) {
17 		for (i; i < m; i++) {
18 			if (m%i == 0) {
19 				for (int j = i; j <= m / i; j++) {
20 					if ((m / i) % j == 0) {
21 						a[t].r = i;
22 						a[t].d = j;
23 						a[t].min = j - i;
24 					}
25 				}
26 			}
27 		}
28 		t++;
29 		if (i == n) break;
30 	}
31 	int c;
32 	long min = a[0].min;
33 	for (int j = 1; j < t; j++) {
34 		if (min > a[0].min) {
35 			min = a[0].min;
36 			c = j;
37 		}
38 	}
39 	cout << a[c].r << " " << a[c].d;
40     return 0;
41 }

Bài 2:

Có N hồ nước, hồ thứ i có lượng nước ban đầu là a[i] và mỗi ngày lượng nước bốc hơi là b[i]. Hãy xác định tổng lượng nước của các hồ ở từng ngày trong t ngày (ngày 0, ngày 1, ngày 2,......., ngày t).

Input Output
10 5
17 3
22 5
19 5
17 5
13 4
20 2
14 2
27 1
29 2
12 3
190
158
126
94
69
57
 1 #include <iostream>
 2 #define ll long long
 3 #define MAX 1000000
 4 
 5 using namespace std;
 6 
 7 ll a[MAX], b[MAX];
 8 
 9 int main(){
10 	int N, t;
11 	cin >> N >> t;
12 	
13 	ll sum = 0;
14 	for (int i = 1; i <= N; i++){
15 		cin >> a[i] >> b[i];
16 		sum += a[i];
17 	}
18 	cout << sum << endl;
19 
20 	for (int i = 1; i <= t; i++){
21 		for (int k = 1; k <= N; k++){
22 			if (a[k] > 0){
23 				a[k] -= b[k];
24 			}
25 		}
26 		sum = 0;
27 		for (int j = 1; j <= N; j++){
28 			if (a[j] >= 0){
29 				sum += a[j];
30 			}
31 		}		
32 		
33 		cout << sum << endl;
34 	}
35 
36 	return 0;
37 }

Bài 3: Bài toán tám quân hậu

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int dong[100], cot[100], HoangHau[100], QuyPhi[100];
 5 int n, dem;
 6 
 7 void Try(int x);
 8 
 9 int main() {
10 	cin >> n;
11 	Try(0);
12 	cout << dem;
13 	return 0;
14 }
15 
16 void Try(int x){
17 	if (x == n)
18 		++dem;
19 		
20 	else {
21 		for (int i = 0; i < n; ++i){
22 			if (cot[i] == 0 && HoangHau[x - i + n] == 0 && QuyPhi[i + x] == 0){
23 				cot[i] = 1;
24 				HoangHau[x - i + n] = 1;
25 				QuyPhi[i + x] = 1;
26 				Try(x + 1);
27 				QuyPhi[i + x] = 0;
28 				HoangHau[x - i + n] = 0;
29 				cot[i] = 0;
30 			}
31 		}
32 	}
33 }

Bài 4: Bài toán mã đi tuần

 1 #include <iostream>
 2 #include <fstream>
 3 #define MAX 8
 4 
 5 using namespace std;
 6 
 7 int dong[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
 8 int cot[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
 9 
10 int n, stt, demKQ;
11 int BC[MAX][MAX];
12 
13 void Try(int x, int y);
14 
15 int main(){
16 	cin >> n;
17 	
18 	for (int x = 0; x < n; x++)
19 		for (int y = 0; y < n; y++){
20 			stt = 1;
21 			BC[x][y] = 1;
22 			
23 			Try(x, y);
24 
25 			BC[x][y] = 0;
26 		}
27 
28 	cout << demKQ << endl;
29 	
30 	return 0;
31 }
32 
33 void Try(int x, int y){
34 	if (stt >= n*n)
35 		demKQ++;
36 	else{
37 		for (int i = 0; i < 8; ++i){
38 			int x2 = x + dong[i];
39 			int y2 = y + cot[i];
40 			if (0 <= x2 && x2 < n && 0 <= y2 && y2 < n && BC[x2][y2] == 0){
41 				stt++;
42 				BC[x2][y2] = stt;
43 
44 				Try(x2, y2);
45 
46 				BC[x2][y2] = 0;
47 				stt--;
48 			}
49 		}
50 	}
51 }

Bài 5:

Cô thư ký của một vị giám đốc luôn phải sắp thời gian cho công việc hợp lý. Vì vậy, cô thường phải tra cứu lịch để sắp xếp công việc.

Yêu cầu của bài toán là khi cô thư ký nhập vào ngày tháng năm bất kỳ thì sẽ biết ngay đó là thứ mấy?

  • Dữ liệu đầu vào:

- Dòng đầu tiên: giá trị ngày.

- Dòng thứ hai: giá trị tháng.

- Dòng thứ ba: giá trị năm.

  • Dữ liệu đầu ra:

- Một dòng duy nhất là kết quả của bài toán.

VD:

Input Output
13
1
2017
Thu Sau
15
1
2017
Chu Nhat
 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main() {
 5 
 6 	int ngay , thang , nam ;
 7 	cin >> ngay >> thang >> nam ;
 8 	
 9 	int a , b , D ;
10 	D = nam - 1 ;
11 	
12 	int K = 365 * D ;
13 	D = nam % 4 ;
14 	
15 	int songay ;
16 	int kq = 0 ;
17 	for (a = 1 ; a <= nam - 1 ; a++) {
18 
19 		if (a % 100 == 0) {
20 			if (a % 400 == 0) K++ ;
21 		}
22 		else if (a % 4 == 0) K++ ;
23 		
24 	}
25 	
26 	if (nam % 100 == 0) {
27 			if (nam % 400 == 0) kq = 1 ;
28 			else kq = 0 ;
29 		}
30 		
31 	else {
32 			if (nam % 4 == 0) kq = 1 ;
33 		else kq = 0 ;
34 	}
35 	
36 	int ds = 0 ;
37 	for (a = 1 ; a <= thang ; a++) {
38 		
39 		if (a==1 || a==3 || a==5 || a==7 || a==8 || a==10 || a==12) songay = 31;
40 		if (a==4 || a==6 || a==9 || a==11) songay = 30 ;
41 		if (a==2) {
42 			if (kq==1) songay = 29 ;
43 			else songay = 28 ;
44 		}
45 		
46 		for (b = 1 ; b <= songay ; b++) {
47 			K = K + 1 ;
48 			if (b == ngay && a == thang) {
49 			ds = 1 ;
50 			break;
51 		    }
52 		}
53 		
54 		if (ds == 1) break ;
55 
56 	}
57 	
58 	K = K % 7 ;
59 	switch (K) {
60 	    
61 		case 0 : cout << "Chu Nhat" << endl ;
62 		break ;
63 		case 1 : cout << "Thu Hai" << endl ;
64 		break ;
65 		case 2 : cout << "Thu Ba" << endl ;
66 		break ;
67 		case 3 : cout << "Thu Tu" << endl ;
68 		break ;
69 		case 4 : cout << "Thu Nam" << endl ;
70 		break ;
71 		case 5 : cout << "Thu Sau" << endl ;
72 		break ;
73 		case 6 : cout << "Thu Bay" << endl ;
74 		break ;
75 		
76 	}
77 	
78 }

Bài 6:

n chiếc cọc gỗ được xếp thẳng hàng. Chú ếch xanh muốn nhảy qua các chiếc cọc này để tìm tới cọc chú ếch vàng đang đứng. Đương nhiên sẽ có chướng ngại vật trên đường tìm bạn. Mỗi bước nhảy chú ếch xanh có thể nhảy qua k chiếc cọc từ vị trí đứng hiện tại (có thể nhảy sang trái hoặc sang phải).

Ví dụ, nếu k = 1 thì chú ếch có thể nhảy qua duy nhất một chiếc cọc bên cạnh, còn nếu k = 2 thì chú ếch có thể nhảy mà bỏ qua cọc kế bên.

Nhiệm vụ của bạn là hãy xác định xem, sau một chuỗi các bước nhảy thì chú ếch xanh có tìm được chú ếch vàng bạn mình hay không.

Input[sửa]

  • Dòng đầu tiên: số nguyên dương T là số lượng test.
  • Với mỗi bộ test, dữ liệu vào gồm 2 dòng:

- Dòng thứ nhất chứa hai số nguyên dương n và k (2 <= n <= 100, 1 <= k <= n-1). Với n là số lượng cọc gỗ, k là chiều dài mỗi bước nhảy của chú ếch.

- Dòng thứ hai là một chuỗi n ký tự bao gồm:

+ Ký tự ‘.’ có nghĩa là cọc đó đang trống và chú ếch có thể nhảy tới cọc đó.

+ Ký tự ‘#’ nghĩa là cọc đó đang có chướng ngại vật, và chú ếch không thể nhảy tới đây.

+ Ký tự ‘X’ là vị trí hiện tại của chú ếch xanh.

+ Ký tự ‘V’ là vị trí hiện tại của chú ếch vàng.

Output[sửa]

Với từng test, nếu tồn tại một chuỗi các bước nhảy sao cho chú ếch xanh có thể nhảy tới cọc mà chú ếch vàng đang đứng thì in “YES”. Ngược lại in “NO” (không xuất dấu ngoặc kép).

VD:

Input Output
4
5 2
#X#V#
6 1
V....X
7 3
V..#..X
6 2
..XV..
YES
YES
NO
NO

- Giải thích:

  • Ở test 1: Chú ếch có thể nhảy 1 bước duy nhất từ cọc số 2 đến cọc số 4.
  • Ở test 2: Chú ếch có thể nhảy qua từng chiếc cọc để đến được cọc số 1.
  • Ở test 3: Chú ếch xanh không thể nhảy được bước nào. Vì cọc số 4 có chướng ngại vật.
  • Ở test 4: Chú ếch xanh chỉ có thể nhảy tới các cọc số 1 và cọc số 5, rồi lại quay về cọc 3. Không thể nhảy tới cọc có chú ếch vàng.
 1 #include <iostream>
 2 #include <math.h>
 3 
 4 using namespace std;
 5 
 6 int main() {
 7 
 8 	int T , n , k , vtX , vtV ;
 9 	cin >> T ;
10 	
11 	for (int i = 0; i < T; i++) {
12 		bool kq = false;
13 		
14 	cin >> n >> k ;
15 	
16 	char a[100] ;
17 		for (int i = 0 ; i < n ; i++) {
18 			cin >> a[i] ;
19 			if (a[i] == 'X') vtX = i ;
20 			if (a[i] == 'V') vtV = i ;
21 		}
22 		
23 		if (vtX < vtV) {
24 			for (int j = vtX ; j <= vtV ; j += k) {
25 				if (a[j] != '#') {
26 					if (j == vtV) kq = true ;
27 				}
28 				else break ;
29 			}
30 		}
31 		
32 		else {
33 			for (int j = vtX ; j >= vtV ; j -= k) {
34 				if (a[j] != '#') {
35 					if (j == vtV) kq = true;
36 				}
37 				else break ;
38 			}
39 		}
40 		
41 		if (kq == true) cout << "YES" ;
42 		else cout << "NO" ;
43 	}
44 	
45 	return 0;
46 }

Bài 7:

Tổ ong hình lục giác được cấu tạo bằng từng lớp khối bao quanh. Hãy cho biết với lớp N thì có bao nhiêu khối tính từ lớp N vào.

Input[sửa]

+  Số lớp n

Output[sửa]

+  Số khối tính từ lớp 0 đến lớp n

 1 #include <iostream>
 2 #include <math.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     long long n;
 8     cin >> n;
 9     cout << 3*n*(n+1) + 1;
10     return 0;
11 }

Bài 8:

Cho 1 số N. Thể hiện N như là tổng của ít nhất 2 số nguyên dương liên tiếp. Ví dụ

  • 10 = 1 + 2 + 3 + 4
  • 24 = 7 + 8 + 9

Nếu có nhiều đáp án thì in ra đáp án có số lượng phần tử ít nhất. Nếu không có đáp án thì in 1 dòng chữ "IMPOSSIBLE"

 1 #include <iostream>
 2 #include <string>
 3 
 4 using namespace std;
 5 
 6 bool prc(int a) {
 7 	for (int y = 1; y < a; y++) {
 8 		int x = a / (y + 1) - y / 2;
 9 		if ((y + 1)*(x + (float)y / 2) == a) {
10 			cout << a << " = ";
11 			for (int j = x; j < x + y; j++) {
12 				cout << j << " + ";
13 			}
14 			cout << x + y << endl;
15 			return 1;
16 		}
17 	}
18 	return 0;
19 }
20 
21 int main() {
22 	int N;
23 	cin >> N;
24 	while (N--) {
25 		int a;
26 		cin >> a;
27 		if (!prc(a))
28 			cout << "IMPOSSIBLE" << endl;
29 	}
30 
31 	return 0;
32 }

Bài 9:

Trong 1 lớp học để tập luyện trí nhớ, thầy giáo ra một trò chơi. Bạn thứ nhất nghĩ ra 1 con số x1 và đọc nó. Bạn thứ hai nghĩ ra 1 con số x2 và phải đọc con số x1 x2. Cứ như vậy cho đến bạn thứ n. Hỏi con số đếm thứ k là con số mấy ?

VD:

Input Output
2 2
1 2
1
4 5
10 4 18 3
4

- Giải thích:

  • Test case 1 : Trình tự đọc sẽ là : 1 , 1 , 2 . Nếu k = 2 thì kết quả sẽ là 1.
  • Test case 2 : Trình tự đọc sẽ là : 10, 10 , 4 , 10, 4 , 18 , 10 , 4 , 18 , 3 . Nếu k = 5 thì kết quả sẽ là 4.
 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main() {
 5 
 6     int n , k , a , b ;
 7     cin >> n >> k ;
 8     
 9     int x[n+1] ;
10     for (a = 1 ; a <= n ; a++) {
11         cin >> x[a] ;
12     }
13     
14     int so , dem , ahihi ;
15     so = 0 ; ahihi = 0;
16     
17     for (a = 1 ; a <= n ; a++) {
18         
19         for (b = 1 ; b <= a ; b++) {
20             
21             dem = x[b] ;
22             so++ ;
23             if (so == k) {
24                  cout << dem << endl ;
25                  ahihi = 1 ;
26                  break ;
27             }
28         }
29         if (ahihi == 1 ) break;
30         
31     }
32 }

Bài 10: Theo quan niệm phương Đông, mỗi năm được gọi theo một tên ghép từ 10 can và 12 chi. Ví dụ năm 2017 là năm Đinh Dậu, hãy tính toán các năm khác có tên âm lịch là gì.

#include <iostream>
using namespace std;

int main() {
	int nam , x ;
	cin >> nam ;
	nam = nam - 1800 ;
	x = nam % 10 ;
	
	switch(x) { 
		case 4 : cout << "Giap " ;
		break ;
		case 5 : cout << "At " ;
		break ;
		case 6 : cout << "Binh " ;
		break ;
		case 7 : cout << "Dinh " ;
		break ;
		case 8 : cout << "Mau ";
		break ;
		case 9 : cout << "Ky " ;
		break ;
		case 0 : cout << "Canh " ;
		break ;
		case 1 : cout << "Tan " ;
		break ;
		case 2 : cout << "Nham " ;
		break ;
		case 3 : cout << "Quy " ;
		break ;
	}
	
	x = nam % 12;
	
	switch(x) { 
		case 4 : cout << "Ti" ;
		break ;
		case 5 : cout << "Suu" ;
		break ;
		case 6 : cout << "Dan" ;
		break ;
		case 7 : cout << "Meo";
		break ;
		case 8 : cout << "Thin" ;
		break ;
		case 9 : cout << "Ty" ;
		break ;
		case 10 : cout << "Ngo" ;
		break ;
		case 11 : cout << "Mui" ;
		break ;
		case 0 : cout << "Than" ;
		break ;
		case 1 : cout << "Dau" ;
		break ;
		case 2 : cout << "Tuat" ;
		break ;
		case 3 : cout << "Hoi" ;
		break ;
	}
}

Bài 11:

Có n người được mời tham gia giải quyết 1 vấn đề mang tính toàn cầu. Trong n người này, có a người biết cách giải quyết vấn đề và b người từ chối tham gia. Hỏi có tối thiểu và tối đa bao nhiêu người sẽ bắt tay vào giải quyết vấn đề ?

Dữ liệu[sửa]

Dòng đầu tiên chứa số nguyên t (1<= t < = 10.000) là số lượng test. Sau đó là t test.

Mỗi test gồm 1 dòng duy nhất chứa ba số nguyên n, a và b (1<= n <=1000; 0<= a,b <=n).

Kết quả[sửa]

Với mỗi test ghi ra 1 dòng chứa 2 số nguyên là số lượng người tối thiểu và tối đa tham gia giải quyết vấn đề.

VD:

Input Output
3
3 2 1
5 5 0
4 3 3
1 2
5 5
0 1
 1 #include <iostream>
 2 #include <math.h>
 3 #include <string>
 4 
 5 using namespace std;
 6 
 7 struct Diem {
 8 	int D1, D2, D3 ;
 9 } ;
10 
11 istream & operator >> (istream & is, Diem & D);
12 
13 void Timkiem(Diem D) ;
14 
15 int main() {
16     
17 	Diem D[66666] ;
18 	
19 	int botest , status = 0 ;
20 	
21 	cin >> botest ;
22 
23 	while (cin >> D[status]) {
24 		++status ;
25 		if(status == botest)
26 		    break;
27 	}
28 
29 	for (int j = 0 ; j < status; ++j) {
30 		Timkiem(D[j]) ;
31 		cout << "\n" ;
32 	}
33 }
34 
35 istream & operator >> (istream & is, Diem & D) {
36 	is >> D.D1 >> D.D2 >> D.D3 ;
37 	return is ;
38 }
39 
40 void Timkiem(Diem D) {
41     
42 	int dmbn, dmba, kk, kn;
43 	dmba = D.D2 - D.D3 ;
44 	dmbn = D.D1 - D.D3 ;
45 	
46 	if (dmba <= 0) 
47 		kk = 0 ;
48 	else kk = dmba ;
49 	
50 	if (dmbn <= D.D2)
51 		kn = dmbn ;
52 	else kn = D.D2 ;
53 	
54 	cout << kk << " " << kn ;
55 
56 }