c2tarun

November 6th, 2010, 04:28 AM

i found this problem in codechef NOV10 competition.

http://www.codechef.com/NOV10/problems/BOMBING/

here is my program:

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

// these two variables will store the initial and final house of the particular protection

int* initial;

int* fin;

static int count=0; // will count the total number of protections

// in case protection will applied this function will update initial and final variables

void pro(int u,int v)

{

int i; // loop variable

*(initial+count)=u;

*(fin+count)=v;

count++;

}

// this function will move the protection.

void mov(int u,int v)

{

u--;

*(initial+u)+=v;

*(fin+u)+=v;

}

// this function will return the number of protections protecting the house x

int bomb(int x)

{

int p=0,i;

for(i=0;i<count;i++)

{

if(*(initial+i)<=x && *(fin+i)>=x)

p++;

}

return p;

}

int main(void)

{

long n; // number of houses

long m; // number of lines to be entered, may be protection, move or bombing

char* str=NULL; // take the input

char* temp; // processing on input

size_t sz=25; // used in getline

int u,v; // variables used to extract info from text and pass into various functions

int i; // loop variable

getline(&str,&sz,stdin);

// extracting first two integer i.e. number of houses and input lines

temp=strtok(str," ");

n=atoi(temp);

temp=strtok(NULL,"\n");

m=atoi(temp);

// allocating memory for number of input lines

initial=(int*)malloc((m)*sizeof(int));

fin=(int*)malloc((m)*sizeof(int));

// processing

while(m--)

{

getline(&str,&sz,stdin);

temp=strtok(str," ");

// if protection is applied in input line

if(temp[0]=='P')

{

u=atoi(strtok(NULL," "));

v=atoi(strtok(NULL,"\n"));

pro(u,v);

}

else if(temp[0]=='B') // if bombing is done in input line

{

u=atoi(strtok(NULL,"\n"));

printf("%d\n",bomb(u));

}

else if(temp[0]=='M') // if move is done in input line

{

u=atoi(strtok(NULL," "));

temp=strtok(NULL,"\n");

if(temp[0]=='-')

{

i=1;

v=0;

while(temp[i])

v=v*10 + ((int)temp[i++] - 48);

v*=-1;

}

else

v=atoi(temp);

mov(u,v);

}

}

return 0;

}

i posted all the comments that may be helpful in understanding of the program.

my problem is i need to speed up this program without using too much memory.

can anyone please suggest me a way. please.

http://www.codechef.com/NOV10/problems/BOMBING/

here is my program:

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

// these two variables will store the initial and final house of the particular protection

int* initial;

int* fin;

static int count=0; // will count the total number of protections

// in case protection will applied this function will update initial and final variables

void pro(int u,int v)

{

int i; // loop variable

*(initial+count)=u;

*(fin+count)=v;

count++;

}

// this function will move the protection.

void mov(int u,int v)

{

u--;

*(initial+u)+=v;

*(fin+u)+=v;

}

// this function will return the number of protections protecting the house x

int bomb(int x)

{

int p=0,i;

for(i=0;i<count;i++)

{

if(*(initial+i)<=x && *(fin+i)>=x)

p++;

}

return p;

}

int main(void)

{

long n; // number of houses

long m; // number of lines to be entered, may be protection, move or bombing

char* str=NULL; // take the input

char* temp; // processing on input

size_t sz=25; // used in getline

int u,v; // variables used to extract info from text and pass into various functions

int i; // loop variable

getline(&str,&sz,stdin);

// extracting first two integer i.e. number of houses and input lines

temp=strtok(str," ");

n=atoi(temp);

temp=strtok(NULL,"\n");

m=atoi(temp);

// allocating memory for number of input lines

initial=(int*)malloc((m)*sizeof(int));

fin=(int*)malloc((m)*sizeof(int));

// processing

while(m--)

{

getline(&str,&sz,stdin);

temp=strtok(str," ");

// if protection is applied in input line

if(temp[0]=='P')

{

u=atoi(strtok(NULL," "));

v=atoi(strtok(NULL,"\n"));

pro(u,v);

}

else if(temp[0]=='B') // if bombing is done in input line

{

u=atoi(strtok(NULL,"\n"));

printf("%d\n",bomb(u));

}

else if(temp[0]=='M') // if move is done in input line

{

u=atoi(strtok(NULL," "));

temp=strtok(NULL,"\n");

if(temp[0]=='-')

{

i=1;

v=0;

while(temp[i])

v=v*10 + ((int)temp[i++] - 48);

v*=-1;

}

else

v=atoi(temp);

mov(u,v);

}

}

return 0;

}

i posted all the comments that may be helpful in understanding of the program.

my problem is i need to speed up this program without using too much memory.

can anyone please suggest me a way. please.