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


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

Ви не зайшли.

#1 2008-10-04 16:20:54

partisan
Олімпієць
Звідки: Киев
Зареєстрований: 2005-11-04
Повідомлень: 180

Разбор задач 1-го тура

Задача Simplenumbers:

Тут проходит самое простое решение: просто перебираем все числа от А до Б, проверяем на простоту, и если простое, добавляем +1 для каждой из цифр. Сложность, если считать smile, O((b-a)*sqrt(b)).
Можно найти все простые числа решетом Эратосфена, а потом сделать такой же проход (от А до Б). Это будет O((b-a)*log b). Решето Эратосфена работает где-то между O(n) и O(n*log n) (каждое число считается столько раз, сколько у него делителей -отсечения).

Первый код:

Код:

{$APPTYPE CONSOLE}
{$B-,R-,O+}
const
 maxn=10000;
var
 a,b,x:smallint;
 i,j:smallint;
 d:array[0..9] of longint;
function prost(a:smallint):boolean;
var
 i:smallint;
begin
 if (a mod 2=0) then
  begin
   if a=2 then prost:=true else
    prost:=false;
  end else
  begin
    i:=3;
    while(i*i<=a)and(a mod i<>0)do inc(i,2);
    if a mod i=0 then
     prost:=false else
     prost:=true;
  end;
end;
begin
 readln(a,b);
 fillchar(d,sizeof(d),0);
 for i:=a to b do
  if prost(i) then
   begin
    x:=i;
    while(x>0)do
     begin
      inc(d[x mod 10]);
      x:=x div 10;
     end;
   end;
 x:=0;
 for i:=1 to 9 do
  if d[i]>d[x] then
   x:=i;
 writeln(x);    
end.

Второй код:

Код:

{$APPTYPE CONSOLE}
{$B-,R-,O+}
const
 maxn=10000;
var
 a,b,x:smallint;
 i,j:smallint;
 p:array[2..maxn] of boolean;
 d:array[0..9] of longint;
begin
 readln(a,b);
 fillchar(p,b,1);
 for i:=2 to round(sqrt(b)) do
  if p[i] then
   begin
    j:=i*i;
    while(j<=b)do
     begin
      p[j]:=false;
      inc(j,i);
     end;
   end;
 fillchar(d,sizeof(d),0);
 for i:=a to b do
  if p[i] then
   begin
    x:=i;
    while(x>0)do
     begin
      inc(d[x mod 10]);
      x:=x div 10;
     end;
   end;
 x:=0;
 for i:=1 to 9 do
  if d[i]>d[x] then
   x:=i;
 writeln(x);    
end.

Задача Measure:

Сортируем по левому краю. Далее делаем проход, поддерживая два числа l и r - начало и конец диапазона, покрываемого на даном шаге. Для i-го отрезка, если a[i].l<=r и a[i].r>r, тогда переносим правый конец r:=a[i].r, если a[i].l>r, то в текущий диапазон больше не попадет ни один отрезок (отсортированы по левому краю), тогда добавляем к общей длине r-l, и "начинаем" новый диапазон l:=a[i].l r:=a[i].r. Сложность O(n*log n)

Код:

{$APPTYPE CONSOLE}
{$B-,R-,O+,N+}
const
 maxn=10000;
type
 interval=record
  l,r:extended;
 end;
var
 n,i:smallint;
 a:array[1..maxn] of interval;
 l,r:extended;
 ans:extended;
procedure Sort(l,r:smallint);
var
 i,j:smallint;
 k:extended;
 x:interval;
begin
 if l<r then
  begin
   i:=l;
   j:=r;
   k:=a[l+random(r-l+1)].l;
   repeat
    while a[i].l<k do inc(i);
    while a[j].l>k do dec(j);
    if i<=j then
     begin
      x:=a[i];
      a[i]:=a[j];
      a[j]:=x;
      inc(i);
      dec(j);
     end;
   until i>j;
   Sort(l,j);
   Sort(i,r);
  end;
end;
begin
 readln(n);
 for i:=1 to n do
  readln(a[i].l,a[i].r);
 Sort(1,n);
 ans:=0;
 l:=a[1].l-1;
 r:=a[1].l-1;
 for i:=1 to n do
  if r<a[i].l then
   begin
    ans:=ans+r-l;
    l:=a[i].l;
    r:=a[i].r;
   end else
  if a[i].r>r then
   r:=a[i].r;
 ans:=ans+r-l;  
 writeln(ans:1:1);  
end.

Задача Symmetry:

