Analysis Paralysis

Monday, August 29, 2011

Funny mistakes by Avro Bangla Keyboard users

আনেক = অনেক
ব্রান্দ = ব্র্যান্ড
তেস্ত = টেস্ট
তিপ্তে = টিপতে
হাঙ = হ্যাং
আতপর = অতঃপর
তাশকি = টাসকি

Sunday, August 28, 2011

[UVa] 11121 - Base -2

/* --------------------------> BISMILLAHIR RAHMANIR RAHIM <------------------------------ */
/* ------------------------> Tafhim Ul Islam [ CSE-09@IIUC ] <--------------------------- */
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;

int print[10000];

int convert(int n)
{
    int b=0, i=0;
    if ((n%2)==0)
    {
        b=0;
    } else {
        b=1;
    }
    //cout << b ;
    print[i++]=b;
    while (n)
    {
        n-=b;
        n/=(-2);
        if ((n%2)==0)
        {
            b=0;
        } else
        {
            b=1;
        }
        //cout << b;
        print[i++]=b;
    }
    //cout << endl;
    return i;
}

int main()
{
    int n, i, kase=1, test;
    scanf("%d",&test);
    while (test--)
    {
        scanf("%d",&n);
        if (n==0)
        {
            printf("Case #%d: 0\n",kase++);
            continue;
        }
        printf("Case #%d: ",kase++);
        i = convert(n)-2;
        for ( ; i>=0 ; i--)
        {
            printf("%d",print[i]);
        }
        printf("\n");
    }
    return 0;
}

[UVa] 10935 - Throwing Cards Away

/* --------------------------> BISMILLAHIR RAHMANIR RAHIM <------------------------------ */
/* ------------------------> Tafhim Ul Islam [ CSE-09@IIUC ] <--------------------------- */
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;

queue<int>list;

int main()
{
    bool comma;
    int n, i, v;

    while (cin>>n && n)
    {

        if (n==1)
        {
            cout << "Discarded cards:" << endl;
            cout << "Remaining card: 1" << endl;
            continue;
        }


        for (i=1 ; i<=n ; i++)
        {
            list.push(i);
        }
        comma=false;



        cout << "Discarded cards: ";
        while (1)
        {
            if (comma)
            {
                cout << ", ";
            }
            else
            {
                comma=true;
            }

            v = list.front();
            list.pop();

            cout << v ;
            if (list.size()==1)
                break;

            v = list.front();
            list.pop();
            list.push(v);
        }
        cout << endl << "Remaining card: " << list.front() << endl;
        while (!list.empty())
        {
            list.pop();
        }
    }
    return 0;
}

[UVa] 640 - Self Numbers

/* --------------------------> BISMILLAHIR RAHMANIR RAHIM <------------------------------ */
/* ------------------------> Tafhim Ul Islam [ CSE-09@IIUC ] <--------------------------- */
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;
char s[10];
int digSum(int n)
{
    int i, sum=0;
    sprintf(s,"%d",n);
    for (i=0 ; s[i] ; i++)
    {
        sum+=(s[i]-'0');
    }
    return sum;
}

bool ver[1000001]={false};

void selfer()
{
    int i, j;

    for (i=1 ; i<=1000000 ; i++)
    {
        if (!ver[i])
        {
            printf("%d\n",i);
            for (j=i+digSum(i) ; j<=1000000 ; j+=digSum(j))
            {

                if (ver[j])
                    break;
                ver[j]=true;
            }
        }
    }
}

int main()
{
    int i;

    selfer();
    return 0;
}

Saturday, August 27, 2011

[UVa] 10922 - 2 the 9s

/* --------------------------> BISMILLAHIR RAHMANIR RAHIM <------------------------------ */
/* ------------------------> Tafhim Ul Islam [ CSE-09@IIUC ] <--------------------------- */
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;

int degFinder(char *a)
{
    int i, sum, deg=0, presum=-1;


    do {
        sum=0;
        for (i=0 ; a[i] ; i++)
        {
            sum+=(a[i]-'0');
        }

        //printf("--> %d\n",sum);

        if (sum==presum)
            return deg;
        if ((sum%9)==0)
        {
            deg++;

            sprintf(a,"%d",sum);
            presum=sum;
        }
        else
        {
            return deg;
        }
    } while (1);
    return deg;
}
char inp[10000], pro[10000];
int main()
{
    int print;
    while (gets(inp))
    {
        if (!strcmp(inp,"0"))
            break;
        else
        {
            strcpy(pro,inp);
            print = degFinder(pro);
            if (print)
            {
                printf("%s is a multiple of 9 and has 9-degree %d.\n",inp,print);
            }
            else
            {
                printf("%s is not a multiple of 9.\n",inp);
            }
        }
    }
    return 0;
}

