PAT Level - A1038 Recover The Smallst Number - A1038, Number, PAT, Recover, Smallst

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given {32, 321, 3214, 0229, 87 }, we can recover many numbers such like 32-321 -3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.

Input Specification:

Each input file contains one test case. Each case gives a positive integer $< span class="strut">$

Output Specification:

For each test case, print the smallest number in one line. Notice that the first digit must not be zero.

Sample Input:

5 32 321 3214 0229 87

Sample Output:




22932132143287

 1 #include 

 2 #include <string>

 3 #include 

 4 #include 

 5 using  namespace std;

 6 //Sequencing issues

 7 int N;

 8 vector<string>v, temp;

 9 string res = "", str = "";

10 void permuteDFS(int u,vector<bool>&visit)//< /span>Use DFS

11 {

12 if (u == v.size())

13  {

14 for (auto a: temp)

15 str += a;

16 res = res> str ? str: res;

17 str = "";

18 return;

19 }

20 for (int i = 0; i i)

21  {

22 if (visit[i] == < span style="color: #0000ff;">true)continue;

23 visit[i] = true;

24  temp.push_back(v[i]);

25 permuteDFS(i + 1, visit);

26  temp.pop_back();

27 visit[i] = false;

28 }

29 }

30

31 void permutex(int u)//Use recursion

32 {

33 if (u == v.size())

34  {

35 for (auto a: v)

36 str += a;

37 res = res> str ? str: res;

38 str = "";

39 }

40 for (int i = u; i i)

41  {

42  swap(v[i], v[u]);

43 permutex(i + 1);

44  swap(v[i], v[u]);

45 }

46 }

47

48 void Sort()//Use sorting rules

49 {

50 sort(v.begin(), v.end(), [](string a, string b) {return a + b  a; });

51 res = "";

52 for (auto a: v)

53 res += a;

54 }

55

56 int main()

57 {

58 cin >> N;

59  v.resize(N);

60 vector<bool>visit(N, < span style="color: #0000ff;">false);

61 for (int i = 0; i i)

62  {

63 cin >> v[i];

64 res += v[i];

65 }

66 //permutex(0);

67 //permuteDFS(0, visit);

68  Sort();

69 while (!res.empty() && res[0] == '0')

70 res.erase(0, 1);

71 if (res.size() == 0)cout << 0 ;

72 cout << res << endl;

73 return 0;

74 }

1 #include
2 #include <string>
3 #include
4 #include
5 using namespace std;
6 //Sequencing issues
7 int N;
8 vector<string>v, temp;
9 string res = "", str = "";
10 void permuteDFS(int u,vector<bool>&visit)//< /span>Use DFS
11 {
12 if (u == v.size())
13 {
14 for (auto a: temp)
15 str += a;
16 res = res> str ? str: res;
17 str = "";
18 return;
19 }
20 for (int i = 0; i i)
21 {
22 if (visit[i] == < span style="color: #0000ff;">true)continue;
23 visit[i] = true;
24 temp.push_back(v[i]);
25 permuteDFS(i + 1, visit);
26 temp.pop_back();
27 visit[i] = false;
28 }
29 }
30
31 void permutex(int u)//Use recursion
32 {
33 if (u == v.size())
34 {
35 for (auto a: v)
36 str += a;
37 res = res> str ? str: res;
38 str = "";
39 }
40 for (int i = u; i i)
41 {
42 swap(v[i], v[u]);
43 permutex(i + 1);
44 swap(v[i], v[u]);
45 }
46 }
47
48 void Sort()//Use sorting rules
49 {
50 sort(v.begin(), v.end(), [](string a, string b) {return a + b a; });
51 res = "";
52 for (auto a: v)
53 res += a;
54 }
55
56 int main()
57 {
58 cin >> N;
59 v.resize(N);
60 vector<bool>visit(N, < span style="color: #0000ff;">false);
61 for (int i = 0; i i)
62 {
63 cin >> v[i];
64 res += v[i];
65 }
66 //permutex(0);
67 //permuteDFS(0, visit);
68 Sort();
69 while (!res.empty() && res[0] == '0')
70 res.erase(0, 1);
71 if (res.size() == 0)cout << 0 ;
72 cout << res << endl;
73 return 0;
74 }

PAT Level – A1038 Recover The Smallst Number

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Leave a Comment Cancel reply