Pizza Stack

Kamaldeep is good at making pizzas. Generally he gets requests to serve N pizzas at once. He serves them in the form of a stack. A pizza should be treated as a circular disk with some radius.

Kamaldeep needs to take care that when he places a pizza on the top of the stack the radius of the pizza should not exceed the radius of the largest pizza in the stack by more than 1. Additionally all radii should be positive integers, and the bottom most pizza should have its radius as 1. Kamaldeep is week in maths :P, so he wants you to find out in how many ways can he create a stack containing N pizzas.

Input

First line of the input contains T (T <= 1000) denoting the number of test cases.

T lines follow each containing a single integer N (1 <= N <= 1000) denoting the size of the required stack.

Output

For each case the output should be a single integer representing the number of ways a stack of size N can be created. As

the answer can be large print it modulo 1000000007.

ANS------->

dp[i][j] -> stack size of i with j different value .

dp[i][j] = j*dp[i-1][j] + dp[i-1][j-1];

1. #include <iostream>
2. using namespace std;
3.  
4. int main()
5. {
6. int t ;
7. cin >> t;
9. long long mo = 1000000007;
10.  
11. long long dp[1002][1002];
12. long long top[1002];
14. for(int i=0 ; i < 1002 ; i++)
15. for(int j=0 ; j < 1002 ; j++)
16. dp[i][j]=0;
17.  
18. dp[1][1]=1 ;
19. top[1]=1;
22. for(int i=2 ; i < 1002 ; i++){
23. long long temp = 0 ;
24. for(int j=1; j<=i; j++){
25. dp[i][j]=j*dp[i-1][j]%mo + dp[i-1][j-1]%mo;
26. temp=(temp+dp[i][j])%mo;
27. }
28. top[i]=temp;
29. }
33. while(t--){
35. int val ;
36. cin >> val ;
37. cout << top[val] << endl ;
39. }
41.  
42. return 0;
43. }

Volleyball Match

Tatyana is a big sports fan and she likes volleyball a lot! She writes down the final scores of the game after it has ended in her notebook.

If you are not familiar with the rules of volleyball, here’s a brief:

• 2 teams play in total
• During the course of the game, each team gets points, and thus increases its score by 1.
• The initial score is 0 for both teams.

The game ends when

• One of the teams gets 25 points and another team has < 24 points ( strictly less than 24).
• If the score ties at 24:24, the teams continue to play until the absolute difference between the scores is 2.

Given the final score of a game in the format A:B i.e., the first team has scored Apoints and the second has scored B points, can you print the number of different sequences of getting points by teams that leads to this final score?

Input Format
The first line contains A and the second line contains B.

Constraints

0 ≤ A , B ≤ 109

Output Format
Output the number of different sequences of getting points by the teams that leads to the final score A : B. Final means that the game should be over after this score is reached. If the number is larger than 109+7, output number modulo 109 + 7. Print 0 if no such volleyball game ends with the given score.

Example input #00

3
25

Example output #00

2925

Example input #01

24
17

Example output #01

0

Explanation #01

There’s no game of volleyball that ends with a score of 24 : 17.

solution -->

Lets consider there are r−1 blocks, so that, there will be r spaces to be filled (including the left of the left most block and right of the right most block). Now, n identical things should be filled in these spaces. There are n+r−1 things in that line now, which can be arranged in (n+r−1)!ways.

But, we should avoid the arrangements between the n things and r−1 blocks, since they are identical.

So, the final answer is

(n+r−1)!n!(r−1)!=C(n+r−1,r−1).

code-->

#include<iostream>
using namespace std ;

long long fact[100];
int  p = 1000000007 ;

long long pow(long long a , int b){
    long long x=1 , y=a; 
     while(b){
         if(b%2==1){
         x=x*y;
         x=x%p;
     }
     y=y*y;
    y=y%p ;
    b=b/2;
     }
    return x ;
    
}
int max(int a , int b ){
    return a>b?a:b ;
}

