codechef HOTEL - "hotel bytelandia" solution

codechef HOTEL - "hotel bytelandia": http://www.codechef.com/problems/HOTEL

codechef HOTEL - "hotel bytelandia" solution: http://ideone.com/CGE5AA

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int main() {

// your code goes here

int t, n, arr[105], dep[105], hr, count, max;

scanf("%d", &t);

while(t--) {

scanf("%d", &n); hr=0; count=0; max=0;

for(int i=0; i<n; i++) scanf("%d", &arr[i]);

for(int i=0; i<n; i++) scanf("%d", &dep[i]);

while(hr<1005) {

for(int i=0; i<n; i++) {

if(hr==arr[i]) count++; if(count>max) max=count;

if(hr==dep[i]) count--; 

} hr++;

}

printf("%d\n", max);

}

return 0;

}

codechef HOTEL - "hotel bytelandia" guidance:

start from hr=0; increase hour(hr++), if you encounter arrival(arr[i]) then increase guest(count++), if you encounter departure(dep[i]), then decrease guest(count--). meanwhile, keep record of maximum guest number(if(count>max) max=count). print out max.

typedef struct, pointers, qsort and codechef POINTS - "the way to a friends house is never too long" solution

codechef POINTS - "the way to a friends house is never too long": http://www.codechef.com/problems/POINTS

codechef POINTS - "the way to a friends house is never too long" solution: http://ideone.com/zUh4EH

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstdlib>

using namespace std;

int arr[100005][2];

typedef struct A { long long x, y; }; 

int comp(const void *a, const void *b) {

A *i1, *i2;

i1=(A*)a; i2=(A*)b;

if(i1->x > i2->x) return 1;

if(i1->x == i2->x && i1->y < i2->y) return 1;

return 0;

}

int main() {

// your code goes here

int t, n, i;

double dis;

A arr[100005];

scanf("%d", &t);

while(t--) {

scanf("%d", &n); 

for(i=0; i<n; i++) cin>>arr[i].x>>arr[i].y;

qsort(arr, n, sizeof(A), comp);

dis=0;

for(i=1; i<n; i++) dis=dis+sqrt((arr[i].x-arr[i-1].x)*(arr[i].x-arr[i-1].x)+(arr[i].y-arr[i-1].y)*(arr[i].y-arr[i-1].y));

printf("%.2f\n", dis);

}

return 0;

}

typedef struct, pointers, qsort and codechef POINTS - "the way to a friends house is never too long" guidance:

in this problem a newbie coder has to look at sorting(qsort here): http://stackoverflow.com/questions/1787996/c-library-function-to-do-sort

here is also some qsort c++ explained: http://www.cplusplus.com/reference/cstdlib/qsort/

c pointers in wiki: http://en.wikipedia.org/wiki/Pointer_(computer_programming)

typedef struct c: http://en.wikipedia.org/wiki/Struct_(C_programming_language)

and after glancing all the links above, the coder would understand the above problems solutions

codechef MARCHA2 - "johnny and the beanstalk" solution

codechef MARCHA2 - "johnny and the beanstalk": http://www.codechef.com/problems/MARCHA2

codechef MARCHA2 - "johnny and the beanstalk" solution: http://ideone.com/MCNevO

#include <iostream>

#include <cstdio>

using namespace std;

int main() {

// your code goes here

int t, k, a, b, flag;

scanf("%d", &t);

while(t--) {

scanf("%d", &k);

b=1; flag=0;

while(k--) {

scanf("%d", &a); if(a>b) {

flag++; break;

} b=(b-a)*2;

}

if(flag || b) printf("No\n");

else printf("Yes\n");

}

return 0;

}

codechef MARCHA2 - "johnny and the beanstalk" guidance: 

from tutorial: http://www.codechef.com/wiki/tutorial-johnny-and-bean-stalk

Approach-1 (Lowest to highest level):

1.  The number of leaves on every level is at most the number of stems brought over from the previous level.

2.  The tree will stop growing once there are no more stems.  At the last level the number of stems is zero (they should all be leaves).

1st case: if(a>b) {

flag++; break;

}
2nd case: b=(b-a)*2; b=0;

codechef CARVANS - "carvans" solution

codechef CARVANS - "carvans": http://www.codechef.com/problems/CARVANS

codechef CARVANS - "carvans" solution: http://ideone.com/6jhSPA

#include <iostream>

#include <cstdio>

using namespace std;

int main() {

// your code goes here

int t, n, k, temp, count;

scanf("%d", &t);

while(t--) {

scanf("%d", &n);

count=0;

for(int i=0; i<n; i++) {

scanf("%d", &k); if(i==0) temp=k;

if(k<=temp) {

temp=k; count++;

}

}

cout<<count<<endl;

}

return 0;

}

codechef COMM3 - "three way communications" solution

codechef COMM3 - "three way communications": http://www.codechef.com/problems/COMM3

codechef COMM3 - "three way communications" solution: http://ideone.com/lDQrrt

#include <iostream>

using namespace std;

