Tư duy toán và lập trình - bài toán về thay đổi số chữ số thi tin học trẻ bảng A 2024

Trong bài này, thầy Hiếu sẽ phân tích về giải thuật để code bài toán về thay đổi số chữ số thi tin học trẻ bảng A 2024.

Đề bài:

Phân tích giải thuật:

- Ta cần chú ý tình huống số chữ số của s nhỏ hơn hoặc bằng k. Khi đó ta có thể thay đổi s thành số có dạng 1000...002, đây là số nhỏ nhất chia hết cho 3 thỏa mãn đề bài.

- Xét số chữ số của s lớn hơn k.

+ Nếu số chữ số khác 0 của s nhỏ hơn hoặc bằng k --> ta có thể thay về dạng 100...002 ở trên.
+ Nếu số chữ số khác 0 của s lớn hơn k, ta sẽ thay k - 1 chữ số khác 0 đầu tiên của s thành chữ số 0, sau đó ta thay chữ số khác 0 tiếp theo thành 0, 1 hay 2 phụ thuộc vào số dư của tổng các chữ số lúc này của s khi chia cho 3.

Dưới đây là code tham khảo do thầy Hiếu cài đặt.

#include
#include
#include
using namespace std;

long long int timsochuso(long long int s)
{
       int dem = 0;
       if (s == 0) return 1;
       while (s != 0)
       {
              s = s/10;
              dem++;
       }
       return dem;
}
long long int tongcacchuso(long long int s)
{
       int tong = 0;
       if (s == 0) return 0;
       while (s != 0)
       {
              tong = tong + s%10;
              s = s/10;
       }
       return tong;
}
long long int sochusokhac0(long long int s)
{
       int dem = 0;
       if (s == 0) return 0;
       while (s != 0)
       {
              if(s%10 != 0)
              {
                     dem++;
              }
              s = s/10;
       }
       return dem;
}
int main()
{
       long long int s, k;
       cin >> s;
       cin >> k;
       long long int sochuso = timsochuso(s);
       long long int tongcs = tongcacchuso(s);
       long long int cskhac0 = sochusokhac0(s);
       long long int cs[sochuso];
       
       for(int i = 0; i < sochuso; i++)
       {
              cs[sochuso - 1 - i] = s%10;
              s = s/10;
       }
       if(sochuso < k or cskhac0 <= k)    // Neu so chu so nho hon k, hoac so chu so khac 0 nho hon k
       {
              cs[0] = 1; cs[sochuso-1] = 2;
              for(int i = 1; i < sochuso - 1; i++)
              {
                    cs[i] = 0;
              }
       }else{
              if(cs[0] != 1)
              {
                     tongcs = tongcs + 1 - cs[0]; // Thay doi tong cac chu so
                     cs[0] = 1;                  // Gan chu so dau tien bang 1
                     k--;
              }
              
              for(int i = 1; k > 0; i ++)
              {
                     if(cs[i] != 0 && k > 1)
                     {
                            tongcs = tongcs - cs[i];
                            cs[i] = 0;
                            k --;
                     }
                     if(cs[i] != 0 && k == 1)
                     {
                            tongcs = tongcs - cs[i];
                            if(tongcs % 3 == 0)
                            {
                                   cs[i] = 0;
                                   k --;
                            }else
                            {
                                   cs[i] = 3 - tongcs%3;
                                   k --;
                            }
                     }
              }
       }
       for(int i = 0; i < sochuso; i++)
       {
              cout << cs[i];
       }
}

Các em học sinh có thể tham khảo các khóa học lập trình Scratch, Python, C, C++ tại website của thầy Hiếu và đội ngũ sáng lập: http://mathcode.vn/