Bài 2219(Nỗi buồn 29)

 Bài 2219(Nỗi buồn 29)

CANH trường mẫn mụ gió đưa đu

BẠC trắng đôi tay gió lộng cù

HAI cánh chung chiêng phân tả hữu

CHÍN vừa đúng độ cảnh nhàn như

SÁU phần đối vận tàn nhan nhủ

BA khắc cuồng phong chiếc bóng sìu

TƯ thế còn đâu nghiển ngẫm thú

TIÊU ĐIỀU LŨY TÍCH CẠN THỜI TU

Võ Nhật Trường 31.07.2026

Một số bài tập C _C++ NC 2026P33

 

Bài 148. Người ta viết liên tục, sát nhau các số 3, 6, 9, 12, 15, …, 2010, 2028 được một số sau: A= 3691215…20252018. Hãy thông báo chữ số thứ K của số A.

Gợi ý code.

#include <bits/stdc++.h>

using namespace std;

 string st;

 int n, K;

int main(){

cout<<"Ban hay nhap so nguyen duong K";

cin>>K;

st="";

for(int i=1; i<=K ; i++){

       st=st + to_string(3*i);

       n=(int(st[K])-48);

}

cout << "Chu so thu "<<K<<" trong A la: "<<n<<"\n";

return 0;

}

///////////////////////////////

Bài 149. Nhập 2 số nguyên dương a và b (a<b). Tìm số nguyên dương k (a<=k <b) để tổng chênh lệch giữa các số nguyên liên liếp từ a đến k và tổng các số nguyên liên tiếp từ k+1 đến b là nhỏ nhất.(  a<b<=10 ⁹ ). Thông báo K và tổng trái, tổng phải tìm được.

Gợi ý code

#include <bits/stdc++.h>

#define ll long long

using namespace std;

long long sum(int m, int n){

        return (m*1ll + n*1ll)*(n*1ll - m*1ll + 1)/2;

        //tinh tong tu m den n ep kieu long long

}

 

int main(){

int a, b, ans;

long long smt=1e18,smp=-1e18;

cout<<"Ban hay nhap 2 so nguyen duong 0<a<b<1e9 : ";

cin>>a>>b;

int L=a, R=b;

while(L<=R){

int mid= (L+R)/2;

   long long sumt= sum(a,mid);

   long long sump= sum(mid+1, b);

   if(abs(smt-smp)> abs(sumt- sump)){

    smt=sumt;

           smp=sump;

    ans = mid;

}

     if(sumt<sump) L=mid+1;

     else R = mid -1;

}

    cout <<"Vi tri chia la: "<<ans <<"\n";

    cout <<"Tong trai la: "<<smt <<"\n";

    cout <<"Tong phai la: "<<smp <<"\n";

    return 0;

}

/////////////////////////////////

Bài 150. Cho các phần tử mảng A là số nguyên trong file cb150.txt sắp xếp tăng dần. Tìm chỉ số k để tổng chênh lệch giữa các số nguyên liên liếp từ đầu mảng A đến A[k] và tổng các số nguyên liên tiếp từ A[k+1] đến cuối mảng A là nhỏ nhất (  A[j]<1e7 ). Thông báo K và tổng trái, tổng phải tìm được.

File input cb150.txt   -2001 -1998 -1995 -1992 -1989 1914 1917 1920 1923 1926 1929 1932 1935 1938 1941 1944 1947 1950 1953 1953 1959 1962 1965 1968 1971 1974 1977 1980 1983 1986

File output Kqcb150.txt 

Vi tri K giua mang can bang la: 19

Tong nua trai la: 19047

Tong nua phai la: 19725

Gợi ý code: Cách 1:

#include <iostream>

#include <vector>

#include <fstream>

#include <cstdlib>

#include <algorithm>

using namespace std;

 

