「CFgym100541」ATM withdrawal

2015年3月14日2,9050

Vinh works for an ATM machine manufacturing company. The basic functionality of an ATM machine is cash withdrawal. When a user requests a cash withdrawal of W VND (Vietnamese Dong), the ATM has to dispense Nmoney notes such that they sum up to W. For the next generation of ATM machine, Vinh is working on an algorithm to minimize the number N of money notes for each cash withdrawal transaction.

Your task is to help Vinh to do his job given that the money notes come in the values of 1000, 2000, 3000, 5000, 1000 * 10¹, 2000 * 10¹, 3000 * 10¹, 5000 * 10¹, …, 1000 * 10^c, 2000 * 10^c, 3000 * 10^c, 5000 * 10^c where c is a positive integer and Vinh has unlimited supply of money notes for each value.

Input

The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 1000. The following lines describe the datasets.

The first line consists of one positive integer W (W ≤ 10¹⁸);
The second line consists of one positive integer c (c ≤ 15).

Output

For each dataset, write in one line two space-separated integers N and S where S is the number of ways to dispense the fewest number N of money notes. In case there is no way to serve the cash withdrawal request, write out 0 in one line instead.

Sample test(s)

input

1000

7000

output

1 1
2 1

1 1

2 1

题解

显然低位不涉及进位的问题。。。

所以预处理组成1-9的最少个数和方案

低于c的按位统计，其余乱搞一下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define eps 1e-6
#define inf 1000000000
#define mod 1000000009
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll T,n,c;
int s[10]={0,1,1,1,2,1,2,2,2,3};
int t[10]={1,1,1,1,2,1,2,1,1,3};
void solve()
{
	ll a1=0,a2=1;
	n/=1000;
	for(int i=1;i<=c;i++)
	{
		int tmp=n%10;
		a1+=s[tmp],a2*=t[tmp];
		n/=10;
	}
	if(n<=5)
		a1+=s[n],a2*=t[n];
	else 
	{
		a1+=n/5-1;
		n=n%5+5;
		a1+=s[n],a2*=t[n];
	}
	cout<<a1<<' '<<a2<<endl;	
}
int main()
{
	T=read();
	while(T--)
	{
		n=read();c=read();
		if(n%1000)puts("0");
		else solve();
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define eps 1e-6

#define inf 1000000000

#define mod 1000000009

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll T,n,c;

int s[10]={0,1,1,1,2,1,2,2,2,3};

int t[10]={1,1,1,1,2,1,2,1,1,3};

void solve()

{

ll a1=0,a2=1;

n/=1000;

for(int i=1;i<=c;i++)

{

int tmp=n%10;

a1+=s[tmp],a2*=t[tmp];

n/=10;

}

if(n<=5)

a1+=s[n],a2*=t[n];

else

{

a1+=n/5-1;

n=n%5+5;

a1+=s[n],a2*=t[n];

}

cout<<a1<<' '<<a2<<endl;

}

int main()

{

T=read();

while(T--)

{

n=read();c=read();

if(n%1000)puts("0");

else solve();

}

return 0;

}

« 「BZOJ3036」绿豆蛙的归宿「BZOJ1962」模型王子 »

hzwer.com _ Home | http://hzwer.com

「CFgym100541」ATM withdrawal

分类目录

热门文章

Myfriends

近期评论