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


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

Ви не зайшли.

#1 2013-12-29 12:22:45

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Разбор задач

1. Strip.
Можно сразу заметить, что нужно отсортировать данные нам строки. Нужно лишь определиться по какому принципу это сделать. Вначале может показаться, что достаточно лексикографической сортировки, однако это даст неправильный ответ на, например, вот таком тесте:
2
777
77799

Правильным же решением будет при сортировке использовать компаратор, сравнивающий лексикографически конкатенации двух рассматриваемых в данный момент строк.
Наилучшая ассимптотика: O(n*n*logn).

Код:

bool lee(string a,string b)
{return a+b>b+a;}

main()
 {
    int n;
    cin>>n;
    string a[101];
    for(int i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n,lee);
    for(int i=0;i<n;i++)
    cout<<a[i];
    cout<<endl;
 }

2. Paint.
Для начала научимся считать сумму на участке 1..n. Очевидно, что сумму на участке l..r после этого можно будет получить, вычев из суммы 1..r сумму 1..l-1.
Можно заметить, что на участке 1..(2^n) сумма будет равна (2^n)-1. Отсюда получаем следующий алгоритм: ищем наибольшую степень двойки, которая находится в промежутке 1..n. Для определённости назовём эту степень k. Затем добавляем к ответу (2^k)-1 и отнимаем из n 2^k. Продолжаем так делать, пока n не станет равным нулю.
Наилучшая ассимптотика: O(logn).

Код:

#define int long long
int log_2(int num)
{
int t=0;
while(num>1)
{num>>=1;
t++;}
return t;
}

main()
{
    int l,r;
    cin>>l>>r;
    l--;
    int sum1=0,sum2=0,log1;
    while(l)
    {log1=log_2(l);
    sum1+=(1ll<<log1)-1;
    l-=1ll<<log1;}
    
    while(r)
    {log1=log_2(r);
    sum2+=(1ll<<log1)-1;
    r-=1ll<<log1;}
    
    cout<<sum2-sum1<<endl;
}

3. MyTV
Заведём массив на 100 элементов, изначально заполненный тройками. Обозначим значение в элементе с номером канала, в котором мы сейчас находимся равным нулю. Затем проставим единицы во все однозначные номера и все номера, соседствующие с нашим. После этого проставим двойки везде, где в данный момент находится три, но по соседству с данной ячейкой есть ячейка с числом 1. После этого выведем число из искомой ячейки.

Наилучшая ассимптотика: О(1).

Код:

main()
 {
    int a,b;
    cin>>a>>b;
    if(a==b){cout<<0<<endl;return 0;}
    int ans[100];
    for(int i=0;i<100;i++)
    ans[i]=100;
    
    for(int i=1;i<10;i++)
    ans[i]=1;
    
    ans[a==1?99:a-1]=1;
    if(a!=99)
    ans[a+1]=1;
    
    ans[99]=min(ans[99],2ll);
    
    for(int i=10;i<99;i++)
    if(ans[i-1]==1 || ans[i+1]==1)ans[i]=min(ans[i],2ll);
    else ans[i]=min(ans[i],3ll);
    cout<<ans[b]<<endl;
 }

4. Spell.
Используем динамическое программирование. Сперва считаем для каждой ячейки длину наибольшего палиндрома с центром в ней. Затем ведём массив DP[i], в котором храним ответ для подстроки 0..i-1. Идём в цикле от 0 до n и пытаемся улучшить ответ для строки, последним палиндромом в которой будет тот, центр которого находится в данной ячейке.

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

Наилучшая ассимптотика: O(n^2).

Код:

main()
 {
     char a[256];
    cin>>a;
    
    int n=strlen(a);
    
    int d1[256],d2[256];
    for(int i=0;i<256;i++)
    d1[i]=1,d2[i]=0;
    
    for(int i=0;i<n;i++)
    {while(i-d1[i]>=0 && i+d1[i]<n && a[i-d1[i]]==a[i+d1[i]])d1[i]++;    
    while(i-d2[i]-1>=0 && i+d2[i]<n && a[i-d2[i]-1]==a[i+d2[i]])d2[i]++;}
    
    int DP[256];
    for(int i=0;i<n;i++)
    DP[i]=i+1;
    
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<d1[i];j++)
        DP[i+j]=min(DP[i+j],(i-j-1>=0?DP[i-j-1]:0)+1);
        for(int j=0;j<d2[i];j++)
        DP[i+j]=min(DP[i+j],(i-j-2>=0?DP[i-j-2]:0)+1);
    }
    cout<<DP[n-1]<<endl;
}

