小P的故事——神奇的換零錢

小P的故事——神奇的換零錢

Time Limit: 1000MS Memory limit: 65536K

題目描述

已知A國經濟很落後，他們隻有1、2、3元三種面值的硬币，有一天小P要去A國旅行，想換一些零錢，小P很想知道将錢N兌換成硬币有很多種兌法，但是可惜的是他的數學竟然是體育老師教的，是以他不會啊、、、他隻好求助于你，你可以幫他解決嗎？

輸入

每行隻有一個正整數N，N小于32768。

輸出

對應每個輸入，輸出兌換方法數。

示例輸入

100 
1500      

示例輸出

884 
188251      

分析：

先考慮有三分的情況，再把三分的一個個換成二分，剩下的全是一分。

來源

xfl

示例程式

#include<stdio.h>
int main()
{
	int i,s,a;
	
	while(scanf("%d",&a)!=-1)
	{
		s=a/3+1;
		for(i=0;i<=a/3;i++)
		{
			s=s+(a-i*3)/2;
		}
		printf("%d\n",s);
	}
}
           

• 送出
• 狀态