We will do semi-brute force in here. We will keep an array of sums, where A[i] shows the number of elements which has a sum of it's digit equal to i. In the input we get a number which we will call 2n because it is always even. So we need to calculate the number of elements in which the sum of the first n digits equals to the sum of the second n digits. We need to look over all the tickets of size n ( the total number will be 10^n which is 10^4 on the worst case) and increase the corresponding sum in the array A by 1 in other words, we loop over all the numbers from 000...00 (n times) to 99...99( n times) and calculate the sum of digits suppose it is S, and increment A[S] by 1. Then loop over all the tickets from 00..000 ti 99...99 and calculate every time the sum of digits again (this can be considered as taking the current ticket as the first half and seeing how many other sequences there are that have the same sum of digits) and add the corresponding answer from A[] to our final answer.
No comments:
Post a Comment