5. Gnusmas
Задача, уже ставшая классической. Нужно найти кол-во клеток, которые покроет отрезок с двумя целочисленными координатами. Сразу можно заметить, что наш отрезок каждый раз будет либо продвигаться на одну клетку влево, либо на одну клетку вверх, либо и на одну клетку влево, и на одну клетку вверх. Понятно, что всего ему прийдётся преодолеть n клеток по вертикали и m по горизонтали. Но в случае, когда он проходит через угол, счётчик пройденных им клеток увеличивается и по горизонтали, и по вертикали. Стало быть, ответом будет n+m-*кол-во прохождений отрезком клеток с целочисленными координатами*. Несложно заметить, что вычитаемое в данном случае будет равно наибольшему общему делителю m и n. Таким образом...
Наилучшая ассимптотика: O(logn).

Код:

#define int long long
int gcd(int a,int b){return b?gcd(b,a%b):a;}

main()
 {
    int m,n;
    cin>>m>>n;
    cout<<m*n-m-n+gcd(m,n)<<endl;
 }

Відредаговано adamant (2013-12-29 13:53:57)

Поза форумом

 

#2 2013-12-29 12:43:35

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

UPD: решение Paint всё-таки полнобально. Прошу простить за преждевременность smile

Поза форумом

 

#3 2013-12-29 13:00:40

Maxim1296
Новий користувач
Зареєстрований: 2013-12-22
Повідомлень: 2

Re: Разбор задач

У меня задача MyTV тоже все проходит и более быстрая, так как нет ни циклов, ни массивов.

Код:

#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    int x = abs(b - a), z = abs(99 - b + a);
    cout << (b < 10  ?  1 : b == 10 || (b == 99 && a !=1) ? 2 : min(min(x, z),3));
    return 0;
}

Поза форумом

 

#4 2013-12-29 13:03:10

Taras_Z
Новий користувач
Звідки: Львів
Зареєстрований: 2012-10-25
Повідомлень: 25

Re: Разбор задач

У мене за задачу Gnusmas 32 бали з 40 і я не можу зрозуміти чому.
Ось код:

Код:

#include <iostream>
using namespace std;
int GCD(int a,int b) {
  return b?GCD(b,a%b):a;
}
int main()
{
    int m,n;
    cin >> m >>n;
    cout << m*n-m-n+GCD(m,n);
    return 0;   
}

Він повністю збігається із кодом поданим вище.
У чому помилка?

Відредаговано Taras_Z (2013-12-29 15:03:56)

Поза форумом

 

#5 2013-12-29 13:05:19

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Taras_Z, у вас происходит переполнение типа int. В моём отрывке кода этого не видно (сейчас исправлю), однако я использую макрос

Код:

#define int long long

Поза форумом

 

#6 2013-12-29 13:10:43

Taras_Z
Новий користувач
Звідки: Львів
Зареєстрований: 2012-10-25
Повідомлень: 25

Re: Разбор задач

У мене при n і m = 10000000 видається нормальна відповідь.

Поза форумом

 

#7 2013-12-29 13:13:31

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Ваша программа выдаёт 266447232, в то время, как правильный ответ - 99999990000000.

Поза форумом

 

#8 2013-12-29 13:22:17

Hfljvbh
Новий користувач
Зареєстрований: 2013-12-29
Повідомлень: 1

Re: Разбор задач

По моему, в задаче Strip ассимптотика O(n*n*logn) потому, что сравнение строк за O(n).

Поза форумом

 

#9 2013-12-29 13:23:55

Taras_Z
Новий користувач
Звідки: Львів
Зареєстрований: 2012-10-25
Повідомлень: 25

Re: Разбор задач

adamant, Дякую.
Це тупа помилка...

Поза форумом

 

