Page **1** of **1**

### 11472 - Beautiful Numbers

Posted: **Sun Aug 03, 2008 6:19 pm**

by **hamedv**

i think it's a simple DP problem but i'm getting WA

here is my code:

Code: Select all

```
#include <iostream>
using namespace std;
int main()
{
long long dp[11][101][10];
memset(dp, 0, sizeof dp);
for (int i = 0; i < 11; i++)
for (int j = 0; j < 10; j++)
if (j)
dp[i][1][j] = 1;
else
dp[i][1][j] = 0;
for (int base = 2; base <= 10; base++)
for (int len = 2; len <= 100; len++)
for (int lastd = 0; lastd < base; lastd++)
{
if (lastd == 0)
dp[base][len][lastd] = dp[base][len-1][lastd+1];
if (lastd == base-1)
dp[base][len][lastd] = dp[base][len-1][lastd-1];
if (lastd > 0 && lastd < base-1)
dp[base][len][lastd] = (dp[base][len-1][lastd-1] + dp[base][len-1][lastd+1]) % 1000000007;
}
int N, M, t;
cin >> t;
while (t--)
{
cin >> N >> M;
long long ans = 0;
for (int l = 1; l < M; l++)
for (int ld = 0; ld < N; ld++)
ans = (ans + dp[N][l][ld]) % 1000000007;
cout << ans << endl;
}
}
```

### Re: 11472 - Beautiful Numbers

Posted: **Sun Aug 03, 2008 6:27 pm**

by **Robert Gerbicz**

Yes, this is dp, but what is fantastic that it is solvable by recursion, for every B(ase) there is a linear recursion (but this way is a little heavier than the dp). But you send also a precomputed (large) table, because there are 9*101 required numbers and that fits in the 40 Kbyte.

### Re: 11472 - Beautiful Numbers

Posted: **Sun Aug 03, 2008 8:39 pm**

by **hamedv**

yes you are right but can you tell me why i'm getting WA:

mydpfunction(BASE, DIGITS, LASTDIGIT) = number of the beautiful numbers in base BASE which have DIGITS digits and their last digit is LASTDIGIT.

if (LASTDIGIT = 0 and DIGITS = 1)

----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = 0;

if (DIGITS = 1)

----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = 1;

if (LASTDIGIT = 0)

----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = mydpfunction(BASE, DIGITS-1, LASTDIGIT+1);

if (LASTDIGIT = BASE-1)

----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = mydpfunction(BASE, DIGITS-1, LASTDIGIT-1);

if (LASTDIGIT = 1 to BASE-2)

----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = (mydpfunction(BASE, DIGITS-1, LASTDIGIT-1) + mydpfunction(BASE, DIGITS-1, LASTDIGIT-1)) % 1000000007;

Is my implementation wrong?

Please help me...?

### Re: 11472 - Beautiful Numbers

Posted: **Sun Aug 03, 2008 8:58 pm**

by **Leonid**

Code: Select all

```
if (LASTDIGIT = 0 ans DIGITS = 1)
----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = 0;
```

IMHO the problem may be here. Don't assume, that the number 0 can't be used in DIGITS > 1. Since the number 10 is produced by adding 1 to zero.

Once you have found the answer of a particular length. You can iterate the length and sum up all valid states excluding the states where a number begins with 0. I got AC with a different O(2^N * N * M) solution.

### Re: 11472 - Beautiful Numbers

Posted: **Mon Aug 04, 2008 5:33 am**

by **andmej**

Leonid wrote:Code: Select all

```
if (LASTDIGIT = 0 ans DIGITS = 1)
----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = 0;
```

IMHO the problem may be here. Don't assume, that the number 0 can't be used in DIGITS > 1. Since the number 10 is produced by adding 1 to zero.

Once you have found the answer of a particular length. You can iterate the length and sum up all valid states excluding the states where a number begins with 0. I got AC with a different O(2^N * N * M) solution.

I also used an O(2^N * N * M) solution. My state is dp[length][used digits][first digit], where dp

*[j][k] = number of ways to form a number with i digits, such that the first digit is k and j is a bitwise mask indicating which digits I have used. This method took 1 second (slow!) using memoization.*

### Re: 11472 - Beautiful Numbers

Posted: **Mon Aug 04, 2008 8:30 am**

by **hamedv**

Leonid wrote:Code: Select all

```
if (LASTDIGIT = 0 ans DIGITS = 1)
----------- mydpfunction(BASE, DIGITS, LASTDIGIT) = 0;
```

