Iqbal Habibie

Greenhorn

Posts: 5

posted 4 years ago

I have an even number 1 to 10 and each number have a frequency that comes up.

example the number 2,4,6,8 then the frequency of each number are 2,1,0,0.It means that we can use up to two digits of 2 and one digit of 4. There are exactly 8 distinct numbers that can be

constructed using the above digits: 2, 4, 22, 24, 42, 224, 242, 422. The sum of all those numbers is 982. but the first line of input contains an integer T (T ≤ 500) denoting the number of testcases. Each testcase contains nine (not four) integers Pi (0 ≤ Pi ≤ 9) denoting the number of i-th digit for i = 1..9.

And the Output For each test case, the output contains a line in the format Case #x: M, where x is the case number (starting from 1) and M is the output in a single line the sum of all possible numbers generated from the available digits. Modulo the output with 1,000,000,007.

I have tried to sum up 1 to 1000. How I settle to the case above?

Code:

example the number 2,4,6,8 then the frequency of each number are 2,1,0,0.It means that we can use up to two digits of 2 and one digit of 4. There are exactly 8 distinct numbers that can be

constructed using the above digits: 2, 4, 22, 24, 42, 224, 242, 422. The sum of all those numbers is 982. but the first line of input contains an integer T (T ≤ 500) denoting the number of testcases. Each testcase contains nine (not four) integers Pi (0 ≤ Pi ≤ 9) denoting the number of i-th digit for i = 1..9.

And the Output For each test case, the output contains a line in the format Case #x: M, where x is the case number (starting from 1) and M is the output in a single line the sum of all possible numbers generated from the available digits. Modulo the output with 1,000,000,007.

I have tried to sum up 1 to 1000. How I settle to the case above?

Code:

Piet Souris

Master Rancher

Posts: 2044

75

posted 4 years ago

Alway a wise advise, the question how an OP would do it by hand. And I am curious to what OP

will come up with.

But having read three times OP's question, I must admit: that's not a trivial question!

It is certainly very different from the sum that OP does in his code.

The problem being equal to: you have a collection containing k white marbles, m red, n yellow, p green, ...

Then form every possible subcollection from these marbles, where wwgw is different from wgww,

value each marble according to the place where it is in the subcollection, and then find the total sum

of all these subcollections (again, if I understand OP correctly).

Not trivial at all. And something tells me that there must be a formula that calculates, at once, the

required sums, given the frequencies. But what that formula should be, I have, as yet, no clue.

Interesting!

Greetz,

Piet

will come up with.

But having read three times OP's question, I must admit: that's not a trivial question!

It is certainly very different from the sum that OP does in his code.

The problem being equal to: you have a collection containing k white marbles, m red, n yellow, p green, ...

Then form every possible subcollection from these marbles, where wwgw is different from wgww,

value each marble according to the place where it is in the subcollection, and then find the total sum

of all these subcollections (again, if I understand OP correctly).

Not trivial at all. And something tells me that there must be a formula that calculates, at once, the

required sums, given the frequencies. But what that formula should be, I have, as yet, no clue.

Interesting!

Greetz,

Piet

Sresh Rangi

Ranch Hand

Posts: 54

5

posted 4 years ago

The constraints are too high to be adding individual values together. You want to rewrite the sum to use multiplication and factorials where possible.

Take your example, you want to calculate: 2 + 4 + 22 + 24 + 42 + 224 + 242 + 422

This is the sum of numbers of length 1, 2, 3. Take the ones of length 3 for example:

224 + 242 + 422

Break it into hundreds, tens, and units:

(2*100 + 2*10 + 4*1) + (2*100 + 4*10 + 2*1) + (4*100 + 2*10 + 2*1)

and regroup the values:

(2*2*100 + 4*1*100) + (2*2*10 + 4*1*10) + (2*2*1 + 4*1*1)

(2*2*100 + 2*2*10 + 2*2*1) + (4*1*100 + 4*1*10 + 4*1*1)

2*2*(100+10+1) + 4*1*(100+10+1)

So the digit '2' in the 3 digit numbers contributes a value to the total equal to: 2 * 2 * ((10^3 - 1) / 9)

The first '2' is the digit, the second is the number of combinations of possible digits remaining after using the '2', and '3' is the number of digits.

So there's a subproblem here: Calculate the number of combinations possible after removing a digit. This should be easier than the original problem but it's still not obvious. I suspect something based on binomial coefficients or the inclusion/exclusion principle should do it (all possibilities minus the union of possibilities that violate the constraints for each digit).

Do you have a link to the testcases or the original problem?

Take your example, you want to calculate: 2 + 4 + 22 + 24 + 42 + 224 + 242 + 422

This is the sum of numbers of length 1, 2, 3. Take the ones of length 3 for example:

224 + 242 + 422

Break it into hundreds, tens, and units:

(2*100 + 2*10 + 4*1) + (2*100 + 4*10 + 2*1) + (4*100 + 2*10 + 2*1)

and regroup the values:

(2*2*100 + 4*1*100) + (2*2*10 + 4*1*10) + (2*2*1 + 4*1*1)

(2*2*100 + 2*2*10 + 2*2*1) + (4*1*100 + 4*1*10 + 4*1*1)

2*2*(100+10+1) + 4*1*(100+10+1)

So the digit '2' in the 3 digit numbers contributes a value to the total equal to: 2 * 2 * ((10^3 - 1) / 9)

The first '2' is the digit, the second is the number of combinations of possible digits remaining after using the '2', and '3' is the number of digits.

So there's a subproblem here: Calculate the number of combinations possible after removing a digit. This should be easier than the original problem but it's still not obvious. I suspect something based on binomial coefficients or the inclusion/exclusion principle should do it (all possibilities minus the union of possibilities that violate the constraints for each digit).

Do you have a link to the testcases or the original problem?

Sresh Rangi

Ranch Hand

Posts: 54

5

Iqbal Habibie

Greenhorn

Posts: 5

posted 4 years ago

I have try improving from above to this,but i am confuse :

1). Each case add number if you choose a number, example below i choose 2,4,22,24,42,224,242,422 then i sumup but i don't get into loop of the case. if i input sample Input:3,the ouput should like Case#1:982;then sample Input : 0 2 0 1 0 0 0 0 0 ,the ouput should like Case#2:2

2). How i add the Modulo 1,000,000,007?

Here's my code

The output :

Enter the size of the input you want to enter: 8

Enter 8 numbers: 2 4 22 24 42 224 242 422

Output 500 times

Digits Frequency

0 0

1 91

2 85

3 73

4 85

5 77

6 89

7 0

8 0

9 0

The sum of the numbers is: 982BUILD SUCCESSFUL (total time: 20 seconds)

1). Each case add number if you choose a number, example below i choose 2,4,22,24,42,224,242,422 then i sumup but i don't get into loop of the case. if i input sample Input:3,the ouput should like Case#1:982;then sample Input : 0 2 0 1 0 0 0 0 0 ,the ouput should like Case#2:2

2). How i add the Modulo 1,000,000,007?

Here's my code

The output :

Enter the size of the input you want to enter: 8

Enter 8 numbers: 2 4 22 24 42 224 242 422

Output 500 times

Digits Frequency

0 0

1 91

2 85

3 73

4 85

5 77

6 89

7 0

8 0

9 0

The sum of the numbers is: 982BUILD SUCCESSFUL (total time: 20 seconds)

Campbell Ritchie

Marshal

Posts: 56562

172

Iqbal Habibie

Greenhorn

Posts: 5

Campbell Ritchie

Marshal

Posts: 56562

172