Question

Python Algorithm Coding

There are N paper with three letters written on each paper. Characters are 0 to 9 digits or *.You can create a continuous number by attaching the paper in a proper order. Print out the maximum number of digits sum of a sequence of numbers that can be made when N paper is given.

For example, suppose you have a piece of paper with a lettering as shown below.

3 45

In this case, the consecutive numbers of strings that can be created are as follows:  

12, 126, 12345, 123456, 345, 3456, 6

The largest sum of each number of these is 123456, so the answer is 21. (1+2+3+4+5+6) (additionally, when 723521 & 72358 > the answer is 72358)

[Constraint]

1. The number N of paper is not more than 1,000. (1 ≤ N ≤ 1,000)

[Input]

The first line of input gives the total number of test cases T.

From the next line, each test case is given, and the first row is given the number N of paper.

The next line is given three letters written on N paper.

[Output]

The results for test case T are taken "#T" and output the maximum value of the digit agreement among the single space and consecutive numbers.

(T refers to the number of the test case and starts at 1.)

sample input

5
4
*15
7**
402
**3
6
**1
7**
567
24*
8**
234
8
16*
9*8
*24
52*
3*1
532
4*4
111
4
*12
121
*9*
1**
6
7*8
8*9
111
**8
8**
276

sample output

#1 19
#2 36
#3 28
#4 9
#5 35

Answer 1

---------------------------------------------------------------------------------------------------------

// Screenshots of Python Code

def max(a,b): if(aくb); return b 1 return a 4 namemain" t - int(input()) for i in range(t): # get the Number of papers n - int(input()) 8 9 10 papers [] # Assumption :-the input characters are either numbers from '0' to '9' or for j in range (n): s-input() 12 13 14 15 papers.append (s) 16 0 Sum # find the sum of digits of numbers in which there is no for elem in papers: 17 18 if(elem[] !* and elem[1]and elem[2]*'): sum int(elem[ ]) sum int(elem[1]) sum +- int(elem[2]) 19 20 21 23 # finding the maximum among the numbers where "*' occurs at the start but not the end forwardMaxSum0 24 25 curSum 26 for elem in papers: 27 if(elem[2] 1 * and elem]*): curSum- int(elem[2]) if(elem[1] ! curSum int (elem[1]) if(forwardMaxSum < curSum): forwardMaxsum cursum 28 29 30 31 32 34 35

36 # find the maximum among the numbers where .*. occurs at the end but not the start backwardMaxSume 37 38 for elem in papers: if(elem[]and elem[2]): curSum int(elem[]) if(elem1]: curSum-int(elem[1]) if(backwardMaxSum < curSum): 40 42 43 45 backwardMaxSumcurSum 46 # find the maximum among the number where '*. occurs both at the start and end 47 middleMaxsum = 0 48 49 for elem in papers: if(elem[e] =- '*. and elem[2]ー.*. if(middleMaxsum < ǐnt(elem[1])); middleMaxSumint (elem[1]) and elem[1] !'*'): 51 52 53 # find those elements where . occurs in the middle but not at the start and end 54 dict -{ for elem in papers: 56 if(elem[0] !-.*. and elem[1]--'*, and elem[2] != '*'): dict[elem] [] # first index contains digit that would be appended at the back dict[elem.append (int(elem[e])) # second index contains digit that would be appended at the front dict[elem].appen(int(elem[2])) 57 58 59 60 61 62 63 64 65 67

67 # Let us call the elements where occurs ONLY in the middle as .Middlestar' 68 # Let us call the elements where . occurs in the start but not at the end as 'Forwardstar . 69 # Let us call the elements where . occurs in the end but not at the start as 'Backwardstar. 70 71 # There are 4 subcases here : 72 # (i) A Forwardstar element occurs in the start and Middlestar occurs in the end 73 backwardMiddlestarSum 0 74 for key in dict.keys): if(backwardMiddlestarSum< dict[key] [0]): backwardMiddleStarSum-dict[key][e] 75 76 78 # (İİ) A Middlestar element occurs in the start and Backwardstar element occurs in the end forwardMiddlestarSum0 80 for key in dict.keys ): if(forwardMiddlestarSum< dict[key][1]): forwardMiddlestarSum -dict[key][1] 81 82 83 84 # (iii) one Middlestar element occurs in the start and a different Middlestar element occurs in the end doubleMiddlestasum0; for ki in dict.keys(): for k2 in dict.keys( 85 86 87 if (k1- k2): if(doubleMiddlestarSumdict[k1][1] + dict[k2] [0]): doubleMiddlestarSum-dict[k1][1] dict[k2][0] 90 91 92 # (IV) A Forwardstar element occurs in the start while Backwardstar element occurs in the end 93 95 candidateSum max (forwardMaxSum+sum+backwardMiddlestarSum,middleMaxSum) candidateSum-max (forwardMiddlestarSum+sum+backwardMaxSum, candidateSum) candidateSum -max (doubleMiddlestarSum+sum,candidateSum) candidateSum-max (forwardMaxSum+sum+backwardMaxSum, candidateSum) 96 97 98 100 print("#"+str(1+1)+" "+stricandidatesun)

---------------------------------------------------------------------------------------------------------

// Screenshot of Outputs

15 402 #1 19 567 248 234 #2 36 168 9*8 824 52 3 *1 532 #3 28 121 #4 9 7*8 849 276 #5 35 Process finished with exit code 0