10193 - All You Need Is Love

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

10193 - All You Need Is Love

Post by Almost Human » Tue Apr 29, 2003 8:24 am

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
Guru
Posts: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Apr 29, 2003 10:38 am

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

Happy hunting
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Tue Apr 29, 2003 10:59 am

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

thanks

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Wed Apr 30, 2003 6:34 am

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
Guru
Posts: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Apr 30, 2003 7:49 am

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

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Wed May 07, 2003 10:57 am

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
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

speed

Post by zsepi » Mon Jun 23, 2003 1:15 pm

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
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

justforfun
New poster
Posts: 5
Joined: Sun Feb 23, 2003 7:33 pm

can someone answer me??

Post by justforfun » Fri Jul 18, 2003 6:49 pm

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

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

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Fri Jul 18, 2003 7:28 pm

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
New poster
Posts: 7
Joined: Fri Feb 14, 2003 12:50 pm

still active this topic??

Post by dvntae » Fri Apr 02, 2004 11:46 am

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

User avatar
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

10193 - Time Limit Exceed in Java

Post by Jemerson » Thu May 05, 2005 2:02 am

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

User avatar
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by Jemerson » Thu May 05, 2005 3:06 am

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

Good luck

unuguntsai
New poster
Posts: 6
Joined: Mon Aug 15, 2005 4:40 am

10193 Why WA pls help~

Post by unuguntsai » Thu Aug 25, 2005 4:23 am

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
New poster
Posts: 2
Joined: Tue Feb 07, 2006 11:54 am

10193---All You Need Is Love

Post by jiarung.yeh » Tue Feb 07, 2006 12:02 pm

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
New poster
Posts: 2
Joined: Mon Feb 06, 2006 3:24 pm
Location: Korea

Post by seogi81 » Tue Feb 07, 2006 1:18 pm

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"

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest