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

Silicious Man · 2010-11-22 00:18:39

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

//Начинаю выкладывать полнобальные решения.
//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)

Silicious Man · 2010-11-22 00:21:25

// 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 > 1{ // начиная с девяти, потому что взять, скажем, 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;
}

Silicious Man · 2010-11-22 00:22:45

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

Silicious Man · 2010-11-22 00:40:31

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

redman17 · 2010-11-22 01:13:53

Ну в 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++;
    }
}

Silicious Man · 2010-11-22 01:16:12

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

MItornaDOS · 2010-11-22 08:40:09

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

Loginf · 2010-11-22 08:48:28

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

LeonID · 2010-11-22 08:52:16

дихлофос

Код:

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.

MItornaDOS · 2010-11-22 08:52:43

Код:

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)

LeonID · 2010-11-22 08:54:41

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.

LeonID · 2010-11-22 09:04:35

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.

pilya · 2010-11-22 11:18:26

Кому интересно 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;
}

kreed · 2010-11-22 15:45:19

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

Присяжнюк А.В. · 2010-11-22 16:36:30

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

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

kreed · 2010-11-22 16:39:08

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

Присяжнюк А.В. · 2010-11-22 16:45:20

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

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

Александр · 2010-11-23 09:33:40

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

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

LeonID · 2010-11-23 10:03:36

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

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

LVV · 2010-11-23 12:22:39

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)

Александр · 2010-11-23 14:24:44

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

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

Silicious Man · 2010-11-23 14:30:22

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

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

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

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

Loginf · 2010-11-23 16:13:27

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

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

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

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

Александр · 2010-11-23 18:44:02

Loginf написав:
Александр написав:
Да согласен, я ошибся, вместо НОД - НОК, не все-же на первоначальный вопрос ответа от жури не было
Прочитайте ещё раз вопрос:
" Скільки обертів зробить перша шестерня до того моменту, коли мітки на всіх шестернях знову співпадуть? "

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

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

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

Присяжнюк А.В. · 2010-11-23 18:55:19

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Код:

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

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

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

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

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

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

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

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

Код:

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

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

Код:

Код:

Код:

Код:

Код:

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

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

Код:

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

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

Код:

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

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

Код:

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

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

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

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

kreed написав:

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

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

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

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

kreed написав:

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

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

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

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

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

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

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

Silicious Man написав:

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

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

LeonID написав:

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

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

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

LVV написав:

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

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

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

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

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

Loginf написав:

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

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

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

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

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