#10 2013-12-29 13:25:40

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Ну... В принципе да, n*n*logn, ошибочка-с, сейчас исправлю smile

Поза форумом

 

#11 2013-12-29 13:40:01

Taras_Z
Новий користувач
Звідки: Львів
Зареєстрований: 2012-10-25
Повідомлень: 25

Re: Разбор задач

2.Paint
На 40 балів робилася також так:
Будемо шукати суму степенів між l-им і r-им стовпчиками як суму від 1..r - сума 1..l
Розглянемо таку послідовність:
1 2 1 3 1 2 1 4 1...
Це висота стовпчика фарби на парних позиціях, так як на непарних - нулі. Нам потрібно порахувати суму елементів цієї послідовності із 1 по n. Позначимо її через S(n). Для цього згенеруємо таку послідовність із попередньої послідовності, забравши всі нулі:
1 3 4 7 8 10 11 15 16...
Кожен елемент цієї послідовності це S(n), тобто сума із 1 по n. Нам залишається лише знайти  n-тий елемент цієї послідовності.
Тоді можна замітити таку властивість: S(n)=s([n/2])+n; S(0)=0;
Шукана відповідь: S([r/2])-S([l/2]). r/2 і l/2 - тому, що ми забрали непарні позиції.
Код:

Код:

long double f(long double n)
{
    if(n==0)return 0;
    return f(floor(n/2))+n;
}
int main()
{
    long double l,r;
    cin >> l >> r;
    cout << f(floor(r/2))- f(floor((l-1)/2));
    return 0;   
}

Відредаговано Taras_Z (2013-12-29 14:23:10)

Поза форумом

 

#12 2013-12-29 13:53:06

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Хм... Ваша программа ведь фактически работает с целыми числами... И её можно заменить такой:

Код:

#define int long long

int f(int n)
{if(n)return f(n/2)+n;}

main()
{
    int l,r;
    cin >> l >> r;
    cout << f(r/2)- f((l-1)/2);  
}

Тем не менее, решение весьма интересное smile

Відредаговано adamant (2013-12-29 13:56:50)

Поза форумом

 

#13 2013-12-29 14:37:17

Taras_Z
Новий користувач
Звідки: Львів
Зареєстрований: 2012-10-25
Повідомлень: 25

Re: Разбор задач

adamant, Можна і так smile

Поза форумом

 

#14 2013-12-29 15:00:18

frswedom
Новий користувач
Зареєстрований: 2011-11-22
Повідомлень: 6

Re: Разбор задач

Решение задачи Paint за O(1).
Идея такая же, как и у adamant, но сумму ряда 1..a (a - парное) можно найти как a-bits(a) , где bits(a) - количество единичных (выставленных) битов в числе а. Реализации такой ф-ции легко ищутся в интернете и на stackoverflow, одкуда, собственно, я и взял.

Код:

typedef long long int ull;
const ull m1  = 0x5555555555555555ll;
const ull m2  = 0x3333333333333333ll;
const ull m4  = 0x0f0f0f0f0f0f0f0fll;

ull bits(ull x)
{
    x -= (x >> 1) & m1;
    x = (x & m2) + ((x >> 2) & m2);
    x = (x + (x >> 4)) & m4;
    x += x >>  8;
    x += x >> 16;
    x += x >> 32;
    return x & 0x7f;
}

int main()
{
    ull l,r,ans;
    cin >> l >> r;
    if (l & 1) ++l;
    if (r & 1) --r;
    l -= 2;
    ans = r-bits(r)-l+bits(l);
    cout << ans;
    return 0;
}

Відредаговано frswedom (2013-12-29 15:58:45)

Поза форумом

 

#15 2013-12-29 15:19:44

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

Re: Разбор задач

Тоже удобное решение Paint за O(1)
var
l,r:qword;
function st(x:qword):qword;
var s:qword;i:longint;
begin
s:=1;
for i:=1 to x do s:=s*2;
st:=s;
end;
function f(x:qword):qword;
var s:qword;i:longint;
begin
s:=0;
for  i:=1 to 59 do
inc(s,x div st(i)) ;
f:=s;
end;
begin
read(r,l);
if r>l then begin writeln(0);halt;end;
writelN(f(l)-f(r-1));
end.