int main() {

// your code goes here

int t, r, x1, x2, x3, y1, y2, y3, count;

cin>>t;

while(t--) {

cin>>r>>x1>>y1>>x2>>y2>>x3>>y3;

count=0;

if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=r*r) count++;

if((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3)<=r*r) count++;

if((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1)<=r*r) count++;

if(count>1) cout<<"yes"<<endl;

else cout<<"no"<<endl;

}

return 0;

}

codechef LECANDY - "little elephant and candies" solution

codechef LECANDY - "little elephant and candies": http://www.codechef.com/problems/LECANDY

codechef LECANDY - "little elephant and candies" solution: http://ideone.com/9WVsf3

#include <iostream>
using namespace std;

int main() {
// your code goes here
int t, n, c, ak, i;
cin>>t;
while(t--) {
cin>>n>>c;
ak=0;
while(n--) { cin>>i; ak=ak+i; }
if(ak<=c) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}

codechef J7 - "the best box" guidance and solution

codechef J7 - "the best box": http://www.codechef.com/problems/J7

codechef J7 - "the best box" solution: http://ideone.com/6fldJE

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

int main() {
// your code goes here
double t, p, s;
cin>>t;
while(t--) {
cin>>p>>s;
cout<<fixed<<setprecision(2)<<(pow((p-(sqrt(pow(p, 2)-(24*s))))/12, 2)*((p/4)-(2*((p-(sqrt(pow(p, 2)-(24*s))))/12))))<<endl;
}
return 0;
}

codechef J7 - "the best box" guidance: 

- to get optimal maximum size: (special thanks to falcon - Sahin Mammadov)

suppose we have 2 functions "a" & "b". function "f(x)=a*b" and constant "c=a+b". b=c-a, from that f(x)=a*b, f(x)=a*(c-a)=a*c-a**2. to get that functions maximum, we get their derivatives(look at images below).

maximum function

max and min function

and after derivative f '(x)=c-2*a=0, a=c/2, b=c-a=c-(c/2)=c/2. so from the equation there we understand that to get optimal maximum "a" and "b" needs to be equal.

- calculation of volume of rectangle, given surface area and perimeter:

suppose all sides are not equal: P(perimeter)=4*(a+b+c), S(surface area)=2*a*b+2*a*c+2*b*c and V(volume)=a*b*c. but on the above calculation i've shown that at least two sides needs to be equal to get optimal maximum. so,  a=b, (but here i will put "b" intsead of "c") P(perimeter)=4*(a+a+b), S(surface area)=2*a*a+2*a*b+2*a*b and V(volume)=a*a*b.

next step, P/4=2*a+b, S=2*a**2+4*a*b
take square of P/4 side: (P/4)**2=(2*a+b)**2=4*a**2+4*a*b+b**2=2*a**2+4*a*b+2*a**2+b**2=S+2*a**2+b**2;
(P/4)**2=S+2*a**2+b**2;
next step, P/4=2*a+b, from there P/4-2*a=b.
and then put P/4-2*a instead of b at the equation above: (P/4)**2=S+2*a**2+(P/4-2*a)**2.
from there we get: 6*a**2-P*a+S=0;
and now apply discrimination formula(shown below): a1,a2=(P+-sqrt(P**2-24*S))/12;

discrimination

and after all, we apply a1,a2 to "b" and "V"(volume):
V=a**2*b, P/4-2*a=b;
V=((P+-sqrt(P**2-24*S))/12)**2*b =
   =((P+-sqrt(P**2-24*S))/12)**2 * P/4-2*a
   =((P+-sqrt(P**2-24*S))/12)**2 * P/4-2*((P+-sqrt(P**2-24*S))/12);

but i actually printed out, ((P-sqrt(P**2-24*S))/12) instead of ((P+sqrt(P**2-24*S))/12), and got AC, dont know why. (it would be nice if you rectify me)

and also to print out 2 digits after ","(comma) use
#include <iomanip>
and cout<<fixed<<setprecision(2)<<etc.

thanks. any cooperation will be appreciated

NOTE: "x**2" means pow(x, 2), x power of 2

codechef GCD2 - "gcd2" guidance and solution

codechef GCD2 - "gcd2": http://www.codechef.com/problems/GCD2

codechef GCD2 - "gcd2" solution: http://ideone.com/sNmT36

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

char arr[255];

int mod(int a) {
int c=0;
for(int i=0; i<strlen(arr); i++) c=((arr[i]-'0')+c*10)%a;
return c;
}

int gcd(int a, int b) {
if(b==0) return a;
else return gcd(b, a%b);
}

int main() {
// your code goes here
int n, a;
cin>>n;
while(n--) {
cin>>a>>arr;
if(a==0) cout<<arr<<endl;
else {
int d=mod(a);
cout<<gcd(a, d)<<endl;
}
}
return 0;
}

codechef GCD2 - "gcd2" guidance: 

look for ASCII codes - http://en.wikipedia.org/wiki/ASCII, there '0' starts with 48. so when getting character arr[i] just arr[i]-'0' or arr[i]-48 to get 0 as a result.
and pay attention to mod, hope this helps: http://discuss.codechef.com/questions/2475/gcd2-problem-easy

here is my draft to get "B" as a string array, on my draft i used ".size()" to get size; however, on the above code i used "strlen": http://ideone.com/E6dp20
#include <iostream>
#include <cstring>
using namespace std;

int main() {
// your code goes here
int b=0, c;
string a;
cin>>a>>c;
for(int i=0; i<a.size(); i++) {b=b*10+a[i]-48; if(b>c) b=b%c;}
cout<<b<<endl<<a.size();
return 0;
}

codechef VOTERS - "discrepancies in the voters list" solution

codechef VOTERS - "discrepancies in the voters list": http://www.codechef.com/problems/VOTERS

codechef VOTERS - "discrepancies in the voters list" solution: http://ideone.com/Y5Wz76

#include <iostream>
using namespace std;

int main() {
// your code goes here
long long n1, n2, n3, arr[1000000], k, count=0, n;
cin>>n1>>n2>>n3; n=n1+n2+n3;
for(int i=0; i<1000000; i++) arr[i]=0;
while(n--) {cin>>k; arr[k]++;}
for(int i=0; i<1000000; i++) if(arr[i]>1) count++;
cout<<count<<endl;
for(int i=0; i<1000000; i++) if(arr[i]>1) cout<<i<<endl;
return 0;
}

codechef VOTERS - "discrepancies in the voters list" guidance: 

assume the every ID in the list ranges 0<ID<1000000. and also dont forget that not 0<ID<50000, it is 0<n1<50000, 0<n2<50000 and 0<n3<50000. imho, that is all

codechef PCYCLE - "permutation cycles" solution

codechef PCYCLE - "permutation cycles": http://www.codechef.com/problems/PCYCLE

codechef PCYCLE - "permutation cycles" solution: http://ideone.com/7JzmTr

#include <iostream>
using namespace std;

int main() {
// your code goes here
int n, arr[1005], a, b[2005], count=0;
cin>>n;
for(int i=1; i<=n; i++) cin>>arr[i];
for(int i=1; i<=2005; i++) b[i]=true;
for(int i=1; i<=n; i++) {
if(b[i]) {
count++;
b[i]=false; a=arr[i];
while(a!=i) {b[a]=false; a=arr[a];}
}
}
cout<<count<<endl;
for(int i=1; i<=2005; i++) b[i]=true;
for(int i=1; i<=n; i++) {
if(b[i]) {
cout<<i<<" "; b[i]=false; a=arr[i]; cout<<a;
while(a!=i) {b[a]=false; a=arr[a]; cout<<" "<<a;}
cout<<endl;
}
}
return 0;
}

codechef PCYCLE - "permutation cycles" guidance: 

take an boolean array b[2005], initialize to true all indice of b[]. start from i=1 and go to the last index(here n). make it false(b[i]=false). set a=arr[i], and loop it with while(a!=i). here we use "a" just to represent the value of index "i". everytime you encounter b[i]==true, increase counter(count++). at the end print out it(cout<<count). and then again from beginning print out the rest of array, with endlines or spaces when necessary.

codechef MUFFINS3 - "packaging cupcakes" solution

codechef MUFFINS3 - "packaging cupcakes": http://www.codechef.com/problems/MUFFINS3

codechef MUFFINS3 - "packaging cupcakes" solution: http://ideone.com/1yBjTS
#include <iostream>
using namespace std;

int main() {
// your code goes here
int t, n;
cin>>t;
while(t--) {
cin>>n;
cout<<n/2+1<<endl;
}
return 0;
}

codechef MAXCOUNT - "count of maximum" solution

codechef MAXCOUNT - "count of maximum": http://www.codechef.com/problems/MAXCOUNT

my c++ solution to codechef MAXCOUNT - "count of maximum": http://ideone.com/IZ573R
#include <iostream>
using namespace std;

int main() {
// your code goes here
int t, n, b, index, arr[10005], max, temp;
cin>>t;
while(t--) {
cin>>n; b=n;
for(int i=0; i<10005; i++) arr[i]=0; max=0;
while(b--) {
cin>>index; arr[index]++;
}
for(int i=0; i<10005; i++) {
if(arr[i]>max) {
max=arr[i]; temp=i;
}
}
cout<<temp<<" "<<max<<endl;
}
return 0;
}

codechef CIELRCPT - "ciel and receipt" problem solution

codechef CIELRCPT - "ciel and receipt" problem: http://www.codechef.com/problems/CIELRCPT

my c++ solution to codechef CIELRCPT - "ciel and receipt" problem: http://ideone.com/9pmILI
#include <iostream>
#include <cmath>
using namespace std;

int main() {
// your code goes here
int t, p, arr[12], count;
for(int i=0; i<12; i++) arr[i]=pow(2, i);
cin>>t;
while(t--) {
count=0;
cin>>p;
while(p>0) {
for(int i=11; i>=0; i--) {
if(p>=arr[i]) {
p=p-arr[i]; count++; i++;
}
}
}
cout<<count<<endl;
}
return 0;
}

note on my code: initialize the array of power 2, starting from 0 goes to 11. after getting p, starting from the maximum value of array(here 2048, index is arr[11]=2048) and check if p is equal to or greater than that value. if so, p=p-arr[i], count++. i also increased i++ so that continues from the index last visited. thnx

codechef CANDLE - "birthday candles" problem guidance and solution

codechef CANDLE - "birthday candles" problem: http://www.codechef.com/problems/CANDLE

editorial: http://discuss.codechef.com/questions/4212/candle-editorial

my c++ solution to codechef CANDLE - "birthday candles" problem: http://ideone.com/IdZCJD
#include <iostream>
using namespace std;

int main() {
// your code goes here
int t, arr[10], minVal, minVal2, minIndex, minIndex2;
cin>>t;
while(t--) {
minVal=15; minVal2=15; minIndex=-1; minIndex2=-1;
for(int i=0; i<10; i++) {
cin>>arr[i];
if(arr[i]<minVal) {
minVal=arr[i]; minIndex=i;
}
else if(arr[i]<minVal2 && i!=0) {
minVal2=arr[i]; minIndex2=i;
}
}
if(minIndex!=0) for(;minVal>=0; minVal--) cout<<minIndex;
else if(minVal==minVal2) for(;minVal2>=0; minVal2--) cout<<minIndex2;
else {
cout<<1; for(;minVal>=0; minVal--) cout<<minIndex;
}
cout<<endl;
}
return 0;
}

codechef CANDLE - "birthday candles" problem guidance: (or note on my code): if there was no zero index, or value for zero then we would not be having any confusion and it would be ok if we just printed out the minimum value's index. so lets take 2 minimum values and their indices. minVal and minIndex registers the minimum value and its index, while minVal2 and minIndex2 registers the minimum value other than 0(zero). if minVal's index(minIndex) is not zero then we just print out minIndex and that is ok. however, if minVal's index(minIndex) is zero, then we check if there any other value that equals to zero index's value(in this case, minVal) - checking process: if(minVal==minVal2), if yes, then print out minVal2's index(minIndex2). else if minVal is the least value in the array and index is 0(minIndex=0) then print out 1(because of decimal order. zero itself does not have any meaning) and then print 0 till zero index's value becomes lesser than zero.(for(;minVal>=0; minVal--) cout... stuff). thnx

codechef CIELAB - "Ciel and A-B Problem" solution

codechef CIELAB - "Ciel and A-B Problem": http://www.codechef.com/problems/CIELAB

my c++ solution to codechef CIELAB - "Ciel and A-B Problem": http://ideone.com/zPkaCz
#include <iostream>
using namespace std;

int main() {
// your code goes here
int a, b;
cin>>a>>b;
if((a-b)%10==9) cout<<(a-b)-1;
else cout<<(a-b)+1;
return 0;
}

C/C++ bitwise operators, gcd(greatest common divisor) algorithm, codechef RECIPE - "cutting recipe" problem guidance and solution

codechef RECIPE - "cutting recipe" problem: http://www.codechef.com/problems/RECIPE

guidance: http://discuss.codechef.com/questions/4201/recipe-editorial

imho, we(including myself) have to learn Euclid's algorithm: http://en.wikipedia.org/wiki/Euclid%27s_algorithm
and there they talk of bitwise operators -  "<<", ">>",  "->", "&" and "XOR", stuff which i havent learnt yet. so, lets begin with that "<<", ">>" - left shift and right shift in C/C++ languages. for them have a look at:
1 - http://en.wikipedia.org/wiki/Bitwise_operations_in_C
2 - http://publib.boulder.ibm.com/infocenter/comphelp/v8v101/index.jsp?topic=%2Fcom.ibm.xlcpp8a.doc%2Flanguage%2Fref%2Fbitshe.htm
3 - http://www.c4learn.com/c-programming/c-bitwise-right-shift/
4 - http://www.cprogramming.com/tutorial/bitwise_operators.html
now, i suppose you have learnt C/C++ bitwise operators and lets move on to Euclidean or gcd(greatest common divisor) algorithm. i liked binary gcd algorithm much, here it is: http://en.wikipedia.org/wiki/Binary_GCD_algorithm

my c++ solution to codechef RECIPE - "cutting recipe" problem: http://ideone.com/m3Lebc
#include <iostream>
#include <algorithm>
using namespace std;

unsigned int gcd(unsigned int u, unsigned int v)
{
    // simple cases (termination)
    if (u == v)
        return u;

    if (u == 0)
        return v;

    if (v == 0)
        return u;

    // look for factors of 2
    if (~u & 1) // u is even
    {
        if (v & 1) // v is odd
            return gcd(u >> 1, v);
        else // both u and v are even
            return gcd(u >> 1, v >> 1) << 1;
    }

    if (~v & 1) // u is odd, v is even
        return gcd(u, v >> 1);

    // reduce larger argument
    if (u > v)
        return gcd((u - v) >> 1, v);

    return gcd((v - u) >> 1, u);
}

int main() {
int t, n, arr[50], cmmn, yes;
cin>>t;
while(t--) {
cin>>n;
for(int i=0; i<n; i++) cin>>arr[i];
cmmn=1005; yes=1;
for(int i=1; i<n; i++) if(gcd(arr[0], arr[i])<cmmn) cmmn=gcd(arr[0], arr[i]);
for(int i=0; i<n; i++) if(cmmn!=arr[i]) yes=0;
if(yes) for(int i=0; i<n; i++) cout<<1<<" ";
else if(cmmn==1) for(int i=0; i<n; i++) cout<<arr[i]<<" ";
else for(int i=0; i<n; i++) cout<<(arr[i]/cmmn)<<" ";
cout<<endl;
}
return 0;
}

note on  my code: the gcd block is taken from wiki url i have shown above. and main block is my c++ code. i initialised arr of 50 ingredients and saved ingredients in it. and then i have taken cmmn - the greatest common divisor for ingredients in the array. if cmmn==1 then the array has no gcd, so i just printed out the arr itself. if cmmn is equal to ingredients of arr then yes==1, which means that all ingredients in the arr are same numbers,  for ex 4 as given in the codechef sample output, if so i printed out 1 for every ingredient of  arr. and if there exist gcd(here cmmn) other than 1 and ingredints itself, then print out arr[i]/cmmn. that is it.

NOTE: i still have difficulty in understanding the binary gcd algo. can anyone pls post the easier way to learn binary gcd algo. tnx

codechef CLEANUP - "cleaning up" problem guidance and solution

codechef CLEANUP - "cleaning up" problem: http://www.codechef.com/problems/CLEANUP

guidance: http://discuss.codechef.com/questions/4241/cleanup-editorial

my c++ solution to codechef CLEANUP - "cleaning up" problem: http://ideone.com/4SDbhv
#include <iostream>
using namespace std;

int main() {
// your code goes here
int t, m, n, job[1002], k, a=1, count;
cin>>t;
while(t--) {
cin>>m>>n;
for(int i=0; i<1002; i++) job[i]=false;
for(int i=1; i<=m; i++) job[i]=true;
for(int i=1; i<=n; i++) {
cin>>k; job[k]=false;
}
for(int i=1, count=1; i<=m; i++) {
if(job[i]&&(count%2)) cout<<i<<" ";
if(job[i]) count++;
}
cout<<endl;
for(int i=1, count=1; i<=m; i++) {
if(job[i]&&(count%2==0)) cout<<i<<" ";
if(job[i]) count++;
}
cout<<endl;
}
return 0;
}

codechef NUKES - "nuclear reactors" problem guidance and solution

codechef NUKES - "nuclear reactors" problem: http://www.codechef.com/problems/NUKES

guidance: http://www.youtube.com/watch?v=5sS7w-CMHkU

suppose input:
25 4 4
that means A=25(bombarded particles), N=4(capacity of chamber), K=4(number of chambers)
step-by-step illustration of chambers with consisting particles in it:
1: 1 0 0 0
2: 2 0 0 0
3: 3 0 0 0
4: 4 0 0 0
5: 0 1 0 0
6: 1 1 0 0
7: 2 1 0 0
8: 3 1 0 0
9: 4 1 0 0
10: 0 2 0 0
11: 1 2 0 0
12: 2 2 0 0
13: 3 2 0 0
14: 4 2 0 0
15: 0 3 0 0
16: 1 3 0 0
17: 2 3 0 0
18: 3 3 0 0
19: 4 3 0 0
20: 0 4 0 0
21: 1 4 0 0
22: 2 4 0 0
23: 3 4 0 0
24: 4 4 0 0
25: 0 0 1 0


my c++ solution to codechef NUKES - "nuclear reactors" problem: http://ideone.com/7omT5g
#include <iostream>
using namespace std;

int main() {
// your code goes here
int a, n, k;
cin>>a>>n>>k;
while(k--) {
cout<<a%(n+1)<<" "; a=a/(n+1);
}
return 0;
}

codechef EASYPROB - "easy problem" solution

codechef EASYPROB - "easy problem": http://www.codechef.com/problems/EASYPROB/

my c++ solution to codechef EASYPROB - "easy problem": http://ideone.com/7upexe
#include<stdio.h>
int main()
{
printf("137=2(2(2)+2+2(0))+2(2+2(0))+2(0)\n");
printf("1315=2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)\n");
printf("73=2(2(2)+2)+2(2+2(0))+2(0)\n");
printf("136=2(2(2)+2+2(0))+2(2+2(0))\n");
printf("255=2(2(2)+2+2(0))+2(2(2)+2)+2(2(2)+2(0))+2(2(2))+2(2+2(0))+2(2)+2+2(0)\n");
printf("1384=2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2)+2(2(2)+2(0))+2(2+2(0))\n");
printf("16385=2(2(2+2(0))+2(2)+2)+2(0)\n");
return 0;
}

my draft to get log2 of the numbers:
http://ideone.com/3AcHkc
#include <iostream>
#include <math.h>
using namespace std;

int main() {
// your code goes here
int a, b, arr[17], temp[17];
cin>>a; b=a;
for(int i=0; i<17; i++) {
arr[i]=pow(2, i);
}
for(int j=16; b>0; j--) {
while(b>=arr[j]) {
temp[j]=log2(arr[j]); b=b-arr[j];
cout<<temp[j]<<" "<<arr[j]<<" "<<b<<endl;
}
}
return 0;
}

codechef DOUBLE - double strings solution

codechef DOUBLE - double strings: http://www.codechef.com/problems/DOUBLE/

editorial: http://discuss.codechef.com/questions/3696/double-editorial

my c++ solution to codechef DOUBLE - double strings: http://ideone.com/7Yh2kB
#include <iostream>
using namespace std;

int main() {
// your code goes here
int a, b;
cin>>a;
while(a--) {
cin>>b;
if(b%2) cout<<b-1<<endl;
else cout<<b<<endl;
}
return 0;
}

my codechef PRPALIN - "prime palindromes" guidance and solution

codechef PRPALIN - "prime palindromes": http://www.codechef.com/problems/PRPALIN

PRIMES SECTION:

to understand the logic of prime no's, here is the illustrated sieve of Eratosthenes: http://www.algolist.net/Algorithms/Number_theoretic/Sieve_of_Eratosthenes

sieve of Sundaram explained in an easy way: http://plus.maths.org/content/sundarams-sieve

Atkin, Eratosthenes & Sundaram algorithms are compared, written in C#: http://www.codeproject.com/Articles/490085/Eratosthenes-Sundaram-Atkins-Sieve-Implementation

Eratosthenes & Sundaram algorithms coded, and Sundaram's validity explained: http://luckytoilet.wordpress.com/?s=sundara

my c++ code of sieve of Eratosthenes: http://ideone.com/exSigi

#include <iostream>

using namespace std;

int main() {

// your code goes here

int arr[1003003], i, j;

for(int k=0; k<1003003; k++) arr[k]=true;

arr[0]=arr[1]=false;

for(i=2; i*i<=1003003; i++) {

if(!arr[i]) continue; //doesnt execute the inner loop if "i" is

for(j=i*i; j<=1003003; j=j+i) { // false, or not prime

arr[j]=false; //all multiples of "i" are assigned "false", or not prime

}

}

return 0;

}

PALINDROMES SECTION:

my c++ code for palindromes: http://ideone.com/I75EIf
#include <iostream>
using namespace std;

int main() {
// your code goes here
int a, b=0, i;
cin>>a;
i=a;
while(i>0) {
b=b*10+i%10;
i=i/10;
}
return 0;
}


my c++ SOLUTION to codechef PRPALIN - "prime palindromes": http://ideone.com/iBmV4l
#include <iostream>
using namespace std;

bool pal(int n) {
int p, q=0;
p=n;
while(p>0) {
q=q*10+p%10;
p=p/10;
}
if(q==n) return true;
else return false;
}

int main() {
// your code goes here
int a, arr[1005000], b;
cin>>a; b=a;
for(int k=0; k<1005000; k++) arr[k]=true;
arr[0]=arr[1]=false;
for(int i=2; i*i<1005000; i++) {
if(!arr[i]) continue;
for(int j=i*i; j<1005000; j=j+i) {
arr[j]=false;
}
}
for(b=a;;b++) {
if(arr[b] && pal(b)) {
cout<<b; break;
}
}
return 0;
}

codechef MARCHA1 - "paying up" guidance and solution

codechef MARCHA1 - "paying up": http://www.codechef.com/problems/MARCHA1

tutorial: http://www.codechef.com/wiki/tutorial-paying

subset sum problem explained in dp(dynamic programming): http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/

rutgers university algo for subset sum problem: http://crab.rutgers.edu/~guyk/ex/part.pdf

reduction of subset-sum-optimization to subset-sum-decision(washington university):  http://courses.cs.washington.edu/courses/csep521/05sp/lectures/sss.pdf

carnegie-mellon courtesy, subset-sum and knapsack explained: http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/subsetsum.pdf

i suggest to have a look at MIT knapsack recitation: http://www.youtube.com/watch?v=wFP5VHGHFdk

subset sum(backtracking) video: http://www.youtube.com/watch?v=WRT8kmFOQTw

my c++ solution to codechef MARCHA1 - "paying up" problem: http://ideone.com/p04R4k

// A recursive solution for subset sum problem
#include <stdio.h>
#include <iostream>
using namespace std;
// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
//cout<<set[n]<<" "<<n<<" "<<sum<<endl; i've printed it to learn what my code is doing
   // Base Cases
   if (sum == 0)
     return true;
   if (n == 0 && sum != 0)
     return false;

   // If last element is greater than sum, then ignore it
   if (set[n-1] > sum)
     return isSubsetSum(set, n-1, sum);

   /* else, check if sum can be obtained by any of the following
      (a) including the last element
      (b) excluding the last element   */
   return isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1]);
}

