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


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

Ви не зайшли.

#26 2011-01-25 18:28:08

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

Re: Загальні питання

Хоча ні, не варто...
Для мене Ви вже нічого не доведете. Інших це не цікавить:)

Поза форумом

 

#27 2011-01-25 19:51:26

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

Re: Загальні питання

А коли буде проходити четвертий тур і хто до нього проходить?

13.02.2011, там же написано.

А можете подсказать, где написано, что четвертый (очный) тур будет проходить 13.02.2011? Что-то не могу найти.

Почему спрашиваю - именно 13.02.2011 в Киеве проходит второй тур городской олимпиады по информатике sad. Обидно получится.

Відредаговано Зевс (2011-01-25 19:53:23)

Поза форумом

 

#28 2011-01-25 20:03:24

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Загальні питання

99%, що 12.02.2011.
А можливо, уже й 100%, а я ще не знаю

Поза форумом

 

#29 2011-01-25 20:08:09

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

Re: Загальні питання

неактивним написано:

Завдання 4-го Real-Time туру NetOI-2010 (13/02/10)

Поза форумом

 

#30 2011-01-25 20:10:25

programist
Новий користувач
Зареєстрований: 2010-11-16
Повідомлень: 19

Re: Загальні питання

MItornaDOS написав:

неактивним написано:

Завдання 4-го Real-Time туру NetOI-2010 (13/02/10)

Це у минулому році. У цей рік можуть бути деякі зміни.

Поза форумом

 

#31 2011-01-25 23:05:44

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

Re: Загальні питання

Хм... я вважав, що /10 - це просто очепятка

Поза форумом

 

#32 2011-01-26 13:14:59

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

Re: Загальні питання

LeonID написав:

Статистика 3-го туру на 14 годину 25 січня.
Задача Division - 93 варіанти розвязків;
Задача Prize - 105 варіантів розвязків;
Задача Column - 109 варіантів розвязків;
Задача Towns - 67 варіантів розвязків;
Задача Іnstigator - 45 варіантів розвязків.

Статистика 3-го туру на 14 годину 26 січня.
Задача Division - 94 варіанти розвязків;
Задача Prize - 106 варіантів розвязків;
Задача Column - 110 варіантів розвязків;
Задача Towns - 67 варіантів розвязків;
Задача Іnstigator - 45 варіантів розвязків.

Цікаво...

Поза форумом

 

#33 2011-01-26 13:25:07

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

Re: Загальні питання

Ці 3 нові розв'язки перевірятись не будуть

Поза форумом

 

#34 2011-01-26 13:26:30

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 19

Re: Загальні питання

Division

Код:

#include <iostream.h>
long long a,b,p[100],k,i;

long long divise(long long m, long long n, int r){
  if(!r--)return n-m;
  long long x,y;
  x=m/p[r];y=n/p[r];
  if(x==y)return divise(m,n,r);  
  return divise(m,n,r)-divise(x,y,r);
}

int main(){  
  cin >> a >> b >> k;
  while(i<k)cin >> p[i++];
  cout << divise(--a,b,k);
  return 0;
}

Column

Код:

#include <iostream.h>

int N, n0,n,n2,i,x;

int main(){
  cin >> N;
  while(i++<N){
    cin >> x;
    n0+=!x;
    n2+=2*x-1;
    n<?=n2;
  }
  cout << n+n0;
  return 0;
}

Prize

Код:

#include<iostream.h>
int N,n,sum[101][101];               //we look for sum[0][0];
int pl[101][101],pl1[10001][2];      //pl[raw][column]=point. pl1[point][0] - raw, pl1[point][1]-column  
int num[10001],bet[10001],win[10001];//win[i] =1 if i-th point won.
int trace[10001];                    //to trail back traces positions. 

