Weight of Numbers

Problem code: WEIGHT

All submissions for this problem are available.

Statement

Let us denote an n digit decimal number by a1a2a3...an with the condition that each ai should be between 0 and 9 inclusive except a1 which should be between 1 and 9 inclusive. The weight of such a number is defined as the sum of absolute difference between adjacent numbers. Precisely the weight can be defined as,

	weight = 0
	For i = 1 to n-1
  		weight = weight + ABS(ai+1 - ai)
Here ABS is the absolute value of the argument.
Given n and a weight w, find all the n digit numbers having a weight w. Since the answer could be very large, print the answer modulo 1000007.

Input Format:


The first line contains one integer t, the number of testcases. (1 <= t <= 150)
This will be followed by t lines each consisting of numbers n and w.

Constraints:


  • 2 <= n <= 20
  • 0 <= w <= 200

Output Format:


For each test case print the answer modulo 1000007 in a separate line.

Sample Input:


2
10 0
2 1

Sample Output:


9
17
Date: 2010-09-10
Time limit: 2s
Source limit: 50000
Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS


Comments

Can you please

occams_razor @ 24 Sep 2010 09:49 PM

Can you please clarify

"Given n and a weight w, find all the n digit numbers having a weight w. Since the answer could be very large, print the answer modulo 1000007."

so the answer is all the possible numbers.. each number modulo 1000007..

but the sample shows only one number per test case

@Occam's Razor: The answer is

harsha_adm @ 24 Sep 2010 09:52 PM

@Occam's Razor: The answer is the total count of possible numbers.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions