10370 - Above Average

[amd-RS]

How can I get 0:00:000 for this problem? Any hints would be welcome !!!

Thanks !

[Stefan Pochmann]

How long do you need with your current program? I need 10 milliseconds, but I think that's only because I use the fairly slow cin of C++. Maybe try using scanf or write your own input function.

[junjieliang]

Nopes, scanf also gives you 10 ms. What's your current time? IMHO 10 ms is not a bad time... Maybe the problem lies in floating numbers, try not using floating-points at all and see what happens...
All the best

[amd-RS]

My current time is 10ms, and I'm using fscanf for input. I note that the six persons who get zero used C++ or Pascal. Stefan, how can I write my own input function.

Thanks both of you for the replies!!!

Aur

[Stefan Pochmann]

You could use getc or getchar or something like that to read single characters. Or even fread to read large blocks. Or maybe read the numbers as strings. In all of these cases, you have to write your own code to transform the single digits to the whole numbers.

Furthermore, try using int instead of float/double (in case you do that), just as junjieliang suggested. This will also give you safety from rounding errors if you do it right.

[amd-RS]

I used only int !!! Can I put my algo. here fou you to check it out ?

Thanks !!!

[gvcormac]

Preamble:

I know that this is just a puzzle and as such you have every right to spend your time thinking about it, but wouldn't it be more interesting to attack some of the harder problems rather than to try to wring the last millisecond out of this one?

Solution:

As has been mentioned, scanf() and/or cin consume the majority of the time. If you replace them by a single read() [called "big inhale" in the trade] followed by strtok/atoi, you'll make it run in 0.000 seconds. The use of floating point vs. integer is a Red Herring. I have no idea if the STL equivalents of strtok/atoi would be fast enough. I'm skeptical.

[venia]

I got several times WA about 10370. Is there any special case that I didn't consider? Could someone give some test data for me? You may also mail to me. email:u89417@ice.ntnu.edu.tw. Thank you.

[turuthok]

Hi, ...

10370 - Above Average is I believe one of the easiest problems in this site. Not sure what's wrong with your WA ... most likely it's a precision problem or other simple mistakes ... please post a little bit of your code here and let's see ...

-turuthok-

[soyoja]

I agree. : )

It's a really easy problem. You only need to calculate average of input numbers,

and count above average of input data.

Be careful when you print your output, especially conversion to percentage format.

Good Luck~ : )

[Whinii F.]

you may find out you don't need any floating number type variables in solving this problem..

try small cases, like just one number or that kind of things.
it may be your code, not the algorithm that is wrong..

[turuthok]

That's correct, I know I don't use any double or float type in my C solution ... But I definitely did real-numbers calculation at the end (when I print the output, of course).

-turuthok-

[Sajid]

Why may i not use floating point variable??? the answer should be floating point variable. what do u think???

[cytse]

When N=1, the answer should be 0.000%, because the score of the only student is equal to the average, which is surely not above average

[Riyad]

i went through both the topics about 10370 available in the board . i tried to follow the advices . but i am constantly getting WA . may be it is the precision problem or i am missing some thing . i did not use any floating point number in my calculation . only used them while printing the answer.

here , pliz Take a look at my clumpsy code :(:(:(:(

Code: Select all

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

void bubble_sort(int v[],int n ){

   int i , j,temp;
   
   for(i=0;i<n;i++){
      for(j=i+1;j<n;j++){
         if(v[i]>v[j]){
            temp=v[i];
            v[i]=v[j];
            v[j]=temp;
         }
         else
            continue;
      
      }
   
   }

}

void check(int numbers[], int index, int sum, int nos){

   
   int count=0,i;
   int avg;
   double s,n;

   
   
   n=nos;
   
   avg=(int)(sum/nos);
   

   
   
   for(i=0;i<index;i++){
      
      if(numbers[i] > avg){
      
         count=index-i;
         
         break;
                                                //count++;
         
         
         
      }
      
      else
         continue;
   
   }
   

   s=(double)(count/n)*100.0;
   
        printf("%.3lf!\n",s);



}


int main(){

   int cases;
   int numbers[1500];
   int index,flag,nos,sum;
   char *p;
   char input[10000];




   while(scanf("%d",&cases)==1){
   
      getchar();

      while(cases>0){
      
         flag=0;
         index=0;
         sum=0;

         gets(input);
         

         p=strtok(input," \n");
         
         while(p!=NULL){
         
            if(flag==0){
               nos=atoi(p);
            }

            else{
            
               numbers[index++]=atoi(p);
               sum+=atoi(p);
            }
            p=strtok(NULL," \n");
            flag++;
         
         }
         

         
      
         bubble_sort(numbers,index);
         
         
         check(numbers,index,sum,nos);
         
         
         cases--;
      }

      

   
   
   
   }


   
   return 0;
}

Waiting for any kind of reply and help .
Bye
Riyad