Created
January 16, 2016 14:59
-
-
Save vishnujayvel/bc0f61d026c12775340b to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <vector> | |
| #include <list> | |
| #include <map> | |
| #include <set> | |
| #include <deque> | |
| #include <queue> | |
| #include <stack> | |
| #include <string> | |
| #include <bitset> | |
| #include <algorithm> | |
| #include <functional> | |
| #include <numeric> | |
| #include <utility> | |
| #include <sstream> | |
| #include <iostream> | |
| #include <iomanip> | |
| #include <cstdio> | |
| #include <cmath> | |
| #include <cstdlib> | |
| #include <ctime> | |
| #include <cstring> | |
| #include <climits> | |
| #include <stdlib.h> | |
| #include <stdio.h> | |
| using namespace std; | |
| #define REP(i,n) for(int i=0; i<n; i++) | |
| #define FOR(i,st,end) for(int i=st;i<end;i++) | |
| #define db(x) cout << (#x) << " = " << x << endl; | |
| #define mp make_pair | |
| #define pb push_back | |
| #define mod 1000003 | |
| typedef long long int ll; | |
| vector<int> denominations; | |
| void generateBinaryNumber(int n,int digitCount){ | |
| if(digitCount == 0){ | |
| return; | |
| } | |
| denominations.pb(n*10); | |
| generateBinaryNumber(n*10,digitCount-1); | |
| denominations.pb(n*10+1); | |
| generateBinaryNumber(n*10+1,digitCount-1); | |
| } | |
| int getDigitCount(int n){ | |
| int digits = 0; | |
| int temp = n; | |
| while(temp>0){ | |
| digits++; | |
| temp=temp/10; | |
| } | |
| return digits; | |
| } | |
| int main(){ | |
| int n; | |
| cin>>n; | |
| int c[999999]; | |
| int s[999999]; | |
| int digitCount = getDigitCount(n); | |
| int min1,numberIndex; | |
| denominations.pb(1); | |
| generateBinaryNumber(1,digitCount-1); | |
| FOR(i,1,n+1){ | |
| c[i] = INT_MAX; | |
| } | |
| c[0]=0; | |
| FOR(i,1,n+1){ | |
| min1= INT_MAX; | |
| numberIndex = -1; | |
| int len = denominations.size(); | |
| FOR(j,0,len){ | |
| if(denominations[j]<=i){ | |
| if(c[i-denominations[j]]!=INT_MAX){ | |
| if(c[i-denominations[j]]+1<min1){ | |
| min1=c[i-denominations[j]]+1; | |
| numberIndex=j; | |
| } | |
| } | |
| } | |
| } | |
| if(min1!=INT_MAX){ | |
| c[i]=min1; | |
| s[i]=numberIndex; | |
| } | |
| } | |
| cout<<c[n]<<endl; | |
| while(n>0){ | |
| cout<<denominations[s[n]]<<" "; | |
| n-=denominations[s[n]]; | |
| } | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment