10193 - All You Need Is Love

[Almost Human]

I think it is just a simple case, but I got WA for this...

any suggestion ?

the input will only in the range of 2^32 right ?

[Dominik Michniewski]

Yes ...
Maybe you have error in part, which read input ?
I use simple GCD to solve this problem ...

Happy hunting
DM

[Almost Human]

Do you have some sample input ??? and the expected output of course.

thanks

[Almost Human]

this is my code ...

Code: Select all

include <math.h>
#include <stdio.h>

int main ( )
{
  int i , j , len , NumOfCase ;
  unsigned long input1 , input2 , temp ;
  char preinput1[100] , preinput2[100] , flag ;
  double limit ;

/*  freopen ( "10193.in" , "r" , stdin ) ;
  freopen ( "10193.out" , "w" , stdout ) ;*/

  scanf ( "%i\n" , &NumOfCase ) ;
  temp = 1 ;

  for ( i = 1 ; i <= NumOfCase ; i ++ )
  {
	 gets ( preinput1 ) ; gets ( preinput2 ) ;

	 for ( len = 0 ; preinput1[len] ; len ++ ) ;
	 len -- ;

	 for ( input1 = 0 , j = 0 ; len >= 0 ; len -- , j ++ )
		if ( preinput1[len] == '1' )
		  input1 = input1 | ( temp << j ) ;

	 for ( len = 0 ; preinput2[len] ; len ++ ) ;
	 len -- ;

	 for ( input2 = 0 , j = 0 ; len >= 0 ; len -- , j ++ )
		if ( preinput2[len] == '1' )
		  input2 = input2 | ( temp << j ) ;

	 if ( input1 > input2 ) limit = sqrt ( input2 ) ;
	 else limit = sqrt ( input1 ) ;

	 for ( j = 2 , flag = 0 ; j <= limit ; j ++ )
		if ( ! ( input1 % j ) && ! ( input2 % j ) )
		{
		  flag = 1 ; break ;
		}

	 if ( flag )
		printf ( "Pair #%i: All you need is love!\n" , i ) ;
	 else
		printf ( "Pair #%i: Love is not all you need!\n" , i ) ;
  }

  return 0 ;
}

[Dominik Michniewski]

try
111
111
and you got wrong answer ...
output should be:
All you need is love!

Best regards
DM

[Almost Human]

I have changed my code a little and it still got WA...

Any more suggestion or sample inputs ?

Code: Select all

#include <math.h>
#include <stdio.h>

int main ( )
{
  int i , j , len , NumOfCase ;
  unsigned long input1 , input2 , temp ;
  char preinput1[100] , preinput2[100] , flag ;
  double limit ;

/*  freopen ( "10193.in" , "r" , stdin ) ;
  freopen ( "10193.out" , "w" , stdout ) ;*/

  scanf ( "%i\n" , &NumOfCase ) ;
  temp = 1 ;

  for ( i = 1 ; i <= NumOfCase ; i ++ )
  {
	 gets ( preinput1 ) ; gets ( preinput2 ) ;

	 for ( len = 0 ; preinput1[len] ; len ++ ) ;
	 len -- ;

	 for ( input1 = 0 , j = 0 ; len >= 0 ; len -- , j ++ )
		if ( preinput1[len] == '1' )
		  input1 = input1 | ( temp << j ) ;

	 for ( len = 0 ; preinput2[len] ; len ++ ) ;
	 len -- ;

	 for ( input2 = 0 , j = 0 ; len >= 0 ; len -- , j ++ )
		if ( preinput2[len] == '1' )
		  input2 = input2 | ( temp << j ) ;

	 if ( input1 > input2 ) limit = ceil ( sqrt ( input2 ) ) ;
	 else limit = ceil ( sqrt ( input1 ) ) ;

	 if ( input1 == input2 )
		printf ( "Pair #%i: All you need is love!\n" , i ) ;
	 else
	 {
		for ( j = 2 , flag = 0 ; j <= limit ; j ++ )
		  if ( ! ( input1 % j ) && ! ( input2 % j ) )
		  {
			 flag = 1 ; break ;
		  }

		if ( flag )
		  printf ( "Pair #%i: All you need is love!\n" , i ) ;
		else
		  printf ( "Pair #%i: Love is not all you need!\n" , i ) ;
	 }
  }

  return 0 ;
}

[zsepi]

I've just solved the problem, but I w/ a surprisingly slow time 8.174 seconds and using 388 kb memory and on the ranklist everyone is having 0.00:00 times.... and i am playing around with register variables, all function variables (except for arguments) not register are static so I am totally puzzled.... is there some real efficient algorithm to convert a string of bnary digits into an int?
thanx

[justforfun]

what is the correct output when input are:
1
1
and
0
0

or is there any special input??
i always got WA....

[Per]

For the first test case, the answer is "Love is not all you need!", and the second test case will not appear in input (though if it did appear I guess the answer would be the same as for the first).

