// -*- mode: c++ -*-
// $Id: ackermann.g++,v 1.3 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <iostream>
#include <stdlib.h>

using namespace std;

int Ack(int M, int N) {
    if (M == 0) return( N + 1 );
    if (N == 0) return( Ack(M - 1, 1) );
    return( Ack(M - 1, Ack(M, (N - 1))) );
}

int main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);

    cout << "Ack(3," << n << "): " << Ack(3, n) << endl;
    return(0);
}

// -*- mode: c++ -*-
// $Id: ary3.g++,v 1.2 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
    int i, k, n = ((argc == 2) ? atoi(argv[1]) : 1);
    typedef vector<int> ARY;
    ARY x(n);
    ARY y(n);

    for (i=0; i<n; i++) {
    x[i] = i + 1;
    }
    for (k=0; k<1000; k++) {
    for (int i = n - 1; i >= 0; --i) {
        y[i] += x[i];
    }
    }

    cout << y[0] << " " << y.back() << endl;
}

// -*- mode: c++ -*-
// $Id: wc.g++,v 1.4 2001/07/08 18:45:52 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <iostream>
#include <vector>

using namespace std;

enum {
    OUT,            
    IN                
};

int
main(int argc, char *argv[]) {
    char c;
    int nl, nw, nc, state;

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    state = OUT;
    nl = nw = nc = 0;
    while (cin.get(c)) {
    ++nc;
    if (c == '\n')
        ++nl;
    if (c == ' ' || c == '\n' || c == '\t')
        state = OUT;
    else if (state == OUT) {
        state = IN;
        ++nw;
    }
    }
    cout << nl << " " << nw << " " << nc << endl;
}

// -*- mode: c++ -*-
// $Id: except.g++,v 1.4 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/
// from Bill Lear

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

size_t HI = 0;
size_t LO = 0;

class Hi_exception {
public:
    explicit Hi_exception(size_t _n) : n(_n) {}
    const char* what() { sprintf(N, "%d", n); return N; }
private:
    size_t n; char N[8];
};

class Lo_exception {
public:
    explicit Lo_exception(size_t _n) : n(_n) {}
    const char* what() { sprintf(N, "%d", n); return N; }
private:
    size_t n; char N[8];
};

void blowup(size_t num) {
    if (num % 2) {
        throw Lo_exception(num);
    }
    throw Hi_exception(num);
}

void lo_function(size_t num) {
    try {
        blowup(num);
    } catch(const Lo_exception& ex) {
        ++LO;
    }
}

void hi_function(size_t num) {
    try {
        lo_function(num);
    } catch(const Hi_exception& ex) {
        ++HI;
    }
}

void some_function(size_t num) {
    try {
        hi_function(num);
    } catch (...) {
        cerr << "We shouldn't get here\n"; exit(1);
    }
}

int
main(int argc, char* argv[]) {
    size_t NUM = (argc == 2 ? (atoi(argv[1]) < 1 ? 1 : atoi(argv[1])): 1);
    while (NUM--) {
        some_function(NUM);
    }
    cout << "Exceptions: HI=" << HI << " / " << "LO=" << LO << endl;
}

// -*- mode: c++ -*-
// $Id: fibo.g++,v 1.3 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <iostream>
#include <stdlib.h>

using namespace std;

unsigned long fib(unsigned long n) {
    if (n < 2)
    return(1);
    else
    return(fib(n-2) + fib(n-1));
}

int main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);

    cout << fib(n) << endl;
    return(0);
}

// -*- mode: c++ -*-
// $Id: hash.g++,v 1.2 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <stdio.h>
#include <iostream>
#include <hash_map.h>

using namespace std;

struct eqstr {
    bool operator()(const char* s1, const char* s2) const {
    return strcmp(s1, s2) == 0;
    }
};

int
main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);
    char buf[16];
    typedef hash_map<const char*, int, hash<const char*>, eqstr> HM;
    HM X;

    for (int i=1; i<=n; i++) {
    sprintf(buf, "%x", i);
    X[strdup(buf)] = i;
    }

    int c = 0;
    for (int i=n; i>0; i--) {
    sprintf(buf, "%d", i);
    if (X[strdup(buf)]) c++;
    }

    cout << c << endl;
}

// -*- mode: c++ -*-
// $Id: hash2.g++,v 1.2 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <stdio.h>
#include <iostream>
#include <hash_map.h>

using namespace std;

struct eqstr {
    bool operator()(const char* s1, const char* s2) const {
    return strcmp(s1, s2) == 0;
    }
};