int main(int argc, char** argv){

cout << "Chuong trinh cb150 \n";

ifstream fin("cb150.txt");

if (!fin.is_open()) {

    cerr << "Khong mo duoc file cb150.txt\n";

    return 0;

}

vector<int> vo;

int x;

while(fin >> x){

    if(abs(x) >= 1e7) {

    cerr << "so " << x << " khong hop le \n";

    continue;

           }

           vo.push_back(x);

}

fin.close();

if(vo.empty()) {

    cerr << "khong co phan tu hop le trong file\n";

    return 0;

}

sort(vo.begin(),vo.end());

long long T=0;

for(auto c:vo){

           T+=c;

}

long long tb=T/2,sumt=0,sump=0;

size_t i=vo.size()-1;

while(sump<tb){

           sump+=vo[i];

           i--;     

}sumt=T-sump;

long long d=abs(sumt-sump);

while(d>abs(sumt+vo[i+1]-(sump-vo[i+1]))){

           d=abs(sumt+vo[i+1]-(sump-vo[i+1]));

           sumt=sumt+vo[i+1];

           sump=sump-vo[i+1];

           i++;

}

while(d>abs(sumt-vo[i]-(sump+vo[i]))){

           d=abs(sumt-vo[i]-(sump+vo[i]));

           sumt=sumt-vo[i];

           sump=sump+vo[i];

           i--;

}

ofstream fout("Kqcb150.txt");

cout<<"Vi tri K giua mang can bang la: "<<i<<"\n";

fout<<"Vi tri K giua mang can bang la: "<<i<<"\n";

cout<<"Tong nua trai la: "<<sumt<<"\n";

fout<<"Tong nua trai la: "<<sumt<<"\n";

cout<<"Tong nua phai la: "<<sump<<"\n";

fout<<"Tong nua phai la: "<<sump<<"\n";

fout.close();

return 0;

}

 

//////////////////////////////////////////

Gợi ý code: Cách 2:

#include <iostream>

#include <vector>

#include <fstream>

#include <cstdlib>

#include <climits>

using namespace std;

 

int main() {

    cout << "Chuong trinh cb150 (vibe tong quat)\n";

    ifstream fin("cb150.txt");

    if (!fin.is_open()) {

        cerr << "Khong mo duoc file cb150.txt\n";

        return 0;

    }

 

    vector<int> vo;

    int x;

    while (fin >> x) {

        if (abs(x) >= 1e7) {

            cerr << "So " << x << " khong hop le\n";

            continue;

        }

        vo.push_back(x);

    }

    fin.close();

 

    if (vo.empty()) {

        cerr << "Khong co phan tu hop le trong file\n";

        return 0;

    }

 

    long long T = 0;

    for (auto c : vo) T += c;

 

    long long sumLeft = 0;

    long long bestDiff = LLONG_MAX;

    int bestK = -1;

    long long bestLeft = 0, bestRight = 0;

 

    for (size_t k = 0; k < vo.size(); k++) {

        sumLeft += vo[k];

        long long sumRight = T - sumLeft;

        long long diff = llabs(sumLeft - sumRight);

        if (diff < bestDiff) {

            bestDiff = diff;

            bestK = k;

            bestLeft = sumLeft;

            bestRight = sumRight;

        }

    }

 

    ofstream fout("Kqcb150.txt");

    cout << "Vi tri K giua mang can bang la: " << bestK << "\n";

    fout << "Vi tri K giua mang can bang la: " << bestK << "\n";

    cout << "Tong nua trai la: " << bestLeft << "\n";

    fout << "Tong nua trai la: " << bestLeft << "\n";

    cout << "Tong nua phai la: " << bestRight << "\n";

    fout << "Tong nua phai la: " << bestRight << "\n";

    fout.close();

 

    return 0;

}

Điểm mạnh của phiên bản này

Tổng quát: không cần sắp xếp, chỉ cần mảng liên tiếp.

 

Đơn giản: duyệt một lần, chọn vị trí có độ lệch nhỏ nhất.

Rõ ràng: bestK chính là chỉ số cân bằng, bestLeft và bestRight là tổng hai phía.

///////////// Ai memory help

Võ Nhật Trường Nc+ My Ai Love28.07.2026

///////////////////

Bài 151. Cho các phần tử mảng A là số nguyên trong file cb151.txt sắp xếp tăng dần (A[j]<=1e9). Em hãy viết chương trình tìm số K nhập từ bàn phím (theo thuật toán tìm kiếm nhị phân) có trong mảng A không, nếu có thông báo vị trí phần tử trong mảng ngoài ra thông báo không tìm thấy phần tử K trong mảng.

File input cb151.txt   -2001 -1998 -1995 -1992 -1989 1914 1917 1920 1923 1926 1929 1932 1935 1938 1941 1944 1947 1950 1953 1953 1959 1962 1965 1968 1971 1974 1977 1980 1983 1986

