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

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

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

MItornaDOS написав:

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

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

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

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 варіантів розвязків.

Цікаво...

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

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

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

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

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

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

MItornaDOS написав:

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

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

programist написав:

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

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

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

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

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

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

LeonID написав:

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

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

Ilya Porublyov написав:

programist написав:

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

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

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