// Driver program to test above function
int main()
{
  int set[100];
  int sum;
  int a, b;
  //int n = sizeof(set)/sizeof(set[0]);
  cin>>a;
  for(int z=0; z<a; z++) {
  int n;
  cin>>n>>sum;
  for(int k=0; k<n; k++) cin>>set[k];
  if (isSubsetSum(set, n, sum) == true)
     printf("Yes\n");
  else
     printf("No\n");
  }
  return 0;
}

NOTE: to be honest, i myself don't have any idea about what my code is doing. i havent understood the topic yet, so i appreciate any guiding comments. thnx

codechef COOLING - Cooling Pies solution

problem: http://www.codechef.com/problems/COOLING/

editorial: http://discuss.codechef.com/questions/4211/cooling-editorial

EXPLANATION

The following greedy algorithm always finds the optimum answer:

• Choose the lightest pie not yet on a rack
• If none of the remaining racks can hold this pie, stop
• Of all the racks that can hold this pie, place the pie on the rack with the smallest weight limit
• If there are no more pies, stop. Otherwise, go back to step 1

my (copied) c++ solution to codechef COOLING - Cooling Pies: http://ideone.com/cQAzcX

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

int main() {
// your code goes here
int a, b, i, j, weigh[35], limt[35], count;
cin>>a;
while(a--) {
cin>>b;
count=0;
for(i=0; i<b; i++) cin>>weigh[i];
for(j=0; j<b; j++) cin>>limt[j];
std::stable_sort(weigh, weigh+b);
std::stable_sort(limt, limt+b);
for(i=0, j=0; i<b && j<b; i++) {
while(j<b && weigh[i]>limt[j]) {
j++;
}
if(j<b) {
count++; j++;
}
}
cout<<count<<endl;
}
return 0;
}

