11889 - Benefit

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

Moderator: Board moderators

patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

Re: 11889 - Benefit

Post by patsp » Wed Dec 01, 2010 7:25 pm

What exactly do you want explained? Problem statement?
For some tips on how to solve it, take a look at some posts above.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11889 - Benefit

Post by plamplam » Tue Jun 21, 2011 2:00 pm

I still haven't solved this problem. I mean I got AC after getting 8 Runtime errors, 7 Wrong Answers and 2 Time Limits :oops: :oops:. But I don't know yet how the same code can get AC and Runtime Error. My AC code randomly gets AC or Runtime Error and this is very confusing. But anyway if you are getting consecutive Wrong Answers, then here are some cases.
I generated the first 450 primes and got AC.

Code: Select all

10
5 772195
1 1
1 903389
8 9
8 16
60 150
60 240
357 111384
56 10696
8866 1844128 (Thanks to ?ab for providing me this test case, I got AC after trying with this one :))

Code: Select all

154439
1
903389
NO SOLUTION
16
NO SOLUTION
16
936
191
5408
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

User avatar
shaon_cse_cu08
New poster
Posts: 50
Joined: Tue May 25, 2010 9:10 am
Contact:

11889 - Benefit : WA WA!!

Post by shaon_cse_cu08 » Mon Nov 07, 2011 6:04 pm

Code: Select all

Code Removed After AC  :wink: 
Last edited by shaon_cse_cu08 on Thu May 30, 2013 1:12 pm, edited 1 time in total.
I'll keep holding on...Until the walls come tumbling down...And freedom is all around ..... :x

patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

Re: 11889 - Benefit

Post by patsp » Sat Nov 19, 2011 2:58 pm

shaon_cse_cu08 wrote:Hello every1... My code gives Correct answer for every Input i have tested... But I can't understand Why WA... Plz help me... :oops:
I can't say why your approach does not work, but try this case:

input:

Code: Select all

1
36 4680
My solution outputs 520, while yours outputs 4680.

SDU_Phonism
New poster
Posts: 1
Joined: Tue Oct 23, 2012 11:59 am

Re: 11889 - Benefit

Post by SDU_Phonism » Wed Oct 24, 2012 8:10 am

thanks to plamplam and his examples.... :D :D :D

Masum
New poster
Posts: 9
Joined: Tue Jul 10, 2012 11:39 am

Re: 11889 - Benefit

Post by Masum » Fri Nov 30, 2012 5:00 pm

naseef_07cuet wrote:Can anyone explain me about the problem?
You are given a, c, you have to find the minimum b such that Lcm(a,b)=c. So c must be divisible by a, otherwise there is no such b. Now, for a prime p dividing a or b, Lcm(a,b)= product of p^{max(e1, e2)} where e1=power of p in prime factorization of a, e2 = power of b. Use this.

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

Re: 11889 - Benefit

Post by Sabiha_Fancy » Sun Feb 10, 2013 7:33 am

Help me. I am getting wrong answer for this problem.

here is my code

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

#define N 1000000

using namespace std;

bool a[N];
vector<int> primelist;

void seive()
{
int i,j,k;
memset(a,true,sizeof(a));
a[0]=a[1]=false;
for(i=4; i<N; i+=2)
{
a=false;
}
for(i=3; i*i<=N; i+=2)
{
if(a)
{
j = i*i;
while(j<N)
{
a[j]=false;
j = j+(2*i);
}
}
}
primelist.clear();
primelist.push_back(2);
for(i=3; i<N; i+=2)
{
if(a)
{
primelist.push_back(i);
}
}
}
int main()
{
int T,A,C,B,i,prime,n;
seive();
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&A,&C);
if(C%A != 0)
{
printf("NO SOLUTION\n");
continue;
}
B=1;
n=C;
i=0;
printf("%d ",primelist);
while(primelist<=sqrt((double)C))
{
prime = 1;
while(1)
{
if(n%primelist == 0)
{
prime *= primelist;
n /= primelist;
}
else
break;
}
if(A%prime != 0)
B *= prime;
i++;
}
if(B==1)
B = C/A;
printf("%d\n",B);
}
return 0;
}
Fancy

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11889 - Benefit

Post by brianfry713 » Wed Feb 13, 2013 12:03 am

Remove line 60:
printf("%d ",primelist);
Check input and AC output for thousands of problems on uDebug!

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

Re: 11889 - Benefit

Post by Sabiha_Fancy » Thu Feb 14, 2013 7:17 am

After removing that line i am still getting wrong answer.
Fancy

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11889 - Benefit

Post by brianfry713 » Thu Feb 14, 2013 9:38 pm

Input:

Code: Select all

1
14 97692
AC output:

Code: Select all

13956
Check input and AC output for thousands of problems on uDebug!

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 11889 - Benefit

Post by @ce » Fri Jun 21, 2013 9:22 am

Getting WA...getting correct answer for all test cases given in this thread...

Code: Select all

Code Removed.
Last edited by @ce on Tue Jul 02, 2013 4:31 pm, edited 1 time in total.
-@ce

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11889 - Benefit

Post by brianfry713 » Sun Jun 23, 2013 5:32 am

If C is divisible by A, then B is the smallest multiple of (C / A) where LCM(A, B) = C and B is less than or equal to C.
Check input and AC output for thousands of problems on uDebug!

rosynirvana
New poster
Posts: 4
Joined: Thu Oct 03, 2013 10:16 pm

Re: 11889 - Benefit

Post by rosynirvana » Wed Oct 09, 2013 9:21 pm

There is no need to factor a or c.
c % a != 0 -> NO SOLUTION

factoring gcd(c/a, a) is enough

Post Reply

Return to “Volume 118 (11800-11899)”