SumCards
TCO18 Poland · 2018-04-20 · by lg5293
Problem Statement
You are given n cards. For each i, card i has the number a[i] written on one side and the number b[i] written on the other. These numbers will be positive integers without leading zeros.
You are going to place all n cards onto a table. For each card, you can choose which side is facing up. Then, you will arrange all cards into a row, forming one large number as the concatenation of the numbers written on the individual cards. Out of all possible orders of cards, you will always choose one that produces the smallest final number.
There are 2^n ways to flip the cards when placing them onto the table, hence there are 2^n (not necessarily distinct) numbers you can make. Find the sum of these 2^n numbers, modulo 10^9 + 7.
Constraints
- n will be between 1 and 100.
- a, b will have exactly n elements.
- Each element of a and b will contain between 1 and 30 characters, inclusive.
- Each character of each element of a and b will be between '0' and '9'.
- Each side of each card will represent a positive integer without leading zeros.
{"1", "2"}
{"2", "1"}
Returns: 57
Here we have two cards. Card 0 has "1" on one side and "2" on the other. Card 1 has "2" on one side and "1" on the other. We can place these cards onto the table in four ways. (The first item is always the number seen on card 0, the second one is the number on card 1.) "1", "2" -> Minimum number is "12" "1", "1" -> Minimum number is "11" "2", "1" -> Minimum number is "12" "2", "2" -> Minimum number is "22" The sum of the four minimum numbers is 57.
{"123","32","2"}
{"4","321","53"}
Returns: 15300403
The numbers can have different numbers of digits. Here, there are 2^3 different scenarios. In one of those scenarios we get "4" from card 0, "321" from card 1, and "2" from card 2. Then, we arrange these into the number "23214".
{"999999999999999999999999999999"}
{"999999999999999999999999999999"}
Returns: 999314005
These numbers can be very long. Don't forget about the modulo.
{"20"}
{"18"}
Returns: 38
{"587442411746014",
"7391939024138512",
"50980017755152835",
"488662892723915792",
"7026824218386174856",
"52371452738503046620",
"7317861954444022766",
"923007240569260396",
"40394883764710929",
"2944922081700832"}
{"337900896168224",
"1680756932473764",
"60195764231473580",
"492449859170499416",
"3439143338368292504",
"63371534035998249791",
"2992684350669004880",
"254375621668899054",
"64240381324840589",
"6750847231270874"}
Returns: 198073141
Submissions are judged against all 19 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SumCards with a public method int findsum(vector<string> a, vector<string> b) · 19 test cases · 2 s / 256 MB per case