Codechef July 2014 Long Contest - RETPO - reach the point solution

Codechef July 2014 Long Contest - RETPO - reach the point: http://www.codechef.com/JULY14/problems/RETPO

Codechef July 2014 Long Contest - RETPO - reach the point editorial: http://discuss.codechef.com/questions/47238/retpo-editorial

Codechef July 2014 Long Contest - RETPO - reach the point solution: http://ideone.com/gu1gDi

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

int main() {
    int t, x, y;
    long long cnt;
    scanf("%d", &t);
    while(t--) {
        cnt=0;
        scanf("%d%d", &x, &y);
        x=abs(x), y=abs(y);
        while(x>0 && y>0) {
            cnt+=min(x, y), cnt<<=1;
            if(x<y) y-=x, x=0;
            else x-=y, y=0;
        }
        if(x==0 && y>0) {
            if(y%2==0) y<<=1;
            else y<<=1, y--;
            cnt+=y;
        }
        else if(y==0 && x>0) {
            if(x%2==0) x<<=1;
            else x<<=1, x++;
            cnt+=x;
        }
        printf("%lld\n", cnt);
    }
    return 0;
}

Codechef July 2014 Long Contest - CSUB - count substrings solution

Codechef July 2014 Long Contest - CSUB - count substrings: http://www.codechef.com/JULY14/problems/CSUB/

Codechef July 2014 Long Contest - CSUB - count substrings editorial: http://discuss.codechef.com/questions/47237/csub-editorial

Codechef July 2014 Long Contest - CSUB - count substrings solution: http://ideone.com/ET04pJ

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

int main() {
    int t, n;
    long long cnt, r;
    string s;
    scanf("%d", &t);
    while(t--) {
        r=0;
        cnt=0;
        scanf("%d", &n);
        cin>>s;
        for(int i=0; i<s.length(); i++) if(s[i]=='1') cnt++;
        while(cnt>0) r+=cnt, cnt--;
        printf("%lld\n", r);
    }
    return 0;
}

Codechef SUMTRIAN - Sums in a triangle solution

Codechef SUMTRIAN - Sums in a triangle: http://www.codechef.com/problems/SUMTRIAN

Codechef SUMTRIAN - Sums in a triangle editorial: http://discuss.codechef.com/questions/4557/need-guidance-in-sums-in-triangle-problem#4561

Codechef SUMTRIAN - Sums in a triangle solution: http://ideone.com/1Qb7Ce

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

long long int a[105][105]={0};

int main() {
    int n, m;
    scanf("%d", &n);
    while(n--) {
        scanf("%d", &m);
        for(int i=0; i<m; i++) for(int j=0; j<=i; j++) scanf("%lld", &a[i][j]);
        for(int i=m-2; i>=0; i--) for(int j=i; j>=0; j--) {
            if(a[i+1][j+1]>a[i+1][j]) a[i][j]+=a[i+1][j+1];
            else a[i][j]+=a[i+1][j];
        }
        printf("%lld\n", a[0][0]);
        for(int i=0; i<105; i++) for(int j=0; j<105; j++) a[i][j]=0;
    }
    return 0;
}

note: use dp(dynamic programming), start from the right bottom of the triangle, and the loop from right to left. for each specific cell(a[i][j]), try to find which cell, directly below(a[i+1][j]) or directly below and one place to the right(a[i+1][j+1]), is bigger to add to current one(a[i][j]). when all looping and summing up finishes just print the value of top cell(a[0][0]), because that cell will represent the maximum possible sum of triangle.

codechef SAD - gift rift solution

codechef SAD - gift rift: http://www.codechef.com/problems/SAD

codechef SAD - gift rift editorial: http://discuss.codechef.com/questions/1591/sad-editorial

codechef SAD - gift rift solution: http://ideone.com/ZxgVo4

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

int a[105][105];

