[UVa] 10830 - A New Function

#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>

typedef unsigned long long ull;
typedef long long xll;
typedef long double ld;

using namespace std;
ull sumfind(ull a, ull n)
{
    return ((n*(n+1)/2) - (a*(a-1)/2));
}
ull csod(ull n)
{
    ull root = (ull)sqrt((double)n), i, j;
    ull lim, sum=0;

    for (i=2 ; i<=root ; i++)
    {
        lim = n/i;
        sum += (sumfind(i+1,lim) + (i*(lim-i+1)));
    }

    return sum;
}

int main()
{
    ull n, sum=0, kase=1;

    while (cin >> n && n)
    {
        cout << "Case " << kase++ << ": " << csod(n) << endl;
    }
    return 0;

}

[UVa] 160 - Factors & Factorials

#include <cstdio>
#include <iostream>
#define MP 100
using namespace std;
bool ver[300]={false};
int list[1000];
int siever() {
    int i, j, k=0;
    list[k++]=2;
    for (i=3 ; i<=200 ; i+=2)
    {
        if (ver[i]==false)
        {
            list[k++]=i;
            for (j=3 ; i*j<=200 ; j+=2)
            {
                ver[i*j]=true;
            }
        }
    }
    list[0]=2;
    return k;
}

int test(int x, int p)
{
    int i, counter=0, temp, rem=1, n=x;
    for (i=x ; i>1 ; i--)
    {
        n=i;
        while (n%p == 0)
        {

            counter++;
            n/=p;
        }
    }
    return counter;
}

int main() {
    int pl=siever();
    int i, n;
    while (cin >> n && n)
    {
        printf("%3d! =",n);
        for (i=0 ; i<pl && list[i]<=n ; i++)
        {
            printf("%3d",test(n,list[i]));
            if (i%14 == 0 && i>0 && list[i+1]<=n) printf("\n%6c",' ');
        }
        printf("\n");
    }
    return 0;
}

[UVa] 11000 - Bee

This is all about careful reading and a very bit of analysis.
First analyze what happens with a Male bee. You'll see every year the number of bees in that tree is a Fibonacci number, since all the past bees are dead by then.
Then for a Female be, it's actually the same, because it gives birth to a Male bee the next year. And since the special bee produces one Male bee each year, so the result is actually the sum of Fibonacci numbers till n.

#include <iostream>
#include <cmath>
using namespace std;
long long sum[100], fibs[100];
int fib( ) {
    int i;
    long long lim = (long long)pow(2.00,32);

    fibs[0]=0LL; sum[0]=0LL;
    fibs[1]=1LL; sum[1]=1LL;
    fibs[2]=1LL; sum[2]=2LL;
    for (i=3 ; sum[i-1]<lim ; i++) {
        fibs[i]=fibs[i-1]+fibs[i-2];
        sum[i]=sum[i-1]+fibs[i];
    }

    return i;
}

int main( ) {
    fib();
    int n;
    while (cin >> n && n>=0)
    {
        cout << sum[n] << " " << sum[n+1] << endl;
    }
    return 0;
}

[UVa] 392 - Polynomial Showdown

Just conditioning, loads of ifs

If you're getting PE or WA just test with some isolated values for different coefficients. Some of my test cases are.

0    0    0    1   22 -333    0    1   -1
0    0    0    0    0    0  -55    5    0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 -1 0
0 0 0 0 0 0 -1 0 0
0 0 0 0 0 -1 0 0 0
0 0 0 0 -1 0 0 0 0
0 0 0 -1 0 0 0 0 0
0 0 -1 0 0 0 0 0 0
0 -1 0 0 0 0 0 0 0
-1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

x^5 + 22x^4 - 333x^3 + x - 1
-55x^2 + 5x
0
-1
-x
-x^2
-x^3
-x^4
-x^5
-x^6
-x^7
-x^8
0

#include <stdio.h>
#include <string.h>

int a[10];

