Problem H: 【2012提高】请客
Memory Limit:64 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:43
Solved:6
Description
小T和小K都是班干部,经常要为班集体做一些事情。有一天,班主任派他们一起出去执行任务,他们完成任务后回到学校已经接近傍晚,就直接赶去食堂吃晚饭了,还没到食堂门口两人又发生了争执,原因是小T和小K都争着要请对方吃饭,争到最后他俩决定以猜拳来解决争端,因为小T没带“分歧终端机”,猜拳结果当然又是小T输了,所以他要请小K吃饭~。
食堂里有100种不同的菜,每种菜有一个1到100之间的整数标号,每种菜的标号都不相同,每种菜的单价定为它的标号的平方(即标号*标号),如标号为1的菜单价为1元,标号为2的菜单价为4元,标号为3的菜单价为9元,标号为4的菜单价为16元,……
现在小T和小K要在这些菜中点N个菜,每一种菜最多只会点一个。由于小T只有S元钱,为了避免请小K吃饭后没钱坐公交车回家之类的尴尬,必须保证所点菜的总价严格小于S。
现在请你编一个程序统计有多少种不同的点菜组合,如果你能解决这个难题,小T将会额外奖励你一件奖品。
食堂里有100种不同的菜,每种菜有一个1到100之间的整数标号,每种菜的标号都不相同,每种菜的单价定为它的标号的平方(即标号*标号),如标号为1的菜单价为1元,标号为2的菜单价为4元,标号为3的菜单价为9元,标号为4的菜单价为16元,……
现在小T和小K要在这些菜中点N个菜,每一种菜最多只会点一个。由于小T只有S元钱,为了避免请小K吃饭后没钱坐公交车回家之类的尴尬,必须保证所点菜的总价严格小于S。
现在请你编一个程序统计有多少种不同的点菜组合,如果你能解决这个难题,小T将会额外奖励你一件奖品。
Input
仅有一行包含两个用空格隔开的整数N和S,其中1≤N≤30,1≤S≤10,000。
Output
仅有一行包含一个整数,即不同的点菜组合的总数。
Sample Input Copy
3 30
Sample Output Copy
4
HINT
【样例解释】
小T只有30元钱,他们想点3个菜,总价严格小于30元的点菜组合有以下4种:
1 2 3 总价为1+4+9=14元
1 2 4 总价为1+4+16=21元
1 3 4 总价为1+9+16=26元
2 3 4 总价为4+9+16=29元
1 2 5的点菜组合是不可以的,因为1+4+25=30元,不满足严格小于30元的条件。
【数据规模】
30%的数据满足:1≤N≤5,1≤S≤500
100%的数据满足:1≤N≤30,1≤S≤10,000
后记:CZ中学今年共有18位信息学保送生被清华北大等名牌大学提前录取,更为可喜的是蒋中天同学于去年暑假赴泰国芭提雅参加第23届国际信息学奥林匹克竞赛荣获金牌,创造了CZ中学新的历史。这些oier们将满腔热情都倾注到了信息学奥林匹克活动中去了,他们走过的路程既充满艰辛,又充满乐趣,在自己取得优异成绩的同时,还十分关心小选手们的成长,他们对本次活动非常热心,有的参与命题,有的担任志愿者,大家都殷切期待不久的将来在同学们中间能够涌现出第二个蒋中天。另外本次选拔活动表现优异的同学将获得谷歌(google)公司提供的奖品。
小T只有30元钱,他们想点3个菜,总价严格小于30元的点菜组合有以下4种:
1 2 3 总价为1+4+9=14元
1 2 4 总价为1+4+16=21元
1 3 4 总价为1+9+16=26元
2 3 4 总价为4+9+16=29元
1 2 5的点菜组合是不可以的,因为1+4+25=30元,不满足严格小于30元的条件。
【数据规模】
30%的数据满足:1≤N≤5,1≤S≤500
100%的数据满足:1≤N≤30,1≤S≤10,000
后记:CZ中学今年共有18位信息学保送生被清华北大等名牌大学提前录取,更为可喜的是蒋中天同学于去年暑假赴泰国芭提雅参加第23届国际信息学奥林匹克竞赛荣获金牌,创造了CZ中学新的历史。这些oier们将满腔热情都倾注到了信息学奥林匹克活动中去了,他们走过的路程既充满艰辛,又充满乐趣,在自己取得优异成绩的同时,还十分关心小选手们的成长,他们对本次活动非常热心,有的参与命题,有的担任志愿者,大家都殷切期待不久的将来在同学们中间能够涌现出第二个蒋中天。另外本次选拔活动表现优异的同学将获得谷歌(google)公司提供的奖品。