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


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

Ви не зайшли.

#1 2014-11-14 13:27:49

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

РОЗБІР РІШЕНЬ

Пропоную поділитись своїми кращими рішеннями, які набрали максимальний бал.
Ось тут мої: https://yadi.sk/i/DO0YE28kchy7p

Відредаговано LVV (2014-11-14 13:28:27)


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

Поза форумом

 

#2 2014-11-14 17:12:03

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

Re: РОЗБІР РІШЕНЬ

LVV написав:

Пропоную поділитись своїми кращими рішеннями, які набрали максимальний бал. ...

Есть пара предложений по задаче Robot:

1) Если использовать двумерный массив для моделирования перемещения робота, то совсем не обязательно по окончанию "перемещений" сканировать ВСЮ матрицу на предмет подсчета нужных клеток. Достаточно считать их прямо по ходу "движения" - если после попадания на клетку там оказывается РОВНО "2", то cnt++, иначе - ничего не делаем.

2) Можно обойтись и без матрицы. После каждого хода (включая нулевой ход, приведший в стартовую клетку) получаем "хэш" клетки hash = i * 3000 + j; и заносим его в массив/список. По окончанию движения - подсчитываем число хэшей, повторяющихся в массиве более одного раза (для этого удобно сначала отсортировать массив).

По поводу этой задачи созрел вопрос к жюри...
Если немного изменить условие, зафиксировав размер поля = (n x n) и число ходов = M, то :
1-й способ использует k1*(n^2) памяти и имеет асимптотику О(M).
2-йспособ - использует только k2*M памяти и имеет асимптотику O(M log(M)) - из-за сортировки массива.

Т.о. получаем, что при достаточно большом числе M второй способ будет получать TimeLimit по сравнению с 1-ым способом, если этот самый TL задавать от "самого быстрого" решения. Но неужели 2-ой способ хуже? На всех известных мне контестах по ACM-правилам, а также на 4-ом туре Всеукра и на Межнаре по информатике максимальное время решения - фиксировано и приведено в условии задач.

Может, уже пора использовать общепринятые критерии ограничения по времени на решения ? И тем самым - приучать участников к общепринятым условиям контестов?

И отдельным вопросом с прошлых лет осталось предоставление участникам финального (очного) тура оперативной полной оценки (хотя бы баллов) каждого отосланного решения.... - это я забежал сильно вперёд. Но с другой стороны - потом будет уже поздно что то менять wink

Поза форумом

 

#3 2014-11-14 17:50:26

YaKr3v3tko
Новий користувач
Зареєстрований: 2014-11-14
Повідомлень: 2

Re: РОЗБІР РІШЕНЬ

http://goo.gl/7V9jGZ

shoa169 написав:

Есть пара предложений по задаче Robot

Сделал с помощью vector + поиск по всей матрице. Полный балл.

Поза форумом

 

#4 2014-11-15 01:20:22

FordPerfect
Новий користувач
Зареєстрований: 2014-11-15
Повідомлень: 30

Re: РОЗБІР РІШЕНЬ

Поделюсь, пожалуй, своими версиями решений.

MaxBox2

Код:

#include <iostream>

int main()
{
    long long a;
    std::cin>>a;
    std::cout<<(a+3LL)/6LL;
    return 0;
}

Grain

Код:

#include <iostream>

int main()
{
    int T;
    int a,b;
    std::cin>>T;
    for(int i=0;i<T;++i)
    {
        std::cin>>a>>b;
        std::cout<<1+(a%2);
    }
    return 0;
}

Commerce

Код:

#include <iostream>

int main()
{
    int N,M;
    std::cin>>N;
    M=N/2+1;
    std::cout<<M*N-2*N-M*M+2*M;
    return 0;
}

Apples

Код:

#include <iostream>

int main()
{
    int T;
    unsigned long long A,B,C;
    std::cin>>T;
    for(int i=0;i<T;++i)
    {
        std::cin>>A>>B>>C;
        std::cout<<1+(
            ((A+B)&1ULL)+((B+C)&1ULL)+((C+A)&1ULL)!=2||
            ((A==0ULL)+(B==0ULL)+(C==0ULL)>1&&A+B+C!=1));
    }
    return 0;
}

