Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2010-11-22 00:18:39

Silicious Man
Новий користувач
Звідки: Донецк
Зареєстрований: 2007-11-11
Повідомлень: 79

Решения задач с первого тура

// Результаты вывешены.


//Начинаю выкладывать полнобальные решения.
//GEARSET


#include <iostream>
#include <cmath>

using namespace std;

unsigned long long gcd (unsigned long long a, unsigned long long b){ // НОД
    if (b > a) swap (a, b);
    while (b > 0){
        unsigned long long c = a % b;
        a = b;
        b = c;
    }
    return a;
}

unsigned long long lcm (unsigned long long a, unsigned long long b){ // НОК
    return (a / gcd (a, b)) * b;
}

int main (void) {
    unsigned long long n;
    unsigned long long g[20];
    cin >> n;
    unsigned long long LCM = 1;
    for (unsigned long long i = 0; i < n; i++){
        cin >> g[i];
        if (g[i] % 2 == 0 && i != 0 && i != n - 1)
            LCM = lcm(LCM, g[i] / 2); // шестерня с четным количеством зубов посередине может рассматриваться как в два раза меньшая
        else
            LCM = lcm(LCM, g[i]);
    }
   
    cout << LCM / g[0] << "\n";
   
    return 0;
}

Відредаговано Silicious Man (2010-11-22 14:04:53)


—————————————————————————————————
Life is a beautiful place where dreams and reality live in peace.

Поза форумом

 

#2 2010-11-22 00:21:25

Silicious Man
Новий користувач
Звідки: Донецк
Зареєстрований: 2007-11-11
Повідомлень: 79

Re: Решения задач с первого тура

// MULTIPLICATION

#include <iostream>

using namespace std;

int main (void) {
    int n;
    cin >> n;    // n <= 2147483647
    if (n == 1) { cout << "1\n"; return 0; }
    int factors[10];
    memset (factors, 0, sizeof factors);
   
    for (int current = 9; n > 1wink{ // начиная с девяти, потому что взять, скажем, 9, выгоднее, чем 3 * 3 * 3.
        if (n % current == 0){
            factors[current]++;
            n /= current;
        } else {
            current--;
            if(current == 1){ // мы дошли до единицы, но при этом остались ещё делители (которые, очевидно, больше 9)
                cout << "0\n";
                return 0;
            }
        }
    }
    for (int i = 2; i <= 9; i++) // Начиная с двойки, потому что, например 25 меньше 52
        for (int j = 1; j <= factors[i]; j++)
            cout << i;
    cout << "\n";
    return 0;
}


—————————————————————————————————
Life is a beautiful place where dreams and reality live in peace.

Поза форумом

 

#3 2010-11-22 00:22:45

Silicious Man
Новий користувач
Звідки: Донецк
Зареєстрований: 2007-11-11
Повідомлень: 79

Re: Решения задач с первого тура

// BOREDOM2


#include <iostream>
#include <cmath>

using namespace std;

long long gcd (long long a, long long b){ // НОД
    if (b > a) swap (a, b);
    while (b > 0){
        long long c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main (void) {
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    long long x, y;
    x = abs(x1 - x2);
    y = abs(y1 - y2);
    cout << gcd (x, y) - 1 << "\n";
    return 0;
}


—————————————————————————————————
Life is a beautiful place where dreams and reality live in peace.

Поза форумом

 

#4 2010-11-22 00:40:31

Silicious Man
Новий користувач
Звідки: Донецк
Зареєстрований: 2007-11-11
Повідомлень: 79

Re: Решения задач с первого тура

// DIHLOFOS

#include <iostream>
using namespace std;

int main (void) {
    int n, k;
    int a[1100];
    memset(a, 0, sizeof a);
    cin >> n >> k;
   
    for (int i = 0; i < k; i++){
        int x, y, z;
        cin >> x >> y >> z;
        a[x] -= z;
        a[y] += z;
    }
   
    int sum = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] < 0)
            sum -= a[i];
   
    cout << sum << "\n";
    return 0;
}


—————————————————————————————————
Life is a beautiful place where dreams and reality live in peace.

Поза форумом

 

#5 2010-11-22 01:13:53

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Решения задач с первого тура

Ну в RUNAWAY-е идея довольно проста - гибрид задачи поиска длины пути короля между двумя клетками на доске и нахождение количества наименьших чисел из списка:

Код:

//Runaway

#include <iostream>

using namespace std;

int KingPath(int x1, int y1, int x2, int y2);
void UpdateAnsBy(int curPath, int &minPath, int &numMins);

main()
{
    int m, n, x, y;
    
    cin >> m >> n >> x >> y;
    
    int i, minPath = m*n + 1, numMins = 0;
    
    for (i=1; i<=m; i++)
    {
        UpdateAnsBy(KingPath(x,y,i,1), minPath, numMins);     
        if (n!=1) UpdateAnsBy(KingPath(x,y,i,n), minPath, numMins);
    }
    for (i=2; i<=n-1; i++)
    {
         UpdateAnsBy(KingPath(x,y,1,i), minPath, numMins);
         if (m!=1) UpdateAnsBy(KingPath(x,y,m,i), minPath, numMins);
    }
    
    cout << numMins;
}

int KingPath(int x1, int y1, int x2, int y2)
{
    return max(abs(x2-x1),abs(y2-y1));
}

void UpdateAnsBy(int curPath, int &minPath, int &numMins)
{
    if (curPath < minPath)
    {
        minPath = curPath;
        numMins = 1;
    } else
    if (curPath == minPath)
    {
        numMins++;
    }
}

WE DIE HARD!!!

Поза форумом

 

#6 2010-11-22 01:16:12

Silicious Man
Новий користувач
Звідки: Донецк
Зареєстрований: 2007-11-11
Повідомлень: 79

Re: Решения задач с первого тура

Пол часа назад там было что-то не так с третьим тестом... Я, будучи уверенным в решении, пытался его вытащить, отправляя разные решения, но когда мне это удалось, тест поправили smile


—————————————————————————————————
Life is a beautiful place where dreams and reality live in peace.

Поза форумом

 

#7 2010-11-22 08:40:09

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Решения задач с первого тура

Кидати варіанти з паскаля, чи всі і в сі розберуться?

Поза форумом

 

#8 2010-11-22 08:48:28

Loginf
Новий користувач
Зареєстрований: 2009-11-25
Повідомлень: 37

Re: Решения задач с первого тура

MItornaDOS
Кинь будь-ласка GEARSET)

