BALNUM - Balanced Numbers
Balanced numbers have been used by mathematicians for centuries. A positive integer is considered a balanced number if:
- Every even digit appears an odd number of times in its decimal representation
- Every odd digit appears an even number of times in its decimal representation
For example, 77, 211, 6222 and 112334445555677 are balanced numbers while 351, 21, and 662 are not.
Given an interval [A, B], your task is to find the amount of balanced numbers in [A, B] where both A and B are included.
Input
The first line contains an integer T representing the number of test cases.
A test case consists of two numbers A and B separated by a single space representing the interval. You may assume that 1 <= A <= B <= 1019
Output
For each test case, you need to write a number in a single line: the amount of balanced numbers in the corresponding interval
Example
Input: 2 1 1000 1 9 Output: 147 4
hide comments
shishank_93774:
2023-08-22 20:03:57
MUST TRY https://www.spoj.com/problems/NUMTSN/ before solving this problem.
|
|
spark_7:
2022-01-28 11:01:34
A very interesting problem. |
|
yogeshk972:
2019-08-17 10:31:27
time limit is strict ! A small factor in complexity gave me tle Last edit: 2019-08-17 10:33:55 |
|
[Rampage] Blue.Mary:
2017-08-30 06:54:04
The number of test cases is relatively "small", i.e. there won't be 1000 test cases with 19 digits number. |
|
Satyanveshi_Byomkesh_bakshy:
2014-11-06 22:31:18
awesome problem :) !! |
|
Piyush Kapoor:
2012-05-10 22:11:04
@Buda IM: I completely agree with you ,test cases should be mentioned in the problem description. |
|
Buda IM (retired):
2012-03-30 09:19:05
I think number of test cases should be in problem description. Because you should know whether to do overkill by precalculating all results, or calc solution for each test alone. But usually authors leave out that number .. |
|
Angel Paredes:
2012-02-13 15:41:24
You may assume a thousand. |
|
Saransh Bansal:
2012-02-13 12:49:14
How many test cases are there? |
Added by: | Angel Paredes |
Date: | 2012-02-12 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: PERL6 |
Resource: | Cuban Olympiad in Informatics 2012 - Day 2 Problem A |