int main()
{
    int i, print, z;
    //freopen("input.txt","r+",stdin);
    //freopen("output.txt","w+",stdout);
    while (scanf("%d %d %d %d %d %d %d %d %d",&a[8],&a[7],&a[6],&a[5],&a[4],&a[3],&a[2],&a[1],&a[0])==9)
    {
        for (i=0, z=1 ; i<9 && z; i++)      //-----|Checking if the
            if (a[i]) z=0;                  //-----|polynomial is zero

        if (z) {                            //-----|The polynomial is found
            printf("0\n");                  //-----|to be zero in fact
            continue;
        }

    //-[ The first value of the equation is not printed yet ]
        print=0;
        for (i=8 ; i>1 ; i--)
        {
            if (print && a[i]) printf(" ");

            if (a[i]==-1)
            {
                (print? printf("- x^%d",i) : printf("-x^%d",i) );
            } else if (a[i]==1)
            {
                (print? printf("+ x^%d",i) : printf("x^%d",i) );
            } else if (a[i]<0)
            {
                (print? printf("- %dx^%d",-1*a[i],i) : printf("%dx^%d",a[i],i) );
            } else if (a[i])
            {
                (print? printf("+ %dx^%d",a[i],i) : printf("%dx^%d",a[i],i) );
            }
        //-- [ From the next time a space will seperate characters ]
            if(a[i]) print=1;
        }
        if (a[i])
        {
            if (print && a[i]) printf(" ");
            if (a[i]==-1)
            {
                (print? printf("- x") : printf("-x") );
            } else if (a[i]==1)
            {
                (print? printf("+ x") : printf("x") );
            } else if (a[i]<0)
            {
                (print? printf("- %dx",-1*a[i]) : printf("%dx",a[i]) );
            } else if (a[i])
            {
                (print? printf("+ %dx",a[i]) : printf("%dx",a[i]));
            }
        //-- [ From the next time a space will seperate characters ]
            if(a[i]) print=1;
        }
        i--;
        if (a[i])
        {
            if (print && a[i]) printf(" ");
            if (a[i]<0)
            {
                (print ? printf("- %d",-1*a[i]) : printf("%d",a[i]) );
            } else if (a[i])
            {
                (print ? printf("+ %d",a[i]) : printf("%d",a[i]) );
            }
        }

        printf("\n");
    }
    return 0;
}

IIUC Programmer's ranklist project

One of my fellow ACMers at IIUC (Shimul) is keeping a nice ranklist on his site. But he has to manually update that list every time any one of us solves new problems :P
Keeping that and my practice on Java in mind, I'm building a Ranklist that will update itself.

For this project the tools and resources that I'm using are:
1. Javascript
2. jQuery
3. uHunt API (by Felix Halim)

Since I don't have any knowledge on Java that can really help me right now, I'm learning some Javascript right now. I'll keep updating this post with new progress reports.

[UVa] 10190 - Divide but not quite conquer

Critical point:
If n<2 or m<2, it's "Boring!"
If at some point (n%m != 0), it's "Boring!" to the limit :P
Method:
I store the result in a string (char arrray) when the division is taking place. If the sequence is found to be not boring, print the string.

#include #include <stdio.h>
#include <string.h>

char output[1000000], temp[1000000];
int addStr(char *des, int val, int len)
{

    if (!len)
        sprintf(des,"%d",val);
    else
    {
        int i, j;
        sprintf(temp," %d",val);
        int ln = strlen(temp);
        for (i=len, j=0 ; j<ln ; i++, j++)
        {
            des[i]=temp[j];
        }
        des[i]='\0';
        return (len+j);
    }
    return strlen(des);
}

int main()
{
    int n, m;
    while (scanf("%d %d",&n,&m)==2)
    {
        int lnt = 0;
        int b=0;
        if (n<2 || m<2)
        {
            printf("Boring!\n");
            continue;
        }
        while (n>1)
        {
            lnt=addStr(output,n,lnt);
            if (n%m != 0)
                b=1;
            n/=m;
        }
        lnt=addStr(output,n,lnt);


        if (b)
            printf("Boring!\n");
        else
            printf("%s\n",output);
    }
    return 0;
}

[UVa] 11428 - A Minimum Land Price

#include <stdio.h>
#include <stdlib.h>
typedef long long ll;
ll pr(ll a, ll t)
{
    ll ret=1;
    while (t--)
        ret*=a;
    return ret;
}
ll a[100];
int cmp (const void *a, const void *b)
{
    return *(ll*)b-*(ll*)a;
}
int main()
{
    ll test, i, sum, j;
    scanf("%lld",&test);

    while (test--)
    {
        for (i=0 ; scanf("%lld",&a[i]) && a[i] ; i++);
        qsort(a,i,sizeof(ll),cmp);

        for (sum=0, j=0 ; j<i ; j++ )
        {
            sum += (pr(a[j],j+1));
        }
        sum *= 2;
        if (sum<=5000000)
            printf("%lld\n",sum);
        else
            printf("Too expensive\n");
    }
    return 0;
}

