Bài tập C++ có lời giải/Một số bài tập nâng cao
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 |
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int n ;
cin >> n;
for (int i = int(sqrt(n)); i > 0 ;i--)
{
if (n%i ==0 )
{
cout << i <<" " << n/i<<endl;
break;
}
}
return 0 ;
}
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 |
|---|---|
17 3 22 5 19 5 17 5 13 4 20 2 14 2 27 1 29 2 12 3 |
158 126 94 69 57 |
#include <iostream>
#define ll long long
#define MAX 1000000
using namespace std;
ll a[MAX], b[MAX];
int main(){
int N, t;
cin >> N >> t;
ll sum = 0;
for (int i = 1; i <= N; i++){
cin >> a[i] >> b[i];
sum += a[i];
}
cout << sum << endl;
for (int i = 1; i <= t; i++){
for (int k = 1; k <= N; k++){
if (a[k] > 0){
a[k] -= b[k];
}
}
sum = 0;
for (int j = 1; j <= N; j++){
if (a[j] >= 0){
sum += a[j];
}
}
cout << sum << endl;
}
return 0;
}
//Cách khác
#include <iostream>
using namespace std;
#define ll long long
int main()
{
int N, t, sum = 0;
cin >> N >> t ;
ll a[N], b[N];
for (int i =0; i<N; i++)
{
cin >> a[i] >> b[i];
sum = sum + a[i];
}
cout << sum <<endl;
for (int j = 0; j<t;j++)
{
int i = 0;
while (i<N)
{
if (a[i] >= b[i])
{
sum = sum - b[i];
a[i] = a[i] - b[i];
}
else
{
sum = sum - a[i];
a[i] = 0;
}
i++ ;
}
cout << sum << endl;
}
return 0;
}
Bài 3: Bài toán tám quân hậu
#include <iostream>
using namespace std;
int dong[100], cot[100], HoangHau[100], QuyPhi[100];
int n, dem;
void Try(int x);
int main() {
cin >> n;
Try(0);
cout << dem;
return 0;
}
void Try(int x){
if (x == n)
++dem;
else {
for (int i = 0; i < n; ++i){
if (cot[i] == 0 && HoangHau[x - i + n] == 0 && QuyPhi[i + x] == 0){
cot[i] = 1;
HoangHau[x - i + n] = 1;
QuyPhi[i + x] = 1;
Try(x + 1);
QuyPhi[i + x] = 0;
HoangHau[x - i + n] = 0;
cot[i] = 0;
}
}
}
}
Bài 4: Bài toán mã đi tuần
#include <iostream>
#include <fstream>
#define MAX 8
using namespace std;
int dong[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int cot[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int n, stt, demKQ;
int BC[MAX][MAX];
void Try(int x, int y);
int main(){
cin >> n;
for (int x = 0; x < n; x++)
for (int y = 0; y < n; y++){
stt = 1;
BC[x][y] = 1;
Try(x, y);
BC[x][y] = 0;
}
cout << demKQ << endl;
return 0;
}
void Try(int x, int y){
if (stt >= n*n)
demKQ++;
else{
for (int i = 0; i < 8; ++i){
int x2 = x + dong[i];
int y2 = y + cot[i];
if (0 <= x2 && x2 < n && 0 <= y2 && y2 < n && BC[x2][y2] == 0){
stt++;
BC[x2][y2] = stt;
Try(x2, y2);
BC[x2][y2] = 0;
stt--;
}
}
}
}
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 |
|---|---|
1 2017 |
Thu Sau |
1 2017 |
Chu Nhat |
#include <iostream>
using namespace std;
int main() {
int ngay , thang , nam ;
cin >> ngay >> thang >> nam ;
int a , b , D ;
D = nam - 1 ;
int K = 365 * D ;
D = nam % 4 ;
int songay ;
int kq = 0 ;
for (a = 1 ; a <= nam - 1 ; a++) {
if (a % 100 == 0) {
if (a % 400 == 0) K++ ;
}
else if (a % 4 == 0) K++ ;
}
if (nam % 100 == 0) {
if (nam % 400 == 0) kq = 1 ;
else kq = 0 ;
}
else {
if (nam % 4 == 0) kq = 1 ;
else kq = 0 ;
}
int ds = 0 ;
for (a = 1 ; a <= thang ; a++) {
if (a==1 || a==3 || a==5 || a==7 || a==8 || a==10 || a==12) songay = 31;
if (a==4 || a==6 || a==9 || a==11) songay = 30 ;
if (a==2) {
if (kq==1) songay = 29 ;
else songay = 28 ;
}
for (b = 1 ; b <= songay ; b++) {
K = K + 1 ;
if (b == ngay && a == thang) {
ds = 1 ;
break;
}
}
if (ds == 1) break ;
}
K = K % 7 ;
switch (K) {
case 0 : cout << "Chu Nhat" << endl ;
break ;
case 1 : cout << "Thu Hai" << endl ;
break ;
case 2 : cout << "Thu Ba" << endl ;
break ;
case 3 : cout << "Thu Tu" << endl ;
break ;
case 4 : cout << "Thu Nam" << endl ;
break ;
case 5 : cout << "Thu Sau" << endl ;
break ;
case 6 : cout << "Thu Bay" << endl ;
break ;
}
}
Bài 6:
Có 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.
sốnguyên n (0 < n <106)
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 |
|---|---|
5 2 #X#V# 6 1 V....X 7 3 V..#..X 6 2 ..XV.. |
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.
#include <iostream>
#include <math.h>
using namespace std;
int main() {
int T , n , k , vtX , vtV ;
cin >> T ;
for (int i = 0; i < T; i++) {
bool kq = false;
cin >> n >> k ;
char a[100] ;
for (int i = 0 ; i < n ; i++) {
cin >> a[i] ;
if (a[i] == 'X') vtX = i ;
if (a[i] == 'V') vtV = i ;
}
if (vtX < vtV) {
for (int j = vtX ; j <= vtV ; j += k) {
if (a[j] != '#') {
if (j == vtV) kq = true ;
}
else break ;
}
}
else {
for (int j = vtX ; j >= vtV ; j -= k) {
if (a[j] != '#') {
if (j == vtV) kq = true;
}
else break ;
}
}
if (kq == true) cout << "YES" ;
else cout << "NO" ;
}
return 0;
}
//Khác. Hơi dài xíu. cái này chỉ tét được từng cặp nhé
#include <iostream>
using namespace std;
int findmin(int a, int b)
{
int min = a;
if (b<a){
min = b;
}
return min;
}
int findmax(int a, int b)
{
int max = a;
if (b>a){
max = b;
}
return max;
}
int main()
{
int n ,k, count = 0, min, max ;
cin >> n >> k;
char road[n];
for (int i =0; i<n; i++)
{
cin >>road[i] ;
}
for (int i=0; i<n; i++)
{
for (int j = 0 ; j<n; j++)
{
if (road[i] == 'X' && road[j]=='V')
{
min = findmin(i,j);
max = findmax(i,j);
break;
}
}
}
if ((max-min)%k!=0) cout << "NO" <<endl;
else
{
if (max-min == k) cout <<"YES" <<endl;
else
{
for (int t = min +k; t<max; t=t+k)
{
if (road[t] == '#')
{
count;
break;
}
else count ++;
}
if (count == 0) cout <<"NO" <<endl;
else cout <<"YES" <<endl;
}
}
return 0;
}
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.
Output[sửa]
+ Số khối tính từ lớp 0 đến lớp n
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
long long n;
cin >> n;
cout << 3*n*(n+1) + 1;
return 0;
}
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"
#include <iostream>
#include <string>
using namespace std;
bool prc(int a) {
for (int y = 1; y < a; y++) {
int x = a / (y + 1) - y / 2;
if ((y + 1)*(x + (float)y / 2) == a) {
cout << a << " = ";
for (int j = x; j < x + y; j++) {
cout << j << " + ";
}
cout << x + y << endl;
return 1;
}
}
return 0;
}
int main() {
int N;
cin >> N;
while (N--) {
int a;
cin >> a;
if (!prc(a))
cout << "IMPOSSIBLE" << endl;
}
return 0;
}
//Khác
#include <iostream>
using namespace std;
int tong(int a, int b )
{
int s =0;
for (int i=a; i<=b; i++)
{
s= s+i;
}
return s;
}
void print(int a, int b)
{
for (int i= a; i<=b; i++)
{
cout << i <<" ";
}
}
int main()
{
int n;
cin >> n;
int sum = 0;
for (int i = 1; i<=int(n/2); i++)
{
for (int j = i+1; j<=int(n/2)+1; j++)
{
if (tong(i,j) == n)
{
print(i,j);
cout <<"\n" ;
break;
}
else
{
sum++;
}
}
}
if (sum == tong(1,int(n/2)))
{
cout <<"IMPOSSIBLE" <<endl;
}
return 0;
}
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 ? mmmm VD:
| Input | Output |
|---|---|
1 2 |
1 |
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.
#include <iostream>
using namespace std;
int main() {
int n , k , a , b ;
cin >> n >> k ;
int x[n+1] ;
for (a = 1 ; a <= n ; a++) {
cin >> x[a] ;
}
int so , dem , ahihi ;
so = 0 ; ahihi = 0;
for (a = 1 ; a <= n ; a++) {
for (b = 1 ; b <= a ; b++) {
dem = x[b] ;
so++ ;
if (so == k) {
cout << dem << endl ;
ahihi = 1 ;
break ;
}
}
if (ahihi == 1 ) break;
}
}
//Khác
#include <iostream>
#define MAX 1000
using namespace std;
int main()
{
int n,k;
cin >> n >> k;
int Arr[n] ;
int New[MAX] = {};
int pos = 0;
for (int i=0; i<n; i++)
{
cin >> Arr[i];
}
for (int i =0; i<n; i++)
{
for (int t = 0; t<= i ; t++)
{
New[pos] = Arr[t];
pos ++ ;
}
}
for (int i = 0 ; i< pos ; i++)
{
cout << New[i] <<" ";
}
cout << "\n" ;
cout << New[k-1] <<endl;
return 0;
}
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 <=10000; 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 2 1 5 5 0 4 3 3 |
5 5 0 1 |
#include <bits/stdc++.h>
using namespace std;
struct Diem {
int D1, D2, D3 ;
} ;
istream & operator >> (istream & is, Diem & D);
void Timkiem(Diem D) ;
int main() {
Diem D[66666] ;
int botest , status = 0 ;
cin >> botest ;
while (cin >> D[status]) {
++status ;
if(status == botest)
break;
}
for (int j = 0 ; j < status; ++j) {
Timkiem(D[j]) ;
cout << "\n" ;
}
}
istream & operator >> (istream & is, Diem & D) {
is >> D.D1 >> D.D2 >> D.D3 ;
return is ;
}
void Timkiem(Diem D) {
int dmbn, dmba, kk, kn;
dmba = D.D2 - D.D3 ;
dmbn = D.D1 - D.D3 ;
if (dmba <= 0)
kk = 0 ;
else kk = dmba ;
if (dmbn <= D.D2)
kn = dmbn ;
else kn = D.D2 ;
cout << kk << " " << kn ;
}