10407 - Simple division

Moderator: Board moderators

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

GOT IT RIGHT BUDDIES

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 .
Bye
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?

#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

#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;
}

}
}

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

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
Contact:
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

10407::somebuddy help::Why RE??

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);
}

kana
New poster
Posts: 19
Joined: Mon Mar 13, 2006 6:03 pm
Location: dhaka
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
Contact:
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

kana
New poster
Posts: 19
Joined: Mon Mar 13, 2006 6:03 pm
Location: dhaka
thanks jan !!!

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

Re: 10407 - Simple division

I found the following type of test cases very helpful

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!?

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?

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

Re: 10407 - Simple division

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

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

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

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 ?