[UVa] 11830 - Contract Revision

#include <stdio.h>
#include <string.h>
char input[100000], pro[100000];
int rmv(char *a, char c)
{
    int i, z, len=strlen(a);

    for (i=0 ; i<len ; i++)
    {
        if (a[i]==c)
            a[i]='\\';
    }
    for (i=0, z=1 ; i<len ; i++)
    {
        if (a[i]!='0' && a[i]!='\\')
            z=0;
        if (!z && a[i]!='\\')
            putchar(a[i]);
    }

    if (z)
        printf("0");
    putchar('\n');
    return 0;
}

int main()
{
    char c;
    while (gets(input))
    {
        if (!strcmp("0 0",input))
            break;
        sscanf(input,"%c %s",&c,pro);

        rmv(pro,c);
    }
    return 0;
}

[UVa] 343 - What base is this?

I was too lazy when I saw this problem for the very first time 2 years ago. Solving problems that required parsing a string were too tedious for me back then. Well, guess what it generated a great code for future problems from this domain.

#include <stdio.h>
#include <math.h>
#include <string.h>
#define isChar(i) ((i>='A'&&i<='Z')||(i>='0'&&i<='9'))
typedef unsigned long long ULL;
int vals[1000];
char input[1000], val1[1000], val2[1000];
ULL getVal(char *a, int base, int ln)
{
    int len = ln, i;
    ULL val=0;
    for (i=len-1 ; i>=0 ; i--)
    {
        val = val + (vals[a[i]]) * (int)pow((double)base,(len-1-i));
    }
    return val;
}

int setVals()
{
    int i;
    for (i=0 ; i<=9 ; i++)
    {
        vals[i+'0'] = i;
    }
    for (i='A' ; i<='Z' ; i++)
    {
        vals[i] = (i-55);
    }
}

int parser(char *a, int *l1, int *l2, int *mb1, int *mb2)
{
    int i, j, min;
    for (i=0 ; !isChar(a[i]) ; i++);
    min=-1;
    for (j=0 ; isChar(a[i]) ; i++, j++)
    {
        val1[j]=a[i];
        if (vals[a[i]]>min)
            min = vals[a[i]];
    }
    val1[j]='\0';
    *l1=j;
    *mb1=min+1;

    for ( ; !isChar(a[i]) ; i++);
    min=-1;
    for (j=0 ; isChar(a[i]) ; i++, j++)
    {
        val2[j]=a[i];
        if (vals[a[i]]>min)
            min = vals[a[i]];
    }
    val2[j]='\0';
    *l2=j;
    *mb2=min+1;
}

int main()
{
    int l1, l2, minb1, minb2, f, i, j;
    setVals();

    while (gets(input))
    {
        parser(input,&l1,&l2,&minb1,&minb2);

        f=0;

        for (i=(minb1>1?minb1:2) ; i<=36 && !f ; i++)
        {
            for (j=(minb2>1?minb2:2) ; j<=36 && !f ; j++)
            {
                if (getVal(val1,i,l1) == getVal(val2,j,l2))
                {
                    printf("%s (base %d) = %s (base %d)\n",val1,i,val2,j);
                    f=1;
                }
            }
        }

        if (!f) printf("%s is not equal to %s in any base 2..36\n",val1,val2);

    }
    return 0;
}

Lucidity

Everything that happens, happens at the mercy of Allah (SWT)
You aren't eligible to be proud, you aren't eligible to be ashamed
What you are eligible is to pray for the best to come
Life is a journey that started with the will of Allah (SWT)
It's a journey on the road selected by Allah (SWT)
It ends with the will of Allah (SWT)
You are not someone who decides what must become of you here.
You think you're in control? Maybe you never even had read this, maybe I never had it written. You just saw this because Allah made you do so :)

Tell me one thing, how do you know you're not in a lucid dream?

Believe what you do

Never hate what you do
Never do what you hate
Today may not be a bad day for you
But cruel are the hands of fate

Alhamdulillah

Maybe I didn't get what I wanted.
Maybe I won't reach what I want from the deepest corner of my heart.
Maybe I'm born to just dream.
Maybe life was never what it seemed.
Maybe I was never to be a leader.
Maybe I'm only to follow others.