NOTE: in my opinion, it would be nice if you count++ inversely. assume weight is X, and limit is Y func respectively. we have(or reach) our desired count++ when Y's element is bigger than or equal to X's particular element. and in that condition we count++. otherwise, we just pass onto Y's next element, till we meet the condition.

codechef NUMGAME - yet another number game solution

http://www.codechef.com/problems/NUMGAME/

my c++ solution to codechef NUMGAME - yet another number game: http://ideone.com/L7cjyb

#include <iostream>
using namespace std;

int main() {
// your code goes here
int a, b;
cin>>a;
while(a--) {
cin>>b;
if(b%2) cout<<"BOB"<<endl;
else cout<<"ALICE"<<endl;
}
return 0;
}

NOTE: imho, you should focus on divisor, the least possible divisor(here 1) so that rounds take longer, and chances of player get maximized

my c++ solution to codechef TLG - The Lead Game problem

codechef TLG - The Lead Game problem: http://www.codechef.com/problems/TLG/

The Lead Game

All submissions for this problem are available.

The game of billiards involves two players knocking 3 balls around
on a green baize table. Well, there is more to it, but for our
purposes this is sufficient.

The game consists of several rounds and in each round both players
obtain a score, based on how well they played. Once all the rounds
have been played, the total score of each player is determined by
adding up the scores in all the rounds and the player with the higher
total score is declared the winner.