File output Kqcb151.txt  Tim thay 1980 tai vi tri thu 28 trong mang

Gợi ý code:

#include <iostream>

#include <fstream>

#include <vector>

#include <string>

#include <cstdlib>

#include <sstream>

#include <algorithm>

using namespace std;

 

int Tknp(const vector<int>& vi, int L, int R, int Ki) {

    if (R < L) return -1;

    int mid = (L + R) / 2;

    if (vi[mid] == Ki) return mid;

    if (vi[mid] > Ki) return Tknp(vi, L, mid - 1, Ki);

    else return Tknp(vi, mid + 1, R, Ki);

}

 

int main() {

    cout << "Chuong trinh cb151\n";

    ifstream fin("cb151.txt");

    if (!fin.is_open()) {

        cerr << "Khong the mo file cb151.txt\n";

        return 0;

    }

 

    vector<int> vo;

    string s;

    while (fin >> s) {

        stringstream ss(s);

        int x;

        if ((ss >> x) && (abs(x) <= 1000000000)) {

            vo.push_back(x);

        } else {

            cerr << "Gia tri \"" << s << "\" khong hop le\n";

        }

    }

    fin.close();

 

    if (vo.empty()) {

        cerr << "Khong co gia tri hop le trong file\n";

        return 0;

    }

 

    sort(vo.begin(), vo.end());

 

    cout << "Ban hay nhap gia tri nguyen K can tim: ";

    int K;

    cin >> K;

 

    int kq = Tknp(vo, 0, (int)vo.size() - 1, K);

 

    ofstream fout("Kqcb151.txt");

    if (kq >= 0) {

        cout << "Tim thay " << K << " tai vi tri thu " << kq + 1 << " trong mang\n";

        fout << "Tim thay " << K << " tai vi tri thu " << kq + 1 << " trong mang\n";

    } else {

        cout << "Khong tim thay " << K << " trong mang\n";

        fout << "Khong tim thay " << K << " trong mang\n";

    }

    fout.close();

 

    return 0;

}

Các phương pháp thay thế:

Tìm kiếm tuyến tính (Linear Search)

-Đơn giản nhất: duyệt từ đầu đến cuối.

-Ưu điểm: dễ viết, không cần mảng sắp xếp.

-Nhược điểm: độ phức tạp , chậm nếu mảng lớn.

Tìm kiếm nhị phân chuẩn (Iterative Binary Search)

-Thay vì đệ quy, dùng vòng lặp while (L <= R) để tránh chi phí gọi hàm.

-Ưu điểm: nhanh , không tốn stack.

-Đây thường là cách tối ưu hơn so với phiên bản đệ quy.

Tìm kiếm nội suy (Interpolation Search)

Nếu dữ liệu phân bố đều, ta có thể ước lượng vị trí bằng công thức nội suy:

