Блог пользователя Steven-_-AbuAlkhair

Автор Steven-_-AbuAlkhair, история, 3 года назад, По-английски

in this code

main (){
    
  int n  ; cin >> n  ;
  double  arr[n] ;
  for(int i = 0 ; i < n ; i++)cin >>arr[i] ;
        int cnt  = 0; 
  for(int i = 0 ;  i < n-1  ;  i++)
  
  for(int j = i +1 ; j < n ; j ++ )
   {
       double l = log10(arr[i]+arr[j])/log10(2);
       int r = l ; 
      if(l-(double)r==0) cnt++ ;
   }
   cout<<cnt ; 
  }

when input is

4 7 3 2 1 it gives cnt = 1 because the the compiler of codeforces when arr[i] =7 and arr[j]=1 gives l=3 but r=2 ! (it dosent happen in other compilers)

even this similar code gives wa i think because of the same reason 147734731 thanks .

  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Don't use == to compare doubles.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i did this if ( fabs(l - (double)d) < 1e-9 ) cnt++ ; but it stil gives the same answer , i think there is a problem in casting because the DOUBLE << log10(7+1)/log10(2) = 3 >> != the INT << log10(7+1)/log10(2) = 2>> so , what modification should i do ? thanks.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

      Oh, are you trying to use int r = l to get r to be the value of l rounded?

      Then I think your issue is that it always rounds down. If l = 2.99999999999, then r = 2. Floating point calculations introduce small errors like that, especially if you use log10 and division...

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Two additional remarks:

        • It is possible to check whether a number is a power of two without using floats, for example by using __builtin_popcount.
        • Your approach is altogether too slow — $$$\Theta(n^2)$$$. Just trying all possibilities is almost always too slow in cp, you need some kind of clever idea.
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Even after making a few changes, this still gives TLE Here
I basically took into account the precision errors that are commonly ignored when people use "double"

Here

However, to solve it under given constraints, you can simply precompute the powers of 2 you want to attain :)
Like this