COOLNUMS - Cool Numbers

no tags 

Cool numbers are those, whose digits can be partitioned into two sets such that the sum of the digits in either sets are equal.
Example: 23450 is cool because 3+4+0 = 2+5; So is 91125;
The numbers 567, 34523 are not cool, since there is no such digit partition.

Write a program that prints the number of cool numbers in the inclusive range [A,B].


Input Format:
The input file consists of multiple testcases.
Each case contains one line containing two 32-bit unsigned integers A and B. (1 <= A <= B <= 4*109).
Input terminates with a line containing two zeros and must not be processed.

Output Format:
For each testcase print a single line containing one integer saying the number of cool numbers between A and B, inclusive.

Sample Input:
1 11
12 20
1 20
3 100
6354 234363
123456789 234567891
0 0
Sample Output:
1
0
1
9
82340
54801678

Test Data:
About 50 testcases.


hide comments
cuman: 2023-09-12 16:44:06

I've found an even cooler approach. just store the whole knapsack array in the dp state (not sure why this doesn't TLE)

lftroq: 2023-08-26 10:02:52

I've found a cool approach on codeforces. Keep in mind the 50KB source limit

thuylinhcbhk64: 2023-08-11 04:57:07

can someone help me the solution ... =))

ak2006: 2021-06-13 07:38:35

Yes 4e9 fits into a 32-bit unsigned integer

Last edit: 2021-06-13 07:40:13
jeroenodb: 2021-06-13 02:17:10

2**32 is a little bigger than 4*10^9, so it just fits.

Ricardo Oliveira [UFPR]: 2013-02-26 14:21:17

4*10^9 does not fit in a 32-bit UNsigned integer, right?


Added by:Prasanna
Date:2007-10-08
Time limit:5.673s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:NITT ACM ICPC Local Contest 2007 [Topcoder problem with Constraints raised]