Luyện tập hàm

Alice và Bob đang tham gia một trò chơi với những con số khổng lồ. Alice thách đố Bob bằng cách đưa cho anh một số nguyên dương \(N\) cực kỳ lớn, có thể lên đến \(10^5\) chữ số.

Quy tắc trò chơi như sau: Bob phải liên tục thay thế số \(N\) hiện tại bằng tổng các chữ số của nó. Quá trình này lặp đi lặp lại cho đến khi kết quả thu được là một số chỉ có duy nhất một chữ số. Alice hứa sẽ tặng Bob một món quà nếu anh tìm ra được "số còn lại" cuối cùng đó một cách nhanh nhất.

Bạn hãy giúp Bob thực hiện thử thách này nhé!

Học sinh cần định nghĩa và hoàn thiện hàm sau:

int SumDigit(int n){
    // Thực hiện tính tổng các chữ số của n và trả về kết quả
}

Input

• Một dòng duy nhất chứa số nguyên dương \(N\).

Output

• Một số nguyên duy nhất là kết quả cuối cùng sau khi thực hiện quy tắc trên.

Constraints

• Số nguyên \(N\) có không quá \(10^5\) chữ số.

Example

16

7

9875

2

Viết các hàm xử lý sau:

• Hàm đảo ngược xâu:
  
  C++

  string Reverse(string S){
      // Code xử lý
      return ans;
      // Với ans là xâu S sau khi đảo ngược
  }
  

• Hàm trích xuất số trong xâu:
  
  C++

  void Split_Number(string S, int a[], int &n){
      // Học sinh hoàn thiện hàm này thực hiện việc tách các số trong xâu S 
      // và đưa vào mảng a, và biến n là số lượng số tách được.
      // Ví dụ: S = "abc123ek991" thì n = 2 và mảng a chứa 2 số 123, 991.
  }
  

• Hàm ghép xâu:
  
  C++

  string mergeString(int a[], int n){
      // Ghép tất cả các số của mảng a để tạo thành một số và trả về kết quả, nếu n = 0 trả về "0".
  }
  

Dùng các hàm đã định nghĩa bên trên để giải quyết bài toán sau: Cho một xâu ký tự \(S\) gồm các chữ cái và chữ số. Thực hiện đảo ngược xâu \(S\) đã nhập, sau đó tách toàn bộ số xuất hiện trong xâu \(S\) vào mảng \(a\). Khi đó ta có được mảng \(a\) gồm \(n\) phần tử. Tiếp tục dùng hàm mergeString đã định nghĩa và in ra màn hình giá trị trả về của hàm này.

Có thể tham khảo mã nguồn sau:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], n;

string Reverse(string S){
    // Code xử lý
    return ans;
    // Với ans là xâu S sau khi đảo ngược
}
void Split_Number(string S, int a[], int &n){
    // Học sinh hoàn thiện hàm này thực hiện việc tách các số trong xâu S 
    // và đưa vào mảng a, và biến n là số lượng số tách được.
    // Ví dụ: S = "abc123ek991" thì n = 2 và mảng a chứa 2 số 123, 991.
}
string mergeString(int a[], int n){
    // Ghép tất cả các số của mảng a để tạo thành một số và trả về kết quả
}

signed main(){
    string S; getline(cin, S);
    Split_Number(Reverse(S), a, n);
    cout << mergeString(a, n);
}

Input

• Một dòng duy nhất chứa xâu ký tự \(S\).

Output

• Một dòng duy nhất là kết quả của hàm mergeString sau khi thực hiện các bước theo yêu cầu.

Constraints

• \(|S| \le 10^5\).
• Các chữ số liên tiếp tạo thành các số có giá trị không quá \(10^9\).

Example

abc123ek991

199321

Stack (ngăn xếp) là một cấu trúc dữ liệu hoạt động theo nguyên lý LIFO (Last In, First Out), nghĩa là phần tử được đưa vào sau sẽ được lấy ra trước.

Ví dụ:

Ban đầu:      []
push(1):      [1]
push(2):      [1, 2]
push(3):      [1, 2, 3]
top():        3
pop():        [1, 2]
top():        2

Trong bài tập này, Stack được cài đặt bằng mảng một chiều, không sử dụng struct, class hay thư viện STL.

Các biến đã được định nghĩa

const int MAXN = 1000;

