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

Хорошие были задачки. К сожалению традиции NetOi таковы, что решения мы увидим лишь через несколько месяцев.
А участники не очень спешат поделиться своими 60-бальными  решениями

Paint "в лоб" решается легко, вложенными циклами:
Рассматриваем различные пары точек (два цикла i,0,N; j,i,N; ) и для каждой пары (Xi,Yi)-(Xj,Yj) рассматриваем все имеющиесся точки (третий цикл z,0,N; ) на принадлежность прямой: (Xz-Xi)*(Yj-Yi)==(Yz-Yi)*(Xj-Xi).
Правда, при N=1000 придётся произвести около 500 000 000 проверок на выполнение условия, а значит тайм-лимит выдержан не будет.

Можно использовать двумерный массив, индексы которого являются координатами точек. Тогда достаточно в обнулённом массиве отметить, единицами, наличие координат, и, для каждой из 500 000 возможных прямых рассматривать не все 1000 вариантов, а определить целочисленный шаг для координат, и проверять через этот шаг наличие единицы в двумерном масиве. Но тут возникает другая проблема: даже для битового массива (в С++ есть bitset) объём 1000000 х 1000000 слишком велик.
Учитывая, что точек (ячеек) в таком огромном массиве используется всего лишь 1000, следует использовать так называемый разреженный массивы.

Відредаговано LVV (2013-02-08 16:46:21)

Для успішного розв’язку задачі № 5 потрібно звести складність до n^2 log(n).
А. Перебираємо по всім точкам від 1 до n-2 і знаходимо трійки точок, до яких обов’язково входить і-та.
  Б. Сортуємо інші точки (j від i+1 до n) за напрямом від і-ї точки. Я пробував три способи, вони дають приблизно однаковий результат за часом:
    а. (тип double)За кутовим коефіцієнтом k прямої, яка проходить через точки Pi та Pj.
       Для вертикальної прямої можна обрати, наприклад, k=3*10^9.
    б. (тип int64) За векторним добутком (Xk-Xi)(Yj-Yi)-(Xj-Xi)(Yk-Yi).
    в. (тип int) За вектором PiPj. Коефіцієнти вектора скорочують на НСД((Xj-X),(Yj-Yi)).
        Окремо розглядаються горизонтальний та вертикальний одиничні вектори.
  В. Визначається кількість точок К, що лежать на одній прямій. Тоді кількість трійок збільшується на 3К(К-1)/2.
Найбільший час проходження одного теста – 0,38с.
#include <iostream>
#include <cstdio>
#include <stdlib.h>
using namespace std;
#define N 1001
int G(int a,int b){
  return (b)?G(b,a%b):a;
}
struct L{int x,y;};
L a[N];
int C(const void* a,const void* b){
  const L* c = (L*)a;
  const L* d = (L*)b;
  int k=c->x-d->x;
  if(k)return k;
  return (c->y-d->y);
}
int main(){
  int i,j,k,m,n,r,x[N],y[N],dx,dy,q,res=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d%d",&x[i],&y[i]);
  for(i=0;i<n-2;i++){
    for(m=-1,j=i+1;j<n;j++){
      dx=x[i]-x[j];dy=y[i]-y[j];
      if(dx)
        if(dy){
          if(dx<0){dx=-dx;dy=-dy;}
          r=G(dx,abs(dy));
          if(r>1){dx/=r;dy/=r;}
          a[++m].x=dx;a[m].y=dy;
        }else {a[++m].x=1;a[m].y=0;}
      else {a[++m].x=0;a[m].y=1;}
    }
    qsort(a,m+1,sizeof(L),C);
    for(q=k=1;k<=m;k++)
      if((a[k].y==a[k-1].y)&&(a[k].x==a[k-1].x))q++;
      else{if(q>1)res+=q*(q-1);q=1;}
    res+=q*(q-1);
  }
  cout << 3*res/2 << endl;
  return 0;
}

Відредаговано Alex_Bulany (2013-02-08 15:31:27)

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

#include "iostream.h"
using namespace std;
int main()
{
  int  w[600]={0};
    int a, b, i, j=1, k=0, m, p=1 ;
     cin >> m >> a;
     for (i=2; i<m; i++)
    {  cin >> b;
       if  ((a>b) && (j==1) || (a<b) && (j==-1))  p++; else
       {j=-j;w[k]=p;k++; p=1;}
       a=b;
    }  if (j==-1) w[k]=p+1; else {w[k]=p; k++;w[k]=1;}
    p=0;
    for (i=1; i<=k; i=i+2)
    {
      if (w[i-1]%2==0 && w[i]%2)
      {cout << p+w[i-1] << " ";p=p+w[i-1]+w[i];continue;}
      if (w[i-1]%2 && w[i]%2==0)
      {cout << p+w[i-1] +1<< " ";p=p+w[i-1]+w[i];continue;}
      p=p+w[i-1]+w[i];
    }     
    return 0;
}