int main(){
  int x,y;
  cin >> N;
  for(int i=1;i<=N;i++){
    cin >> x;
    bet[x]=i; //куда поставил х
    num[i]=x; //кто поставил на i
  }
  
  x=y=0;   
  while(n*n!=N)n++;           //  n=sqrt(N);
  for(int i=1;i<=N;i++){      //  "fundamental" square;  
    pl[x][y]=i;               //  1  3  6    pl[2][1] = 7;
    pl1[i][0]=x;              //  2  5  8    pl1[7][0] = 2;
    pl1[i][1]=y;              //  4  7  9    pl1[7][1] = 1;
    x--;y++;
    if(y==n){y=2+x;x=n-1;} 
    if(x<0){x=y;y=0;}
  }       
 
  for(int i=n-1;i>=0;i--){
    for(int j=n-1;j>=0;j--){
      sum[i][j] = (sum[i][j+1] > sum[i+1][j])?       
      sum[i][j+1] : sum[i+1][j];                     
      trace[pl[i][j]]= (sum[i][j+1] > sum[i+1][j])?  
      pl[i][j+1] : pl[i+1][j];                       
      sum[i][j] +=  num[pl[i][j]];
    }
  }
  
  win[num[1]]=1;
  x=1;
  while(x=trace[x])win[num[x]]=1; 
  cout << sum[0][0] << "\n";
  for(int i=1;i<=N;i++)if(win[i])cout << i << " ";
  return 0;
}

Towns

Код:

#include <iostream.h>
const int NMAX=555+1;
int N,d[NMAX][NMAX],f[NMAX][NMAX],res;

int main(){
  cin >> N;
  for(int i=1;i<N;i++){
    for(int j=i+1;j<=N;j++){
      cin >> d[i][j];                      
      f[i][j] = f[i-1][j] + d[i-1][i];
      f[i][j] <?= f[i-1][i] + d[i-1][j];
      if(i==2)f[i][j] = d[1][j] + d[1][2];
    }
    res+=d[i][i+1];
  }
  f[N][N] = f[N-1][N] + d[N-1][N];
  cout << res << " " << f[N][N];
  return 0;
}

Поза форумом

 

#35 2011-01-26 14:48:02

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

Re: Загальні питання

andervish, яка ідея розвязку задачі division?

Поза форумом

 

#36 2011-01-26 15:04:30

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

Re: Загальні питання

Division вирішувати рекурсією - це утопія

Поза форумом

 

#37 2011-01-26 15:18:08

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

Re: Загальні питання

MItornaDOS написав:

Division вирішувати рекурсією - це утопія

Цей розвязок проходить тест 1е+18 на 30 перших дільників за 44 секунди на моєму слабенькому нетбуці(мій розвязок тратить на 10 секунд більше). Окрім цього мій розвязок такий довгий, що дочитавши його до кінця забуваєш що було на початку.

Відредаговано LeonID (2011-01-26 15:23:17)

Поза форумом

 

#38 2011-01-26 15:44:03

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

Re: Загальні питання

Точно! smile O_o
у мене працює 35 сек, а ця 25

Поза форумом

 

#39 2011-01-26 15:56:59

andervish
Новий користувач
Зареєстрований: 2011-01-16
Повідомлень: 19

Re: Загальні питання

LeonID написав:

яка ідея розвязку задачі division?

Если ищем кол-во тех, которые не делятся на k указанных простых чисел, то сначала найдем количество таких, которые не делятся на k-1 первых простых divise(a,b,k-1) и из него вычтем все те, которые делятся на последнее простое число p[k-1], но не делятся на все остальные divise(a/p[k-1],b/p[k-1],k-1).

Осталось показать, почему то, что вычитаем равно divise(a/p[k-1],b/p[k-1],k-1).
Все, числа между a и b, которые делятся на p[k-1] можно представить в виде p[k-1]*m, где m пробегает значения от a/p[k-1] (не включительно) до b/p[k-1] включительно. Если m не делится на k-1 первых простых чисел, то и исходное число не делится.

Окончание рекурсии
1) divise(a,b,0) = b-a;
2) divise(a,a,k) = 0;

В дальнейшем при оптимизации отсек последний шаг рекурсии (увеличило скорость на ~10...15%) и сделал как в коде. 

Старый более медленный исходник такой.

Код:

#include <iostream.h>
long long a,b,p[100],k,i;

long long divise(long long m, long long n, int r){
  if(!r--)return n-m;
  if(m==n)return 0;  
  return divise(m,n,r)-divise(m/p[r],n/p[r],r);
}

int main(){  
  cin >> a >> b >> k;
  while(i<k)cin >> p[i++];
  cout << divise(--a,b,k);
  return 0;
}

Поза форумом

 

#40 2011-01-26 16:27:16

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

Re: Загальні питання