Перебираем каждый символ и пропуск между символами, и от него расходимся в стороны, пока символы на концах совпадают. Так мы переберем все наибольшие палиндромы для каждого возможного "центра", и получим ответ. Этот подход применяется во многих задачах на такие палиндромы. Сложность O(n^2)

Код:

{$APPTYPE CONSOLE}
{$B-,R-,O+}
const
 maxn=1000;
var
 n,i,j:smallint;
 a:array[1..maxn] of smallint;
 ans,index:smallint;
begin
 readln(n);
 for i:=1 to n do
  read(a[i]);
 ans:=1;
 index:=1;
 for i:=1 to n-1 do
  begin
   j:=0;
   while(i-j>1)and(i+j<n)and(a[i-j-1]=a[i+j+1])do inc(j);
   if 2*j+1>ans then
    begin
     ans:=2*j+1;
     index:=i-j;
    end;
   j:=0;
   while(i-j>=1)and(i+j+1<=n)and(a[i-j]=a[i+j+1])do inc(j);
   if 2*j>ans then
    begin
     ans:=2*j;
     index:=i+1-j;
    end;
  end;
 writeln(index,' ',ans); 
end.

Задача Perfectlines:

Можно сделать за O(n^2) с помощью хеширования: Перебираем длину подслова (бинарный поиск не пройдет). Составляем хеш-коды всех подстрок заданой длины (k), это можно сделать за линейный проход, сдвигаясь на одну букву. Потом для каждого i=1,n-2k+1 рассматриваем i-й символ, как начало вхождения T. Если T+T входит начиная с i-го символа, то хеш-функции f[i] и f[i+k] должны быть равны изза необходимого равенства подстрок. Если они равны, делаем посимвольное сравнение, и в случае удачи записываем результат. В среднем это будет O(n^2). Для тех, кто не знает: хеш-функция чего-то - это некоторый его "отпечаток", например для строки в качестве хеш-функции можно взять ее представление как числа в какой-то системе счисления (например, с основанием b=257), взятое по какому-то модулю M (например, 299993). Так, строка a1,a2,...,an будет именть хеш-функцию (a1*b^(n-1)+a2*b^(n-2)+...+a(n-1)*b+an)mod M. Значение этой хеш-функции будет целым числом от 0 до M-1. Если строки равны, то и их хеш-функции должны быть равны. Обратное, понятно, не всегда верно, но если строк будет даже до 10000, а модуль порядка 300000, то вероятность этого очень низкая. В одну ячейку попадет максимум несколько строк (O(1) smile). Модуль и базу желательно брать простым числом, или хотя бы не делящиеся на 2,3,5.

Код:

{$APPTYPE CONSOLE}
{$B-,R-,O+}
const
 maxn=100;
 base=257;
 modul=299993;
var
 s:string;
 a:array[1..maxn] of smallint;
 n,i,j,k:smallint;
 f:array[1..maxn] of longint;
 tek,maxdigpow:longint;
 flag:boolean;
begin
 readln(s);
 n:=length(s);
 for i:=1 to n do
  a[i]:=Ord(s[i])-Ord('a');
 flag:=false;
 k:=n div 2+1;
 while(k>0)and(not flag)do
  begin
   dec(k);
   tek:=0;
   maxdigpow:=1;
   for i:=1 to k do
    begin
     tek:=(tek*base+a[i])mod modul;
     maxdigpow:=(maxdigpow*base)mod modul;
    end;
   f[1]:=tek;
   for i:=2 to n-k+1 do
    begin
     tek:=(tek*base+modul-(maxdigpow*a[i-1])mod modul+a[i+k-1])mod modul;
     f[i]:=tek;
    end;
   for i:=k+1 to n-k+1 do
    if f[i]=f[i-k] then
     begin
      j:=0;
      while(j<k)and(a[i+j]=a[i-k+j])do inc(j);
      if j=k then
       flag:=true;
     end;
  end;
 writeln(k);
end.

Поза форумом

 

#2 2008-10-04 19:57:15

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Разбор задач 1-го тура

Молодец smile

Теперь свои 5 копеек...

В первой задаче у меня, опять же, предпросчет всех чисел, только я решил сэкономить еще больше времени и засунул их в ansistring, i-тый символ которого равен '1', если число простое, или '0', если нет; в результате размер исходника возрос до 10+ Кб, но это все еще в пределах допустимости smile
Цифры находил обычным div-mod'овским методом. Если не учитывать эту особенность — вполне O(N).

