runtah

Show all combinations of numbers from 1 to 9 that add up to 100 by adding subtracting and concatenating

So, this week I saw a blog post somewhere where the poster claimed that if you cant solve the mentioned 5 problems each in under and hour, you aint no programmer, dev or software engineer. So, I went in and read the problems. 1-4 were easy but number 5 got me a worrying a little. And expected, I failed to solve that in under 1 hour yesterday. But today morning I solved that in less than 30 minutes. But whatever, I cant call myself a programmer anymore :(
Heres my approach though, using recursion:
Each i (from 1 through 9) has 2 different ways of connecting to the sequence.
1. Add itself to the closest sum (1 + 23 + 4 + .......)
2. Or concatenate itself (1 + 234 + ......)
So if we either add an i to the sequence that has reached it or we concatenate. Examples: .......8 + 9
.......89
Now the part before 8 has the same behavior with 8
.......7 + 8
.......78
This goes all the way back to 1 and 2
1 + 2
12
So, the program works something like this

Each branch ultimately ends on the leftmost call.
Code:

#include <cstdio>
#include <iostream>
#include <sstream>

using namespace std;

string i2s(int i) {
 stringstream op;
 op << i;
 return op.str();
}

int solveS(int i, int sum, string p) {

 if (i >= 10) {
 if (sum == 100) {
 cout << p + " = " << sum << endl;
 }
 return 0;
 }

 int iSum = 0;
 for (int j = i ; j<=9 ; j++) {
 iSum = iSum * 10 + j;
 if (i == 1) {
 solveS(j+1, iSum, i2s(iSum));
 } else {
 solveS(j+1, sum+iSum, p + " + " + i2s(iSum));
 solveS(j+1, sum-iSum, p + " - " + i2s(iSum));
 }
 }

 return 0;
}

int main() {

 //freopen("output.txt", "w+", stdout);

 solveS(1, 0, "");

 return 0;
}

Go to link download

UVa 471 Magic Numbers

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <clocale>


using namespace std;


typedef long long lint;

bool cmp(pair<lint,lint> a, pair<lint,lint> b) {
 
 return (a.first<b.first);
 
}


bool check(lint n) {
 
 bool ver[20];
 char buf[100];
 lint len;
 for (int i=0 ; i<=20 ; i++) ver[i]=false;
 
 sprintf(buf,"%lld",n);
 
 len = strlen(buf);
 
 if (len>10) return false;
 
 for (int i=0 ; i<len ; i++) {
 if ( ver[ buf[i]-0 ] == true ) return false;
 else ver[ buf[i]-0 ] = true;
 }
 return true;
}


int main( void ) {
 
 lint kase, n, i, j, numerator, x, k;
 bool first=true, dis, ver[10];
 
 vector< pair<lint,lint> > lst;
 
 scanf("%lld",&kase);
 
 while (kase--) {
 
 scanf("%lld",&n);
 
 if (n==0) continue;
 
 lst.clear();
 
 for (i=1 ; (n*i)>=0 ; i++) {
 
 numerator = n*i;
 
 x = numerator;
 
 for (k=0 ; x ; k++, x/=10) if (k>10) break; // if length of the current
 if (k>10) { break; } // numerator exceeds 10 the loop ends
 
 if (check(i) && check(numerator)) 
 lst.push_back(make_pair(numerator,i));

 }
 
 sort(lst.begin(),lst.end(),cmp);
 
 if (!first) putchar( );
 first = false;
 for (i=0 ; i<lst.size() ; i++) {
 printf("%lld / %lld = %lld ",lst[i].first,lst[i].second,n);
 }
 
 }
 
 return 0;
 
}

Go to link download