But, my friend. God has gifted me with the sweet experiences of loving what He has created.
Of knowing how to want His creation.
How to love His craft.
How to beg for more.
How to keep going back to Him after dreams shatter in front of me.

Alhamdulillah, for each and every moment. Couldn't be any better.

[UVa] 11850 - Alaska

With this, I finish 300 solves in UVa. :) Took too long.
My stats at the moment:

Submissions: 1701
Problems tried: 322
Problems solved: 300
First submission: 2009-11-17
Last submission: 2011-10-21

And details on the last submission:
Problem number: 11850
Rank of solution: 225
Submission number: 9395891
Date: 2011-10-21
Time: 20:54:39
Runtime: 0.008

Method:
1. Take the input and sort the array.
2. Check if between two consecutive stations the distance is > 200. If so IMPOSSIBLE
3. At last she has to go to the destination and come back to the last station, so check if (1422-[last station])X2 > 200.

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}
int miles[4000];
int main()
{
    int n, i, set;
    while (scanf("%d",&n) && n)
    {
        for (i=0 ; i<n ; i++)
            scanf("%d",&miles[i]);
        qsort(miles,n,sizeof(int),cmp);
        set=1;

        for (i=1 ; i<n && set ; i++)
        {
            if (miles[i]-miles[i-1]>200) set=0;
        }
        if (2*(1422-miles[n-1])>200) set=0;
        if (set) printf("POSSIBLE\n");
        else printf("IMPOSSIBLE\n");
    }
    return 0;
}

[UVa] 10432 - Polygon inside a circle

#include <stdio.h>
#include <math.h>
#define PI (2*acos(0))
int main()
{
    double area, r, n;
    while (scanf("%lf %lf",&r,&n)==2)
    {
        area = r*r*sin(2*PI/n)/2.0;
        printf("%.3lf\n",area*n);
    }
    return 0;
}

[UVa] 374 - Big Mod

Used a recursive method from Art of Programming Contest

LL bigMod(LL b, LL p, LL m)
{
    if (!p) return 1;
    else if (!(p&0x01)) return power(bigMod(b,p/2,m),2)%m;
    else return (b%m * bigMod(b,p-1,m))%m;
}

#include <stdio.h>
#define LL long
LL power(LL a, LL p)
{
    int ret=1;
    while (p--)
        ret*=a;
    return ret;
}
LL bigMod(LL b, LL p, LL m)
{
    if (!p) return 1;
    else if (!(p&0x01)) return power(bigMod(b,p/2,m),2)%m;
    else return (b%m * bigMod(b,p-1,m))%m;
}

int main()
{
    LL b, p, m;
    while (scanf("%ld %ld %ld",&b,&p,&m)==3)
    {
       printf("%ld\n",bigMod(b,p,m));
    }
    return 0;
}

[UVa] 11650 - Mirror Clock

Nice and fun! The only tricky case probably is a time that generated 0 hours, just make it 12 but keep the minute same. I don't know if handling for 24 hours time is needed but added that too.

#include <stdio.h>

int main()
{
    int tst, h, m, time;
    scanf("%d",&tst);
    while (tst--)
    {
        scanf("%d:%d",&h,&m);
        time = h*60 + m;
        if (time>720) time-=720;
        time = 720-time;

        h = (time/60);
        m = time%60;

        if (!h) h = 12;

        if (h<10)
            printf("0%d:",h);
        else
            printf("%d:",h);
        if (m<10)
            printf("0%d\n",m);
        else
            printf("%d\n",m);
    }
    return 0;
}

[UVa] 10550 - Combination Lock

#include <stdio.h>

/* Guilty by association */

int main()
{
    int i, a, b, c, deg;
    while (scanf("%d %d %d %d",&i,&a,&b,&c)==4)
    {
        if (!i && !a && !b && !c) break;

        deg = 720+360 + (((a>i?(40-a)+i:(i-a)) + (b<a?(40-a)+b:(b-a)) + (c>b?(40-c)+b:(b-c))))*9;

        printf("%d\n",deg);
    }
    return 0;
}

[UVa] 455 - Periodic Strings

