Bài Tập C++ Có Lời Giải/Một Số Bài Tập Nâng Cao - Wikibooks

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> usingnamespacestd; intmain() { intn; cin>>n; for(inti=int(sqrt(n));i>0;i--) { if(n%i==0) { cout<<i<<" "<<n/i<<endl; break; } } return0; }

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 517 322 519 517 513 420 214 227 129 212 3	190158126946957

#include<iostream> #define ll long long #define MAX 1000000 usingnamespacestd; lla[MAX],b[MAX]; intmain(){ intN,t; cin>>N>>t; llsum=0; for(inti=1;i<=N;i++){ cin>>a[i]>>b[i]; sum+=a[i]; } cout<<sum<<endl; for(inti=1;i<=t;i++){ for(intk=1;k<=N;k++){ if(a[k]>0){ a[k]-=b[k]; } } sum=0; for(intj=1;j<=N;j++){ if(a[j]>=0){ sum+=a[j]; } } cout<<sum<<endl; } return0; } //Cách khác #include<iostream> usingnamespacestd; #define ll long long intmain() { intN,t,sum=0; cin>>N>>t; lla[N],b[N]; for(inti=0;i<N;i++) { cin>>a[i]>>b[i]; sum=sum+a[i]; } cout<<sum<<endl; for(intj=0;j<t;j++) { inti=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; } return0; }

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

#include<iostream> usingnamespacestd; intdong[100],cot[100],HoangHau[100],QuyPhi[100]; intn,dem; voidTry(intx); intmain(){ cin>>n; Try(0); cout<<dem; return0; } voidTry(intx){ if(x==n) ++dem; else{ for(inti=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 usingnamespacestd; intdong[]={-1,-2,-2,-1,1,2,2,1}; intcot[]={-2,-1,1,2,2,1,-1,-2}; intn,stt,demKQ; intBC[MAX][MAX]; voidTry(intx,inty); intmain(){ cin>>n; for(intx=0;x<n;x++) for(inty=0;y<n;y++){ stt=1; BC[x][y]=1; Try(x,y); BC[x][y]=0; } cout<<demKQ<<endl; return0; } voidTry(intx,inty){ if(stt>=n*n) demKQ++; else{ for(inti=0;i<8;++i){ intx2=x+dong[i]; inty2=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
1312017	Thu Sau
1512017	Chu Nhat

#include<iostream> usingnamespacestd; intmain(){ intngay,thang,nam; cin>>ngay>>thang>>nam; inta,b,D; D=nam-1; intK=365*D; D=nam%4; intsongay; intkq=0; for(a=1;a<=nam-1;a++){ if(a%100==0){ if(a%400==0)K++; } elseif(a%4==0)K++; } if(nam%100==0){ if(nam%400==0)kq=1; elsekq=0; } else{ if(nam%4==0)kq=1; elsekq=0; } intds=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; elsesongay=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){ case0:cout<<"Chu Nhat"<<endl; break; case1:cout<<"Thu Hai"<<endl; break; case2:cout<<"Thu Ba"<<endl; break; case3:cout<<"Thu Tu"<<endl; break; case4:cout<<"Thu Nam"<<endl; break; case5:cout<<"Thu Sau"<<endl; break; case6: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
45 2#X#V#6 1V....X7 3V..#..X6 2..XV..	YESYESNONO