Фух, мій розв'язок Division пройшов на 54 бали
я вже почав думати, що він і 30 не набере, після того, як виставили ідею andervish big_smile

Поза форумом

 

#41 2011-01-26 16:52:38

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Загальні питання

Сію хвилину бали ще не остаточні.
Остаточними бали будуть вважатися після того, як розішлють відповідного листа.
(якщо все гаразд -- дуже скоро).

Поза форумом

 

#42 2011-01-26 17:43:41

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

Re: Загальні питання

Дуже цікава ситуація. Удосконалена програма Division отримала меньше балів ніж початковий варіант. sad чи smile ...


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

Поза форумом

 

#43 2011-01-26 18:07:46

programist
Новий користувач
Зареєстрований: 2010-11-16
Повідомлень: 19

Re: Загальні питання

У статистиці у мене по задачі Prize - 52 бали. А на онлайн перевірці той самий розв'язок отримав 60 балів. Як таке може бути?

Поза форумом

 

#44 2011-01-26 18:09:01

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

Re: Загальні питання

Плз, киньте хтось ідею на Towns і Instigator

Поза форумом

 

#45 2011-01-26 18:14:28

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

Re: Загальні питання

programist написав:

У статистиці у мене по задачі Prize - 52 бали. А на онлайн перевірці той самий розв'язок отримав 60 балів. Як таке може бути?

Див. повідомлення Ilya Porublyov

Поза форумом

 

#46 2011-01-26 18:16:22

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Загальні питання

MItornaDOS написав:

Плз, киньте хтось ідею на Towns і Instigator

Towns -- Кормен, Лейзерсон, Ривест, Штайн, задача 15-1 (битоническая евклидова задача коммивояжера)
Instigator -- геометрія щоб з'ясовувати які пари вершин видимі одна з одної (не затуляють інші ребра), далі алгоритм Дейкстри або який-небудь аналог

programist написав:

У статистиці у мене по задачі Prize - 52 бали. А на онлайн перевірці той самий розв'язок отримав 60 балів. Як таке може бути?

Наскільки великий запас часу при он-лайн перевірці? Скопіюй час (по кожному тесту окремо) скільки працює ця програма і скільки працює яка-небудь дуже дурна, яка буде перевищувати ліміт часу абсолютно завжди. Якщо різниця по кільком тестам сумарною вартістю 8 балів мала -- ситуація нормальна і не підлягає апеляції.

==============================

А чому досі ніхто з учасників не виклав на форумі запит (адресу) який генерить сумарні результати за три тури? Зазвичай викладували раніше ніж у журі доходили руки писати цей запит... wink wink wink

А то я написав тільки http://www2.olymp.vinnica.ua/cgi-bin/v_ … nguage=ukr а всі 15 задач вписувати ліньки...

Відредаговано Ilya Porublyov (2011-01-26 18:28:53)

Поза форумом

 

#47 2011-01-26 18:26:30

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

Re: Загальні питання

Видаю свій код розвязку задачі division на  аудиторію, незважаючи на те, що він набирає(поки, що) лише 51 бал. Думаю, я один хто використав у цій задачі тип extended. Справа в тому, що множення довгих(int64) чисел займає набагато більше часу ніж додавання логарифмів цих чисел разом з наступним експонціюванням суми.

Код:

function dlinachisla(m:int64):extended;
begin
        dlinachisla:=ln(m);
end;
var
v:array[1..15]of integer;
k,n,p,p1:integer;
flag:boolean;
procedure inicializacia;
var i:integer;
begin
k:=0;
for i:=n-p1+1 to n do begin
inc(k);
v[k]:=i;
end;
end;
procedure novacombinacia;
var i:integer;
begin
    if v[1]>1 then dec(v[1]) else
                begin
            for i:=2 to p1 do
            if v[i]>i then begin
            dec(v[i]);
            break;
            end;
     for i:=i-1 downto 1 do v[i]:=v[i+1]-1;
    end;
end;
function novaformacia:boolean;
var i:integer;
begin
novaformacia:=false;
  for i:=2 to p1 do begin
        if (v[i]-v[i-1]>1) then begin
        dec(v[i]);
        novaformacia:=true;
        break;
        end;
  end;
    for i:=i-1 downto 1 do v[i]:=v[i+1]-1;