int main() {
    int r, c, mi, ma, cnt;
    scanf("%d%d", &r, &c);
    for(int i=0; i<r; i++) for(int j=0; j<c; j++) scanf("%d", &a[i][j]);
    for(int i=0; i<r; i++) {
        mi=INT_MAX, ma=INT_MIN;
        for(int j=0; j<c; j++) {
            mi=min(mi, a[i][j]);
        }
        for(int j=0; j<c; j++) {
            if(a[i][j]==mi) {
                cnt=0;
                for(int k=0; k<r; k++) if(mi>=a[k][j]) cnt++;
                if(cnt==r) {printf("%d", mi); return 0;}
            }
        }
    }
    printf("GUESS");
    return 0;
}

note: try this input
2 3
1 1 1
2 2 2

codechef APPROX - approximately solution

codechef APPROX - approximately: http://www.codechef.com/problems/APPROX

codechef APPROX - approximately editorial: http://discuss.codechef.com/questions/7268/approx-editorial

codechef APPROX - approximately solution: http://ideone.com/V5x0Nx

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

int main() {
    int t, k, a, b, c;
    scanf("%d", &t);
    while(t--) {
        a=103993, b=33102;
        scanf("%d", &k);
        printf("%d", a/b);
        c=a/b;
        a=(a-c*b)*10;
        for(int i=1; i<=k; i++) {
            if(i==1) printf(".");
            c=a/b;
            printf("%d", c);
            a=(a-c*b)*10;
        }
        printf("\n");
    }
    return 0;
}

Codechef ANUDTC - Divide the Cake solution

Codechef ANUDTC - Divide the Cake: http://www.codechef.com/problems/ANUDTC

Codechef ANUDTC - Divide the Cake editorial: http://discuss.codechef.com/questions/43059/anudtc-editorial

Codechef ANUDTC - Divide the Cake solution: http://ideone.com/uRDFQe

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

int main() {
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        if(360%n) printf("n ");
        else printf("y ");
        if(360/n<1) printf("n ") ;
        else printf("y ");
        if(n*(n+1)/2>360) printf("n ");
        else printf("y ");
        printf("\n");
    }
    return 0;
}

Codechef ANUUND - Ups and Downs solution

Codechef ANUUND - Ups and Downs: http://www.codechef.com/problems/ANUUND

Codechef ANUUND - Ups and Downs editorial: http://discuss.codechef.com/questions/43062/anuund-editorial

Codechef ANUUND - Ups and Downs solution: http://ideone.com/niVTWv

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

int main() {
    int t, n, a[100005], tmp;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i=0; i<n; i++) scanf("%d", &a[i]);
        sort(a, a+n);
        for(int i=1; i<n; i++) {
            if(i%2==0) {
                tmp=a[i];
                a[i]=a[i-1];
                a[i-1]=tmp;
            }
        }
        for(int i=0; i<n; i++) printf("%d ", a[i]);
        printf("\n");
    }
    return 0;
}

Codechef June 2014 long challenge GUESS - Guessing Game solution

Codechef June 2014 long challenge GUESS - Guessing Game: http://www.codechef.com/JUNE14/problems/GUESS

Codechef June 2014 long challenge GUESS - Guessing Game editorial: http://discuss.codechef.com/questions/44794/guess-editorial

Codechef June 2014 long challenge GUESS - Guessing Game solution: http://ideone.com/PRCoWZ

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

long long int gcd(long long int u, long long int v) {
    if(u==v) return u;
    if(u==0) return v;
    if(v==0) return u;
    if(~u & 1) {
        if(v&1) return gcd(u>>1, v);
        else return gcd(u>>1, v>>1)<<1;
    }
    if(~v & 1) return gcd(u, v>>1);
    if(u>v) return gcd((u-v)>>1, v);
    return gcd((v-u)>>1, u);
}

int main() {
    int t;
    long long int n, m, a, g, cnt, tot;
    scanf("%d", &t);
    while(t--) {
        scanf("%lld%lld", &n, &m);
        a=n/2;
        if(a*2!=n) a++;
        cnt=a*(m/2);
        a=m/2;
        if(a*2!=m) a++;
        cnt+=a*(n/2);
        tot=n*m;
        g=gcd(tot, cnt);
        cnt/=g;
        tot/=g;
        printf("%lld/%lld\n", cnt, tot);
    }
    return 0;
}

