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

Решение Binfriend

Пусть k - минимальное a, при котором 2^a=1(mod n)
По условию 2^t+1=0(mod n)
Если t>k, то 2^(t-k)+1=0(mod n). Откуда следует, что t<k.
Из того, что 2^t+1=0(mod n), следует что 2^(2t)-1=0(mod n)
Тогда, 2t = k.
Остается найти k - показатель числа 2 по модулю n и проверить, что 2^(k/2)+1=0(mod n)
Чтоб найти k можно перебрать делители функции Эйлера от n (алгоритм 4.79 http://cacr.uwaterloo.ca/hac/about/chap4.pdf)

Відредаговано traveller6 (2018-02-19 15:31:53)

Задача Maxtriangle

Заметим, что поскольку объединяются только смежные стороны многоугольника, то после "треугольнизации" стороны будут равны суммам подряд идущих элементов входного массива. Чтоб не пересчитывать суммы каждый раз, можно выражать их из частичных сумм.
Выходит, нам нужно найти три позиции: начала трех сторон конечного треугольника. Назовем их i, j и k (i<j<k).
Сами стороны треугольника тогда будут (при индексации от 1)
a = sum(i,j-1)
b = sum(j,k-1)
c = sum(k,N)+sum(1,i-1)
Пусть f(i,j,k) - площадь треугольника со сторонами a, b, c.
Несложно показать, что при фиксированных i и j, функция f от k сначала монотонно возрастает, а затем убывает. То есть, если известны i и j, то k можно найти тернарным поиском.
Пусть g(i,j) - максимальное значение функции f при фиксированных i и j.
Аналогично, легко видеть, при фиксированной i, функция g от j сначала возрастает, а затем убывает. Значит, j тоже можно найти тернарным поиском.
Получается такое вот решение:
Перебираем i, тернарным поиском ищем j, максимизируя g(i,j), а для этого тернарным поиском ищем k, максимизируя f(i,j,k).
Остается один вопрос. Что делать, если треугольника со сторонами a, b, c не существует?
Чтоб тернарный поиск работал, нам нужно так изменить функцию f, чтоб сохранился её вид: сначала возрастает, потом спадает.
Например, если в формуле Герона, по которой мы естественно будем считать площадь, у нас получится, что квадрат площади отрицательный, то мы будем брать отрицательный корень из модуля этого квадрата вместо площади.

Асимптотика: O(n log^2(n))

#include <iostream>
#include <iomanip>
#include <iterator>
#include <algorithm>

template<typename Iterator>
Iterator ternary_search(Iterator first, Iterator last) {
    typedef typename std::iterator_traits<Iterator>::difference_type DistanceType;
    struct iterator : public std::iterator<std::random_access_iterator_tag, bool, DistanceType> {
        bool operator * () const { auto next = it; ++next; return *it >= *next; }
        iterator &operator ++ () { ++it; return *this; }
        iterator &operator = (const iterator &other) { it = other.it; return *this; }
        iterator &operator += (const DistanceType &add) { it += add; return *this; }
        DistanceType operator - (const iterator &other) const { return it - other.it; }

        iterator(Iterator it) : it(it) { }
        Iterator it;
    };

    if (std::distance(first, last) > 0) {
        --last;
        return lower_bound(iterator(first), iterator(last), true).it;
    }
    return first;
}

template<typename Container>
typename Container::iterator ternary_search(Container cont) {
    using std::begin;
    using std::end;
    return ternary_search(begin(cont), end(cont));
}

template<class Fn, class Arg, class Result>
struct generator {
    generator (Fn fn, Arg first, Arg last) : fn_(fn), first_(first), last_(last) { }

    struct iterator : public std::iterator<std::random_access_iterator_tag, Result, Arg> {
        Result operator * () const { return fn_(arg_); }
        iterator &operator ++ () { ++arg_; return *this; }
        iterator &operator -- () { --arg_; return *this; }
        iterator &operator = (const iterator &other) { arg_ = other.arg_; return *this; }
        iterator &operator += (const Arg &add) { arg_ += add; return *this; }
        Arg operator - (const iterator &other) const { return arg_ - other.arg_; }

        iterator(Fn fn, Arg arg) : fn_(fn), arg_(arg) { }

    private:
        Fn fn_;
        Arg arg_;
    };

    iterator begin() const { return iterator(fn_, first_); }
    iterator end() const { return iterator(fn_, last_); }

private:
    Fn fn_;
    Arg first_;
    Arg last_;
};

template<class Fn, class Arg, class Result = typename std::result_of<Fn(Arg)>::type>
generator<Fn, Arg, Result> for_range(Arg from, Arg to, Fn generator) {
    return {generator, from, to};
}

int main() {
    using namespace std;
    int m;
    cin >> m;
    int sum[m];
    for (int i = 0; i < m; ++i)
        cin >> sum[i];
    partial_sum(sum, sum+m, sum);

    auto area = [&](int m1, int m2, int m3) {
        int a = sum[m2]-sum[m1],
            b = sum[m3]-sum[m2],
            c = sum[m-1]-a-b;
        double p = (a+b+c) / 2.;
        double sq = p * (p-a) * (p-b) * (p-c);
        return sq > 0 ? sqrt(sq) : -sqrt(-sq);
    };

    double res = 0;
    for (int i = 0; i < m-2; ++i) {
        res = max(res, *ternary_search(for_range(i+1, m-1,
            [&](int j) {
                return *ternary_search(for_range(j+1, m, 
                    [&](int k) {
                        return area(i, j, k);
                    }
                ));
            }
        )));
    }
    cout << fixed << setprecision(20) << res << endl;
}

Результаты тестирования:

Тест    Результат    Час роботи
00    PASSED (+0)    0.01 с
01    PASSED (+7)    0.01 с
02    PASSED (+7)    0.01 с
03    PASSED (+7)    0.01 с
04    PASSED (+6)    0.01 с
05    PASSED (+6)    0.01 с
06    PASSED (+6)    0.01 с
07    PASSED (+6)    0.01 с
08    PASSED (+6)    0.02 с
09    PASSED (+7)    0.02 с
10    PASSED (+7)    0.02 с
11    PASSED (+7)    0.11 с
12    PASSED (+7)    0.12 с
13    PASSED (+7)    0.12 с
14    PASSED (+7)    0.12 с
15    PASSED (+7)    0.12 с

Прошло тестов: 16 из 16.

Набрано баллов: 100 из 100.

П.С. Поскольку система на данной олимпиаде с С++11 не работает, то приходится отправлять уже скомпилированный код ассемблерной вставкой
https://www.hastebin.com/raw/ayasubujiv

g++ -std=gnu++11 -O2 -S Maxtriangle.cpp -o Maxtriangle.s

Відредаговано traveller6 (2018-03-02 17:42:43)

“Затверджую”
В. о. директора  Департаменту освіти і науки
Вінницької обласної державної адміністрації

_____________   В. Буняк.

19  лютого 2018  р.
Рішення
спільного засідання оргкомітету та журі Всеукраїнської Інтернет - олімпіади з інформатики NetOI-2017

Шістнадцята Всеукраїнська учнівська Інтернет-олімпіада з інформатики проведена згідно з «Положенням про Всеукраїнські Інтернет-олімпіади», що затверджено наказом МОНМолодьспорт України № 671 від 11.06.2012 р. з 1 вересня 2017 р. до 17  лютого 2018 р.  в 3 тури. Всього в олімпіаді брало участь 865 учасників із усіх регіонів України.  Четвертий, “real-time” фінальний тур, до якого було допущено 58 школярів з 14 регіонів України, що набрали прохідний бал в попередніх турах, проведено згідно з наказом МОН України «Про проведення Всеукраїнських учнівських Інтернет-олімпіад з математики, фізики, хімії, біології, географії, економіки, інформатики, інформаційних технологій у 2017-2018 навчальному році» №841 від 13.06.2017 р. Олімпіада проводилася з використанням технічних можливостей лабораторії інформаційних та комунікаційних технологій фізико-математичної гімназії №17 Вінницької міської ради. Для проведення олімпіади застосовувалось спеціальне  програмне забезпечення, що функціонує в мережі Інтернет по захищеному протоколу, забезпечує організацію обміну інформацією між учасниками та журі  та можливість автоматизованої перевірки робіт учасників, зокрема – самостійну автоматичну перевірку в режимі on-line.
Списки учасників, умови задач та інші матеріали олімпіади доступні в мережі Інтернет  на сайті олімпіади  https://netoi.org.ua  завдання олімпіади  можливо перевірити самостійно в будь-який час, що є корисним з навчальною метою.
    Розглянувши результати олімпіади та технічні протоколи, згенеровані системою проведення олімпіади (вони також доступні на сайті), журі та оргкомітет на своєму спільному засіданні

ВИРІШИЛИ:
1.1    Визнати переможцями  олімпіади  серед школярів України та нагородити дипломами 
        1 ступеня таких учнів:
Мельник Софію Валентинівну, ученицю 9 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
Деньгу Назарія Олександровича, учня 10 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
Смельського Данііла Сергійовича, учня 11 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
1.2      Визнати переможцями  олімпіади  серед школярів України та нагородити дипломами 
  2 ступеня таких учнів:
Заводника Владислава Олександровича, учня 9 класу Українського фізико-математичного ліцею Київського національного університету ім. Т.Г.Шевченка;
Денисова Констянтина Ігоровича, учня 9 класу комунального закладу освіти «Дніпровський ліцей інформаційних технологій при Дніпропетровському національному університеті ім. О.Гончара»  Дніпровської міської ради;
Нікітенко Максима Вадимовича, учня 10 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
Зуба  Максима Олеговича, учня 10 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
Макаровича Адальберта Віталійовича, учня 11  класу комунального закладу «Ужгородська класична гімназія» Закарпатської області;
Гришечкіна  Марка Сергійовича, учня 11 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;

1.3    Визнати переможцями  олімпіади  серед школярів України та нагородити   дипломами  3 ступеня таких учнів:
Дядюка Антона Віталійовича, учня 9 класу Хмельницького колегіума ім. В. Козубняка;
Ковригіна Андрія Ігоровича, учня 8 класу ліцею №208 м. Києва;
Куца Андрія Віталійовича, учня 9 класу комунального закладу «Сароконстантинівський НВК» Староконстянтинівської міської ради;
    Орапа Андрія Максимовича,  учня  10 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
    Безкоровайного Станіслава Васильовича, учня  10 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
    Дяківнича Дмитра Васильовича, учня  10 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
Чіха Богдана Івановича, учня 11 класу Парищенської загальноосвітнбої школи І-ІІІ ступенів Надвірнянського району Івано-Франківської області;
Жуікова Назара Олександровича,  учня  11 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
Мазаєа Сергія Миколайовича, учня 11 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;

2. Просити Міністерство освіти і науки України дозволити   переможцям, нагородженим дипломами 1 та 2 ступеня,  взяти участь у 4-му етапі Всеукраїнської олімпіади з інформатики 2018 р. понад визначену відповідному регіону  рейтингову кількість учасників (як це передбачено чинним “Положенням про Всеукраїнські  учнівські олімпіади”),  а саме:
Мельник Софія Валентинівна, учениця 9 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
Деньга Назарій Олександрович, учень 10 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
Смельськй Данііл Сергійович, учень 11 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
Заводник Владислав Олександрович, учень 9 класу Українського фізико-математичного ліцею Київського національного університету ім. Т.Г.Шевченка;
Денисов Констянтин Ігорович, учень 9 класу комунального закладу освіти «Дніпровський ліцей інформаційних технологій при Дніпропетровському національному університеті ім. О.Гончара»  Дніпровської міської ради;
Нікітенко Максим Вадимович, учень 10 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
Зуб Максим Олегович, учень 10 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;
Макарович Адальберт Віталійович, учень 11  класу комунального закладу «Ужгородська класична гімназія» Закарпатської області;
Гришечкін  Марко Сергійович, учень 11 класу Полтавської обласної спеціалізованої школи-інтернату ІІ-ІІІ ступенів з поглибленим вивченням окремих предметів та курсів при Кременчуцькому педагогічному коледжі імені А. С. Макаренка;


Голова журі,                                          О. Азаров
д.т.н., професор,
заслужений працівник освіти України,   
декан  ФІТКІ ВНТУ

Заст. голови оргкомітету,                                 Б. Кремінський
д.пед.н., гол. науковий співробітник
ІМЗО МОН України

Директор ФМГ№17 м. Вінниці,                                 В. Нестюк
член оргкомітету

Системний  адміністратор                                       Ю.  Пасіхов 
вузла PMG17,  заст. голови журі,   
народний вчитель України


17.02.2018 р.                                  м.  Вінниця