Robot

Код:

#include <cstdio>

int main()
{
    int c,a,b,i,j,x[1024],y[1024];
    x[0]=0;y[0]=0;
    for(i=1;(c=fgetc(stdin))>13;i+=(c>32))
    {
        x[i]=x[i-1]+(c=='L')-(c=='R');
        y[i]=y[i-1]+(c=='U')-(c=='D');
    }
    for(a=0;i;a+=(b==1))
        for(j=--i,b=0;j--;)
            b+=(x[i]==x[j]&&y[i]==y[j]);
    printf("%d",a);
    return 0;
}

Все приведённые решения набирали полный балл на онлайн-проверке.

Как легко видеть, решение Robot имеет сложность O(M^2), и при этом укладывается в time-limit.

Но решение shoa169 с сортировкой, конечно, имеет преимущества.

При желании, если не ошибаюсь, можно реализовать решение, укладывающееся в O(M) времени и O(M) памяти, следующим образом:

Код:

#include <iostream>
#include <string>
#include <vector>

// Somewhat inspired by http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

int main()
{
    int answer;
    std::vector<std::vector<int> > y(2048);
    std::vector<int> v;
    int xc,yc;
    int x_min,x_max,y_min,y_max;
    std::string s;

    std::cin>>s;

    xc=1024;
    yc=1024;
    x_min=xc;
    x_max=xc;
    y_min=yc;
    y_max=yc;
    y[yc].push_back(xc);

    for(int i=0;i<s.size();++i)
        if(s[i]>='A'&&s[i]<='Z')
        {
            xc+=((s[i]=='R')-(s[i]=='L'));
            yc+=((s[i]=='U')-(s[i]=='D'));
            y[yc].push_back(xc);
            if(xc<x_min) x_min=xc;
            if(xc>x_max) x_max=xc;
            if(yc<y_min) y_min=yc;
            if(yc>y_max) y_max=yc;
        }

    v.resize(x_max-x_min+1,0);
    answer=0;

    for(int i=y_min;i<=y_max;++i)
    {
        for(int j=0,n=y[i].size();j<n;++j)
            if(v[y[i][j]-x_min]++==1)
                ++answer;
        for(int j=0,n=y[i].size();j<n;++j)
            v[y[i][j]-x_min]=0;
    }

    std::cout<<answer;
    return 0;
}

(Решение набирает полный балл на онлайн-проверке).
Таким образом заданный выше вопрос:

shoa169 написав:

По поводу этой задачи созрел вопрос к жюри...
Если немного изменить условие, зафиксировав размер поля = (n x n) и число ходов = M, то :
1-й способ использует k1*(n^2) памяти и имеет асимптотику О(M).
2-йспособ - использует только k2*M памяти и имеет асимптотику O(M log(M)) - из-за сортировки массива.

становится несколько менее актуальным.

Добавлю ещё, что
1. Выделение (и обнуление) памяти - небесплатно, и О(M) - это в каком-то смысле O(n^2+M) (здесь можно удариться в схоластику о том, как операционная система выделяет страницы виртуальной памяти, однако не буду развивать данную тему).
2. Если n намного меньше M, то на мой взгляд, да - 1-й способ лучше. Очевидно, n>2*M+1 рассматривать не особо осмысленно. Для небольших M разницу в ассимптотике измерить нетривиально. Если же n~M и M достаточно велико (чтобы появилась ощутимая разница во времени исполнения), то 1-й способ всё-равно требует чрезмерного количества памяти и использовать его не представляется возможным.

Поза форумом

 

#5 2014-11-15 17:30:20

JP3005
Новий користувач
Звідки: Вінниця
Зареєстрований: 2013-11-16
Повідомлень: 13
Вебсайт

Re: РОЗБІР РІШЕНЬ