The Siruseri Sports Club organises an annual billiards game where
the top two players of Siruseri play against each other. The Manager
of Siruseri Sports Club decided to add his own twist to the game by
changing the rules for determining the winner. In his version, at the
end of each round the leader and her current lead are calculated. Once
all the rounds are over the player who had the maximum lead at the
end of any round in the game is declared the winner.

Consider the following score sheet for a game with 5 rounds:

    Round     Player 1       Player 2

      1             140                 82
      2              89                 134 
      3              90                 110 
      4              112              106
      5              88                  90 

The total scores of both players, the leader and the lead after
each round for this game is given below:

    Round      Player 1       Player 2     Leader     Lead

      1               140             82        Player 1     58
      2               229            216       Player 1     13
      3               319            326       Player 2      7
      4               431            432       Player 2      1
      5               519            522       Player 2      3

The winner of this game is Player 1 as he had the maximum lead (58
at the end of round 1) during the game.

Your task is to help the Manager find the winner and the winning
lead. You may assume that the scores will be such that there will
always be a single winner. That is, there are no ties.

Input

The first line of the input will contain a single integer N (N
≤ 10000) indicating the number of rounds in the game. Lines
2,3,...,N+1 describe the scores of the two players in the N rounds.
Line i+1 contains two integer Si and Ti, the scores of the Player 1
and 2 respectively, in round i. You may assume that 1 ≤ Si ≤
1000 and 1 ≤ Ti ≤ 1000.