Поза форумом

 

#9 2010-11-22 08:52:16

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Решения задач с первого тура

дихлофос

Код:

var n,k,i,kol,per,pri,summ:longint;
mic:array[1..2000]of integer;
begin
read(n);
read(k);
for i:=1 to k do begin
    read(per);read(pri);read(kol);
    mic[per]:=mic[per]-kol;
    mic[pri]:=mic[pri]+kol;
end;
for i:=1 to n do
    if mic[i]<0 then
    summ:=summ+mic[i];
writeln(abs(summ));
end.

Поза форумом

 

#10 2010-11-22 08:52:43

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Решения задач с первого тура

Код:

program Boredom2;

var
  X1, X2, Y1, Y2, X, Y, T: Longint;
begin
  Read(X1, Y1, X2, Y2);
  X := Abs(X2 - X1);
  Y := Abs(Y2 - Y1);
  if X < Y then
    begin
      T := X;
      X := Y;
      Y := T;
    end;
  while Y > 0 do
    begin
      X := X mod Y; 
      T := X;
      X := Y;
      Y := T;
    end;
  Write(X - 1);   
end.

Код:

program Dihlofos;

uses
  Math;
var
  N, K, I, A, B, C: Longint;
  Balance: array [1..1000] of Longint;

begin
  FillChar(Balance, SizeOf(Balance), 0);
  Read(N, K);

  for I := 1 to K do
    begin
      Read(A, B, C);
      Dec(Balance[A], C);
      Inc(Balance[b], C);
    end;
  K := 0;  
  for I := 1 to N do
    if Balance[i] < 0 then K := K - Balance[i]; //"-" бо від'ємні числа

  Write(K);
end.

Код:

program GearSet;

uses
  Math;
var
  N, I: Longint;
  Z: array [1..10] of Longint;
  C: Int64;

function NSK(X, Y: Int64): Int64;
var
  A, B, C: Int64;
begin
  A := X;
  B := Y;
  if A < B then
    begin
      C := A;
      A := B;
      B := C;
    end;
  while B > 0 do
    begin
      A := A mod B;
      C := A;
      A := B;
      B := C;
    end;
  NSK := X * Y div A;  
end;

begin
  Read(N);
  for I := 1 to N do
    begin
      Read(Z[i]);
      if (Z[i] mod 2 = 0) and (I <> 1) and (I <> N) then
        Z[i] := Z[i] div 2;
    end;
  C := NSK(Z[1], Z[2]);
  for I := 3 to N do C := NSK(C, Z[i]);
  Write(C div Z[1]);  
end.

Код:

program Multiplication;

var
  N: Int64;
  I, J: Longint;
  A: array[2..9] of Longint;

begin
  Read(N);
  FillChar(A, SizeOf(A), 0);
  for I := 9 downto 2 do
    while N mod I = 0 do
      begin
        N := N div I;
        Inc(A[i]);
      end;
  if N = 1
    then
      for I := 2 to 9 do
        for J := 1 to A[i] do
          Write(I)
    else Write(0);
end.

Код:

program Runaway;

uses
  Math;
var
  M, N, X, Y, P, I: Longint;
  K: array [0..4] of Longint;
  B: array [0..4] of Boolean;

begin
  Read(M, N, X, Y);
  K[1] := Y - 1;
  K[2] := X - 1;
  K[3] := N - Y;
  K[4] := M - X;
  K[0] := Min(K[1], K[2]);
  K[0] := Min(K[3], K[0]);
  K[0] := Min(K[4], K[0]);
  P := 0;
  for I := 1 to 4 do
    begin
      B[i] := K[0] = K[i];
      if B[i] then Inc(P, 2 * K[0] - 1);
    end;
  if B[1] or B[2] then Inc(P);
  if B[2] or B[3] then Inc(P);
  if B[3] or B[4] then Inc(P);
  if B[4] or B[1] then Inc(P);

  if K[0] = 0
    then Write(1)
    else Write(P); 
end.

Відредаговано MItornaDOS (2010-11-22 08:54:04)

Поза форумом

 

#11 2010-11-22 08:54:41

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Решения задач с первого тура

boredom2

Код:

var a,b,c,d:longint;
begin
read(a,b,c,d);
a:=abs(a-c);
b:=abs(b-d);
if (a=0) and (b=0)then begin
a:=1;
b:=1;
end else
if (a=0) then a:=b else if (b=0) then b:=a;
while a<>b do begin
if a>b then a:=a mod b;
if a=0 then a:=b;
if b>a then b:=b mod a;
if b=0 then b:=a;
end;
writeln(a-1);
end.

Поза форумом

 

#12 2010-11-22 09:04:35

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Решения задач с первого тура

gearset

Код:

function nsk(a,b:Int64):Int64;
var c,d:Int64;
begin
     c:=a;d:=b;
     while(a<>b)do begin
                   if a>b then begin
                   a:=a mod b;
                   if a=0 then a:=b;
                   end else begin
                   b:=b mod a;
                   if b=0 then b:=a;
                   end;
     end;
     nsk:=(c*d)div a;
end;
var z1,pz1,z2:Int64;
i,n:longint;
begin
read(n);read(z1);pz1:=z1;
        for i:=2 to n-1 do begin
            read(z2);
            if (z2 mod 2=0) then z2:=z2 div 2;
            z1:=nsk(z1,z2);
        end;
        read(z2);
        z1:=nsk(z1,z2);
writeln(z1 div pz1);
end.

Поза форумом

 

#13 2010-11-22 11:18:26

pilya
Новий користувач
Зареєстрований: 2009-11-14
Повідомлень: 98

Re: Решения задач с первого тура

Кому интересно dihlofos c одинарным прохождением массива

Код:

#include <iostream>
using namespace std;
int main(void)
{
    long i,n,k,a[1000];
    cin>>n>>k;
    for(i=0;i<n;i++) a[i]=0;
    long n1,n2,e;
    long s;
    s=0;
    for(i=0;i<k;i++)
    {
        cin>>n1>>n2>>e;
        if(a[n1-1]<e) 
        {
            if (a[n1-1]>0) s+=e-a[n1-1]; else s+=e;
        }
        if(a[n2-1]<0)
        {
            if(a[n2-1]+e<0) s-=e; else s-=-a[n2-1];
        }
        a[n1-1]-=e;
        a[n2-1]+=e;
    }
    cout<<s<<endl;
    return 0;
}

Поза форумом

 

#14 2010-11-22 15:45:19

kreed
Новий користувач
Звідки: Ставрополь
Зареєстрований: 2010-11-13
Повідомлень: 17

Re: Решения задач с первого тура

Можно тестовых данных побольше?

Поза форумом

 

#15 2010-11-22 16:36:30

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Решения задач с первого тура

kreed написав:

Можно тестовых данных побольше?

К какой задачке? smile


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#16 2010-11-22 16:39:08

kreed
Новий користувач
Звідки: Ставрополь
Зареєстрований: 2010-11-13
Повідомлень: 17

Re: Решения задач с первого тура

>К какой задачке?
К каким есть. wink
Хотелось бы проверить где и почему ошибся.

Поза форумом

 

#17 2010-11-22 16:45:20

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Решения задач с первого тура

kreed написав:

>К какой задачке?
К каким есть. wink
Хотелось бы проверить где и почему ошибся.

Ну так сгенерите ВСЕ возможные, потом  выложенными выше полнобальными решениями пполучите ВСЕ ответы и сравнивайте с тем, что выдаст Ваша программа.
Удачи !!!


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#18 2010-11-23 09:33:40

Александр
Новий користувач
Звідки: Киев
Зареєстрований: 2008-11-20
Повідомлень: 18

Re: Решения задач с первого тура

Уважаемое жури, не могли бы вы объяснить, почему в задаче GearSet, в условии которой нету упоминания о "МИНИМАЛЬНОМ количестве оборотов" обычный НОД набирает 9 балов, а НОД с делением парных шестеренок на 2 - набирает 20 балов?
В чем логока? И тот и другой ответ правильный: в обоих случаях "шестеренки снова совпадут", разница только во времени совпадения, но веде МИНИМАЛЬНОЕ время в задачи не спрашивалося!
И последнее -исходя из условии задачи можно было выводить не только НОД, а и 2*НОД, 3*НОД, 4*НОД ...
- ведь время никого не интересует - МИНИМАЛЬНОЕ оно или НЕТ!

Відредаговано Александр (2010-11-23 09:34:27)


Человек живет так, как будто он никогда не умрет,
и умирает так, как будто он никогда не жил...

Поза форумом

 

#19 2010-11-23 10:03:36

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Решения задач с первого тура

Александр написав:

Уважаемое жури, не могли бы вы объяснить, почему в задаче GearSet, в условии которой нету упоминания о "МИНИМАЛЬНОМ количестве оборотов" обычный НОД набирает 9 балов, а НОД с делением парных шестеренок на 2 - набирает 20 балов?
В чем логока? И тот и другой ответ правильный: в обоих случаях "шестеренки снова совпадут", разница только во времени совпадения, но веде МИНИМАЛЬНОЕ время в задачи не спрашивалося!
И последнее -исходя из условии задачи можно было выводить не только НОД, а и 2*НОД, 3*НОД, 4*НОД ...
- ведь время никого не интересует - МИНИМАЛЬНОЕ оно или НЕТ!

Насколько я понял, в задаче надо выводить не НОД(наибольший общий делитель), а НОК(наименьшее общее кратное) деленное на число зубьев первой шестерни, а это не НОД.

Поза форумом

 

#20 2010-11-23 12:22:39

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Решения задач с первого тура

Silicious Man написав:

// BOREDOM2


#include <iostream>
#include <cmath>

using namespace std;

long long gcd (long long a, long long b){ // НОД
    if (b > a) swap (a, b);
    while (b > 0){
        long long c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main (void) {
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    long long x, y;
    x = abs(x1 - x2);
    y = abs(y1 - y2);
    cout << gcd (x, y) - 1 << "\n";
    return 0;
}

почему везде long long ??? Ведь по условию задачи "Всі числа не перевищують за модулем 30000"  !!!
Но даже, если и long long, то не abs, а labs (от LongAbs)

Відредаговано LVV (2010-11-23 12:37:49)


Вік живи - вік навчайся.

Поза форумом

 

#21 2010-11-23 14:24:44

Александр
Новий користувач
Звідки: Киев
Зареєстрований: 2008-11-20
Повідомлень: 18

Re: Решения задач с первого тура

LeonID написав:

Александр написав:

Уважаемое жури, не могли бы вы объяснить, почему в задаче GearSet, в условии которой нету упоминания о "МИНИМАЛЬНОМ количестве оборотов" обычный НОД набирает 9 балов, а НОД с делением парных шестеренок на 2 - набирает 20 балов?
В чем логока? И тот и другой ответ правильный: в обоих случаях "шестеренки снова совпадут", разница только во времени совпадения, но веде МИНИМАЛЬНОЕ время в задачи не спрашивалося!
И последнее -исходя из условии задачи можно было выводить не только НОД, а и 2*НОД, 3*НОД, 4*НОД ...
- ведь время никого не интересует - МИНИМАЛЬНОЕ оно или НЕТ!

Насколько я понял, в задаче надо выводить не НОД(наибольший общий делитель), а НОК(наименьшее общее кратное) деленное на число зубьев первой шестерни, а это не НОД.

Да согласен, я ошибся, вместо НОД -  НОК, не все-же на первоначальный вопрос ответа от жури не было


Человек живет так, как будто он никогда не умрет,
и умирает так, как будто он никогда не жил...

Поза форумом

 

#22 2010-11-23 14:30:22

Silicious Man
Новий користувач
Звідки: Донецк
Зареєстрований: 2007-11-11
Повідомлень: 79

Re: Решения задач с первого тура

LVV написав:

почему везде long long ??? Ведь по условию задачи "Всі числа не перевищують за модулем 30000"  !!!
Но даже, если и long long, то не abs, а labs (от LongAbs)

long long потому что я тупо скопировал всё из GearSet и переделал; за labs спасибо — не знал

UPD: только наверное llabs?

Відредаговано Silicious Man (2010-11-23 14:54:53)


—————————————————————————————————
Life is a beautiful place where dreams and reality live in peace.

Поза форумом

 

#23 2010-11-23 16:13:27

Loginf
Новий користувач
Зареєстрований: 2009-11-25
Повідомлень: 37

Re: Решения задач с первого тура

Александр написав:

Да согласен, я ошибся, вместо НОД -  НОК, не все-же на первоначальный вопрос ответа от жури не было

Прочитайте ещё раз вопрос:
" Скільки обертів зробить перша шестерня  до того моменту, коли мітки на всіх шестернях знову співпадуть?  "

В любом случае он будет трактоваться как для минимального количества. Ведь вы тоже поняли его в начале правильно, но допустили ошибку в решении, и сейчас пытаетесь что-то сделать)) Позно уже какбы...

