# Donghua oj advanced question 57 number game 57 digital games

Author: xxx time limit: 1S chapter: recursion

Problem Description:

Now, there are many digital games for children. These games are easy to play, but it is not so easy to create one. Here, we will introduce an interesting game.

You'll get N positive integers. You can concatenate one integer with another to make a larger integer. For example, there are four numbers 123, 124, 56,
90, they can make the following integers - 1231245690, 1241235690, 5612312490, 9012312456,
9056124123… Wait, a total of 24 (4!) numbers can be combined. But 9056124123 is the biggest one.

You may think it's a simple thing, but is it a simple task for a child who just has a digital concept

The input contains multiple sets of test data.

Each group of test data has two lines, the first line is a positive integer N (N < = 50), and the second line has N positive integers.

When N=0, it means the end of input.

Output Description:

For each set of test data, output a row, and output the largest integer that can be combined with these N integers.

Input example: 5 123 124 56 90 9 11 5 991 9909 99 990 989 2 191 1919 0
Output example: 99056124123 1 999919909990989 1919191

At first, I didn't deal with recursion, and there was no problem with the test results, but the prompt timed out after submission. In fact, it can also be understood that if N takes 50, 50! Call times, no timeout.
Original code:

```/*
T57 Digital game
Algorithm overview: store the concatenated number with string, and set the string to null at the beginning
The given number is traversed first according to the sequence number from small to large depth, and the currently selected number is spliced into the above string every time
At the last level of recursion, the final string is compared with the current maximum string, and the maximum number is updated
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 1000

int N = 0;
int flag;// flag[i] indicates that the number with subscript i in nums has been selected
int nums = {0};// Number given
char max[MAX_SIZE] = "";// String of the largest number
void DFS(char res[], int index, int layer);

int main() {

int i = 0;
char res[MAX_SIZE] = "";// Results of digital splicing

//	res = '\0';
//	itoa(123456, res, 10);
//printf("%s\n", itoa(123456, res, 10));

while (scanf("%d", &N) != EOF) {
if (N == 0)
break;

for (i = 1; i <= N; i++)
scanf("%d", &nums[i]);

//nums = 991, nums = 9909, nums = 99, nums = 990, nums = 989;

for (i = 1; i <= N; i++) {// Depth first traversal from small to large
res = '\0';// Reset results
memset(flag, 0, sizeof(flag));// Reset mark
flag[i] = 1;
DFS(res, i, 1);
}

printf("%s\n", max);
}

return 0;
}

// Depth first digit
// res represents the result of digital splicing, index represents the subscript of the currently selected number, and layer represents the number of layers of current recursion
void DFS(char res[], int index, int layer) {
char temp = "";// For numeric to string
char oriRes[MAX_SIZE] = "";// The original result of each layer of recursion
int i = 0;

strcpy(oriRes, strcat(res, itoa(nums[index], temp, 10)));// Splicing

if (layer == N) {// Recursive export
if (strcmp(res, max) == 1)// Only when strcmp(res, max) returns 1 and - 1 can execute, so the result will be wrong
strcpy(max, res);// Update Max
flag[index] = 0;// De sign

return ;
}

for (i = 1; i <= N; i++) {// Choose another number
if (!flag[i]) {// If the current number is not selected
flag[i] = 1;
strcpy(res, oriRes);// Reset results
DFS(res, i, layer + 1);
}
}
flag[index] = 0;// De sign
}
```

Later, I thought that when there was res = "989", max="999 *******" this situation, the current recursive path actually didn't need to go on, because the results are the same, you can reduce the number of recursions according to this pruning.

```// Judge whether pruning is needed
int isCapable(char res[], char max[]) {
int len1 = strlen(res);
int len2 = strlen(max);
int len = len1 < len2 ? len1 : len2;
int i = 0;

for (i = 0; i < len; i++) {
// The number of res is smaller than that of max, so the current recursive path can be cut out
if ((res[i] - '0') < (max[i] - '0')) {
//printf("+++%c %c\n", res[i], max[i]);
return 1;
}
if ((res[i] - '0') > (max[i] - '0')) {
return 0;
}
}
return 0;
}
```

And it did decrease    Many times, but still overtime
Timeout full code:

```/*
T57 Digital game
Algorithm overview: store the concatenated number with string, and set the string to null at the beginning
The given number is traversed first according to the sequence number from small to large depth, and the currently selected number is spliced into the above string every time
At the last level of recursion, the final string is compared with the current maximum string, and the maximum number is updated
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 1000

int N = 0;
int count = 0;
int flag;// flag[i] indicates that the number with subscript i in nums has been selected
int nums = {0};// Number given
char max[MAX_SIZE] = "";// String of the largest number
void DFS(char res[], int index, int layer);
int isCapable(char res[], char max[]);

int main() {

int i = 0;
char res[MAX_SIZE] = "";// Results of digital splicing

//	res = '\0';
//	itoa(123456, res, 10);
//printf("%s\n", itoa(123456, res, 10));

while (scanf("%d", &N) != EOF) {
if (N == 0)
break;

count = 0;
//		for (i = 1; i <= N; i++)
//			scanf("%d", &nums[i]);

nums = 991, nums = 9909, nums = 99, nums = 990, nums = 989;

for (i = 1; i <= N; i++) {// Depth first traversal from small to large
res = '\0';// Reset results
memset(flag, 0, sizeof(flag));// Reset mark
flag[i] = 1;
DFS(res, i, 1);
}

printf("%s\n", max);
printf("Total call%d second\n", count);
}

return 0;
}

// Depth first digit
// res represents the result of digital splicing, index represents the subscript of the currently selected number, and layer represents the number of layers of current recursion
void DFS(char res[], int index, int layer) {
char temp = "";// For numeric to string
char oriRes[MAX_SIZE] = "";// The original result of each layer of recursion
int i = 0;

count++;

if (strlen(res) != 0 && isCapable(res, max)) {// Prune
//printf("res=%s, max=%s\n", res, max);
flag[index] = 0;// De sign
return ;
}

strcpy(oriRes, strcat(res, itoa(nums[index], temp, 10)));// Splicing

if (layer == N) {// Recursive export
if (strcmp(res, max) == 1)// Only when strcmp(res, max) returns 1 and - 1 can execute, so the result will be wrong
strcpy(max, res);// Update Max
flag[index] = 0;// De sign

return ;
}

for (i = 1; i <= N; i++) {// Choose another number
if (!flag[i]) {// If the current number is not selected
flag[i] = 1;
strcpy(res, oriRes);// Reset results
DFS(res, i, layer + 1);
}
}
flag[index] = 0;// De sign
}

// Judge whether pruning is needed
int isCapable(char res[], char max[]) {
int len1 = strlen(res);
int len2 = strlen(max);
int len = len1 < len2 ? len1 : len2;
int i = 0;

for (i = 0; i < len; i++) {
// The number of res is smaller than that of max, so the current recursive path can be cut out
if ((res[i] - '0') < (max[i] - '0')) {
//printf("+++%c %c\n", res[i], max[i]);
return 1;
}
if ((res[i] - '0') > (max[i] - '0')) {
return 0;
}
}
return 0;
}
```

I don't know how to optimize it. I'll see if there's a God who can do it later  Published 76 original articles, won praise 8, visited 9044

Posted on Wed, 11 Mar 2020 01:37:37 -0700 by cowboysdude