下沙的沙子有幾粒？(杭電1267)

下沙的沙子有幾粒？

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 2823    Accepted Submission(s): 1480

Problem Description

2005年11月份，我們學校參加了ACM/ICPC 亞洲賽區成都站的比賽，在這裡，我們獲得了曆史性的突破，盡管隻是一枚銅牌，但獲獎那一刻的激動，也許将永遠銘刻在我們幾個人的心頭。借此機會,特向去年為參加ACM亞洲賽而艱苦集訓了近半年的各位老隊員表示感謝。

實際上，除了獲獎以外，在這次比賽期間還有一件事也讓我們記憶深刻。那是比賽當天等待入場的時候，聽到某個學校的一個隊員在說：“有個學校的英文名很有意思，叫什麼Hangzhou Dianzi University”. 哈哈，看來我們學校的英文名起的非常好，非常吸引人呀。

不過，事情的發展誰也沒有料到，随着杭電英文校名的這一次曝光，影響越來越大，很多人開始對杭電英文校名進行研究，不久以後甚至還成立了一個專門的研究機構，叫做“HDU 校名研究會”。并不斷有報道說-相-當-多的知名科學家改行，專門對該問題進行研究，學術界稱之為“杭電現象”。很多人在國際知名期刊上發表了研究論文，這其中，尤以中國超級女科學家宇春小姐寫的一篇研究報告最為著名，報告發表在science上，标題是“杭電為什麼這樣紅？” 文中研究發現：Hangzhou Dianzi University這個校名具有深刻的哲學思想和内涵，她同時提出了一個大膽的猜想：“假定一個字元串由m個H和n個D組成，從左到右掃描該串，如果字元H的累計數總是不小于字元D的累計數,那麼，滿足條件的字元串總數就恰好和下沙的沙粒一樣多。”

這就是當今著名的“宇春猜想”！

雖然還沒能從數學上證明這個猜想的正确性，但據說美國方面在小布什的親自幹預下，已經用超級計算機驗證了在（1<=n<=m<=1000000000000）時都是正确的。my god! 這是一個多麼偉大的猜想！雖然我們以前總說，21世紀是屬于中國的，可還是沒想這一天來的這麼早，自豪ing... + 感動ing...

感動和自豪之餘，問題也來了，如果已知m和n的值，請計算下沙的沙粒到底有多少。

Ps: 

1. 中國有關方面正在積極行動，着手為宇春小姐申報諾貝爾獎。

2、“宇春猜想”中提到的H和D組成的字元串現在被學術界成為“杭電串串”（“杭電串串”前不久被一個賣羊肉串的注冊了商标，現在我校正在積極聯系買斷，據說賣方的底價是1000萬歐元，絕不打折，看來希望不大，sigh...）

Input

輸入資料包含多個測試執行個體，每個占一行，由兩個整數m和n組成，m和 n 分别表示字元串中H和D的個數。由于我們目前所使用的微機和老美的超級計算機沒法比，是以題目給定的資料範圍是（1<=n<=m<=20）。

Output

對于每個測試執行個體，請輸出下沙的沙粒到底有多少，計算規則請參考“宇春猜想”，每個執行個體的輸出占一行。

Sample Input

1 1

3 1

Sample Output

1

3

#include<stdio.h>
__int64 a[22][22];  //用__int64存儲，否則超記憶體。 
int asd()
{
  int i,j;
  for(i=1;i<=21;i++)
  {
    a[i][1]=i;
  }
  for(i=2;i<=21;i++)
  {
    for(j=2;j<=21;j++)
    {
      if(i>=j)
      a[i][j]=a[i-1][j]+a[i][j-1];
    }
  }
}
int main()
{
  int m,n;
  while(scanf("%d %d",&m,&n)!=EOF)
  {
    asd();
    printf("%I64d\n",a[m][n]);
  }
  return 0;
}