Поза форумом

 

#16 2013-12-29 15:28:05

speles
Новий користувач
Зареєстрований: 2013-12-28
Повідомлень: 2

Re: Разбор задач

Мое решение Paint

Код:

int main()
{
  uint64_t l, r;
  uint64_t res = 0;
  cin>>l>>r;
  if (l>r) swap(l, r);
  l--;
  for (int i = 1; i<64; i++)
  {
      res += r>>i;
      res -= l>>i;
  }
  cout<<res;
  return 0;
}

Відредаговано speles (2013-12-29 15:31:11)

Поза форумом

 

#17 2013-12-29 15:54:41

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

frswedom, вовсе нет! Просто нужно явно указывать в программе, что вы инициализируете эти переменные, как long long следующим образом:

Код:

const ull m1  = 0x5555555555555555ll;
const ull m2  = 0x3333333333333333ll;
const ull m4  = 0x0f0f0f0f0f0f0f0fll;

Тогда всё проходит.

Поза форумом

 

#18 2013-12-29 16:01:04

frswedom
Новий користувач
Зареєстрований: 2011-11-22
Повідомлень: 6

Re: Разбор задач

adamant, благодарю. Добавлю в копилку тупых "фич" С++.

Поза форумом

 

#19 2013-12-29 18:42:59

BW5469
Новий користувач
Зареєстрований: 2013-12-29
Повідомлень: 3

Re: Разбор задач

Здравствуйте!
Я оправила задачу Spell и получила за нее 2 балла. Хотя при отправке этого же решения после объявления результатов в онлайн-проверку набрала 20 баллов.
Почему так может быть? Я делала 4 задачу жадностью, знаю, это не полнобальное решение, но хотя бы половину баллов я бы могла набрать..

Поза форумом

 

#20 2013-12-30 09:21:38

samus1c
Новий користувач
Зареєстрований: 2011-11-09
Повідомлень: 18

Re: Разбор задач

У правилах олімпіади сказано, що всі введені дані повинні бути коректні. ІМХО включення до тестів задачі MyTV випадку коли a=b порушує це правило. В задачі говориться "Зараз телевізор ввімкнений на каналі a, а я хочу дивитися  канал b". Погодьтесь, абсурдно буде звучати, приміром, "Зараз телевізор ввімкнений на каналі СТБ, а я хочу дивитися  канал СТБ". Тобто умова задачі передбачає обов'язкове переключення каналів. Пишу не з метою пред'явити комусь претензіїї. Просто висловив свою думку.

Поза форумом

 

#21 2013-12-31 10:45:33

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

Re: Разбор задач

samus1c написав:

У правилах олімпіади сказано, що всі введені дані повинні бути коректні. ІМХО включення до тестів задачі MyTV випадку коли a=b порушує це правило. В задачі говориться "Зараз телевізор ввімкнений на каналі a, а я хочу дивитися  канал b". Погодьтесь, абсурдно буде звучати, приміром, "Зараз телевізор ввімкнений на каналі СТБ, а я хочу дивитися  канал СТБ". Тобто умова задачі передбачає обов'язкове переключення каналів. Пишу не з метою пред'явити комусь претензіїї. Просто висловив свою думку.

Взагалі то підтримую. За логікою умови, тест, коли а=в є неприйнятним.
Але в технічній умові завдання сказано що 1 ≤ a,b ≤ 99 і більше ніяких обмежень. Отже варіант, коли а=в не виключається.
Доречі, в гілці, де обговорювалось рішення задачі MyTV, це питання розглядалось

Відредаговано LVV (2013-12-31 10:59:48)


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

Поза форумом

 

#22 2014-01-05 15:15:23

Liko
Новий користувач
Зареєстрований: 2014-01-05
Повідомлень: 4

Re: Разбор задач

Решает быстрее, проходило все тесты... почему 38?
Мое решение MyTV

Код:

#include <iostream>
using namespace std;

int main()
{
    int a, b, per;
    cin >> a >> b;
    if ((0 < b)&&(b < 10)||( abs(a - b) == 1, abs(a - b) == 98))
    {
        per = 1;
    }
    else if ((abs(a - b == 2)) || (a != 1 && b == 99)|| b==10)
    {
        per = 2;
    }
    else
    {
        per = 3;
    }
    cout << per << endl;
    return 0;
}