IMHO the problem may be here. Don't assume, that the number 0 can't be used in DIGITS > 1. Since the number 10 is produced by adding 1 to zero.

Once you have found the answer of a particular length. You can iterate the length and sum up all valid states excluding the states where a number begins with 0. I got AC with a different O(2^N * N * M) solution.

It's not ANS. it's AND my function produces 0 if LASTDIGIT = 0 and it is a 1 digit number which there can be only zero.

Please tell me your implementation.

### Re: 11472 - Beautiful Numbers

Posted: **Mon Aug 04, 2008 9:31 am**

by **Leonid**

I keep track of used numbers so far a the first dimension of an array. The other 2 dimensions are length and the last digit. For example 5 (101) means that I used numbers (0 and 2). When I find answers for each length I iterate through (111) values for each length and every digit to the left of the number (except 0, since the number can't start with 0).

### Re: 11472 - Beautiful Numbers

Posted: **Mon Aug 04, 2008 3:38 pm**

by **H_Hima**

hi.

the introduced method was useful but I code a O(N^2 * M) method and this is my code.

but why I got WA.

may anybody send me some testcases in the wrong positions or tell me what is wrong here.

fun2(b,len,ld) : count of numbers in base b with length len and with the last digit ld that all of the digits appears in it.

fun(b,len,ld) : count of numbers in base b with length len and with the last digit ld that all of the digits appears in it and the first digit is not zero.

then I used DP for filling the tables.

this is my code.

Code: Select all

```
deleted after acc with help of hamedv.
```

thanks.

### Re: 11472 - Beautiful Numbers

Posted: **Mon Aug 04, 2008 5:19 pm**

by **hamedv**

Try these:

input:

correct output:

replace this line

by this:

Code: Select all

`tabl[i][j]=(tabl[i][j]+fun(i,j,k))%1000000007;`

### Re: 11472 - Beautiful Numbers

Posted: **Mon Aug 04, 2008 6:20 pm**

by **hamedv**

Leonid wrote:I keep track of used numbers so far a the first dimension of an array. The other 2 dimensions are length and the last digit. For example 5 (101) means that I used numbers (0 and 2). When I find answers for each length I iterate through (111) values for each length and every digit to the left of the number (except 0, since the number can't start with 0).

Thank you!

I misunderstood the problem!

### Re: 11472 - Beautiful Numbers

Posted: **Mon Aug 04, 2008 8:48 pm**

by **H_Hima**

hamedv wrote:Try these:

input:

correct output:

replace this line

by this:

Code: Select all

`tabl[i][j]=(tabl[i][j]+fun(i,j,k))%1000000007;`

Special Thanks Hamedv. what a silly bug.

you exactly found the bug and the code got ACC.

again thanks.

### 11472 - Beautiful Numbers

Posted: **Wed Jul 18, 2012 10:03 am**

by **Blackwizard**

hi...

I've written this code for 11472 but it takes RUNTIME ERROR!

I don't know what is it's reason!!!

please help me to solve this problem... thanks!

here's my code:

Code: Select all

```
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int dp[101][10][1024];
int res;
int main ()
{
memset (dp, 0, sizeof dp);
for (int j = 1; j <= 9; j++)
dp[1][j][1<<j] = 1;
for (int i = 1; i < 101; i++)
for (int j = 0; j < 10; j++)
for (int k = 1; k < 1024; k++)
{
int nx = j+1;
int pr = j-1;
if (nx < 10)
{
res = dp[i+1][nx][k|(1<<nx)];
dp[i+1][nx][k|(1<<nx)] = (res + dp[i][j][k]) % 1000000007;
}
if (pr >= 0)
{
res = dp[i+1][pr][k|(1<<pr)];
dp[i+1][pr][k|(1<<pr)] = (res + dp[i][j][k]) % 1000000007;
}
}
int n, m, t;
cin >> t;
for (; t != 0 && cin >> n >> m; t--)
{
res = 0;
int all = (int)pow (2., n) - 1;
for (int i = n; i <= m; i++)
for (int j = 0; j < n; j++)
res = (res + dp[i][j][all]) % 1000000007;
cout << res << endl;
}
return 0;
}
```

### Re: 11472 - Beautiful Numbers

Posted: **Thu Jul 19, 2012 3:11 am**

by **brianfry713**

Use a debugger with the sample input. On line 23 if i=100 that's a seg fault.

### Re: 11472 - Beautiful Numbers

Posted: **Thu Dec 27, 2012 7:31 pm**

by **gm3t**