#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a) scanf("%c",&a)
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define pbp(a,b) push_back({a,b})
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define sz(x) x.size()
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define loopab(i,a,b) for(int i=a;i<=b;i++)
#define loopba(i,b,a) for(int i=b;i>=a;i--)
#define REV(i,n) for(i=n; i>=0; i--)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d: ",z)
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<r && ty>=0 && ty<c
#define intlim 2147483648
#define MAX 1000000
#define inf 10000000
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
int coin[]={50,25,10,5,1};
int dp[6][7490],make;
int coin_change(int i,int amount)
{
if(i>=5)
{
if(amount==0) return 1;
else return 0;
}
if(dp[i][amount]!=-1) return dp[i][amount];
int ret1=0,ret2=0;
if(amount-coin[i]>=0) ret1=coin_change(i,amount-coin[i]);
ret2=coin_change(i+1,amount);
return dp[i][amount]=ret1 + ret2;
}
int main()
{
//CIN;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ms(dp,-1);
while(cin>>make)
{
cout<<coin_change(0,make)<<endl;
}
return 0;
}
Page 19 of 66
UVa – 357 – Let me count the ways
#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a) scanf("%c",&a)
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define pbp(a,b) push_back({a,b})
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define sz(x) x.size()
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define loopab(i,a,b) for(int i=a;i<=b;i++)
#define loopba(i,b,a) for(int i=b;i>=a;i--)
#define REV(i,n) for(i=n; i>=0; i--)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d: ",z)
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<r && ty>=0 && ty<c
#define intlim 2147483648
#define MAX 1000000
#define inf 10000000
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
int coin[]={1,5,10,25,50},make;
ll dp[6][30001];
ll coin_change(int i,int amount)
{
if(i>=5)
{
if(amount==0) return 1;
else return 0;
}
if(dp[i][amount]!=-1) return dp[i][amount];
ll r1=0,r2=0;
if(amount-coin[i]>=0) r1=coin_change(i,amount-coin[i]);
r2=coin_change(i+1,amount);
return dp[i][amount]=r1+r2;
}
int main()
{
CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
ms(dp,-1);
while(cin>>make)
{
ll ans=coin_change(0,make);
if(ans==1) cout<<"There is only 1 way to produce "<<make<<" cents change."<<endl;
else
cout<<"There are "<<ans<<" ways to produce "<<make<<" cents change."<<endl;
}
return 0;
}
UVa – 11850 – Alaska
Note:
During solving the problem, I was too confused about two things and faced difficulty due to those. And the realizations are:
- Here, it is not mentioned in the problem that whether there is any station in the Delta junction or not. In the solution, it has to be assumed that there is no station in the Delta Junction.
- Here, it is stated that the car can travel up to 200 miles once charged, not greater than this limit. So here it is not meant that, at one station, the car takes charge for 200 miles. For how many miles the car is taking charge, it is not mentioned and it is not even the fact. The summary is, the car can travel up to 200 miles at once, not more than that.
Solution:
/*
Author: Arunima Mandal
*/
#include <bits/stdc++.h>
using namespace std;
bool myfunc(int i,int j)
{
return (i>j);
}
int main()
{
int i,j,n,p,q,c,x;
while(cin>>n)
{
if(n==0) break;
int a[n];
for(i=0; i<n; i++) cin>>a[i];
sort(a,a+n);
c=0;
for(i=0,j=i+1; i<n-1; i++,j++)
{
x=a[j]-a[i];
if(x>200)
{
c=0;
break;
}
if(x<=200) c++;
}
if(c==0) cout<<"IMPOSSIBLE"<<endl;
else
{
p=1422-a[n-1];
q=200-p;
if(q>=p) cout<<"POSSIBLE"<<endl;
else cout<<"IMPOSSIBLE"<<endl;
}
}
return 0;
}
UVa – 12854 – Automated Checking Machine
#include <iostream>
using namespace std;
int a[100000000];
int main()
{
int i,j,c;
while(cin>>a[0])
{
for(i=1;i<10;i++)
{
cin>>a[i];
}
c=0;
for(i=0;i<5;i++)
{
if(a[i]==a[i+5])
{
c=1;
break;
}
}
if(c==1)
{
cout<<"N"<<endl;
}
else
{
cout<<"Y"<<endl;
}
}
return 0;
}
UVa – 12751 – An Interesting Game
#include <stdio.h>
#include <stdlib.h>
int main()
{
int T,i,j,remain,sum1,sum2,n,x,y,k,l;
scanf("%d",&T);
for(l=1;l<=T;l++)
{
scanf("%d",&n);
int A[n];
scanf("%d %d",&k,&x);
for(i=0,j=1;i<n;i++,j++)
{
A[i]=j;
}
sum1=0;
for(i=0;i<n;i++)
{
sum1=sum1+A[i];
}
y=x+k;
sum2=0;
for(i=x-1;i<y-1;i++)
{
sum2=sum2+A[i];
}
remain=sum1-sum2;
printf("Case %d: %d\n",l,remain);
}
return 0;
}
Fall out, Codes! 