int Stack[MAXN];
int Size = 0;
bool Empty = true;

Ý nghĩa của các biến:

• Stack[]: mảng lưu các phần tử của Stack.
• Size: số lượng phần tử hiện có trong Stack.
• Stack[0] ... Stack[Size-1] là các phần tử đang nằm trong Stack.
• Phần tử ở đỉnh Stack luôn nằm tại vị trí Stack[Size-1].
• Khi Size = 0 thì Stack rỗng.

Nhiệm vụ

Bạn chỉ được phép hoàn thiện các hàm dưới đây:

#include <iostream>
using namespace std;

const int MAXN = 1000;

int Stack[MAXN];
int Size = 0;
bool Empty = true;

//=================================================
// HỌC SINH CHỈ ĐƯỢC VIẾT CODE TRONG CÁC HÀM NÀY
//=================================================

void push(int Stack[], int &Size, int value) {
    // Thêm giá trị value vào đỉnh Stack.
    // Sau đó tăng Size lên 1.
}

void pop(int Stack[], int &Size) {
    // Nếu Stack rỗng thì không làm gì.
    // Ngược lại, xóa phần tử ở đỉnh Stack
    // và giảm Size đi 1.
}

int top(int Stack[], int Size) {
    // Trả về giá trị ở đỉnh Stack.
    // Hàm không được làm thay đổi Stack.
}

bool empty(int Size) {
    // Trả về true nếu Stack rỗng.
    // Ngược lại trả về false.
}

//=================================================

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        push(Stack, Size, x);
    }

    while (!empty(Size)) {
        cout << top(Stack, Size) << " ";
        pop(Stack, Size);
    }

    return 0;
}

Mô tả các hàm

1. Hàm push
void push(int Stack[], int &Size, int value)

• Chức năng: Thêm giá trị value vào đỉnh Stack. Sau khi thêm thành công, số lượng phần tử trong Stack tăng thêm \(1\).
• Ví dụ: Trước khi gọi Stack = [4, 7, 2], Size = 3. Sau khi gọi push(Stack, Size, 9), Stack = [4, 7, 2, 9], Size = 4.

2. Hàm pop
void pop(int Stack[], int &Size)

• Chức năng: Nếu Stack rỗng thì không làm gì. Nếu Stack không rỗng thì xóa phần tử ở đỉnh Stack.
• Ví dụ: Trước khi gọi Stack = [4, 7, 2, 9], Size = 4. Sau khi gọi pop(Stack, Size), Stack = [4, 7, 2], Size = 3.

3. Hàm top
int top(int Stack[], int Size)

• Chức năng: Trả về giá trị của phần tử ở đỉnh Stack. Hàm chỉ đọc dữ liệu và không được phép thay đổi Stack.
• Ví dụ: Stack = [4, 7, 2], top(...) trả về \(2\). Sau khi gọi, Stack và Size vẫn giữ nguyên.

4. Hàm empty
bool empty(int Size)

• Chức năng: Trả về true nếu Stack không có phần tử nào. Ngược lại trả về false.
• Ví dụ: Size = 0 \(\rightarrow\) true; Size = 5 \(\rightarrow\) false.

Chương trình hoạt động như thế nào?

Sau khi bạn hoàn thiện các hàm trên, chương trình sẽ thực hiện theo trình tự sau:

• Đọc \(n\).
• Lặp \(n\) lần: Đọc một số nguyên \(x\), gọi push(Stack, Size, x).
• Trong khi Stack chưa rỗng: In top(Stack, Size) và gọi pop(Stack, Size).

Nói cách khác: Tất cả các số sẽ được đưa vào Stack theo đúng thứ tự nhập. Sau đó chương trình sẽ liên tục lấy phần tử ở đỉnh Stack để in ra rồi xóa khỏi Stack. Kết quả sẽ là dãy số theo thứ tự ngược lại so với lúc nhập.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 1000\)).
• Dòng thứ hai chứa \(n\) số nguyên \(x_i\) (\(|x_i| \le 10^9\)).

Output

• In ra các phần tử của Stack theo thứ tự từ đỉnh xuống đáy, mỗi số cách nhau một khoảng trắng.

Example

5
1 2 3 4 5

5 4 3 2 1

Constraints

• \(1 \le n \le 1000\)
• \(|x_i| \le 10^9\)