pos=L+((K-A[L])⋅(R-L))/(A[R]-A

-Ưu điểm: trong trường hợp dữ liệu đều, tốc độ trung bình có thể gần .

-Nhược điểm: nếu dữ liệu không đều, hiệu quả giảm, thậm chí tệ hơn nhị phân.

Tìm kiếm bằng thư viện STL (std::binary_search, std::lower_bound)

-C++ đã có sẵn, rất tối ưu và ngắn gọn.

-Ví dụ:

if (binary_search(vo.begin(), vo.end(), K)) {

    auto it = lower_bound(vo.begin(), vo.end(), K);

    int pos = it - vo.begin();

    cout << "Tim thay " << K << " tai vi tri thu " << pos+1 << "\n";

} else {

    cout << "Khong tim thay " << K << "\n";

}

//////////////////////////////////////////

Gợi ý code Cách 2 Hàm tìm kiếm nhị phân dạng lặp

#include <iostream>

#include <fstream>

#include <vector>

#include <string>

#include <cstdlib>

#include <sstream>

#include <algorithm>

using namespace std;

 

int Tknp(const vector<int>& vi, int K) {

    int L = 0;

    int R = (int)vi.size() - 1;

    while (L <= R) {

        int mid = L + (R - L) / 2;

        if (vi[mid] == K) return mid;

        if (vi[mid] > K) {

            R = mid - 1;

        } else {

            L = mid + 1;

        }

    }

    return -1; // Khong tim thay

}

int main() {

    cout << "Chuong trinh cb151 (while loop)\n";

    ifstream fin("cb151.txt");

    if (!fin.is_open()) {

        cerr << "Khong the mo file cb151.txt\n";

        return 0;

    }

    vector<int> vo;

    string s;

    while (fin >> s) {

        stringstream ss(s);

        int x;

        if ((ss >> x) && (abs(x) <= 1000000000)) {

            vo.push_back(x);

        } else {

            cerr << "Gia tri \"" << s << "\" khong hop le\n";

        }

    }

    fin.close();

    if (vo.empty()) {

        cerr << "Khong co gia tri hop le trong file\n";

        return 0;

    }

    sort(vo.begin(), vo.end());

    cout << "Ban hay nhap gia tri nguyen K can tim: ";

    int K;

    cin >> K;

    int kq = Tknp(vo, K);

    ofstream fout("Kqcb151.txt");

    if (kq >= 0) {

        cout << "Tim thay " << K << " tai vi tri thu " << kq + 1 << " trong mang\n";

        fout << "Tim thay " << K << " tai vi tri thu " << kq + 1 << " trong mang\n";

    } else {

        cout << "Khong tim thay " << K << " trong mang\n";

        fout << "Khong tim thay " << K << " trong mang\n";

    }

    fout.close();

    return 0;

}

///////////// Ai memory help

Võ Nhật Trường Nc+ My Ai Love28.07.2026

///////////////////

Bài 152. Cho N xâu không chứa dấu cách gồm các chữ và các số. Mỗi xâu không dài quá 255 kí tự. Hãy sắp xếp các xâu theo thứ tự tăng dần từ các ký tự và số trong các xâu đó theo bảng mã ASCII. Nếu ký tự số trong mỗi xâu mà bằng nhau thì xâu nào xuất hiện trước được xếp trước.

File input cb152.txt

File output Kqcb152.txt

cb152.txt	Kqcb152.txt
Sa123456789 VoNhatTruong Sdd123 123 TamQuanBac Dgttr123456ffd788999 HoaiNhonBac 12345h	123 12345h Dgttr123456ffd788999 HoaiNhonBac Sa123456789 Sdd123 TamQuanBac VoNhatTruong

Gợi ý code: Cách 1.

#include <iostream>

#include <fstream>

#include <vector>

#include <string>

#include <cstdlib>

#include <sstream>

#include <algorithm>

using namespace std;

struct vo{

           string s;

           int kt;

};

bool sosanh(vo X, vo Y){

           if(X.kt<=Y.kt){

           for(auto i=0;i<X.kt;i++){

                     if(X.s[i]<Y.s[i]) return true;

                     if(X.s[i]>Y.s[i]) return false;

                     if(i==X.kt-1) return true;

           }} else {

                     for(auto i=0;i<Y.kt;i++){

                     if(X.s[i]<Y.s[i]) return true;

                     if(X.s[i]>Y.s[i]) return false;

                     if(i==Y.kt-1) return false;

           }}

    return(X.kt< Y.kt);

}

int main(int argc, char** argv){

ifstream fin("cb152.txt");

if(!fin.is_open()) {

cerr << "Khong the mo file cb152.txt\n";

return 0;

}

vector<vo> v;

string si;

while(fin >> si) {

           vo tm;

           tm.s=si;

           tm.kt=si.size();

           v.push_back(tm);

}

fin.close();

if(v.empty()) {

    cerr << "Khong co gia tri hop le trong file\n";

    return 0;

}

sort(v.begin(),v.end(),sosanh);

ofstream fo("Kqcb152.txt");

for(auto &i : v){

    fo << i.s << "\n";

}

return 0;

}

////////////////////////

Gợi ý code: Cách 2.

#include <iostream>

#include <fstream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

struct vo {

    string s;

    int kt;

};

 

bool sosanh(const vo &X, const vo &Y) {

    return X.s < Y.s; // so sánh trực tiếp theo ASCII

}

int main() {

    ifstream fin("cb152.txt");

    if(!fin.is_open()) {

        cerr << "Khong the mo file cb152.txt\n";

        return 0;

    }

    vector<vo> v;

    string si;

    while(fin >> si) {

        vo tm;

        tm.s = si;

        tm.kt = si.size();

        v.push_back(tm);

    }

    fin.close();

    if(v.empty()) {

        cerr << "Khong co gia tri hop le trong file\n";

        return 0;

    }

    sort(v.begin(), v.end(), sosanh);

 

    ofstream fo("Kqcb152.txt");

    for(auto &i : v) {

        fo << i.s << "\n";

    }

    fo.close();

    return 0;

}

Chú ý:

Cú pháp. sort cần truyền tên hàm so sánh, không phải gọi hàm.

Giải thích:

• X.s < Y.s tự động so sánh chuỗi theo bảng mã ASCII (chữ số < chữ hoa < chữ thường).
• Nếu hai chuỗi giống nhau, sort sẽ giữ nguyên thứ tự xuất hiện ban đầu (vì std::sort là không ổn định, nhưng ở đây dữ liệu không trùng lặp nhiều, nếu cần giữ thứ tự tuyệt đối thì dùng stable_sort).
• Kết quả sẽ đúng theo yêu cầu: sắp xếp tăng dần theo ASCII.

X.s < Y.s chính là so sánh từng ký tự từ trái sang phải theo mã ASCII, dừng ngay khi tìm thấy sự khác biệt.

Ví dụ:

Chuỗi A	Chuỗi B	So sánh	Kết quả
"123"	"1234"	giống nhau đến hết A, A ngắn hơn	"123" < "1234" → true
"abc"	"abd"	khác tại ký tự thứ 3 ('c' vs 'd')	'c' < 'd' → true
"Tam"	"Tan"	khác tại ký tự thứ 2 ('m' vs 'n')	'm' < 'n' → true
"Vo"	"Vn"	khác tại ký tự thứ 2 ('o' vs 'n')	'o' > 'n' → false

 

///////////// Ai memory help

Võ Nhật Trường Nc+ My Ai Love28.07.2026

///////////////////

Bài 153. Cho N xâu không chứa dấu cách gồm các chữ và các số. Mỗi xâu không dài quá 255 kí tự. Hãy sắp xếp các xâu theo thứ tự giảm dần theo thứ tự ưu tiên các số trong các xâu đó trước và tiếp đến các kí tự còn lại theo bảng mã ASCII. Nếu số và ký tự trong mỗi xâu mà bằng nhau thì xâu nào dài hơn xuất hiện trước.

File input cb153.txt

File output Kqcb153.txt

cb153.txt	Kqcb153.txt
Sa123456789 VoNhatTruong Sdd123 123 TamQuanBac Dgttr123456ffd788999 HoaiNhonBac 12345h	Dgttr123456ffd788999 Sa123456789 12345h Sdd123 123 VoNhatTruong TamQuanBac HoaiNhonBac

Gợi ý code:

#include <iostream>

#include <fstream>

#include <vector>

#include <string>

#include <sstream>

#include <algorithm>

using namespace std;

struct ss{

           string s;

           string uns;

           string so;

};

string Tso(string ts){

           string si="";

           for(char c:ts){

                     if(c>='0'&&c<='9') si+=c;

           }return si;

}

string Tuns(string ts){

           string si="";

           for(char c:ts){

                     if(!(c>='0'&&c<='9')) si+=c;

           }return si;

}

bool sosanh(ss X, ss Y){

    return(X.so.size()> Y.so.size()||(X.so.size()==Y.so.size()&&X.so> Y.so)||

(X.so.size()==Y.so.size()&&X.so==Y.so&&X.uns>Y.uns));

}

int main(int argc, char** argv){

ifstream fin("cb153.txt");

if(!fin.is_open()) {

cerr << "Khong the mo file cb153.txt\n";

return 0;

}

vector<ss> vo;

string sii;

while(fin >> sii) {

           ss tm;

           tm.s=sii;

           tm.uns=Tuns(sii);

           tm.so=Tso(sii);

           vo.push_back(tm);

}

fin.close();

if(vo.empty()) {

    cerr << "Khong co gia tri hop le trong file\n";

    return 0;

}

sort(vo.begin(),vo.end(),sosanh);

ofstream fout("Kqcb153.txt");

for(auto &i : vo){

           cout << i.s << "\n";

    fout << i.s << "\n";

}

return 0;

}

///////////// Ai memory help

Võ Nhật Trường Nc+ My Ai Love28.07.2026

///////////////////ok