а что означает эта строка std::cout<<(a+3LL)/6LL;
и вот этот участок кода std::cout<<1+(
            ((A+B)&1ULL)+((B+C)&1ULL)+((C+A)&1ULL)!=2||
            ((A==0ULL)+(B==0ULL)+(C==0ULL)>1&&A+B+C!=1));

Поза форумом

 

#6 2014-11-15 18:22:52

FordPerfect
Новий користувач
Зареєстрований: 2014-11-15
Повідомлень: 30

Re: РОЗБІР РІШЕНЬ

JP3005 написав:

а что означает эта строка std::cout<<(a+3LL)/6LL;
и вот этот участок кода std::cout<<1+(
            ((A+B)&1ULL)+((B+C)&1ULL)+((C+A)&1ULL)!=2||
            ((A==0ULL)+(B==0ULL)+(C==0ULL)>1&&A+B+C!=1));

std::cout вроде бы стандартный способ вывода (в библиотеке C++):
http://en.cppreference.com/w/cpp/io/cout
http://en.cppreference.com/w/cpp/io/bas … rator_ltlt

Если вопрос о суффиксе LL, то он означает целочисленную константу типа long long:
http://www.cplusplus.com/doc/tutorial/constants/

По логике работы строки близки к соответствующему коду от LVV.

Первая выводит a/6 округленное к ближайшему целому (типа long long и только для неотрицательных чисел; 0.5 округляется вверх).

Вторая почти эквивалентна условию от LVV, только записана в одно логическое условие (результат которого приводится к целому (true=1, false=0) и, сложенным с 1, выводится на стандартный output) использует несколько другие условия.

((A+B)&1ULL)+((B+C)&1ULL)+((C+A)&1ULL)!=2
Т. к. ни одна из операций не может изменить чётность пар A+B, B+C, и C+A, то если эти чётности не совпадают с таковыми для выиграшной позиции, то выиграшной стратегии не существует. Условие проверяет, что сумма последних бит в (A+B), (B+C), и (C+A) не равна 2 (т. е. сумме в выиграшной позиции).

((A==0ULL)+(B==0ULL)+(C==0ULL)>1&&A+B+C!=1)

В противном случае, выиграшной стратегии не существует только если как минимум 2 из 3-х чисел A, B и C равны 0, и при этом оставшееся число не равно 1 (что является выиграшной позицией).

Правка: по здравом размышлении, A+B+C!=1 надо заменить на A+B+C!=1ULL. Во имя единообразия.
Правка^2: немного уточнений.

Відредаговано FordPerfect (2014-11-15 18:34:37)

Поза форумом

 

#7 2014-11-16 00:14:45

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

Re: РОЗБІР РІШЕНЬ

Итак, решения как они были посланы. Язык python.
Maxbox2 (5/20)

Код:

a = input()
x = [a/6, a/6+1]
Vol = [(a-2*i)**2*i for i in x]
print x[Vol.index(max(Vol))]

Grain (20/20)

Код:

T = input()
out = ''
for i in xrange(T):
    w = int(raw_input().split()[0])
    out += str(1 + w%2)
print out

Commerce (20/20)

Код:

N = input()
print (N/2-1)*(N/2-1+N%2)

Apples (4/20)

Код:

def iswin(x):
    if(x[0]+x[1]+x[2] == 1): 
        return '1'
    for i in xrange(2):
        if(x[i] ==x[(i+1)%3] == 0): 
            return '2'
    if(x[0]%2 == x[1]%2 == x[2]%2): 
        return '2'
    return '1'

T = input()
out = ''
for i in xrange(T):    
    a = map(int,raw_input().split())
    out += iswin(a)
print out

Robot (11/20)

Код:

path = raw_input()
MOVES = len(path)
MAXX = 2*MOVES +1
START = (MAXX + 1)*MOVES

#pos = MAXX*x + y
move = {'L':-MAXX,
        'R':MAXX,
        'U':1,
        'D':-1}
        
desk = MAXX**2*[0]
pos = START
desk[pos] = 1

ans = 0

for i in path:
    pos += move[i]
    if(desk[pos] == 1):
        ans += 1
    desk[pos] += 1

