TJU 2862. CityStar November 25, 2009

TJU 2862. CityStar

[ took 45-55 mins to code, also implemented qsort function to get AC,
other it was in TLE]

<strong>--AC--</strong>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

int compare (int *a, int *b)
{
       int *da = (int *) a;
       int *db = (int *) b;
     
       return (*da > *db) - (*da < *db);
 }



int main()
{
  int i,j,k;
  int n,a[100002],cases,cs=0;
  int min,diff,tmp,index;
  scanf("%d",&cases);
  while(cases--)
  {
    scanf("%d",&n);
    for(i=1;i<=n;i++)
     scanf("%d",&a[i]);
     
    
     qsort (a+1, n, sizeof (int), compare);

    
   min=99999999;
    for(i=1;i<=n-4;i++)
    {
      diff=a[i+4]-a[i]+1;
      if(diff<min)
      {
        min=diff;
        index=i;
      }
     }

     printf("Scenario #%d:\n",++cs);
     printf("%d:",min);
     for(j=1;j<=5;j++)
      printf(" %d",a[index++]);
    printf("\n\n");
   }

return 0;
}

MULTIPLY TWO INFINITE DIGIT NUMBER September 8, 2009

//two  infinite digit number multiplication
#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

#include<unistd.h>
#include<sys/time.h>
struct timeval start,finish;
long int msec;

int fun(int);
void createlinklist1(int);

void createlinklist2(int);

void multstep1();

void makeacc();

void altacc();

void displayresult();

struct node{

    int data;

    struct node *link;

}*start1,*start2,*startacc,*startacc2;



int main()

{

 int i,j,k,l,item,item1,n1,n2;
 char ch,*p=malloc(100);
 int cases=1;
 gettimeofday(&start,NULL); 
 fgets(p,100,stdin);
 cases=atoi(p);  
 while(cases--){

 start1=NULL;

 start2=NULL;

 startacc=NULL;

 startacc2=NULL;

//printf("enter the first  number \n");


 while((ch=getchar())!=' ')

 {
   

   item=ch-48;

  createlinklist1(item);

   makeacc();

 }
 

 //printf("enter the second  number\n");

  
while((ch=getchar())!='\n')

 {

    
  item=ch-48;
 createlinklist2(item);

 makeacc();

 
 }

 


 multstep1();

 


 



//printf("the result is :-\n");

altacc();



displayresult();
printf("\n");


}
gettimeofday(&finish,NULL);
msec=finish.tv_sec*1000 + finish.tv_usec/1000;
 msec-=start.tv_sec*1000 +start.tv_usec/1000;

//printf("time: %lld milliseconds\n",msec);

return 0;

}



void createlinklist1(int item)

{

 int i,j,k;

 struct node *ptr1,*ptr2;

 ptr1=malloc(sizeof(struct node));

 ptr1->data=item;



   if(start1==NULL){

      ptr1->link=NULL;

      start1=ptr1;

    }

   else{

	ptr2=start1;

	ptr1->link=ptr2;

	start1=ptr1;

      }

}



void createlinklist2(int item)

{

  int i,j,k;

  struct node *ptr1,*ptr2;

  ptr1=malloc(sizeof(struct node));

  ptr1->data=item;



   if(start2==NULL){

      ptr1->link=NULL;

      start2=ptr1;

    }

   else{

	ptr2=start2;

	ptr1->link=ptr2;

	start2=ptr1;

      }

}



void multstep1()

{

  int i=0,j,n,k1,k2,carry1,carry2,prod1,prod2,accitem;

  struct node *ptr1,*ptr2,*ptr3,*ptr4;

  ptr1=start1;

  ptr2=start2;

  carry1=0;

  carry2=0;



   i=n=0;

   while(ptr1!=NULL){

		ptr2=start2;

      ptr3=startacc;

	       for(j=0;j<n;j++)

	    ptr3=ptr3->link;

		 carry1=carry2=0;

		while(ptr2!=NULL){



	    prod1=(ptr1->data)*(ptr2->data);



	   

	    

		 accitem=carry2+prod1+ptr3->data;

		k2=accitem/10;

		 if(k2==0){

			  carry2=0;

			  accitem=accitem;

			 }

		else{

		   carry2=k2;

		   accitem=accitem%10;

		 }

               

		  ptr3->data=accitem;

		 ptr3=ptr3->link;



		 

		 ptr2=ptr2->link;

	     }

	     ptr3->data=carry2+ptr3->data;

	     	  ++i;



	       n=i;

	      ptr1=ptr1->link;



    }

 }





void makeacc()

{

 int i,j,k;

 struct node  *ptr1,*ptr2,*ptr3;

 ptr1=malloc(sizeof(struct node));

 ptr2=startacc;



  ptr1->data=0;

   ptr1->link=NULL;

 if(startacc==NULL){
    startacc=ptr1;
   }
  else

    {
    while(ptr2->link!=NULL)

     ptr2= ptr2->link;

   ptr2->link=ptr1;
   }



}



void altacc()

{  int i,j,k;

  struct node *ptr1,*ptr2,*ptr3;

  ptr1=startacc;

      while(ptr1->link!=NULL)

{

      ptr3=malloc(sizeof(struct node));

      ptr3->data=ptr1->data;

      ptr3->link=startacc2;

      startacc2=ptr3;

      ptr1=ptr1->link;

   }
 if(ptr1->link==NULL){
   ptr3=malloc(sizeof(struct node));
   ptr3->data=ptr1->data;
   ptr3->link=startacc2;
   startacc2=ptr3;
  } 

}





void displayresult()

{

 int i,j,k;

 struct node *ptr1,*ptr2,*ptr3;



 ptr1=startacc2;
     while(ptr1->data==0&&ptr1->link!=NULL)
       ptr1=ptr1->link;
     

      while(ptr1->link!=NULL){

	  printf("%d",ptr1->data);

	  ptr1=ptr1->link;

       }

  printf("%d",ptr1->data);

}