int
main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);
    char buf[16];
    typedef hash_map<const char*, int, hash<const char*>, eqstr> HM;
    HM hash1, hash2;

    for (int i=0; i<10000; i++) {
    sprintf(buf, "foo_%d", i);
    hash1[strdup(buf)] = i;
    }
    for (int i=0; i<n; i++) {
    for (HM::iterator k = hash1.begin(); k != hash1.end(); ++k) {
        hash2[(*k).first] += hash1[(*k).first];
    }
    }
    cout << hash1["foo_1"] << " " << hash1["foo_9999"] << " "
     << hash2["foo_1"] << " " << hash2["foo_9999"] << endl;
}

// -*- mode: c++ -*-
// $Id: heapsort.g++,v 1.4 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <iostream>
#include <stdlib.h>
#include <math.h>

using namespace std;

#define IM 139968
#define IA   3877
#define IC  29573

double
gen_random(double max) {
    static long last = 42;
    return( max * (last = (last * IA + IC) % IM) / IM );
}

void
heapsort(int n, double *ra) {
    int i, j;
    int ir = n;
    int l = (n >> 1) + 1;
    double rra;

    for (;;) {
    if (l > 1) {
        rra = ra[--l];
    } else {
        rra = ra[ir];
        ra[ir] = ra[1];
        if (--ir == 1) {
        ra[1] = rra;
        return;
        }
    }
    i = l;
    j = l << 1;
    while (j <= ir) {
        if (j < ir && ra[j] < ra[j+1]) { ++j; }
        if (rra < ra[j]) {
        ra[i] = ra[j];
        j += (i = j);
        } else {
        j = ir + 1;
        }
    }
    ra[i] = rra;
    }
}

int
main(int argc, char *argv[]) {
    int N = ((argc == 2) ? atoi(argv[1]) : 1);
    double *ary;
    int i;
    
    
    ary = (double *)malloc((N+1) * sizeof(double));
    for (i=1; i<=N; i++) {
    ary[i] = gen_random(1);
    }

    heapsort(N, ary);

    cout.precision(10);
    cout << ary[N] << endl;

    free(ary);
    return(0);
}

// -*- mode: c++ -*-
// $Id: hello.g++,v 1.3 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <iostream>

using namespace std;

int main() {
    cout << "hello world" << endl;
    return(0);
}

// -*- mode: c++ -*-
// $Id: lists.g++,v 1.5 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/
// from Bill Lear

#include <iostream>
#include <list>
#include <numeric>

using namespace std;

const size_t SIZE = 10000;

size_t test_lists() {
    std::list<size_t> li1(SIZE);

    std::iota(li1.begin(), li1.end(), 1);

    std::list<size_t> li2(li1);

    std::list<size_t> li3;

    size_t N = li2.size();
    while (N--) {
        li3.push_back(li2.front());
        li2.pop_front();
    }

    N = li3.size();
    while (N--) {
        li2.push_back(li3.back());
        li3.pop_back();
    }

    li1.reverse();

    return (li1.front() == SIZE) && (li1 == li2) ? li1.size() : 0;
}

int main(int argc, char* argv[]) {
    size_t ITER = (argc == 2 ? (atoi(argv[1]) < 1 ? 1 : atoi(argv[1])): 1);

    size_t result = 0;
    while (ITER > 0) {
        result = test_lists();
        --ITER;
    }

    std::cout << result << std::endl;
}

// -*- mode: c++ -*-
// $Id: matrix.g++,v 1.3 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <iostream>
#include <stdlib.h>

using namespace std;

#define SIZE 30

int **mkmatrix(int rows, int cols) {
    int i, j, count = 1;
    int **m = (int **) malloc(rows * sizeof(int *));
    for (i=0; i<rows; i++) {
    m[i] = (int *) malloc(cols * sizeof(int));
    for (j=0; j<cols; j++) {
        m[i][j] = count++;
    }
    }
    return(m);
}

void zeromatrix(int rows, int cols, int **m) {
    int i, j;
    for (i=0; i<rows; i++)
    for (j=0; j<cols; j++)
        m[i][j] = 0;
}

void freematrix(int rows, int **m) {
    while (--rows > -1) { free(m[rows]); }
    free(m);
}

int **mmult(int rows, int cols, int **m1, int **m2, int **m3) {
    int i, j, k, val;
    for (i=0; i<rows; i++) {
    for (j=0; j<cols; j++) {
        val = 0;
        for (k=0; k<cols; k++) {
        val += m1[i][k] * m2[k][j];
        }
        m3[i][j] = val;
    }
    }
    return(m3);
}

int main(int argc, char *argv[]) {
    int i, n = ((argc == 2) ? atoi(argv[1]) : 1);
    
    int **m1 = mkmatrix(SIZE, SIZE);
    int **m2 = mkmatrix(SIZE, SIZE);
    int **mm = mkmatrix(SIZE, SIZE);

    for (i=0; i<n; i++) {
    mm = mmult(SIZE, SIZE, m1, m2, mm);
    }
    cout << mm[0][0] << " " << mm[2][3] << " " << mm[3][2] << " " << mm[4][4] << endl;

    freematrix(SIZE, m1);
    freematrix(SIZE, m2);
    freematrix(SIZE, mm);
    return(0);
}