end;
var i,j,f,ff:integer;
a1,b1,sum,t,sumdiln,promsum:int64;
q:array[1..100]of int64;
lenge:array[1..100]of extended;
lengb1,lenga1,dl:extended;
begin
read(a1,b1,n);
if a1>b1 then begin sum:=a1;a1:=b1;b1:=sum;end;
for i:=1 to n do begin
    read(sum);
    q[i]:=sum;
end;
for i:=1 to n do
    for j:=n downto i do
    if q[i]<q[j] then begin
    t:=q[i];
    q[i]:=q[j];
    q[j]:=t;
    end;
for i:=1 to n do
lenge[i]:=dlinachisla(q[i]);
lengb1:=dlinachisla(b1);
lenga1:=dlinachisla(a1);
p:=n;f:=0;
dl:=0;a1:=a1-1;
for j:=n downto 1 do begin
        inc(f);
    dl:=dl+lenge[j];
    if dl>lengb1 then begin
        break;
        end;
        p:=f;
end;
ff:=-1;sumdiln:=0;
for i:=1 to p do begin
p1:=i;ff:=-ff;
inicializacia;flag:=false;
promsum:=0;
if (p1<p-1) then
repeat
      sum:=1;dl:=0;
        for j:=1 to p1 do
          dl:=dl+lenge[v[j]];
          if dl<=lengb1 then begin
         sum:=round(exp(dl));
        if dl>lenga1 then
            promsum:=promsum+b1 div sum
            else promsum:=promsum+b1 div sum-a1 div sum;
            if v[p1]=p1 then flag:=true;
            novacombinacia;
          end else
    if novaformacia then flag:=false else flag:=true;
until flag
else
repeat
      sum:=1;dl:=0;
        for j:=1 to p1 do
          dl:=dl+lenge[v[j]];
          if dl<=lengb1 then begin
             for j:=1 to p1 do
         sum:=sum*q[v[j]];
        if dl>lenga1 then
            promsum:=promsum+b1 div sum
            else promsum:=promsum+b1 div sum-a1 div sum;
            if v[p1]=p1 then flag:=true;
            novacombinacia;
          end else
    if novaformacia then flag:=false else flag:=true;
until flag;
sumdiln:=sumdiln+promsum*ff;
end;
writeln(b1-a1-sumdiln);
end.

Поза форумом

 

#48 2011-01-26 18:32:00

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Загальні питання

LeonID написав:

Видаю свій код розвязку задачі division на  аудиторію, незважаючи на те, що він набирає(поки, що) лише 51 бал. Думаю, я один хто використав у цій задачі тип extended.

Не знаю, як щодо часу роботи, але загальновідомо що extended не забезпечує достатню кількість знаків щоб точно зберігати довільне значення з int64. А тести які не проходить -- time limit чи wrong answer?

Поза форумом

 

#49 2011-01-26 18:37:14

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

Re: Загальні питання

Ilya Porublyov написав:

LeonID написав:

Видаю свій код розвязку задачі division на  аудиторію, незважаючи на те, що він набирає(поки, що) лише 51 бал. Думаю, я один хто використав у цій задачі тип extended.

Не знаю, як щодо часу роботи, але загальновідомо що extended не забезпечує достатню кількість знаків щоб точно зберігати довільне значення з int64. А тести які не проходить -- time limit чи wrong answer?

Щоб забезпечити точність прийшлось скоротити кількість доданків, всі помилки - time limit.

Поза форумом

 

#50 2011-01-26 19:03:12

programist
Новий користувач
Зареєстрований: 2010-11-16
Повідомлень: 19

Re: Загальні питання

Ilya Porublyov написав:

programist написав:

У статистиці у мене по задачі Prize - 52 бали. А на онлайн перевірці той самий розв'язок отримав 60 балів. Як таке може бути?

Наскільки великий запас часу при он-лайн перевірці? Скопіюй час (по кожному тесту окремо) скільки працює ця програма і скільки працює яка-небудь дуже дурна, яка буде перевищувати ліміт часу абсолютно завжди. Якщо різниця по кільком тестам сумарною вартістю 8 балів мала -- ситуація нормальна і не підлягає апеляції.

Дурна програма набрала 0 балів із Time Limit. Моя програма має час на 0-13 тестах: 0,01 секунди, а на останніх двох: 0,02 секунди.

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt