ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1053. Пиноккио

Though the problem seems difficult, it is really very simple!
Послано Nijino Saki 9 июн 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!
Послано Stefan Pochmann 9 июн 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!
Послано Maigo Akisame 11 июн 2004 08:04
Just calculate the GCD of the given numbers!