Connection Status:
Competition Arena > ElevenMultiples

ElevenMultiples

TCO12 Round 3B · 2012-03-27 · by rng_58

TCO12 Round 3B · 2012-03-27 · by rng_58 · Dynamic Programming, Math
Class Name: ElevenMultiples
Return Type: int
Method Name: countMultiples
Arg Types: (vector<string>)
Problem Statement

Problem Statement

John and Brus think 4 and 7 are lucky numbers. They think 11, the sum of 4 and 7, is a very lucky number. They decided to make a multiple of 11.

They went to a shop and bought N pieces of strings of digits. You are given String[] pieces containing N elements. The i-th element of pieces is the string of digits written on the i-th piece they bought. They want to make a multiple of 11 by concatenating all N pieces. The pieces are painted with different colors, so it's possible to distinguish two pieces even if they contain the same strings of digits. There are exactly N! ways to concatenate the pieces. How many of them are divisible by 11? Return this number modulo 1,000,000,007.

Constraints

  • pieces will contain between 1 and 50 elements, inclusive.
  • Each element of pieces will contain between 1 and 50 characters, inclusive.
  • Each character in pieces will be a digit ('0'-'9').
  • No element of pieces will start with zero ('0').

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{"58", "2012", "123"}
Returns: 2

There are 6 ways to concatenate the pieces: "582012123", "581232012", "201258123", "201212358", "123582012", and "123201258". Only "582012123" and "201258123" are divisible by 11.

1)
{"1", "1111", "1", "11"}
Returns: 24

There are 24 ways to concatenate the pieces. Even though all of them result in the same number "11111111", they are considered distinct. This number is divisible by 11.

2)
{"43925486943738659795389387498953274"}
Returns: 1

This big number is divisible by 11.

3)
{"983", "4654", "98", "3269", "861", "30981"}
Returns: 96
4)
{"193", "8819", "40676", "97625892", "5719", "45515667", "32598836", "70559374", "38756", "724",
"93391", "942068", "506", "901150", "874", "895567", "7560480", "7427691", "799450", "85127"}
Returns: 537147821

Submissions are judged against all 176 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ElevenMultiples with a public method int countMultiples(vector<string> pieces) · 176 test cases · 2 s / 256 MB per case

Submitting as anonymous