Output

Your output must consist of a single line containing two integers
W and L, where W is 1 or 2 and indicates the winner and L is the
maximum lead attained by the winner.

Example

Input:

5
140 82
89 134
90 110
112 106
88 90

Output:

1 58

---

Author:	admin
Tags	admin
Date Added:	28-07-2009
Time Limit:	1 sec
Source Limit:	50000 Bytes
Languages:	ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.8.1, CPP11, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC

my c++ solution to codechef TLG - The Lead Game problem: http://ideone.com/yiqBAr

#include <iostream>

using namespace std;

int main() {

// your code goes here

int a, b, c, diff, max=0, winner, temp, sc_1=0, sc_2=0;

cin>>a;

while(a--) {

cin>>b>>c;

sc_1=sc_1+b;

sc_2=sc_2+c;

if(sc_1>sc_2) {

diff=sc_1-sc_2; temp=1;

}

else {

diff=sc_2-sc_1; temp=2;

}

if(diff>max) {

max=diff; winner=temp;

}

}

cout<<winner<<" "<<max;

return 0;

}

NOTE: focus on overall lead score

> Your output must consist of a single
> line containing two integers W and L,
> where W is 1 or 2 and indicates the
> winner and L is the maximum lead
> attained by the winner.

there L is maximum overall lead, but it needs to be calculated per round

