AKVQLD03-How to Handle the Fans

How to Handle the Fans

Given below c++ code for akvqld03 spoj or How to Handle the Fans.

This is simple implementation of BIT(binary index tree) . If want to read about this you can

 CLICK HERE

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int MAX=0;
LL a[1000009];

void update(LL a[],int idx,int val)
{
    while(idx <= MAX)
    {
        a[idx]+=val;
        idx+=(idx & -idx);
    }
}
LL query(LL a[],int idx)
{
    LL sum = 0;
    while(idx>0)
    {
        sum+=a[idx];
        idx-=(idx & -idx);
    }
    return sum;
}
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    MAX = n;
    while(q--)
    {
        char s[10];
        int i,j;
        scanf("%s",s);
        if(s[0] == 'f')
        {
            scanf("%d%d",&i,&j);
            printf("%lld\n",query(a,j)-query(a,i-1));
        }
        else{
            scanf("%d%d",&i,&j);
            update(a,i,j);
        }
    }
    return 0;
}

WAYS-PATHS

PATHS

Below given 114 byte c code is for ways spoj or paths spoj.

Here first time i was wondering that this code worked in c . I was thinking this will even not pass compilation but it was running.

f(j){return j<2?2:f(j-1)*(4*j-2)/j;}l="%d\n";main(t,m){for(scanf(l,&t);t--;scanf(l,&m),printf(l,f(m)));return 0;}

CRAN01-An Experiment by Penny

An Experiment by Penny

Below given c++ code is for CRAN01 spoj or An experiment by penny.

Here to find the logic you can test it for some small test by pen & paper. For myself I have checked for approx. 20 test cases then I got the logic .

Logic is maximum corner distance from given point is the minimum time to fill the entire box.

For example I am taking a grid of 7 x 7 and starting position as (4,5).

Here in the above table there are four corners coloured as yellow green black & blue and the starting position is red coloured box. Now the corners coloured with yellow and black are at maximum distances = 7 So here answer will be 7 .I get this logic from observation so if you want to clear your logic please use pen & paper and draw some small test cases or use brute-force.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,x,y;
        scanf("%d%d%d%d",&n,&m,&x,&y);
        int r1,r2,r3,r4,result;
        r1 = abs(x-1) + abs(y-1);
        r2 = abs(x-1) + abs(y-m);
        r3 = abs(x-n) + abs(y-1);
        r4 = abs(x-n) + abs(y-m);
        result = max(r1,max(r2,max(r3,r4)));
        printf("%d\n",result);
    }
    return 0;
}

here also python 2.7 code is for CRAN01 spoj or An experiment by penny.

import sys,math
t=int(sys.stdin.readline())
while t:
    n,m = map(int,sys.stdin.readline().split())
    x,y = map(int,sys.stdin.readline().split())
    r1 = abs(x-1) + abs(y-1)
    r2 = abs(x-1) + abs(y-m)
    r3 = abs(x-n) + abs(y-1)
    r4 = abs(x-n) + abs(y-m)
    result = max(r1,max(r2,max(r3,r4)))
    sys.stdout.write(str(result))
    sys.stdout.write("\n")
    t=t-1