zsepi: if you're a C/C++ programmer, the simplest way is to use the strtol function. In Java I think there's some static method in the Integer class which does the same thing, and in Pascal I have no idea.

[dvntae]

just find if exist a gcd(a,b) between the 2 numbers. convert it 2 decimal first. easy ain't it?

[Jemerson]

Code: Select all

public static void main(String[] args) {
  int numbPairs = Integer.parseInt(readLn(40));
  for (int i = 1; i <= numbPairs; i++) {
     String s1 = readLn(200);
     String s2 = readLn(200);
     int numb1 = Integer.parseInt(s1, 2);
     int numb2 = Integer.parseInt(s2, 2);
     int smaller = numb1 < numb2? numb1 : numb2;
     int counter = 2;
     boolean end = false;
     while (!end && counter <= smaller) {
         if (numb1 % counter == 0 && numb2 % counter == 0) {
            System.out.println("Pair #" + i + ": All you need is love!");
            end = true;
         }
         counter++;
     }
     if (!end) 
       System.out.println("Pair #" + i + ": Love is not all you need!");
     }
}

Can anyone help me? By the way, i've already coded my own binary to int parser and got the same trouble.

Thanx in advance

[Jemerson]

used euclidean algorithm to find out the GCD between the numbers faster. worked perfectly

Good luck

[unuguntsai]

I can't find why WA
and sample i/o i'm all right

Code: Select all

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

unsigned long int power( int exp )
{
  unsigned long int ans = 1 ;
  for( int i = 0 ; i < exp ; i++ )
    ans *= 2 ;
  return ans ;
}
int main()
{
      int time ;
      unsigned long int s , l ;
      char num[30] ;
      int prime[4792] , i , Cprime , k;

      for( k=3 , Cprime=1 , prime[0]=2 ; k<46341 ; k+=2 )
      {

        for( i=0 ; prime[i]*prime[i] < k ;i++ )
          if(k%prime[i]==0)
            break;
        if(prime[i]*prime[i]>k)
          prime[Cprime++]=k;
      }

      scanf("%d\n" , &time ) ;
      for( i = 0 ; i < time ; i++ )
      {
        scanf("%s" , &num ) ;
        s = 0 ;  l = 0 ;
        for( k = strlen(num)-1 ; k >= 0 ; k-- )
          s += int(num[k]-'0') * power( strlen(num)-1-k ) ;
        scanf("%s" , &num ) ;
        for( k = strlen(num)-1 ; k >= 0 ; k-- )
          l += int(num[k]-'0') * power( strlen(num)-1-k ) ;
        Cprime = 0 ;
        if( s > l )
        {
          for( k = 0 ; prime[k] <= l ; k++ )
          {
            if( s % prime[k] == 0 &&  l % prime[k] == 0 )
            {
              Cprime = 1 ;
              break ;
            }
          }
        }
        else
        {
          for( k = 0 ; prime[k] <= s ; k++ )
          {
            if( s % prime[k] == 0 &&  l % prime[k] == 0 )
            {
              Cprime = 1 ;
              break ;
            }
          }
        }
        if( Cprime )  printf("Pair #%d: All you need is love!\n" , i+1 ) ;
        else  printf("Pair #%d: Love is not all you need!\n" , i+1 ) ;
      }
      //system("PAUSE");
      return 0;
}

[jiarung.yeh]

I find all I cound find case , including 111 111...etc

But I also got WA

Why?
Here is my code...

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std ;
int main(){
	int set ;
	cin >> set ;
	for( int Si = 1 ; Si <= set ; Si ++ ){		
		string s1 , s2 ;
		unsigned long int i , j ;
		cin >> s1 >> s2 ;
		int a = 0 , b = 0 ;
		for( i = 0 , j = s1.length() - 1 ; i < s1.length() ; i ++ , j -- )
			if( s1[i] == '1' )
				a += pow( 2 , (double)j ) ;
		for( i = 0 , j = s2.length() - 1 ; i < s2.length() ; i ++ , j -- )
			if( s2[i] == '1' )
				b += pow( 2 , (double)j ) ;
		if( b < a )
			swap( a , b ) ;
		vector< int > F( 0 ) ;
		int temp = a ;
		for( i = 2 ; i <= (int)sqrt( (double)a ) ; i ++ )
			if( temp % i == 0 ){
				F.push_back( i ) ;
				while( temp % i == 0 )
					temp /= i ;
			}
		bool ans = false ;
		for( vector<int>::iterator u = F.begin() ; u != F.end() ; u ++ )
			if( b % (*u) == 0 ){
				ans = true ;
				break ;
			}
		if( s1 == s2 )
			ans = true ;
		cout << "Pair #" << Si << ": " ;
		if( !ans )
			cout << "Love is not all you need!" ;
		else 
			cout << "All you need is love!" ;
		cout << endl ;
	}
}

[seogi81]

I think it is a simple GCD problem..

if GCD( i, j ) > 1 "all you need is love"
else "love is not all you need"