my c++ solution to codechef ONP - Transform the Expression

codechef ONP - Transform the Expression: http://www.codechef.com/problems/ONP/

Transform the Expression

All submissions for this problem are available.

Reverse Polish Notation (RPN) is a mathematical notation where every operator follows all of its operands. For instance, to add three and four, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 − 4 + 5" would be written "3 4 − 5 +" first subtract 4 from 3, then add 5 to that.

Transform the algebraic expression with brackets into RPN form.

You can assume that for the test cases below only single letters will be used, brackets [] will not be used and each expression has only one RPN form (no expressions like a*b*c)

Input

The first line contains t, the number of test cases (less then 100).

Followed by t lines, containing an expression to be translated to RPN form, where the length of the expression is less then 400.

Output

The expressions in RPN form, one per line.

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

---

Author:	admin
Tags	admin
Date Added:	1-12-2008
Time Limit:	5 sec
Source Limit:	50000 Bytes
Languages:	ADA, ASM, BASH, BF, C, C99 strict, CAML, CLPS, CPP 4.3.2, CPP 4.8.1, CPP11, CS2, D, ERL, FORT, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC

my c++ solution to codechef ONP - Transform the Expression: http://ideone.com/eY3A2o

#include <iostream>

#include <string>

#include <stack>

using namespace std;