[UVa] 10759 - Fibonacci Numbers

Done using my BigNum class, you can find that in [Projects] tag.

BigNum a[5000];

int main()
{
    int i, q;

    a[0].setNum("1",3000);
    a[1].setNum("1",3000);
    for (i=2 ; i<4790 ; i++)
    {
        a[i].setNum("0",3000);
        a[i].add(&a[i-2],&a[i-1],&a[i]);
    }


    while (scanf("%d",&q)!=EOF)
    {
        a[q-1].print();
    }

    return 0;
}

I've been thinking about designing my own Class that would handle BigNum and their operations. Recently I've put my hands on it as UVa is down for about two days. I've just added the Addition function. It can handle Numbers with given sizes. And it ignores initial Zeros.

I'm feeling too lazy to write a documentation sorta thing on it right now but for the start:

-> Suppose a is your BigNum. You initialize it with
BigNum a("20000",5);
Since 5 is the length of the number;
You can also initialize it like
BigNum a;
Then it has nothing in it and it's size is 0;

To add you can use both Strings (not the C++ string class, not yet) which are char * or another BigNum. But you must use a BigNum for storing the result. It uses a global array of 1000000 size for temp usage. I'm thinking of binding it inside the object but RTE errors are really boring.

Example: 
a.add("200",c); 
a.add("200",a);
a.add(a,a);

/* --------------------------> BISMILLAHIR RAHMANIR RAHIM <------------------------------ */
/* ------------------------> Tafhim Ul Islam [ CSE-09@IIUC ] <--------------------------- */
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;

char res[1000000];

class BigNum
{
    private:
    char *num;
    int sLen;
    public:
    bool add(BigNum *a, BigNum *stor) {                // a points to the other number, stor points to the location                                                     // where the result is stored
        int i, j, k, car=0, cur;
        for (i=sLen-1, j=(a->length())-1, k=0 ; i>=0 || j>=0 ; i--, j--, k++) {
            cur = (i>=0?num[i]:'0') + (j>=0?a->num[j]:'0') - ('0'+'0') + car; // Turning it into integer, 2 '0's because 2 ASCII char
            if (cur>9) {
                car = 1;
                cur = cur - 10;
            } else {
                car = 0;
            }
            res[k]=cur+'0';
        }
        if (car)
        {
            res[k++]='1';
        }
        for (--k, i=0 ; k>=0 ; k--, i++)
        {
            stor->num[i]=res[k];
        }
        stor->num[i]='\0';
        stor->sLen=i;

        return true;
    }
    bool add(char *a, BigNum *stor) {                // a points to the other number, stor points to the location                                                     // where the result is stored
        int i, j, k, l, car=0, cur;

        for (l=0 ; a[l]=='0' ; l++);

        for (i=sLen-1, j=strlen(a)-1, k=0 ; i>=0 || j>=l ; i--, j--, k++) {
            cur = (i>=0?num[i]:'0') + (j>=l?a[j]:'0') - ('0'+'0') + car; // Turning it into integer, 2 '0's because 2 ASCII char
            if (cur>9) {
                car = 1;
                cur = cur - 10;
            } else {
                car = 0;
            }
            res[k]=cur+'0';
        }
        if (car)
        {
            res[k++]='1';
        }
        for (--k, i=0 ; k>=0 ; k--, i++)
        {
            stor->num[i]=res[k];
        }
        stor->num[i]='\0';
        stor->sLen=i;

        return true;
    }

    int length() {
        return sLen;
    }

    BigNum(char *a, int size)
    {
        num = new char [size];
        int i, k;
        for (i=0 ; a[i]!='\0' && a[i]=='0' ; i++);
        for (i, k=0 ; a[i]!='\0' ; i++, k++)
        {
            num[k]=a[i];
        }
        num[k]='\0';
        sLen=k;
    }
    void print() {
        printf("%s\n",num);
    }
    BigNum()
    {
        num = new char [0];
        sLen = 0;
    }
    ~BigNum()
    {
        free(num);
        sLen=0;
    }

};

int main()
{
    BigNum a("100",3), b("200",3), c;



}