#include <stdio.h>
#include <string.h>
char input[10000];
int finder(char *a)
{
    int len = strlen(a), l, v, i, j;
    char q[100];

    for (l=1 ; l<=(len/2) ; l++)
    {
        for (i=0 ; i<l ; i++)
        {
            q[i]=a[i];
        }
        q[i]='\0';
        v=1;
        for (i=0 ; i<len && v ; i+=l)
        {
            for (j=0 ; j<l && v ; j++)
            {
                if (q[j]!=a[i+j]) v=0;
            }
        }
        if (v) return l;
    }
    return len;

}
int main()
{
    int test, kase=1;
    scanf("%d",&test);
    getchar();
    while (test--)
    {
        gets(input);
        gets(input);
        if (kase++>1) printf("\n");
        printf("%d\n",finder(input));

    }
    return 0;
}

[UVa] 438 - The Circumference of the Circle

Just use the formula here: Circumcenter

#include <stdio.h>
#include <math.h>
#define dis(x1,y1,x2,y2) sqrt(fabs((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)))
#define PI 3.141592653589793
double area(double x1, double y1, double x2, double y2, double x3, double y3)
{
    double a = dis(x1,y1,x2,y2);
    double b = dis(x2,y2,x3,y3);
    double c = dis(x3,y3,x1,y1);



    double s = (a+b+c)/2.0;
    double r = (a*b*c)/sqrt(s*(s-a)*(s-b)*(s-c))/2.0/2.0;
    return (2.0*PI*r);
}

