HDU 5062 Beautiful Palindrome Number——BestCoder Round #13
3115 ワード
Beautiful Palindrome Number
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
A positive integer x can represent as
(a1a2…akak…a2a1)10 or
(a1a2…ak−1akak−1…a2a1)10 of a 10-based notational system, we always call x is a Palindrome Number. If it satisfies
0Now, we want to know how many Beautiful Palindrome Numbers are between 1 and
10N .
Input
The first line in the input file is an integer
T(1≤T≤7) , indicating the number of test cases.
Then T lines follow, each line represent an integer
N(0≤N≤6) .
Output
For each test case, output the number of Beautiful Palindrome Number.
Sample Input
Sample Output
Source
BestCoder Round #13
/****************************************************/
出題者の解題構想:
作り方1.数字の長さは
L\leq 18L≤18
のBeautiful Palindrome Number有
C^9_{(L+1)/2}C(L+1)/29
はい、それで時計を打てばいいです.たとえば長さ3のBeautiful Palindrome Numberの数は、1～9から2つの数字を選択します
C^9_2C29
. やり方2.暴力は数字ごとに満足しているかどうかを判断する.
n<1000000n<1000000
. 作り方3.手で計算してみると、一番大きいのはすでに与えられているからです.
标题:定義xは1つの美しい回文数であり、現在xが(a 1 a 2...akak...a 2 a 1)10または(a 1 a 2...ak−1 akak−1...a 2 a 1)10の十進法形式として表すことができる場合にのみ、0问题解决的想法:本题的N比较小,因为这上最大的情况也已经在样本中出现,所以我们先寻求7种情况应对应的结果,如此寻问时的复杂度是O(n)。2 k比特数与2 k-1比特数相同,例如N=1有1~9,N=2,11,22,33,44,55,66,77,88,99的9种美丽的回文数。然后知道N=6美丽的回文数,所以只能算出N=3的全部情况。N=3的情况下,x形为a 1 a 2 a 1,a 1=1の場合、a 2は8種類ある。a 1=2の場合、a 2には7つのケースがある。顺序類推すると、a 1=8の場合、a 2に1の場合がある。合計8+7+…+1=(8+1)*8/2=36の場合、N 1 2 3 4 5 6 Num 9 9+9 9+9+36 9+9+36+36 9+9+36+36+84 9+9+36+36+84+84 9 18 54 90 174 258或者N=0的情况下没有忘记,结果是1的#pragma comment(linker,"/STOCK:102400000 102400000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #include<stack> #include<math.h> #include<vector> #include<map> #include<set> #include<stdlib.h> #include<cmath> #include<string> #include<algorithm> #include<iostream> #define exp 1e-10 using namespace std; const int N = 105; const int inf = 2147483647; const int mod = 2009; int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); switch(n) { case 0:puts("1");break; case 1:puts("9");break; case 2:puts("18");break; case 3:puts("54");break; case 4:puts("90");break; case 5:puts("174");break; case 6:puts("258"); } } return 0; }菜鳥成長記
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
A positive integer x can represent as
(a1a2…akak…a2a1)10 or
(a1a2…ak−1akak−1…a2a1)10 of a 10-based notational system, we always call x is a Palindrome Number. If it satisfies
0
10N .
Input
The first line in the input file is an integer
T(1≤T≤7) , indicating the number of test cases.
Then T lines follow, each line represent an integer
N(0≤N≤6) .
Output
For each test case, output the number of Beautiful Palindrome Number.
Sample Input
2
1
6
Sample Output
9
258
Source
BestCoder Round #13
/****************************************************/
出題者の解題構想:
作り方1.数字の長さは
L\leq 18L≤18
のBeautiful Palindrome Number有
C^9_{(L+1)/2}C(L+1)/29
はい、それで時計を打てばいいです.たとえば長さ3のBeautiful Palindrome Numberの数は、1～9から2つの数字を選択します
C^9_2C29
. やり方2.暴力は数字ごとに満足しているかどうかを判断する.
n<1000000n<1000000
. 作り方3.手で計算してみると、一番大きいのはすでに与えられているからです.
标题:定義xは1つの美しい回文数であり、現在xが(a 1 a 2...akak...a 2 a 1)10または(a 1 a 2...ak−1 akak−1...a 2 a 1)10の十進法形式として表すことができる場合にのみ、0问题解决的想法:本题的N比较小,因为这上最大的情况也已经在样本中出现,所以我们先寻求7种情况应对应的结果,如此寻问时的复杂度是O(n)。2 k比特数与2 k-1比特数相同,例如N=1有1~9,N=2,11,22,33,44,55,66,77,88,99的9种美丽的回文数。然后知道N=6美丽的回文数,所以只能算出N=3的全部情况。N=3的情况下,x形为a 1 a 2 a 1,a 1=1の場合、a 2は8種類ある。a 1=2の場合、a 2には7つのケースがある。顺序類推すると、a 1=8の場合、a 2に1の場合がある。合計8+7+…+1=(8+1)*8/2=36の場合、N 1 2 3 4 5 6 Num 9 9+9 9+9+36 9+9+36+36 9+9+36+36+84 9+9+36+36+84+84 9 18 54 90 174 258或者N=0的情况下没有忘记,结果是1的#pragma comment(linker,"/STOCK:102400000 102400000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #include<stack> #include<math.h> #include<vector> #include<map> #include<set> #include<stdlib.h> #include<cmath> #include<string> #include<algorithm> #include<iostream> #define exp 1e-10 using namespace std; const int N = 105; const int inf = 2147483647; const int mod = 2009; int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); switch(n) { case 0:puts("1");break; case 1:puts("9");break; case 2:puts("18");break; case 3:puts("54");break; case 4:puts("90");break; case 5:puts("174");break; case 6:puts("258"); } } return 0; }菜鳥成長記