10905 - Children's Game

[shamim]

here is one i was getting wrong initially,
90 9 should be 990.

By the way, this problem can be solved by clever sorting.

[wook]

some random tests


input:

Code: Select all

30
53 206 12 9 3271 17 1 18 2319 9 17445 1813 7486 530 2 6 3 207 484 5 15 2211 214 91 22 33 10163 27690 26267 831 
26
17 20 20345 1715 141 2 241 6 10901 9 1382 13813 681 181 1784 31727 4405 1445 84 520 114 2285 22 30330 10 235 
12
10 5934 2289 30363 45 232 10 1734 160 1206 1029 1244 
8
210 42 18 134 1373 2253 429 1102 
18
8 46 16 826 2067 7593 1991 20 12 1437 7 129 31795 29076 11098 956 329 77 
30
1192 7 32282 19 6 17 43 210 235 203 194 18 9354 6 52 4 3520 31 1639 20093 170 16 17261 667 2028 11 2346 1226 1553 364 
43
17817 16055 968 58 232 11 2015 484 76 9 31469 1435 2 41 98 199 2269 11 87 212 7946 124 4918 72 14 2393 328 9 19 6162 14 10554 8218 15240 216 19250 862 4 66 4 67 98 1 
5
163 21817 528 1905 185 
3
2299 1 896 
46
19 2249 1363 13 12 7 17167 5 57 1229 11 191 31067 25217 17549 2078 2031 2366 67 883 11802 16 19 362 48 10395 416 1997 12 141 5 6 19746 6 7 19 25100 1425 13968 24779 21778 611 1 3 722 154 
20
44 119 31148 1919 7 119 31 13 639 29532 246 4962 168 6813 23431 1373 2 218 14 894 
43
2179 21443 2072 2680 15565 20694 18 31590 11 19 61 4302 16855 69 27381 13 212 87 1966 73 2623 140 24162 141 29700 141 2214 12 152 547 16 25766 687 221 1596 19 626 4 18 32339 22076 13368 2 
31
19 8 17098 4 2076 269 693 6 159 16966 27875 6019 1892 7 172 236 1973 2003 10 27 9717 11 194 6 22 450 1952 9393 2357 45 8030 
23
173 13 181 48 19 1317 674 17 1220 1242 20 26045 1171 30 5887 2187 1425 15767 2385 2 14 8 2266 
38
28987 16848 151 29201 1593 208 18 20693 11 5 78 122 24025 125 1 28484 142 7 20 628 58 182 15641 21226 172 245 20 19 888 201 23544 49 27984 18 16 4 338 17 
3
14 232 16870 
27
4839 1857 1839 119 7 17 6 30 172 2 13 3333 7 19 6 1352 18552 23362 7 96 20 9 6 6 82 17 27291 
49
7 12 8 140 803 16 2004 1726 21212 86 2712 86 1068 811 2141 63 167 16 19 27639 222 3 22672 52 176 7 26439 737 6425 14200 20079 4 838 13 684 19133 202 22836 20250 161 13835 2 6 17 222 31936 18 346 19 
31
342 14 144 14 588 14 20899 17314 8 1249 20372 30038 28 24 29207 227 15 18 17447 164 1304 10 3 441 1 8376 5292 136 23650 13673 122 
2
5 8 
0

output:

Code: Select all

999183174866553530484333327127690262672319222221121420720618181317445171512110163
98468165204405317273033024123522852222034520181178417171514451411382138131141090110
59344530363232228917341601244120610291010
4294222532101813731341102
9568826777759346329317952907620672019911614371291211098
9354766766524433643520322823123523462102032028200931941918172611717016391615531226119211
999898968878628218794676726766616258491848444413283146923932322269221621220151991925019178171605515240143514141241111110554
528218171905185163
89622991
883777226766611575548416362331067252172510024779236622492177820782031199719746191919191175491716716154142514113968136313122912121180211110395
89476813639496244313114829532246234312218191916814137313119119
8773696876266154744302323393159029700273812680262325766241622221422122076217921443212207220694196619191818168551615961556515214114114013368131211
971793938803076936660194545042787527269236235722207620031973195219419189217217098169661591110
86745887483026045238522662218720191811731715767142514131713124212201171
88878762858549433829201289872848427984245240252354421226208206932020201191821818172171684816159315641151142125122111
2321687014
996827776666483933333027291233622201918571855218391721717135213119
88686838811803777376846642563524346331936276392712264392283622672222222221412121220250202200792004191919133181761726171671616161142001401383513121068
883765885292441342330038292072824236502272089920372181744717314164151441414141367313613041249122110
85