// -*- mode: c++ -*-
// $Id: methcall.g++,v 1.7 2001/06/28 14:25:35 doug Exp $
// http://www.bagley.org/~doug/shootout/

// with some help from Bill Lear

// [dada] 2001-09-19 had to add 'int i' at the beggining of main for VC++

#include <stdlib.h>
#include <iostream>

using namespace std;

class Toggle {
public:
    Toggle(bool start_state) : state(start_state) { }
    virtual bool value() {
    return(state);
    }
    Toggle& activate() {
    state = !state;
    return(*this);
    }
    bool state;
};

class NthToggle : public Toggle {
public:
    NthToggle(bool start_state, int max_counter) :
    Toggle(start_state), count_max(max_counter), counter(0) {
    }
    NthToggle& activate() {
    if (++this->counter >= this->count_max) {
        state = !state;
        counter = 0;
    }
    return(*this);
    }
private:
    int count_max;
    int counter;
};

int
main(int argc, char *argv[]) {
    int i;
    int n = ((argc == 2) ? atoi(argv[1]) : 1);

    bool val = true;
    Toggle *toggle = new Toggle(val);
    for (i=0; i<n; i++) {
    val = toggle->activate().value();
    }
    cout << ((val) ? "true" : "false") << endl;
    delete toggle;

    val = true;
    NthToggle *ntoggle = new NthToggle(val, 3);
    for (i=0; i<n; i++) {
    val = ntoggle->activate().value();
    }
    cout << ((val) ? "true" : "false") << endl;
    delete ntoggle;

    return 0;
}

// -*- mode: c++ -*-
// $Id: nestedloop.g++,v 1.2 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <iostream>
#include <stdlib.h>

using namespace std;

int main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);
    int a, b, c, d, e, f, x=0;
    
    for (a=0; a<n; a++)
    for (b=0; b<n; b++)
        for (c=0; c<n; c++)
        for (d=0; d<n; d++)
            for (e=0; e<n; e++)
            for (f=0; f<n; f++)
                x++;

    cout << x << endl;
    return(0);
}

// -*- mode: c++ -*-
// $Id: random.g++,v 1.4 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <iostream>
#include <stdlib.h>
#include <math.h>

using namespace std;

#define IM 139968
#define IA 3877
#define IC 29573

double gen_random(double max) {
    static long last = 42;
    last = (last * IA + IC) % IM;
    return( max * last / IM );
}

int main(int argc, char *argv[]) {
    int N = ((argc == 2) ? atoi(argv[1]) : 1);
    double result = 0;
    
    while (N--) {
    result = gen_random(100.0);
    }
    cout.precision(10);
    cout << result << endl;
    return(0);
}

// -*- mode: c++ -*-
// $Id: regexmatch.g++,v 1.2 2001/06/20 03:20:03 doug Exp $
// http://www.bagley.org/~doug/shootout/
// From Bill Lear


#include <iostream>
#include <zopyra/regx>

using namespace std;

typedef pair<const char*, const char*> span;

int main(int ac, char* av[]) {
    zopyra::regx re(
    "(?x)              # set extended flag for embedded comment fun\n"
        "(?:^|[^\\d(])    # must be preceded by non-digit\n"
        "([(])?           # match 1: possible initial left paren\n"
        "(\\d{3})         # match 2: area code is 3 digits\n"
        "(?(1)[)])        # if match1 then match right paren\n"
        "[ ]              # area code followed by one space\n"
        "(\\d{3})         # match 3: prefix of 3 digits\n"
        "[- ]             # separator is either space or dash\n"
        "(\\d{4})         # match 4: last 4 digits\n"
        "(?:\\D|\\b)      # followed by non-digit or break\n"
    );
    
    string line;
    vector<span> lines;
    while (getline(cin, line)) {
        char* phone = new char[line.size()];
        copy(line.begin(), line.end(), phone);
        lines.push_back(span(phone, phone + line.size()));
    }

    size_t ITER = (ac == 2 ? (atoi(av[1]) < 1 ? 1 : atoi(av[1])): 1);

    char num[13];
    num[0] = '(';
    num[4] = ')';
    num[5] = ' ';
    num[9] = '-';
    size_t count = 0;
    while (ITER--) {
        vector<span>::iterator end = lines.end();
        for (vector<span>::iterator i = lines.begin(); i != end; ++i) {
            zopyra::regx::iterator p = re.find(i->first, i->second);
            if (p++ != re.end()) {
                char* num_p = &num[1];
                ++p;
                copy(p->first, p->second, num_p);

                num_p = &num[6];
                ++p;
                copy(p->first, p->second, num_p);

                num_p = &num[10];
                ++p;
                copy(p->first, p->second, num_p);

                if (!ITER) {
                    cout << ++count << ": ";
                    copy(num, num + 14, ostream_iterator<char>(cout));
                    cout << '\n';
                }
            }
        }
    }
}