Также вопрос почему 18 за
Gnusmas

Код:

#include <iostream>
using namespace std;
int main()
{
    int m, n, k;
    cin >> m >> n;
    if (m!=n)
    {
        if (n % 2 == 0 && m % 2 == 0)
        {
            k = (m - 1)*(n - 1) + 1;
        }
        else
        {
            k = (m - 1)*(n - 1);
        }
    }
    else
    {
        k = m*(m - 1);
    }
    cout << k << endl;
    return 0;
}

Формулы проверялись и составлялись руками, прошли достаточно много тестов(ручных, проверялось на множестве примеров), причины занижения не вижу((( Объясните!
Возможно ли предоставление тестов по которым проверяли?

Відредаговано Liko (2014-01-05 15:25:28)

Поза форумом

 

#23 2014-01-05 18:53:24

StopFan
Новий користувач
Зареєстрований: 2013-12-07
Повідомлень: 15

Re: Разбор задач

Liko написав:

Решает быстрее, проходило все тесты... почему 38?
Мое решение MyTV

Код:

#include <iostream>
using namespace std;

int main()
{
    int a, b, per;
    cin >> a >> b;
    if ((0 < b)&&(b < 10)||( abs(a - b) == 1, abs(a - b) == 98))
    {
        per = 1;
    }
    else if ((abs(a - b == 2)) || (a != 1 && b == 99)|| b==10)
    {
        per = 2;
    }
    else
    {
        per = 3;
    }
    cout << per << endl;
    return 0;
}

Также вопрос почему 18 за
Gnusmas

Код:

#include <iostream>
using namespace std;
int main()
{
    int m, n, k;
    cin >> m >> n;
    if (m!=n)
    {
        if (n % 2 == 0 && m % 2 == 0)
        {
            k = (m - 1)*(n - 1) + 1;
        }
        else
        {
            k = (m - 1)*(n - 1);
        }
    }
    else
    {
        k = m*(m - 1);
    }
    cout << k << endl;
    return 0;
}

Формулы проверялись и составлялись руками, прошли достаточно много тестов(ручных, проверялось на множестве примеров), причины занижения не вижу((( Объясните!
Возможно ли предоставление тестов по которым проверяли?

може бути, що на тестах з великими числами просто по часу не пройшло

Поза форумом

 

#24 2014-01-05 20:42:57

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

Re: Разбор задач

Liko написав:

Решает быстрее, проходило все тесты... почему 38?
Формулы проверялись и составлялись руками, прошли достаточно много тестов(ручных, проверялось на множестве примеров), причины занижения не вижу((( Объясните!
Возможно ли предоставление тестов по которым проверяли?

Не всё проверили)
MyTV
У вас не учтён случай: a=b
И пропущен случай: a=1 b=98 (ваш ответ 3)
Gnusmas
Ограничения на m,n до 10^7
У вас же в цикле k может принять значение почти 10^14, а вы его в int запихиваете.

Відредаговано Andrey1998 (2014-01-05 20:45:34)

Поза форумом

 

#25 2014-01-05 21:00:51

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Отправил решения Liko на проверку и поработал немного с ними, чтобы узнать, в чём их проблема. Итак:
Gnusmas. Во-первых, происходит переполнение типа int. Нужно использовать long long. Во-вторых, само решение неправильное. Например, на тест 3 6 ваше решение выдаст ответ 10, хотя правильный ответ - 12. Скажу честно, не вникал в то, с чем это связано, но думаю, вы можете проверить, что именно ваш ответ неправилен, нарисовав прямоугольник 3х6. Да и вообще решение неправильно работает с тестами вида a,k*a.
MyTV. Решение работает неправильно на очень большом количестве тестов. Разгадка - в его небрежности. Во-первых, в строке
( abs(a - b) == 1, abs(a - b) == 98) вместо запятой должно стоять логическое ИЛИ, то есть ||.


Во вторых, в строке
(abs(a - b == 2)) abs должен закрываться ПЕРЕД ==.
Ну и в третьих, решение должно учитывать случаи, при которых a==b и выводить 0 в них.

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt