10407 - Simple division

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

Moderator: Board moderators

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

GOT IT RIGHT BUDDIES

Post by Riyad » Fri Nov 21, 2003 10:09 am

i got my mistake for this problem . i did not consider a special case , as a result WA . i now got my mistake corrected .every one should consider the case when there r only 2 number in the sequence . :wink:
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

10407 - Wy WA?

Post by medv » Thu Sep 16, 2004 12:06 pm

Help me, please! Why WA???

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

int gcd(int a,int b)
{
return (a == 0) ? b: gcd(b%a, a);
}
void main()
{
int a,b,res;
while(scanf("%d\n",&a),a > 0)
{
scanf("%d",&b); res = abs(a-b);
while (scanf("%d",&b),b>0)
{
res = gcd(res,abs(a-b));
a = b;
}
scanf("\n");
printf("%d\n",res);
}
}

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

10407

Post by efr_shovo » Thu Oct 14, 2004 5:03 pm

#include<iostream.h>
#include<math.h>

long data[1000],sub[1000],n,a,b;

long gcd(long x,long y )
{
if(y==0)
return x;
else
return gcd(y,(x%y));
}


void main()
{
while(1)
{
int i=0;
int k=0;

while(1)
{
cin>>n;
if(n==0)
break;
data[i++]=n;
}
if(data[0]==0||i==1||i>1000)
break;
int j=0;
for(j=0;j<i-1;j++)
{
sub[j]=labs(data[j]-data[j+1]);

}
a=sub[0];

for(k=1;k<j;k++)
{
b=sub[k];
a=gcd(a,b);
}
cout<<a;
for(j=0;j<i;j++)
{
data[j]=sub[j]=0;
}

}
}

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Thu Oct 14, 2004 11:16 pm

Code: Select all

cout<<a;
should be

Code: Select all

cout<<a<<endl;
Istiaque Ahmed [the LA-Z-BOy]

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Oct 20, 2005 4:43 am

Just try the following input:

Input:

Code: Select all

701 701 1059 1417 2312 0
0
Output:

Code: Select all

179
Find res and use a flag then calculate...

Hope it works...
Ami ekhono shopno dekhi...
HomePage

savage
New poster
Posts: 4
Joined: Sat Feb 11, 2006 4:07 pm
Location: Bangladesh

10407::somebuddy help::Why RE??

Post by savage » Tue Aug 01, 2006 8:43 am

i got runtime error but why??somebody help me plz.................
here is da code...

#include <iostream>
#include <math.h>

using namespace std;

#define MAX 10000
#define MEX 100000
long a[MAX],b[MAX];
long prime[MEX];


long gcd(long c,long d);

int main()
{
long i,j,k;
int y,m,n,g,count;
prime[0]=0;
prime[1]=1;
for(m=2;m<=MEX;m++){
prime[m]=1;
}
for(m=2;m<=(MEX/2);m++){
for(n=m+m;n<=MEX;n+=m){
if(prime[n]==1){
prime[n]=0;
}
}
}
do{
i=0;
j=0;
count=0;
cin>>a;
if(*a==0)break;
while(*a){
i++;
cin>>a;
if(a==0)break;
b[j]=a-a[0];
j++;
count++;
}
for(k=0;k<count-1;k++){
j=2;
g=gcd(b[0],b[1]);
g=gcd(g,b[j]);
j++;
}
if(prime[g]==1){
cout<<g<<endl;
}else{
y=2;
while(y<=(g/2)){
if(g%y==0){
g/=y;
}else y+=2;
}
cout<<g<<endl;
}
}while(*a);
return 0;
}

long gcd(long c,long d){
if(c%d==0)return d;else return (d,c%d);
}

User avatar
kana
New poster
Posts: 19
Joined: Mon Mar 13, 2006 6:03 pm
Location: dhaka

Post by kana » Tue Dec 05, 2006 9:34 pm

why WA? can any one help?

Code: Select all


Last edited by kana on Thu Dec 07, 2006 7:57 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Dec 06, 2006 5:07 am

Check the samples...

Input:

Code: Select all

-666 169 0
-650 -164 0
-202 157 0
976 -632 0
762 531 0
615 234 0
-244 -722 0
-145 716 0
-783 482 0
721 421 0
-316 -721 0
0
Output:

Code: Select all

835
486
359
1608
231
381
478
861
1265
300
405
Hope these help.
Ami ekhono shopno dekhi...
HomePage

User avatar
kana
New poster
Posts: 19
Joined: Mon Mar 13, 2006 6:03 pm
Location: dhaka

Post by kana » Thu Dec 07, 2006 8:00 pm

thanks jan !!! :D

Taman
New poster
Posts: 32
Joined: Sun Oct 11, 2009 8:59 pm
Location: Southeast University

Re: 10407 - Simple division

Post by Taman » Fri Sep 02, 2011 9:04 pm

I found the following type of test cases very helpful :wink: :wink:

Code: Select all

2 4 6 8 0
5 10 0
0

theylosehope
New poster
Posts: 1
Joined: Mon Dec 03, 2012 4:17 pm

10407 Simple Division - Can anybody explain!?

Post by theylosehope » Mon Dec 03, 2012 4:22 pm

Hello guys,

I've got "10407 - Simple Division" AC using the description in Algorithmist. However, I don't fully understand it.

My algorithm:
- Add numbers to set "S".
- If size of S is two: print the difference between the two numbers.
- If size of S is > 2: Erase the first element, and find GCD among all the differences between the remaining numbers.

This works correctly. But can anybody explain it in simple words? How can I figure out that the largest dividend with same remainder among a set of numbers is the GCD among the differences except the first difference?

Thanks in advance.

ojha
New poster
Posts: 7
Joined: Wed May 22, 2013 9:07 am

Re: 10407 - Simple division

Post by ojha » Sun Jul 07, 2013 4:57 pm

Getting WA ... help please.

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector< int >v;

int GCD(int y, int x){
    if(!x) return 0;
    int store;
    while(y%x != 0)
    {
        store = y%x;
        y = x;
        x = store;
    }
    return x;
}

int main(){
    int input, pre, post, size, i;

    while((cin >> input) && input){
        v.push_back(input);

        while((cin >> input) && input){
            v.push_back(input);
        }

        sort(v.begin(), v.end());

        size = v.size(); //cout << size << endl;

        for(i = 1; i<size; i++){
            if(i == 1){

                pre = v[i] - v[0]; //cout << v[i] << endl;
            }
            else{
                post = v[i] - v[0];

                if(post >= pre)
                    pre = GCD(post, pre);
                else
                    pre = GCD(pre, post);
            }
        }

        cout << pre << endl;
        v.clear();
    }
    return 0;
}
:-?

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

Re: 10407 - Simple division

Post by brianfry713 » Tue Jul 09, 2013 1:01 am

Input:

Code: Select all

2 2 4 0
0
Output should be 2
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 10407 - Simple division

Post by raj » Fri Sep 20, 2013 5:57 pm

I am facing problem the way of solving it...
Somebody solve by taking difference and then gcd all the numbers
Somebody take the minimum then subtract all the numbers with the minimum and then gcd the numbers

but i want to know how it solves the problem??? please someone explain me if you have time??? :( :( :(

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Re: 10407 - Simple division

Post by richatibrewal » Wed Nov 12, 2014 5:53 pm

I am facing difficulty in understanding its 3rd example:
Input : 14 -22 17 -31 -124 0
output: 3
14%3 = 2
whereas -22%3 = 1
Will someone plz explain this ?

Post Reply

Return to “Volume 104 (10400-10499)”