int main() {

// your code goes here

int a, i;

string s;

stack <char> oper;

stack <char> extra;

cin>>a;

while(a--) {

cin>>s;

for(i=0; i<s.size(); i++) {

if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/' || s[i]=='^' || s[i]=='%') oper.push(s[i]);

else if(s[i]==')') {

cout<<oper.top();

oper.pop();

}

else if(s[i]=='(') extra.push(s[i]);

else cout<<s[i];

}

cout<<endl;

}

return 0;

}

my c++ solution to codechef PERMUT2 - ambiguous permutations problem

codechef PERMUT2 - ambiguous permutations: http://www.codechef.com/problems/PERMUT2

Ambiguous Permutations

All submissions for this problem are available.

Some programming contest problems are really tricky: not only do they
require a different output format from what you might have expected, but
also the sample output does not show the difference. For an example,
let us look at permutations.
A permutation of the integers 1 to n is an
ordering of
these integers. So the natural way to represent a permutation is
to list the integers in this order. With n = 5, a
permutation might look like 2, 3, 4, 5, 1.
However, there is another possibility of representing a permutation:
You create a list of numbers where the i-th number is the
position of the integer i in the permutation.
Let us call this second
possibility an inverse permutation. The inverse permutation
for the sequence above is 5, 1, 2, 3, 4.

An ambiguous permutation is a permutation which cannot be
distinguished from its inverse permutation. The permutation 1, 4, 3, 2
for example is ambiguous, because its inverse permutation is the same.
To get rid of such annoying sample test cases, you have to write a
program which detects if a given permutation is ambiguous or not.

Input Specification

The input contains several test cases.
The first line of each test case contains an integer n
(1 ≤ n ≤ 100000).
Then a permutation of the integers 1 to n follows
in the next line. There is exactly one space character
between consecutive integers.
You can assume that every integer between 1 and n
appears exactly once in the permutation.

The last test case is followed by a zero.

Output Specification

For each test case output whether the permutation is ambiguous or not.
Adhere to the format shown in the sample output.

Sample Input

4
1 4 3 2
5
2 3 4 5 1
1
1
0

Sample Output

ambiguous
not ambiguous
ambiguous

---

Author:	admin
Tags	admin
Date Added:	1-12-2008
Time Limit:	10 sec
Source Limit:	50000 Bytes
Languages:	ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.8.1, CPP11, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC

and here is my c++ solution to codechef PERMUT2 - ambiguous permutations problem: http://ideone.com/qhJAdR

#include <iostream>

using namespace std;

int main() {

    int a=1, i, arr[100005], arrInv[100005], not_amb;

    while(a!=0) {

    cin>>a;

        not_amb=0; 

        for(i=1; i<=a; i++) {

            cin>>arr[i];

        }

        for(i=1; i<=a; i++) {

            arrInv[arr[i]]=i;

        }

        for(i=1; i<=a; i++) {

            if(arr[i]!=arrInv[i]) not_amb=1;

        }

        if(a!=0) {

        if(not_amb) cout<<"not ambiguous"<<endl;

        else cout<<"ambiguous"<<endl;

        }

    }    

    return 0;

}

some explanation:
1 - use 1-based array
2 - think of inverse permutation as bijection function

3 - create inverse(Y) function(permutation) of given array(X)
4 - if array(X) and its inverse(Y) is equal to each other then the function(permutation) is ambiguous
NOTE: all my ideas hold variability due to my lack of math and programming knowledge. thanx

helpful input and output:

input: 
4
1 4 3 2
5
2 3 4 5 1
1
1
7
6 3 7 2 1 4 5
5
4 1 3 2 5
5
1 3 5 4 2
5
2 5 3 1 4
5
2 5 1 3 4
0

output: 
ambiguous
not ambiguous
ambiguous
not ambiguous
not ambiguous
not ambiguous
not ambiguous
not ambiguous