in addition, since this time,

if the problem about which you are going to post has already posted in this forum, please use it![/code]


some tricky:

Code: Select all

5
1 12 123 1234 12345
7
9 98 987 9876 98765 987654 9876543
6
9 900 9 90 9 9
1
24187
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
5
1 11 111 1111 11111
6
9 88 777 6666 55555 444444
0

right answer:

Code: Select all

123451234123121
9989879876987659876549876543
999990900
24187
9876543220191817161514131211110
111111111111111
988777666655555444444

[gmds]

I,ve searched the Board,some body said using dp,and some said "clever sorting"(I guess that's using greedy method), but I need more clue....

I think Dp or greedy are both OK,but I don't know how to.
thank you.

[david]

The idea is actually very intuitive. In fact when I wrote my solution, I didn't think of any justification, but if you are interested there is one in the last paragraph.

Let "++" stand for the operation of concatenation of strings.
If you put string "a" after (but not neccesarily next to) string "b", but a ++ b is lexicographically larger than b ++ a, then exchanging them would yield a greater number. So no such pair will be in the final solution.

(The same reasoning also shows that the relation "a R b iff a ++ b > b ++ a" is indeed an order relation, since if we have three strings a, b and c,
one of the permutations abc, acb, bca... must be the lexicographically largest, which by the remark above wouldn't be possible if R weren't transitive. This allows us to use any comparison-based sorting algorithm)

[gmds]

thank you,Divid.
what a bright idea! and i am really dull. I once thought the comparison should be based on sets(the string I've already got,i mean),but I could'nt go further...
thanks a lot.

[ImLazy]

I think the main point of this problem is this input:
2
345 3453453453453453
2
345 3453453453453454
0

The output should be
3453453453453453453
3453453453453454345

i.e. there may be two numbers which are X and XXXXXy.(X has several digits, y is one digit). So you should compare y and the first digit of X.
Although I use this method to get AC, after reading David's algorithm, I have to confess my method is really dull.

[georgemouse]

I've tried all the inputs listed before but still can't find where is wrong.
I am very confused .
Can someone help me?
Thanks a lot!!!!

My method is to find the order that makes the number combination bigger (the function compare)
,and then use bubble sort.

Code: Select all

 removed after AC

[misof]

Try increasing the array size, maybe there are inputs with more than 20 digit numbers.

Next time if there is already a thread about a problem, use it, don't start a new one.

[georgemouse]

Thank you for your help, misof!!

But I still got WA after increasing the array size.

Could someone tell me where is wrong??

My method is to find the order that makes the number combination bigger (the function compare)
,and then use bubble sort.

Code: Select all

 removed after AC

[misof]

input:

Code: Select all

2
9909 990
5
991 9909 99 990 989
0

correct output:

Code: Select all

9909990
999919909990989

[SRX]

hi ...........

if(n==yl)
{
for(t=0;n<xl;n++,t++)
if(x[0+t]<x[n]) return 1;
else if(x[0+t]==x[n]) continue;
else return 0;
return 1 ;
}

[georgemouse]

Now I have accepted.
Thank you very much, misof and SRX!!
Best wishes,

[Niaz]

What will be the output for this input
3
0 0 0

Thanks in advance.

[misof]

This is an invalid input, the integers have to be positive.

Check the other thread(s) on this problem if you are getting WA.

[Niaz]

I am getting WA again and again ! I cant figure out where is actually my mistake. Would you plz give me some tricky input and output, so that I can find my fault ?