Во второй задаче у меня тоже O(N). Считаем, что каждое начало отрезка — это открывающая скобочка, каждый конец — закрывающая скобочка. Проходим массив слева направо, если попалась открывающая скобочка (или несколько открывающих скобочек в одном месте), то увеличиваем некий счетчик на количество этих самых скобочек. Для закрывающих скобочек, соответственно, счетчик уменьшаем. Если на очередном шаге счетчик больше нуля — увеличиваем ответ на единицу. И ничего не надо сортировать smile

В третьей задаче я передвигал предполагаемый центр палиндрома слева направо, и для каждого значения центра проверял, совпадают ли элементы, отстоящие на N позиций слева и N позиций справа от центра; если они совпадают, N увеличивается, и так происходит, пока найдется несовпадение, либо когда дальше двигаться уже будет нельзя (тогда вся строка — палиндром). Учтены два случая: когда центр состоит из одного элемента (длина палиндрома нечетная) и двух (четная соответственно). В результате — N^2 + N^2 = O(2*N^2).
Перебор можно было усовершенствовать, но мне было лень, и в итоге получилось 27 баллов вместо 30, хотя онлайн-проверка дает все 30 smile

В четвертой задаче я сделал просто полный перебор (N^3), прошло все тесты.

Исходники здесь: http://drop.io/s_olymp

Поза форумом

 

#3 2008-10-04 21:33:03

partisan
Олімпієць
Звідки: Киев
Зареєстрований: 2005-11-04
Повідомлень: 180

Re: Разбор задач 1-го тура

guest1 написав:

Цифры находил обычным div-mod'овским методом. Если не учитывать эту особенность — вполне O(N).

Это как раз дает O(N*log N) (2^(k-1)<N<=2^k. k=log N)

guest1 написав:

Во второй задаче у меня тоже O(N). Считаем, что каждое начало отрезка — это открывающая скобочка, каждый конец — закрывающая скобочка. Проходим массив слева направо, если попалась открывающая скобочка (или несколько открывающих скобочек в одном месте), то увеличиваем некий счетчик на количество этих самых скобочек. Для закрывающих скобочек, соответственно, счетчик уменьшаем. Если на очередном шаге счетчик больше нуля — увеличиваем ответ на единицу. И ничего не надо сортировать smile

Да, точно:) Числа множим на 10 и получаем целые.

Поза форумом

 

#4 2008-10-04 22:08:46

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Разбор задач 1-го тура

partisan написав:

Это как раз дает O(N*log N) (2^(k-1)<N<=2^k. k=log N)

Минут 10 думал — наконец, понял, что этих самых div-mod'овских операций будет столько, какова длина нашего числа. Я-то думал, при чем здесь эти логарифмы smile Голова к вечеру уже не работает...

Поза форумом

 

#5 2008-10-15 20:13:16

NEWUSER
Новий користувач
Зареєстрований: 2007-11-01
Повідомлень: 9

Re: Разбор задач 1-го тура

Еще один вариант решения 1-ой задачи (написан на С++, проходит все тесты). Алгоритм похож на 1-ое решения, предложенное partisan, но есть некоторые отличия в реализации (не связанные с языком программирования), кроме того отбрасываются числа, кратные 3.
#include <stdio.h>
#include <iostream.h>
#include <math.h>


#define BASE    10
#define MIN_DIV 5
#define DELTA    2


int main()
{
    int max, max_div, min, div, i, cur_i, mod3_div, mod3;
    int dig_ar[BASE] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

    cin >> min >> max;

    if (min == 2)
        dig_ar[2]++;

    i = min | 1;

    if (i == 3)
    {
        dig_ar[3]++;
        i = 5;
    }

    if ((mod3 = - (i % 3)) == 0)
    {
        i += DELTA;
        mod3 = -DELTA;
    }

    while (i<= max)
    {
        for (div = MIN_DIV, max_div = int(sqrt(i)), mod3_div = -DELTA; div <= max_div; div += DELTA)
        {
            if (i % div == 0)
                goto cont;
               
            if (++mod3_div == 0)
            {
                mod3_div = -DELTA;
                div += DELTA;
            }

        }

        cur_i = i;
        while (cur_i >= BASE)
        {
            dig_ar[cur_i % BASE]++;
            cur_i /= BASE;
        }
        dig_ar[cur_i]++;

cont:
        i += DELTA;
        if (++mod3 == 0)
        {
            mod3 = -DELTA;
            i += DELTA;
        }
    }

    max = dig_ar[(cur_i = BASE - 1)];

    for (i = BASE - 2; i >= 0; i--)
    {
        if (dig_ar[i] >= max)
            max = dig_ar[(cur_i = i)];
    }

    cout << cur_i;

    return 0;
}

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt