NTU - MERGENUM -Ghep so

MERGENUM - Ghép số

Dữ liệu vào: standard input

Dữ liệu ra: standard output

Giới hạn thời gian: 1.0 giây

Giới hạn bộ nhớ: 128 megabyte

Đăng bởi: middlest

Cho hai số nguyên dương x, y, ta xây dựng số z bằng cách ghép các chữ số của x và y sao cho thứ tự các chữ số của x và y vẫn giữ nguyên trên z. Tìm giá trị bé nhất và lớn nhất của z.

Dữ liệu vào

Một dòng gồm 2 số nguyên dương x, y

Dữ liệu ra

Dòng thứ nhất ghi giá trị bé nhất của z và dòng thứ hai ghi giá trị lớn nhất của z

Giới hạn

1 <= x, y <= 10⁸, dữ liệu đảm bảo không có các chữ số 0 vô nghĩa của x và y.

Ví dụ

• input
  13 26
  output
  1236
  2613

Sol:

#include<bits/stdc++.h>
using namespace std;
struct Node{
   string a,b,res;
};
int main(){
   char s1[20],s2[20];
   scanf("%s",s1);
   scanf("%s",s2);
   Node root;
   root.a=string(s1);
   root.b=string(s2);
   root.res=string("");
   stack<Node> Stack;
   Stack.push(root);
   vector<string> bag;
   Node temp;
   Node newNode1, newNode2;
   set<string> Set;
   while(!Stack.empty()){
     Node temp=Stack.top();
     Stack.pop();
     if((temp.a.size()==0)&&(temp.b.size()==0)){
        Set.insert(temp.res);
     }
     if(temp.a.size()>0){
        newNode1.b=temp.b;
        newNode1.res=temp.res+temp.a[0];
        if(temp.a.size()==1) newNode1.a="";
        else
            newNode1.a=string(&temp.a[1]);
        Stack.push(newNode1);
     }
     if(temp.b.size()>0){
        newNode2.a=temp.a;
        newNode2.res=temp.res+temp.b[0];
        if(temp.b.size()==1) newNode2.b="";
        else newNode2.b=string(&temp.b[1]);
        Stack.push(newNode2);
     }
   }
   set<string>::iterator it=Set.end();
   --it;
   printf("%s\n%s",(*Set.begin()).c_str(),(*it).c_str());
   return 0;
}