CALCULATING THE SIZE OF STRUCTURE IN C/C++:

consider a strucure

struct X
{
    short s; 
    int   i; 
    char  c; 
             
};

what do you think the size of structure will be? 2 + 4 + 1 ?

Sorry, then you are wrong. Because to reduce the lookup time by CPU compiler pads up the bytes untill it becomes a multiple of 4. This is however dependent on hardware,but most compilers does so.

so what happens is 

struct X
{
    short s; /* 2 bytes */
             /* 2 padding bytes */
    int   i; /* 4 bytes */
    char  c; /* 1 byte */
             /* 3 padding bytes */
};

but this is not the best way to declare the struct , why? because you waste space due to  padding of bytes. So here are some tricks to reduce the eat up of byte padding







struct Y
{
    int   i; /* 4 bytes */
    char  c; /* 1 byte */
             /* 1 padding byte */
    short s; /* 2 bytes */
};

struct Z
{
    int   i; /* 4 bytes */
    short s; /* 2 bytes */
    char  c; /* 1 byte */
             /* 1 padding byte */
};

POST YOUR DOUBTS IN THE COMMENTS

SPOJ : NEG2 SOLUTION

I suggest you read wikipedia link. But i can summarise you in a nut shell. Our task is to convert the given decimal to a negative base(2) number to binary form
i.e take for example  7(base 10)

Basically pick the remainder as the positive even when remainder is negative (tricky pay attention!)

 7 = -3*-2 + 1. (least significant digit)
-3 =  2*-2 + 1
 2 = -1*-2 + 0
-1 =  1*-2 + 1
 1 =  0*-2 + 1. (most significant digit)

as you can notice in 2nd step -3 % -2 is actually -1, but we have to store as 1 as binary representation cant contain negative numbers.

so we add 1 to n/2 i.e  -3/-2  = 1 adding 1 we get 2 ( this ensures remainder is always postive)


posting the logic:

  string s="";
     if(n==0)
     {
             printf("0\n");
             return;
     }
     int i=-2;

     while(n)
     {
             if(n%i<0)
             {

             s=(char)(((n%i)+2)+'0')+s;   // When the remainder is negative 

             n=(n/i)+1;                    // adding one so that when divided remainder is > 0
             }
             else
             {
             s=(char)((n%i)+'0')+s;
             n=n/i;
             }

     }
    cout<<s;

SPOJ : ACPC 10D Trigraphs Solution

This problem could be solved by using DP.
Step 1:
        Initialse the adjacent nodes to the source node.
Step 2:
        Loop Across the other i nodes from 2 to N and initialise them.

P re-Requesite: DP
     However Learning Floyd Warshall Algorithm would help you in solving this problem.



Code:


#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;

int main()
{
int i=1;
while(1) {
int n;
cin >>n;
if(n==0)
return 0;
int a[n][3];
for (int i=0;i<n;i++)
cin >>a[i][0]>>a[i][1]>>a[i][2];
cout<<i<<". ";
if(n==1)
cout<<a[0][1]<<endl;
else {
                                                               // Initialisation Step
a[1][0] += a[0][1];
a[0][2] += a[0][1];
a[1][1] += min(min(a[1][0],a[0][1]),a[0][2]);
a[1][2] += min(min(a[0][2],a[0][1]),a[1][1]);


                                                                 // Calculating the remaing nodes
for(int i  = 2 ; i<n;i++)
{
a[i][0] += min(a[i-1][0],a[i-1][1]);
a[i][1] += min(min(min(a[i][0],a[i-1][0]),a[i-1][1]),a[i-1][2]);
a[i][2] += min(min(a[i][1],a[i-1][1]),a[i-1][2]);
}
cout <<a[n-1][1]<<endl;
i++;
}
}
return 0;
}

SPOJ : KURUK 14 (Genie Sequence)

Hints: Consider the fact that for a sequence to be a genie sequence all the possible positions must be satisfied

Solution:
consider 6 elements 5 4 3 2 1 0
This forms a genie sequence as all the possible positions are covered respectively
But the position can be from either sides i.e the first number can be 5 or 0
                                                                       second number can be 4 or 1
                                                                       third number can be 3 or 2
and so on...
notice that sum of this combination ie always n - 1 here it is 6 - 1 = 5
(5+0) , (4+1),(3+2)... = 5

->  Thus create an array and input elements,intialise the array to 0
for each element mark in the arrray as 1 if it is already marked 1 , then mark the pair of that element..
for example if 5 is entered mark array[5] = 1 , but if 5 is entered again mark array[ n - 1 - 5] = 1

->after this process again iterate through the array, if u encounter an element with value 0 that means this cant form a genie sequence..


C code:
#include <stdio.h>
#include <stdlib.h>

int main(void) {
int t,n,temp,i,j,flag;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int *a;
flag = 0;
a = calloc(n+1,sizeof(int));
for ( i = 0 ; i < n ; i++)
{
scanf("%d",&temp);
if(temp < n)
{
if(a[temp] == 0)
a[temp] = 1;
else
a[n -1 - temp] = 1;

}
}

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

if(a[i] == 0)
{
flag  = 1;
break;
}
}
if(flag == 1)
printf("NO\n");
else
printf("YES\n");
}

return 0;

}

SPOJ : MANGOES Solution

Hints:
Just catch the point that GCD of 3 consecutive numbers must be 1.

Solution:
If GCD of three consecutive numbers is 1,the first number cant be an even  number because then the third number would obviously be an even number and so GCD wont be 1 

example
2,3,4
when first number if even (2) third number will be even(4) and GCD wont be 1 here it is 2.
So the first number must be an odd number ex:3,4,5 
Now comes the logic for three consecutive numbers only 2 can be a factor common to all three(if u cant figure out why feel free to comment or mail me,will reply ASAP)
so number of magoes = sum of numbers that satisfy the condition which in case is only the odd numbers
* Sum of odd numbers starting from 1 is n*n where n is the number of terms, here the number of terms is (N-1)/2
so number of mangoes is (N-1)/2*(N-1)/2
But we are required to give a number less than N so take modulo %

Here is the C code:

#include <stdio.h>

int main(void) {
long long int t,n,m;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
m = (n -1)/2;
m = m*m;
m = m %n;
printf("%lld\n",m);
}
return 0;

}

SPOJ : ACT solution (Alpha Centauri Tennis)

Spoj:ACT question

Hints: 
The winner of the match is the winner of the last game

Solution:

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


int main()
{
    int t,n;
    char *s;
    scanf("%d",&t);
    s = (char*)malloc(1000);

    while(t--)
    {
       
        scanf("%d %s",&n,s);
n=strlen(s)-1;
        printf("%c\n",s[n]);
    }
return 0;