## 986 - How Many?

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

### 986 - How Many?

Code: Select all

``````hi,

I don``````
form kisui na ... class tai asol....
iF U hv d class u get the form....

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Code: Select all

``````  /\
/    \/\

/\
/\/    \``````
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU
I too really confused about the problem ?? can u pls explain ?

Thanks in advance
Time that gone is gone forever ...

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Explain of (3, 1, 2):

There are five kind of mountains for n = 3.

Code: Select all

``````                                      /\
/\         /\     /\/\    /  \
/\/\/\    /  \/\   /\/  \   /    \  /    \
``````
1st mountain has 3 peek of height 1, 0 peek of height 2, 0 peek of height 3.
2nd and 3rd mountain has 1 peek of height 1, 1 peek of height 2, 0 peek of height 3.
4th mountain has 0 peek of height 1, 2 peek of height 2, 0 peek of height 3.
5th mountain has 0 peek of height 1, 0 peek of height 2, 1 peek of height 3.

So the number of mountains that has exactly r = 1 peek of height k = 2 is 2 (2nd and 3rd).

Other examples of n = 3.
(3, 0, 2) = 2 (1st and 5th)
(3. 0, 1) = 2 (4th and 5th)
(3, 2, 1) = 0 (none)
(3, 1, 3) = 1 (5th)
(3, 0, 4) = 5 (all)
(3, 1, 4) = 0 (none)

I hope this helps.
----
Sory for my poor English.

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU
Thanks buddy.... Now i can give a try
Time that gone is gone forever ...

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:
Is there any DP solution or anything......
form kisui na ... class tai asol....
iF U hv d class u get the form....

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### dp

Yes, this is a dp problem.

I basically optimized dp[x][y][p][a]..
..ie how many ways I can come to coordinate x,y with p peaks and 'a' indicates last move(down hill or uphill ).

So ultimately the required answer is dp[2*N][0][R][0] // 0 -> downhill

predicate
New poster
Posts: 18
Joined: Tue Jun 17, 2014 9:32 pm
Location: Hyderabad, India

### Re: 986 - How Many?

some random test cases for debugging:
input :

Code: Select all

``````3 1 2
10 3 2
10 5 4
20 5 4
20 1 2
20 0 1
``````
output :

Code: Select all

``````2
2002
69
282172814
1767263190
2892818244
``````