If we represent a date in the format YYYY-MM-DD (for example, 2017-04-09), do you know how many 9s will appear in all the dates between Y1-M1-D1 and Y2-M2-D2 (both inclusive)?
Note that you should take leap years into consideration. A leap year is a year which can be divided by 400 or can be divided by 4 but can't be divided by 100.
Input
The first line of the input is an integer T (1 ≤ T ≤ 105), indicating the number of test cases. Then T test cases follow. For each test case:
The first and only line contains six integers Y1, M1, D1, Y2, M2, D2, their meanings are described above.
It's guaranteed that Y1-M1-D1 is not larger than Y2-M2-D2. Both Y1-M1-D1 and Y2-M2-D2are between 2000-01-01 and 9999-12-31, and both dates are valid.
We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.
<h4< dd="">Output
For each test case, you should output one line containing one integer, indicating the answer of this test case.
<h4< dd="">Sample Input
4
2017 04 09 2017 05 09
2100 02 01 2100 03 01
9996 02 01 9996 03 01
2000 01 01 9999 12 31
<h4< dd="">Sample Output
4
2
93
1763534
<h4< dd="">Hint
For the first test case, four 9s appear in all the dates between 2017-04-09 and 2017-05-09. They are: 2017-04-09 (one 9), 2017-04-19 (one 9), 2017-04-29 (one 9), and 2017-05-09 (one 9).
For the second test case, as year 2100 is not a leap year, only two 9s appear in all the dates between 2100-02-01 and 2100-03-01. They are: 2017-02-09 (one 9) and 2017-02-19 (one 9).
For the third test case, at least three 9s appear in each date between 9996-02-01 and 9996-03-01. Also, there are three additional nines, namely 9996-02-09 (one 9), 9996-02-19 (one 9) and 9996-02-29 (one 9). So the answer is 3 × 30 + 3 = 93.
这题一开始打算暴力模拟过去 结果写着写着不对劲了
后面扔给专门写模拟的队友写了
暴力打表过的
这样好写多了
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <vector>
#define pi acos(-1.0)
#define eps 1e-6
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define bug printf("******\n")
#define mem(a,b) memset(a,b,sizeof(a))
#define fuck(x) cout<<"["<<x<<"]"<<endl
#define f(a) a*a
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
#define pf printf
#define FRE(i,a,b) for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b) for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define FIN freopen("DATA.txt","r",stdin)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) x&-x
#pragma comment (linker,"/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 0x7fffffff;
const int mod = 1e9 + ;
const int maxn = 1e6 + ;
int a[] = {, , , , , , , , , , , };
int check(int x) {
if ((x % ) == || (x % == && x % != )) return ;
return ;
}
int get9(int x) {
int ans = ;
while(x) {
int cnt = x % ;
if (cnt == ) ans++;
x /= ;
}
return ans;
}
int ans[][][];
int main() {
int year = , yue = , day = , cnt = , ret;
while(year < ) {
yue = ;
while(yue <= ) {
day = ;
if (yue == && check(year)) ret = a[yue - ] + ;
else ret = a[yue - ];
while(day <= ret ) {
int temp = get9(year) + get9(yue) + get9(day);
ans[year][yue][day] = cnt + temp;
cnt = ans[year][yue][day];
day++;
}
yue++;
}
year++;
}
int n, v1, m1, d1, v2, m2, d2;
sf(n);
for (int i = ; i < n ; i++) {
sfff(v1, m1, d1);
sfff(v2, m2, d2);
printf("%d\n", ans[v2][m2][d2] - ans[v1][m1][d1] + get9(v1) + get9(m1) + get9(d1));
}
return ;
}