- 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> usingnamespacestd; intmain(){ intT,n,k,vtX,vtV; cin>>T; for(inti=0;i<T;i++){ boolkq=false; cin>>n>>k; chara[100]; for(inti=0;i<n;i++){ cin>>a[i]; if(a[i]=='X')vtX=i; if(a[i]=='V')vtV=i; } if(vtX<vtV){ for(intj=vtX;j<=vtV;j+=k){ if(a[j]!='#'){ if(j==vtV)kq=true; } elsebreak; } } else{ for(intj=vtX;j>=vtV;j-=k){ if(a[j]!='#'){ if(j==vtV)kq=true; } elsebreak; } } if(kq==true)cout<<"YES"; elsecout<<"NO"; } return0; } //Khác. Hơi dài xíu. cái này chỉ tét được từng cặp nhé #include<iostream> usingnamespacestd; intfindmin(inta,intb) { intmin=a; if(b<a){ min=b; } returnmin; } intfindmax(inta,intb) { intmax=a; if(b>a){ max=b; } returnmax; } intmain() { intn,k,count=0,min,max; cin>>n>>k; charroad[n]; for(inti=0;i<n;i++) { cin>>road[i]; } for(inti=0;i<n;i++) { for(intj=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(intt=min+k;t<max;t=t+k) { if(road[t]=='#') { count; break; } elsecount++; } if(count==0)cout<<"NO"<<endl; elsecout<<"YES"<<endl; } } return0; }

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> usingnamespacestd; intmain() { longlongn; cin>>n; cout<<3*n*(n+1)+1; return0; }

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> usingnamespacestd; boolprc(inta){ for(inty=1;y<a;y++){ intx=a/(y+1)-y/2; if((y+1)*(x+(float)y/2)==a){ cout<<a<<" = "; for(intj=x;j<x+y;j++){ cout<<j<<" + "; } cout<<x+y<<endl; return1; } } return0; } intmain(){ intN; cin>>N; while(N--){ inta; cin>>a; if(!prc(a)) cout<<"IMPOSSIBLE"<<endl; } return0; } //Khác #include<iostream> usingnamespacestd; inttong(inta,intb) { ints=0; for(inti=a;i<=b;i++) { s=s+i; } returns; } voidprint(inta,intb) { for(inti=a;i<=b;i++) { cout<<i<<" "; } } intmain() { intn; cin>>n; intsum=0; for(inti=1;i<=int(n/2);i++) { for(intj=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; } return0; }

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
2 21 2	1
4 510 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> usingnamespacestd; intmain(){ intn,k,a,b; cin>>n>>k; intx[n+1]; for(a=1;a<=n;a++){ cin>>x[a]; } intso,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 usingnamespacestd; intmain() { intn,k; cin>>n>>k; intArr[n]; intNew[MAX]={}; intpos=0; for(inti=0;i<n;i++) { cin>>Arr[i]; } for(inti=0;i<n;i++) { for(intt=0;t<=i;t++) { New[pos]=Arr[t]; pos++; } } for(inti=0;i<pos;i++) { cout<<New[i]<<" "; } cout<<"\n"; cout<<New[k-1]<<endl; return0; }

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> usingnamespacestd; intmain(){ intnam,x; cin>>nam; nam=nam-1800; x=nam%10; switch(x){ case4:cout<<"Giap "; break; case5:cout<<"At "; break; case6:cout<<"Binh "; break; case7:cout<<"Dinh "; break; case8:cout<<"Mau "; break; case9:cout<<"Ky "; break; case0:cout<<"Canh "; break; case1:cout<<"Tan "; break; case2:cout<<"Nham "; break; case3:cout<<"Quy "; break; } x=nam%12; switch(x){ case4:cout<<"Ti"; break; case5:cout<<"Suu"; break; case6:cout<<"Dan"; break; case7:cout<<"Meo"; break; case8:cout<<"Thin"; break; case9:cout<<"Ty"; break; case10:cout<<"Ngo"; break; case11:cout<<"Mui"; break; case0:cout<<"Than"; break; case1:cout<<"Dau"; break; case2:cout<<"Tuat"; break; case3: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
33 2 15 5 04 3 3	1 25 50 1

#include<bits/stdc++.h> usingnamespacestd; structDiem{ intD1,D2,D3; }; istream&operator>>(istream&is,Diem&D); voidTimkiem(DiemD); intmain(){ DiemD[66666]; intbotest,status=0; cin>>botest; while(cin>>D[status]){ ++status; if(status==botest) break; } for(intj=0;j<status;++j){ Timkiem(D[j]); cout<<"\n"; } } istream&operator>>(istream&is,Diem&D){ is>>D.D1>>D.D2>>D.D3; returnis; } voidTimkiem(DiemD){ intdmbn,dmba,kk,kn; dmba=D.D2-D.D3; dmbn=D.D1-D.D3; if(dmba<=0) kk=0; elsekk=dmba; if(dmbn<=D.D2) kn=dmbn; elsekn=D.D2; cout<<kk<<" "<<kn; }