int main()
{
    double x1,y1,x2,y2,x3,y3;

    while (scanf("%lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3)==6)
    {
        printf("%.2lf\n",area(x1,y1,x2,y2,x3,y3));
    }
    return 0;
}

[UVa] 278 - Chess

Analyze all 4 cases and soon you'll equations for all of them. The given advantage is the lower limit of 4. Below that the derived theorems fail.

#include <stdio.h>
#include <string.h>
#define min(a,b) (a<b?a:b)
char inp[100];
int main()
{
    int test, x, y;
    char a;
    scanf("%d",&test);
    getchar();
    while (test--)
    {
        gets(inp);


        sscanf(inp,"%c %d %d",&a,&x,&y);
        if (a=='k')
        {
            printf("%d\n",(x*y+1)/2);
        } else if (a=='K')
        {
            printf("%d\n",((x+1)/2) * ((y+1)/2));
        } else if (a=='Q'||a=='r')
        {
            printf("%d\n",min(x,y));
        }
    }
    return 0;
}

[UVa] 12289 - One-Two-Three

Any efficient you know about? :(

#include <stdio.h>
#include <string.h>

int tester(char *in)
{
    int len = strlen(in), i, f1, f2, f3;

    if (len == 3)
    {
        char one[]="one", two[]="two";
        for (i=0, f1=0, f2=0 ; i<3 ; i++)
        {
            if (one[i]!=in[i]) f1++;
            if (two[i]!=in[i]) f2++;
        }
        if (f1<2) return 1;
        if (f2<2) return 2;

    } else if (len == 5)
    {
        char three[]="three";
        for (i=0, f3=0 ; i<5 ; i++)
        {
            if (three[i]!=in[i]) f3++;
        }
        if (f3<2) return 3;
    }
    return 0;
}

int main()
{
    int test, res;
    char input[100];

    scanf("%d",&test);

    while (test--)
    {
        scanf("%s",input);
        res = tester(input);
        printf("%d\n",res);
    }
    return 0;
}

[UVa] 10862 - Connect the Cable Wires

I found a nice way to treat C Structures as same (almost) as C++ Classes, having functions for their operations. While solving this problem I implemented that.

Method:
Analyze the problem with cases 1, 2, 3, 4 and if needed, 5. You'll soon find out that it's about even positioned Fibonacci numbers.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char res[1000000];
typedef struct bNum
{
    int size;
    char val[2000];
} BigNum;

void setNum(char *val, BigNum *pThis)
{
    strcpy(pThis->val,val);
    pThis->size=strlen(val);
}
char *getNum(BigNum *pThis)
{
    return pThis->val;
}
int addNum(BigNum *p1, BigNum *p2, BigNum *p3)
{
    int i, j, k, car=0, cur;

    for (i=p1->size-1, j=p2->size-1, k=0 ; i>=0 || j>=0 ; i--, j--, k++)
    {
        cur = (i>=0?p1->val[i]:'0') + (j>=0?p2->val[j]:'0') + car - 96;
        if (cur>9)
        {
            car=1;
            res[k]=(cur-10)+'0';
        } else
        {
            car=0;
            res[k]=cur+'0';
        }
    }
    if (car)
    {
        res[k++]='1';
    }
    p3->size=k;
    for (--k, i=0 ; k>=0 ; k--, i++)
    {
        p3->val[i]=res[k];
    }
    p3->val[i]='\0';
}

BigNum fibs[5000];

int main()
{
    int i, n;
    setNum("1",&fibs[1]);
    setNum("1",&fibs[2]);

    for (i=3 ; i<=4001 ; i++)
    {
        addNum(&fibs[i-1],&fibs[i-2],&fibs[i]);
    }

    while (scanf("%d",&n) && n)
    {
        printf("%s\n",getNum(&fibs[2*n]));
    }
    return 0;
}

Some tricks for C/C++

Over the years I've been into coding, I've found many techniques coders use to squeeze out more time out of a program or decrease their coding time. Some of them have been given here, for reference.

Use #define as function:

#define isCaps(i) (i>='A" && i<='Z')
int main()
{
    if (isCaps('S')) printf("S is in Caps\n");
    return 0;
}

Shorten your simple for loops:

#define FOR(i, a, b) for(i=a ; i<b ; i++)
int main()
{
    int i;
    FOR(i, 1, 985)
    {
        printf("%d\n",i);
    }
    return 0;
}

Test whether a number is even or odd:

#define isEven(j) (!(j & 0x01))

Divide a number by 2:

n = n >> 1;

You can find some nice bit tricks in this link. [ Bit twiddling hacks ]
I'll add more when I get these more organized :p.

[UVa] 100 - 3n + 1

I'm currently trying to optimize this code as much as I can. If you have some suggestions please do mail me or post a comment at lest.
Method [On the fly calculation + Memoization]
1. Take input and swap if needed.
2. Then on a loop from the low to the high, call the calculation function for each iteration.
3. In the calculation function, if for some number the value is already available, return right from there. This is done even in the middle of the divide and multiplication iterations.
4. For additional optimizing, I use >> in place of divide by 2.

#include <stdio.h>
#define isEven(j) (!(j & 0x01))
#define SWAP(a,b) {if (b<a) {int t=a; a=b; b=t;}}
int dp[1000000];
int get(int i)
{
    int n, counter;

    counter=1;
    n = i;
    while (n>1)
    {

        if (n<1000000 && dp[n])
        {
            return dp[i]=(counter+=(dp[n]-1));
        }
        counter++;
        if ( isEven(n) )
        {
            n = n >> 1;
        } else
        {
            n = (n*3 + 1) >> 1;
            counter++;
        }
    }
    dp[i]=counter;
    return counter;
}
int pro()
{
    int i, n, counter;
    for (i=1 ; i<=1000000 ; i++)
    {
        counter=1;
        n = i;
        while (n>1)
        {

            if (n<i)
            {
                counter+=(dp[n]-1);
                break;
            }
            counter++;
            if ( isEven(n) )
            {
                n = n >> 1;
            } else
            {
                n = (n*3 + 1) >> 1;
                counter++;
            }
        }
        dp[i]=counter;
    }
    return 0;
}

int main()
{
    int i, a, b, low, high;
    int max;
    while (scanf("%d %d",&a,&b)==2)
    {
        low = a; high=b;
        SWAP(low,high);
        max=-1;
        for (i=low ; i<=high ; i++)
        {
            if (get(i)>max)
                max = dp[i];
        }
        printf("%d %d %d\n",a,b,max);
    }
    return 0;
}

11849 - CD

Based on the given conditions you can have it done with Linear Search. A simpler approach would be to use MAP, give O(nlgn).

#include <stdio.h>
int ar[10000000];
int main()
{
    int i, a, b, counter, val, s, temp, min;
    while (scanf("%d %d",&a,&b)==2)
    {
        if (!a && !b) return 0;
        counter=0;

        for (i=0 ; i<a ; i++)
        {
            scanf("%d",&ar[i]);
        }

        for (i=0, s=0 ; i<b ; i++)
        {
            scanf("%d",&temp);
            for ( ; temp>=ar[s] && s<a ; s++)
            {
                if (ar[s] == temp)
                {
                    counter++;
                    break;
                }
            }
        }
        printf("%d\n",counter);
    }
    return 0;
}