int main(){
    
int a,b ;
    
    cin >> a >> b ;
    
    fact[0]=1 ;
    
    for(int i=1 ; i<100 ;i++)
        fact[i]=(fact[i-1]*(long long)i)%p;
    
    
    if( (a<25 && b<25) || abs(a-b)<2){
        cout <<"0";
        return  0 ;
    }
    
    if(a>=24 && b>=24){
        
        if(abs(a-b)!=2){
             cout <<"0";
        return  0 ;
        }
        
        int z =max(a,b)-2;
        z=z-24;
        long long q= (fact[24]*fact[24])%p ;
        long long ans =(fact[24+25-1]*pow(q,p-2))%p;
        
   long long zz=pow(2,z);        

            ans=(ans*zz)%p;
        
        cout << ans << endl ;
        return 0 ;
          }
    
    
        int y;
        if(a>b)
            y=b;
        else
           y=a; 
  
            long long z = (fact[y]*fact[25-1])%p  ;
        long long ans=(fact[25+y-1]*pow(z,p-2))%p;       
         
    cout << ans << endl ;
    
    return 0 ;
}

There are 2 cities A and B, 1000 Kms apart. We have 3000 bananas in city A and a elephant, which can carry max 1000 bananas at any given time. The elephant needs to eat a banana every 1 Km.

How many maximum number of bananas can be transferred to city B?

Note: The elephant cannot go without bananas.

Also solved to generalized problem.

Generalized Question:

There are 2 cities A and B, ‘D’ Km apart. We have ‘N’ bananas in city A and a elephant, which can carry max ‘C’ bananas at any given time. The elephant needs to eat ‘F’ banana every 1 Km.

Write a program that will compute ‘X’, the maximum amount of bananas that can be transported from city A to city B.

Answer:

First, realize that if you take 1000 bananas and walk 1000 kilometers, you arrive with no banana at all. And the elephant is stuck in city B as there is no banana left for return journey. So the elephant needs to travel shorter distances or we can say that we need to subdivide distances.

How can we subdivide distances?

If we subdivide distances for each kilometer. Notice if elephant wants to shift all the bananas 1 km, you will loose 5 bananas every km. Lets see how.

• In 1st trip, elephant will pick 1000 bananas, eat one at 1 km mark, leave 998 bananas at 1 km mark and keep 1 with him for return journey.
• In 2nd trip, elephant will pick next 1000 bananas, eat one at 1 km mark, leave 998 bananas at 1 km mark and keep 1 with him for return journey.
• In 3rd trip, elephant will pick next 1000 bananas, eat one at 1 km mark, leave 999 bananas at 1 km mark. This time, he doesn’t need to keep anything for return journey.

So we transferred 2995 (998+998+999) to one km distance. This process (loosing 5 bananas per km) will continue until we reach a point where we have one less round trip. In this example, that transit point will come after 200 km, when we will have 2000 bananas left with remaining distance of 800 km.

Also note that the rate of consumption remains constant no matter how we subdivide the distance, as long as the number of trips required is the same.

So in place of shifting bananas every km, we can transferred the banans 200 kilometers at once.

• In 1st trip, elephant will pick 1000 bananas, eat 200 till 200 km mark, leave 600 bananas at 200 km mark and keep 200 with him for return journey.
• In 1st trip, elephant will pick next 1000 bananas, eat 200 till 200 km mark, leave 600 bananas at 200 km mark and keep 200 with him for return journey.
• In 3rd trip, elephant will pick next 1000 bananas, eat 200 till 200 km mark and leave 800 bananas at 200 km mark. This time, he doesn’t need to keep anything for return journey.

In this way, we are now left with 2000 bananas and 800 kms to go.

Now if you calculate, we will consume 3 bananas per km till next transit point. And what will be the next transit point. It should be when we are left with just 1000 bananas. This means that it will come after 333.33 (1000/3) kms.

Finally, we have 1000 bananas and 466.67 kms left. Since elephant can carry 1000 bananas at once, it will pick all 1000 bananas and reach the end with 533.33 (1000 - 466.67) bananas left. (Assumed that elephant eats the banana evenly in fractions of 1km as well.)

Generalized Answer:

So we have seen that if we have (Cn + y) where n is an integer and 0<y<=C at any point in time, our cost of walking each km is (2n+1). And from next transit point this rate will become (2n-1). We need to choose transit points such that we reduce one round time every time. In this manner, transit point will come when remaining bananas are integer multiple of C. Now you have a subset of bananas and distance left. You can apply the same process on remaining values.

This recursion will converge, when remaining bananas are less then or equal to C. (So that we can transfer all of them in single trip.)