Just another WordPress.com site

 আশা করি বন্ধুরা ভালই আছ । আজকে আমি আলোচনা করব ACM UVA 10642 এর লজিক । সাথে তো আছেই বোনাস হিসেবে Accepted Code .

      1.Transform the grid coordinates into its index… Remember that x and y axis is reversed (see problem description), not like the ordinary Cartesian coordinate.

                              (0,0) index 1
                              (0,1) index 2
                              (1,0) index 3
                                    …
                              and so on

      2.For each coordinate (x,y), the corresponding index is (1+(y+x))*(y+x)/2 + x;

              The Logic for this formula is very simple . Let  (y+x) indicate the layer this coordinate lies…(1 + (y+x)) * (y+x) / 2 is the arithmetic progression formula . finally add the value with x to complete the mapping.

              Remember that since x,y <= 200.000, 200.000 * 200.000 can be bigger than 32-bit int, use long long instead.

 Code :

#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
    int test,i,x1,x2,y1,y2;
    long long int index1,index2;
    cin>>test;

    for(i=1;i<=test;i++)
    {
        cin>>x1>>y1>>x2>>y2;
        index1=y1+x1;
        index1=((1+index1)*index1)/2+x1;
        index2=y2+x2;
        index2=((1+index2)*index2)/2+x2;
        printf(“Case %d: %lld\n”,i,index2-index1);
    }
    return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: