DAP AN DE SO 6
CÂU 1. Phô tô

include <bits/stdc++.h>

using namespace std;
int main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
if (fopen("BAI1.INP","r")){
freopen ("BAI1.INP", "r", stdin);
freopen ("BAI1.OUT", "w", stdout);
}
long long n,res = 0;
cin>>n;
if ((n/2)<=100) res+=300(n/2);
else res+=280(n/2);
if ((n%2)!=0) res+=250;
cout<<res;
return 0;
}
CÂU 2. Hamming

include <bits/stdc++.h>

using namespace std;
int main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
if (fopen("BAI2.INP","r")){
freopen ("BAI2.INP", "r", stdin);
freopen ("BAI2.OUT", "w", stdout);
}
string x,y;
int res = 0;
cin>>x>>y;
while (x.size()<y.size()) x = '0'+x; while (x.size()>y.size()) y = '0'+y;
for (int i=0;i<x.size();i++)
if (x[i]!=y[i]) res++;
cout<<res;
return 0;
}
CÂU 3. Tích nguyên tố

include <bits/stdc++.h>

using namespace std;

define Amax 1000000

int p[Amax+1],n;
void era(){
p[0]=p[1]=1;
for (long long i = 2; ii<=Amax; i++)
if (p[i]==0)
for (long long j = ii; j<=Amax; j+=i)
p[j] = 1;
}
void sub1(){
int a[101],cnt=0;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<n;i++)
for (int j=i+1;j<=n;j++){
int x = a[i]*a[j];
bool nt = x>1;
for (int u = 2; u<=sqrt(x);u++)
if (x%u==0) nt = false;
if (nt) cnt++;
}
cout<<cnt;
}

int main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
if (fopen("BAI3.INP","r")){
freopen ("BAI3.INP", "r", stdin);
freopen ("BAI3.OUT", "w", stdout);
}
int a;
cin>>n;
era();
long long n1=0,nt=0,res=0;
for (int i = 1; i<=n; i++){
cin>>a;
if (a==1){
res += nt;
n1++;
}
if (p[a]==0){
res += n1;
nt++;
}
}
cout<<res;

return 0;

}

CÂU 4. Dãy ngoặc đúng

include <bits/stdc++.h>

using namespace std;
string s;
void sub1(){
bool ok;
int cnt=0,d;
for (int i=0;i<s.size()-1;i++)
for (int j=i+1;j<s.size();j++){
d=0;ok=true;
for (int k=i;k<=j;k++){
if (s[k]=='(') d++;
else d--;
if (d<0) {
ok = false; break;
}
}
if (ok && d==0) cnt++;
}
cout<<cnt;
}

void sub2(){
bool ok;
int cnt=0,d=0;
for (int i=0;i<s.size()-1;i++){
if (s[i]=='(') d=1;
else continue;
for (int j=i+1;j<s.size();j++){
if (s[j]=='(') d++;
else d--;
if (d==0) cnt++;
if (d<0) break;
}
}
cout<<cnt;
}

int main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
if (fopen("BAI4.INP","r")){
freopen ("BAI4.INP", "r", stdin);
freopen ("BAI4.OUT", "w", stdout);
}

cin>>s;
    sub2();

return 0;

}

------------HẾT------------

TÓM TẮT GIẢI THUẬT VÀ ĐÁP ÁN ĐỀ SỐ 4
Bài 1.
a. Ý tưởng thuật toán: Gán giá trị cần tìm maxx=0, thực hiện vòng lặp duyệt từng giá trị tại vị trí i, j, k. Sau đó gán tổng s=2a[i]-3a[j]+5*a[k]. Hàm maxx=max(s,maxx) sẽ cho ta kết quả cần tìm.
b. Chương trình nguồn:

include<bits/stdc++.h>

using namespace std;
long long i,j,k,n,s=0, a[1003],maxx=0;
int main()
{
freopen("BOMAX.INP","r",stdin);
freopen("BOMAX.OUT","w",stdout);
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
for(j=i+1;i<=n;i++)
for(k=j+1;i<=n;i++){
s=2a[i]-3a[j]+5*a[k];
maxx=max(s,maxx);
}
cout<<maxx;
}
Bài 2.
a. Ý tưởng thuật toán: Trước tiên ta tìm vị trí có số nhỏ nhất trong k kí tự đầu. Xóa các ký tự đầu của xâu s. Sau đó tìm các giá trị đầu tiên lớn nhất sau ký tự đầu và xoá đi.
b. Chương trình nguồn:

include<bits/stdc++.h>

using namespace std ;
string s;
long long k,minn,maxx=0;
int main ()
{
freopen("XOAKT.INP","r",stdin);
freopen("XOAKT.OUT","w",stdout);
cin>>s>>k;
for(int i=0;i<=k;i++)
{
if(s[minn]>s[i]){
minn=i;
}
}
s.erase(s.begin()+0,s.begin()+minn);
k=k-minn;
for(int i=1;i<=k;i++)
{
for(int j=0;j<=s.size()-1;j++)
{
if(s[maxx]<s[j]){
maxx=j;
}
}
s.erase(s.begin()+maxx);
maxx=0;
}
cout<<s;
}
Bài 3.
a. Ý tưởng thuật toán:

• Tính tổng các giá trị của mảng từ vị trí 1 cho đến vị trí v, (t[v]).
  • Tính tổng các giá trị của mảng từ vị trí 1 cho đến vị trí (u-1), t[u-1]