// -*- mode: c++ -*-
// $Id: reversefile.g++,v 1.3 2001/07/06 13:19:30 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    typedef vector<string> LINES;
    LINES l;
    char line[256];
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    while (cin.getline(line, 256)) {
        l.push_back(line);
    }
    for (LINES::reverse_iterator j = l.rbegin(); j != l.rend(); j++) {
    cout << (*j) << endl;
    }    
}

// -*- mode: c++ -*-
// $Id: sieve.g++,v 1.5 2001/06/20 03:20:03 doug Exp $
// http://www.bagley.org/~doug/shootout/
// From Bill Lear

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>

using namespace std;

int main(int argc, char *argv[]) {
    size_t NUM = (argc == 2 ? (atoi(argv[1]) < 1 ? 1 : atoi(argv[1])): 1);

    vector<char> primes(8192 + 1);
    vector<char>::iterator pbegin = primes.begin();
    vector<char>::iterator begin = pbegin + 2;
    vector<char>::iterator end = primes.end();

    while (NUM--) {
        fill(begin, end, 1);
        for (vector<char>::iterator i = begin; i != end; ++i) {
            if (*i) {
                const size_t p = i - pbegin;
                for (vector<char>::iterator k = i + p; k <= end; k += p) {
                    *k = 0;
                }
            }
        }
    }

    cout << "Count: " << count(begin, end, 1) << endl;
}

// -*- mode: c++ -*-
// $Id
// http://www.bagley.org/~doug/shootout/
// Calculate statistical moments of a region, from Bill Lear
// [dada] 2001-09-19 had to change power to pow for VC++

#include <iostream>
#include <vector>
#include <numeric>
#include <iterator>
#include <algorithm>
#include <cstdio>
#include <math.h>

using namespace std;

template <class T>
struct moments {
public:
    template <class InputIterator>
    moments(InputIterator begin, InputIterator end)
        : median(0.0), mean(0.0), average_deviation(0.0),
          standard_deviation(0.0), variance(0.0),
          skew(0.0), kurtosis(0.0)
    {
        T sum = accumulate(begin, end, 0.0);
        size_t N = end - begin;
        mean = sum / N;

        for (InputIterator i = begin; i != end; ++i) {
            T deviation = *i - mean;
            average_deviation += fabs(deviation);
            variance += pow(deviation, 2);
            skew += pow(deviation, 3);
            kurtosis += pow(deviation, 4);
        }

        average_deviation /= N;
        variance /= (N - 1);
        standard_deviation = sqrt(variance);

        if (variance) {
            skew /= (N * variance * standard_deviation);
            kurtosis = kurtosis/(N * variance * variance) - 3.0;
        }

        sort(begin, end);
        size_t mid = N/2;
        median = N % 2 ? *(begin+mid) : (*(begin+mid) + *(begin+mid-1))/2;
    }

    T median;
    T mean;
    T average_deviation;
    T standard_deviation;
    T variance;
    T skew;
    T kurtosis;
};

int main() {
    vector<double> v;
    char line[8];

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    while (cin.getline(line, 8)) {
        v.push_back(atof(line));
    }

    moments<double> m(v.begin(), v.end());

    int n = v.end() - v.begin();

    printf("n:                  %d\n", n);
    printf("median:             %f\n", m.median);
    printf("mean:               %f\n", m.mean);
    printf("average_deviation:  %f\n", m.average_deviation);
    printf("standard_deviation: %f\n", m.standard_deviation);
    printf("variance:           %f\n", m.variance);
    printf("skew:               %f\n", m.skew);
    printf("kurtosis:           %f\n", m.kurtosis);
}

// -*- mode: c++ -*-
// $Id: strcat.g++,v 1.3 2001/06/20 03:20:03 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <iostream>
#include <string>

using namespace std;

int main(int argc, char *argv[]) {
    int i, n = ((argc == 2) ? atoi(argv[1]) : 1);
    string str;

    for (i=0; i<n; i++) {
    str += "hello\n";
    }
    cout << str.length() << endl;
}

// -*- mode: c++ -*-
// $Id: sumcol.g++,v 1.4 2001/07/06 12:15:14 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <iostream>
#include <stdlib.h>

using namespace std;

#define MAXLINELEN 128

int main() {
    char line[MAXLINELEN];
    int sum = 0;
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    while (cin.getline(line, MAXLINELEN)) {
        sum += atoi(line);
    }
    cout << sum << '\n';
}