note: pay attn to probability of odd number till N or M or whatsoever. that is ceil(N/2). and now, we got how many odd numbers we can have from 1 to N. we know that sum of two odd numbers makes even, to get odd from two sums, one must be odd and the other should be even, like:
odd+odd =even,
even+even= even,
odd + even = odd, and this is what we are looking for.
we apply probability of odd in N * probability of even in M, because for case N = 2, M = 3,

as you see on the image above, the probability of odd in sum of N + M is 3 out of total 6 chances. thats is 3/6, and when fraction them it is 1/2.

codechef June 2014 long challenge - CHEFZOT - chef and subarray solution

codechef June 2014 long challenge - CHEFZOT - chef and subarray: http://www.codechef.com/JUNE14/problems/CHEFZOT/

codechef June 2014 long challenge - CHEFZOT - chef and subarray editorial: http://discuss.codechef.com/questions/44792/chefzot-editorial

codechef June 2014 long challenge - CHEFZOT - chef and subarray solution: 

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

int main() {
    int n, a, cnt=0, max=INT_MIN;
    scanf("%d", &n);
    while(n--) {
        scanf("%d", &a); 
        if(a!=0) cnt++;
        if(cnt>max) max=cnt;
        if(a==0) cnt=0;
    }
    printf("%d", max);
    return 0;
}

Codechef May Challange 2014 OJUMPS - Chef-jumping solution

Codechef May Challange 2014 OJUMPS - Chef-jumping: http://www.codechef.com/MAY14/problems/OJUMPS & http://www.codechef.com/problems/OJUMPS/

Codechef May Challange 2014 OJUMPS - Chef-jumping editorial: http://discuss.codechef.com/questions/42547/ojumps-editorial

Codechef May Challange 2014 OJUMPS - Chef-jumping solution: http://ideone.com/h9JOWO

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

int main() {
    long long int a, b=1;
    scanf("%I64d", &a);
    a%=6;
    while(a>0) {
        a-=b;
        b++;
        if(b==4) b=1;
    }
    if(a==0) printf("yes");
    else printf("no");
    return 0;
}

Codechef April Cook-Off 2014 Snape and Ladder solution

Codechef April Cook-Off 2014 Snape and Ladder: http://www.codechef.com/COOK45/problems/SNAPE/

Codechef April Cook-Off 2014 Snape and Ladder editorial: http://discuss.codechef.com/questions/41500/snape-editorial

Codechef April Cook-Off 2014 Snape and Ladder solution: 

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

int main() {
    int t;
    float b, ls, rs;
    scanf("%d", &t);
    while(t--) {
        scanf("%f%f", &b, &ls);
        rs=sqrt(pow(ls, 2) - pow(b, 2));
        printf("%.6f ", rs);
        rs=sqrt(pow(ls, 2) + pow(b, 2));
        printf("%.6f\n", rs);
    }
    return 0;
}

Codechef April Challenge 2014, Long Contest ADIGIT - "Chef and Digits" solution

Codechef April Challenge 2014, Long Contest ADIGIT - "Chef and Digits": http://www.codechef.com/APRIL14/problems/ADIGIT

Codechef April Challenge 2014, Long Contest ADIGIT - "Chef and Digits" editorial: http://discuss.codechef.com/questions/41182/adigit-editorial

Codechef April Challenge 2014, Long Contest ADIGIT - "Chef and Digits" solution: 

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

int main() {
    int n, m, a[12], b[100005], x, tmp;
    char s[100005];
    for(int i=0; i<12; i++) a[i]=0;
    for(int i=0; i<100005; i++) b[i]=0;
    scanf("%d%d", &n, &m);
    scanf("%s", s);
    for(int i=0; i<n; i++) {
        tmp=s[i]-48;
        a[tmp]++;
        for(int j=0; j<10; j++) b[i]+=(max(j, tmp) - min(j, tmp))*a[j];
    }
    while(m--) {
        scanf("%d", &x);
        printf("%d\n", b[x-1]);
    }
    return 0;
}