print ans

Комментарии.
Питон удобный, но медленный язык. Конкретно в этом туре его "скорость" сказалась только в задаче 5 (надо было использовать array).
В задаче Maxbox2 замена первой строки на a = long(raw_input()) повышает результат до 20/20.
Аналогично в задаче Apple замена строки

Код:

    a = map(int,raw_input().split())

на

Код:

    a = map(long, raw_input().split())

повышает балл до 20/20.

Ранее я уже создавал тему по поводу версии питона.
Тогда все дело свелось к тому, что в используемой версии питона нет двух функций, которые я хотел использовать в задаче apple. Забыл, правда, добавить, что при наличии в коде инструкций, которые не могут быть исполнены, программа при jn-line проверке выдает результат BAD DATA. Это не очень информативный вывод, особенно  если код пишется и тестируется в 2.7. Конкретно в том случае всего полчаса проб и ошибок, и неработающие функции обнаруживаются.
С long отдельная история. В отличие от С, стандарт которого был принципиально выверен достаточно давно, python динамично развивается. С версии 2.2 в питоне были объединены типы long и int. Точнее, если результат вычислений в какой-то момент выходит за предел int, то результат автоматически конвертируется в long и далее работа идет с ним.
https://docs.python.org/2/whatsnew/2.2. … d-integers
Начиная с версии 3 тип int убран вообще, и вся целочисленная арифметика ведется в long.
Эту информацию нетривиально найти, например тут утверждается, что "If the argument is outside the integer range, the function returns a long object instead.". Естественно, в 2.7 на максимальных числах тесты проходятся и эта особенность стала неожиданностью.

Знал бы заранее, что к чему, постелил бы себе питон 2.1(?), специально для написания решений задач олимпиады.
Есть пожелание к организаторам по поводу обновления проверялки питона хотя бы до 2.6. Или пусть во вступлении появится x и ссылка на установщик питона этой версии. А то эти неожиданности, хоть и повышают уровень знания языка, но радости никакой не приносят.
Участвую в общем зачете, баллы, в принципе, не важны. Но для участников, ежели они отважатся писать олимпиаду на python, эти вещи могут оказаться критичными.

PS. Кстати, если в программе есть функции, которых нет в питоне <2.2, но они не запускаются при исполнении на тестах jn-line проверки, то такая программа пройдет проверку без ошибок. Поэтому ссылка на установщик вдвойне желательна.
PPS. В Maxbox2 отсутствует тест с a=1. На нем мой код даст неверный ответ 1.
PPPS. Код для robot, который проходит все тесты

Код:

import array

path = raw_input()
MOVES = len(path)
MAXX = 2*MOVES +1
START = (MAXX + 1)*MOVES

#pos = MAXX*x + y
move = {'L':-MAXX,
'R':MAXX,
'U':1,
'D':-1}

desk = array.array('i',[0,0,0,0,0,0,0,0,0,0])
while desk.buffer_info()[1]<MAXX**2:
   desk.extend(desk)
pos = START
desk[pos] = 1

ans = 0

for i in path:
  pos += move[i]
  if(desk[pos] == 1):
    ans += 1
  desk[pos] += 1

print ans

Хотя, если использовать высказанную выше идею с сортировкой, можно обойтись и без array

Код:

path = raw_input()
MOVES = len(path)
MAXX = 2*MOVES +1
START = (MAXX + 1)*MOVES

#pos = MAXX*x + y
move = {'L':-MAXX,
'R':MAXX,
'U':1,
'D':-1}

points = [START]
for i in path:
    points.append(points[-1]+move[i])
points.sort()
i=j=ans=0

while i < len(points):
    if points[i]!=points[j]:
        ans += (i-j)>1
        j = i
    i += 1    

print ans+((i-j)>1)

Відредаговано andervish (2014-11-16 21:42:24)

Поза форумом

 

#8 2014-11-18 17:30:35

dimon_k
Новий користувач
Звідки: Вінниця
Зареєстрований: 2014-10-26
Повідомлень: 8
Вебсайт

