ZCMU--5115: Buying Keys(C语言)

Description

One day Xiao Ming is not happy because he has no idea about how to run out of his pocket money. At that moment, a mysterious man appears with a smile: "My keys are on sale. one key cost 3 yuans and 3 keys cost 10 yuans. How many keys do you wanna buy?" Xiaoming is attracted by mysterious man and wants to spend all his money on buying keys. He doesn't want keep any money at the end. At the same time, because of the heavy weight of keys, Xiaoming Hopes that he can buy as few keys as possible. At the beginning, Xiao Ming had n yuan. Can you tell Xiaoming the minimum number of keys he can bought if he runs out of his pocket money? If Xiaoming can't run out of his money, please output "orz".

Input

The first line contains one integer n(1≤n≤109), the pocket money Xiaoming have.

Output

If Xiaoming can't run out of his money, please output "orz"(without quotes), otherwise output the minimum number of keys he can bought if he runs out of his money.

Sample Input

3

Sample Output

1

HINT

Xiaoming can spend 3 yuan to buy a key

解析：倘若能刚好花完所有钱，那么假设买了 i 个10元套餐，j 个3元套餐，那么肯定满足3*i+10*j=n，我们可以直接暴力枚举看有无满足的 i 和 j。  

#include <stdio.h>
int main()
{
	int n,s,i,j;
	while(~scanf("%d",&n)){
		s=0;
		for(i=n/10;i>=0;i--){	//最多买n/10个 
			for(j=0;j<=n/3;j++){	//最多买n/3个 
				if(i*10+3*j==n){
					s=1;//存在满足i和j 
					break;
				}
			}
			if(s==1) break;
		}
		if(s==1) printf("%d\n",i*3+j);
		else printf("orz\n");
	}
	return 0;
}

优化版本：我们买了 i 个10元，那么剩下钱就是n-3*i，倘若这个能整除3，那么就是满足条件。

#include <stdio.h>
int main()
{
	int n,s,i;
	scanf("%d",&n); 
	s=0;
	for(i=n/10;i>=0;i--){
		if((n-i*10)%3==0){   //剩下的钱能整除3
			s=1;
			break;
		}
	}
	if(s==1) printf("%d\n",i*3+(n-i*10)/3);
	else printf("orz\n");
	return 0;
}