• Tổng các phần tử của mảng A từ phần tử thứ u đến phần tử thứ v là t[v]-t[u-1].
  b. Chương trình nguồn:

include <bits/stdc++.h>

using namespace std;
int n,q,i;
long long a[1000006],t[1000006];
int main()
{
freopen("MANG.INP", "r", stdin);
freopen("MANG.OUT", "w", stdout);
cin>>n>>q;
for(i=1;i<=n;i++) cin>>a[i];
t[0]=0;
for(i=1;i<=n;i++) t[i]=t[i-1]+a[i];
for(i=1;i<=q;i++)
{
int u,v;
cin>>u>>v;
cout<<t[v]-t[u-1]<<endl;
}
}

Bài 4.
a. Ý tưởng thuật toán: Phát biểu lại bài toán như sau: Cho m đoạn thẳng, đoạn thẳng i có điểm đầu, điểm cuối là si, ti và chi phí sử dụng đoạn thẳng i là ci. Tìm cách phủ một đoạn thẳng có điểm đầu, cuối là [0, n] với tổng chi phí là ít nhất. Khi đó ta thực hiện như sau:

• Sắp xếp tăng dần điểm cuối của mỗi đoạn thẳng, thêm một đoạn thẳng có điểm đầu, điểm cuối và chi phí sử dụng là 0, 0 ,0 vào vị trí đầu tiên của đoạn thẳng. Như vậy dãy đoạn thẳng cầ tìm luôn bắt đầu ở vị trí của đoạn thẳng vừa thêm vào.
• Sử dụng phương pháp Quy hoạch động: Gọi dp[i] là tổng chi phí sử dụng khi xét các nghệ sĩ từ đoạn thứ 0 đến đoạn thứ i. Khi đó min(dp[j]) trong đó tj>n là kết quả của bài toán.
  b. Chương trình nguồn:

include<bits/stdc++.h>

define N 400

define inf int(1e9)

using namespace std;
struct singer
{
int s,t,c;
};
singer a[N+2];
int dp[N+2];
int n,m,ans=inf;
bool cmp(singer X,singer Y)
{
return X.t<Y.t; } int main() { freopen("VANNGHE.INP","r",stdin); freopen("VANNGHE.OUT","w",stdout); cin>>n>>m;
for(int i=1;i<=m;i++) cin>>a[i].s>>a[i].t>>a[i].c;
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m+1;i++)
{
dp[i]=inf;
for(int j=0;j<i;j++)
if(a[i].s<=a[j].t)
{
dp[i]=min(dp[i],dp[j]+a[i].c);
if(n<=a[i].t) ans=min(ans,dp[i]);
}
}
cout<<ans;
return 0;
}

DAP AN DE 5
Bai 1

include<bits/stdc++.h>

using namespace std;
int main(){
freopen("chinhphuong.inp","r",stdin);
freopen("chinhphuong.out","w",stdout);
long long n;cin>>n;
long long t=0,d=0;
while(n){
t+=(n%10);
n/=10;
d+=1;
}
int r=sqrt(t);
if(r*r==t)cout<<1<<' '<<d;
else cout<<0<<' '<<d;
}

Bai 2

include<bits/stdc++.h>

using namespace std;
int main(){
freopen("LCS.inp","r",stdin);
freopen("Lcs.out","w",stdout);
string s,t;cin>>s>>t;
int d=0;
for(int i=0;i<s.size();i++)if(t.find(s[i])==string::npos)d++;
for(int i=0;i<t.size();i++)if(s.find(t[i])==string::npos)d++;
cout<<d;
}
Bai 3

include<bits/stdc++.h>

using namespace std;
int main(){
freopen("daydep.inp","r",stdin);
freopen("daydep.out","w",stdout);
int n,d=0;cin>>n;
int a[n];
map<int,int>m;
for(int i=0;i<n;i++){ cin>>a[i];
m[a[i]]++;
}
for(int i=0;i<n;i++){
if(m[a[i]]!=a[i]){
if(a[i]<m[a[i]])d+=(m[a[i]]-a[i]);
else d+=m[a[i]];
m[a[i]]=a[i];
}
}
cout<<d;
}

Bai 4

include<bits/stdc++.h>

using namespace std;

define ll long long

int main(){
freopen("muaqua.inp","r",stdin);
freopen("muaqua.out","w",stdout);
ll m,n;cin>>m>>n;
ll a[n];
for(ll i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
ll mi=a[m-1]-a[0];
for(ll i=m;i<n;i++)mi=min(mi,(a[i]-a[i-m+1]));
cout<<mi;
}

include <bits/stdc++.h>

using namespace std;
int n, i,l,r, d, res, a[100005], f1[100005], f2[100005];

void lis(int a[], int f[])
{
int b[100005];
fill(b+1, b+n+1, 1e9);
for(i = 1; i <= n; i++)
{
int v = lower_bound(b+1, b+n+1, a[i]) - b;
b[v] = a[i];
f[i] = v;
}
}

int main()
{
freopen("SPSEQ.inp","r",stdin);
freopen("SPSEQ.out","w",stdout);

cin >> n;
for(i = 1; i <= n; i++) cin >> a[i];
lis(a, f1);
reverse(a+1, a+n+1);
lis(a, f2);
for(i = 1; i <=n ;i++)
{
    res = max(res, min(f1[i], f2[n-i+1])*2-1);
}
    cout<<res;
return 0;

}