И опять к вопросу....представьте если у вас спросят "Сколько осталось дней до Нового Года?" Вы назовёте количество дней, которое осталось до следующего Нового Года, или же до того, что будет через 10 дней?
Тут даже есть ключевое слову "знову"

Поза форумом

 

#24 2010-11-23 18:44:02

Александр
Новий користувач
Звідки: Киев
Зареєстрований: 2008-11-20
Повідомлень: 18

Re: Решения задач с первого тура

Loginf написав:

Александр написав:

Да согласен, я ошибся, вместо НОД -  НОК, не все-же на первоначальный вопрос ответа от жури не было

Прочитайте ещё раз вопрос:
" Скільки обертів зробить перша шестерня  до того моменту, коли мітки на всіх шестернях знову співпадуть?  "

В любом случае он будет трактоваться как для минимального количества. Ведь вы тоже поняли его в начале правильно, но допустили ошибку в решении, и сейчас пытаетесь что-то сделать)) Позно уже какбы...

И опять к вопросу....представьте если у вас спросят "Сколько осталось дней до Нового Года?" Вы назовёте количество дней, которое осталось до следующего Нового Года, или же до того, что будет через 10 дней?
Тут даже есть ключевое слову "знову"

я не пытаюсь оправдать свое не решение или решение, и с результатами первого тура я тоже полностью согласен, просто хочу зделать акцент на том, что условие заадачи должно быть сформулировано однозначно, чтобы подобных споров больше не возникало


Человек живет так, как будто он никогда не умрет,
и умирает так, как будто он никогда не жил...

Поза форумом

 

#25 2010-11-23 18:55:19

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Решения задач с первого тура

Александр написав:

Уважаемое жури, не могли бы вы объяснить, почему в задаче GearSet, в условии которой нету упоминания о "МИНИМАЛЬНОМ количестве оборотов" обычный НОД набирает 9 балов, а НОД с делением парных шестеренок на 2 - набирает 20 балов?
В чем логока? И тот и другой ответ правильный: в обоих случаях "шестеренки снова совпадут", разница только во времени совпадения, но веде МИНИМАЛЬНОЕ время в задачи не спрашивалося!
И последнее -исходя из условии задачи можно было выводить не только НОД, а и 2*НОД, 3*НОД, 4*НОД ...
- ведь время никого не интересует - МИНИМАЛЬНОЕ оно или НЕТ!

Уважаемый Юрий Яковлевич и остальные члены жюри - участник на 100% прав - читаем условие, после чего СЧИТАЮ НУЖНЫМ сделать чекер и перетестировать все решения согласно выложенного условия, где о МИНИМАЛЬНОСТИ нет ни единого слова, как нет и речи о том, что совпадут в первый раз!.. smile - пусть даже в чекере придётся писать длинную арифметику, но здесь ребята на 100% правы...

"Истина - дороже..."
     (древние римляне)


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt