ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1053. Pinocchio

Though the problem seems difficult, it is really very simple!
Posted by Nijino Saki 9 Jun 2001 07:47
See my accepted program:

Program P1053;
Const Max=1000;
Type TList=Array[1..Max] of Longint;
Var A:TList;
    n,s,i:Integer;
    r1,r2:longint;

Procedure Sort(l,r:Integer);
Var x,t:Longint;
    i,j:Integer;
Begin
  i:=l; j:=r; x:=A[(i+j) div 2];
  repeat
    while A[i]>x do inc(i);
    while A[j]<x do dec(j);
    if i<=j then begin
                   if i<>j then begin
                                  t:=A[i]; A[i]:=A[j]; A
[j]:=t
                                end;
                   inc(i); dec(j)
                 end
  until i>j;
  if i<r then Sort(i,r);
  if l<j then Sort(l,j)
End;

Function Gcd(A,B:Longint):Longint;
Var C:Longint;
Begin
  while B<>0 do
    begin
      C:=A;
      A:=B;
      B:=C mod B
    end;
  Gcd:=A
End;

Begin
  readln(n);
  for i:=1 to n do read(A[i]);
  Sort(1,n);
  for i:=n-1 downto 1 do A[i]:=Gcd(A[i+1],A[i]);
  writeln(A[1])
End.
Re: Though the problem seems difficult, it is really very simple!
Posted by Stefan Pochmann 9 Jun 2001 10:28
Yes, that's really nice. And think about a programming
language that supports sorting like C, C++, Java, Perl, ...
The code would be even smaller.

But if you think a bit further, sorting isn't necessary at
all. That makes the following program getting accepted,
too. Normally I would never ever post a ready-to-submit
program, but since you already did this I think I can't
make things worse...

(I admit that I didn't solve the problem myself; I read
yours in order to understand the problem and unfortunately
the whole solution was clear at first sight :-(

#include <iostream.h>

int gcd( int a, int b ){
  return b ? gcd( b, a%b ) : a;
}

int main () {
  int n, L, g=0;
  cin >> n;
  while( cin >> L ) g=gcd( L, g );
  cout << g << endl;
}
It IS very simple!
Posted by Maigo Akisame 11 Jun 2004 08:04
Just calculate the GCD of the given numbers!