孙壕请一盘青岛大虾呗

Time Limit: 5 Sec Memory Limit: 128 MB

Submit: 577 Solved: 244

Description

话说那一年zstu与gdut进行了一场PK赛,很侥幸的zstu赢了。按照约定，gdut的孙壕得请客。大家呼声很高，均高呼：“孙壕请一盘青岛大呗！”

作为gd的一壕，孙壕爽快的答应了。不过zsj说光吃大虾怎么能过瘾，酒是必须上的。说罢，zsj拿出了2瓶赊店老酒。然而2瓶酒显然不能满足大的要求。xs提议青岛大街走一走，逢店加一倍（酒），逢摊吃大虾并喝一瓶（酒）。这一路走过去，遇到店n次，大排档m次，已知最后1次是大排档，大伙正好把酒喝完。请你计算孙壕请客遇到酒店和大排档的次序，合理的次序一共有多少种？

Input

多组测试数据,每组输入2个整数n和m(均不大于10)

Output

对于每组测试数据输出一行,值为符合条件的次序数.

Sample Input

1 3

Sample Output

1

HINT

1 3的情况是:

先大排档 酒由2瓶变1瓶

然后酒店 酒由1瓶变2瓶

然后2次大排档,各喝1瓶,正好喝完

Source

对于不同的安排我们可以采用搜索的方式进行暴力，由于n,m<=10,所以搜就可以

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#define LL long long

using namespace std;

int n,m;

int num;

void dfs(int x,int y,int sum)

{

    if(x<0||y<1||sum==0)

    {

        return ;

    }

    if(x==0&&y==1&&sum==1)//最后一次为大排档，必定只剩一瓶酒

    {

        num++;

    }

    dfs(x-1,y,sum*2);

    dfs(x,y-1,sum-1);

}

int main()

{

    while(~scanf("%d %d",&n,&m))

    {

        num=0;

        dfs(n,m,2);

        printf("%d\n",num);

    }

    return 0;

}