Re: РОЗБІР РІШЕНЬ

Як Commerce ,без циклів
var
  n: longint; z: int64;

begin
  read(n);
  if n mod 2 = 0 then
    z := sqr(n - 2) div 4;
  if n mod 2 = 1 then
    z := ((n - 3) * (n - 1)) div 4;
  write(z);
end.

Поза форумом

 

#9 2014-11-18 18:08:15

FordPerfect
Новий користувач
Зареєстрований: 2014-11-15
Повідомлень: 30

Re: РОЗБІР РІШЕНЬ

dimon_k написав:

Як Commerce ,без циклів
var
  n: longint; z: int64;

begin
  read(n);
  if n mod 2 = 0 then
    z := sqr(n - 2) div 4;
  if n mod 2 = 1 then
    z := ((n - 3) * (n - 1)) div 4;
  write(z);
end.

А ведь, если вдуматься, if в вашем решении не обязателен.
Т. е., перефразируя andervish:

Код:

N = input()
print (N-2)**2/4

Правка: или даже

Код:

print (input()-2)**2/4

Відредаговано FordPerfect (2014-11-18 18:11:44)

Поза форумом

 

#10 2014-11-19 05:25:31

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

Re: РОЗБІР РІШЕНЬ

FordPerfect написав:

или даже

Код:

print (input()-2)**2/4

Действительно, работает. smile

Код:

#include <iomanip>
#include <cmath>
using namespace std;
int main()
{  
double N;
cin >> N;
cout <<setprecision(15) << long(pow((N-2),2)/4);
return 0;
}

Ну, тогда я не понимаю авторов задач.
Какие такие особые олимпиадные навыки алгоритмизации и программирования нужны участникам I тура, чтобы решить задачи

Commerce:
Z = (N-4)^2/4;

Maxbox2:
x = a/6;

Grain
cout << (B%2==0?1:2);

Эти задачи впору предложить на олимпиадах по математике, а не по информатике.

Відредаговано LVV (2014-11-19 05:27:47)


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

Поза форумом

 

#11 2014-11-19 21:15:09

JP3005
Новий користувач
Звідки: Вінниця
Зареєстрований: 2013-11-16
Повідомлень: 13
Вебсайт

Re: РОЗБІР РІШЕНЬ

LVV написав:

FordPerfect написав:

или даже

Код:

print (input()-2)**2/4

Действительно, работает. smile

Код:

#include <iomanip>
#include <cmath>
using namespace std;
int main()
{  
double N;
cin >> N;
cout <<setprecision(15) << long(pow((N-2),2)/4);
return 0;
}

Ну, тогда я не понимаю авторов задач.
Какие такие особые олимпиадные навыки алгоритмизации и программирования нужны участникам I тура, чтобы решить задачи

Commerce:
Z = (N-4)^2/4;

Maxbox2:
x = a/6;

Grain
cout << (B%2==0?1:2);

Эти задачи впору предложить на олимпиадах по математике, а не по информатике.

не согласен,я commerce u grain решил не по такой формуле. а использовал алгориты которые смог придумать.

Поза форумом

 

#12 2014-11-24 20:30:04

Monstrofil
Новий користувач
Зареєстрований: 2014-11-10
Повідомлень: 1

Re: РОЗБІР РІШЕНЬ

andervish написав:

Участвую в общем зачете, баллы, в принципе, не важны. Но для участников, ежели они отважатся писать олимпиаду на python, эти вещи могут оказаться критичными.

PS. Кстати, если в программе есть функции, которых нет в питоне <2.2, но они не запускаются при исполнении на тестах jn-line проверки, то такая программа пройдет проверку без ошибок. Поэтому ссылка на установщик вдвойне желательна.

Присоединяюсь к вышесказанному. Так и не смог найти, что в моей реализации Robot-а выдаёт "wrong answer" на тестах из условия в онлайне, хотя тест из условия локально - проходит. Хотелось бы всё-таки получить версию python хотя бы 2.6.

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt