Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Interesting Yang Hui Triangle
Description Harry is a Junior middle student. He is very interested in the story told by his mathematics teacher about the Yang Hui triangle in the class yesterday. After class he wrote the following numbers to show the triangle our ancestor studied.
He found many interesting things in the above triangle. It is symmetrical, and the first and the last numbers on each line is 1; there are exactly Then Harry studied the elements on every line deeply. Of course, his study is comprehensive. Now he wanted to count the number of elements which are the multiple of 3 on each line. He found that the numbers of elements which are the multiple of 3 on line 2, 3, 4, 5, 6, 7, … are 0, 0, 2, 1, 0, 4, … So the numbers of elements which are not divided by 3 are 2, 3, 2, 4, 6, 3, …, respectively. But he also found that it was not an easy job to do so with the number of lines increasing. Furthermore, he is not satisfied with the research on the numbers divided only by 3. So he asked you, an erudite expert, to offer him help. Your kind help would be highly appreciated by him. Since the result may be very large and rather difficult to compute, you only need to tell Harry the last four digits of the result. Input There are multiple test cases in the input file. Each test case contains two numbers
Output For each test case, output the last four digits of the number of elements on the Sample Input 3 4 3 48 0 0 Sample Output Case 1: 0004 Case 2: 0012 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator