Как научиться олимпиадному программированию

@qwertyyyyyw · Регистрация: 29.01.2015

Студворк — интернет-сервис помощи студентам

Что делать, если я уже более 5 лет пишу код в веб, c++, но, я не умею решать задачи из олимпиад? Какие сайты изучить?

@Fulcrum_013 · 16.03.2016, 13:28

Сообщение от Shamil1

Итак, для решения этой задачи Вы не будете использовать ООП.

Кстати зависит от языка программирования. В некоторых языках на самом деле условный оператор является объектом. И еще кое от чего. Например от места расположения этих двух интов. Ведь не факт что они лежат в памяти одного процесса. Или даже одного девайса. и не факт что проц и компилятор умеет их сам сравнивать (так же как к примеру int1024 )

Добавлено через 36 секунд

Сообщение от Shamil1

Вы согласны, что использование ООП для решения данной задачи не оправдано?

А давайте будем задачи решать а не арифметические операторы выполнять.

Добавлено через 1 час 0 минут

Сообщение от Shamil1

Итак, для решения этой задачи Вы не будете использовать ООП.

Начнем с того что в ваша постановка задачи некорректна. Хотя бы потому что введение константы 2 ничем не мотивировано. В общем же случае напрашивается вот такой класс для решения данной задачи:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
template <class Type>
class TMax{
private:
    static const AnsiString ErrorStr="TMax: No values";
     Type FMax;
      unsigned FMaxId;
      unsigned FCount=0;
protected:
    inline unsigned GetMaxId()const{
        if (!Count)throw Exception(ErrorStr);
        return FMaxId;
    }
    inline Type GetMax()const{
        if (!Count)throw Exception(ErrorStr);
        return FMax;
    }
public:
    inline TMax& operator << (Type Right){
        if (!Count||FMax<R){
                FMax=R;   
                MaxId=Count;
            
        }
        FCount++;
        return *this; 
    };
    inline TMax& operator << (const TMax& R){
        if (!Count||FMax<R.Max){
            FMax=R.Max;   
            MaxId=Count+R.MaxId;
        }   
        FCount+=R.Count;
        return *this; 
    };
    inline void Reset(){FCount=0;};
    inline explicit operator Type(){ return Max;};
    __property Type Max={read=GetMax};
    __property unsigned MaxId={read=GetMaxId};
    __property unsigned Count={read=FCount};
};

@Shamil1 · 16.03.2016, 22:21

Сообщение от Fulcrum_013

Начнем с того что в ваша постановка задачи некорректна. Хотя бы потому что введение константы 2 ничем не мотивировано.

Постановка задачи корректна: требуемый результат описан без неоднозначностей и исходных данных достаточно, чтобы получить результат. Мотивировка не связана с корректностью и всегда внешняя. Мы решаем задачу, чтобы <тут мотивировка (оценка, деньги, спортивный интерес и т.д.)>. Но Вы можете выбирать способ решения - например, решить более общую задачу и получить требуемый результат как частный случай.

Сообщение от Fulcrum_013

В общем же случае напрашивается вот такой класс для решения данной задачи:

40 строк кода, а зачем, если достаточно описать функцию:

Haskell
1
2
max2 x y | x < y     = y 
         | otherwise = x

Если же вдруг понадобится, например, найти максимальное нескольких чисел, то это - известная абстракция, которая называется свёртка. Поэтому нам даже не нужна для этого отдельная функция - просто используем абстракцию:

Haskell
1
main = print $ (foldr1 max2) [3, 7, 1, 6]

Вот то же самое на C#:

C#
1
2
int Max2(int x, int y) => x < y ? y : x;
void Main() => new List<int>{3, 7, 1, 6}.Aggregate(Max2).Dump();

И этот подход в данном случае гораздо более продуктивен, чем написание класса на 40 строк. В принципе, даже просто процедурный подход в данном случае будет более продуктивен, чем ООП:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Main()
{
    var result = Maxn(new List<int>{3, 7, 1, 6});
    Console.WriteLine(result);
}
 
int Max2(int x, int y) 
{
    return x < y ? y : x;
}
 
int Maxn(List<int> numbers)
{
    if(numbers == null) 
        throw new ArgumentNullException("numbers");
    
    if(numbers.Count == 0) 
        throw new InvalidOperationException("Последовательность не содержит элементов");
    
    int max = numbers(0);
    for(int i = 1; i < numbers.Count; i++)
        max = Max2(max, numbers[i]);
    
    return max;
}

(хотя вместо двух строчек пришлось написать двадцать)

p.s. Функцию f(x,y) = max(x,y) я выбрал просто для примера. С тем же успехом я мог использовать и другую, например, f(x,y) = 2x + y.

@Fulcrum_013 · 17.03.2016, 06:11

Сообщение от Shamil1

Если же вдруг понадобится, например, найти максимальное нескольких чисел, то это - известная абстракция, которая называется свёртка

Что под капотом у этой свертки?

Сообщение от Shamil1

чем написание класса на 40 стро

Который экономит кучу кода при его использовании. Мало того, при его помощи можно считать не толко банально max массива, ну в духе:

C++
1
2
3
4
DynamicArray<int> Array;
......
for(TMax<Int> Max;Max.Count<Array.Length;Max<<Array[Max.Count]);
l

немного уcложним:

C++
1
2
3
4
5
6
DynamicArray<int> Array;
......
for(TMax<Int> Max;Max.Count<Array.Length;Max<<Array[Max.Count]);
 
TStack<int> Stack;
while (Stack.Size)Max<<Stack.Pop();

не меняя самого кода подсчета посчитали максимум и номер максимума канкатенации 2-х различных последовательностей.
при этом кстати можно немного по другому делать:

C++
1
2
3
4
5
6
7
8
9
DynamicArray<int> Array;
......
for(TMax<int> Max;Max.Count<Array.Length;Max<<Array[Max.Count]);
 
TStack<int> Stack;
TMax<int> Max2;
while (Stack.Size)Max2<<Stack.Pop(); 
Max<<Max2;
// т.е. готов боец для парааллеленья счета.

Но можно и подсчитывать например максимум значений вычисляемых в рекурсивной функции, что доставит немало плясок с бубном и проверок чтобы все операторы сравнения были одинаковыми,если в рекурсии участвуют несколько функций. При других подходах будет та еще пляска с бубном. Т.е. эти 40 строк кода экономят гораздо большее количество при повторном использовании.

Добавлено через 9 минут

Сообщение от Shamil1

new List<int>{3, 7, 1, 6}.Aggregate(Max2).Dump();

А что тут типа не вызов списка с инициализацией класса который под капотом? Да кстати огромным недостатком этих ваших реализаций является то что списки из одного источника и т.д и т.п. Мало того, а сколько ваши свертки используют Indirect call и записи в стек на каждый элемент?

Добавлено через 16 минут

Сообщение от Shamil1

Задача: вычислить максимальное из двух int32 чисел.

вот тут как минимум неоднозначность. Масимальное значение или номер максимального? Мой класс решает и то и другое.

Добавлено через 10 минут

Сообщение от Shamil1

требуемый результат описан без неоднозначностей и исходных данных достаточно, чтобы получить результат

Но не соответствует ГОСТ который требует максимальной универсальности алгоритмов

Сообщение от Shamil1

Поэтому нам даже не нужна для этого отдельная функция - просто используем абстракцию:

Вот поэтому и говорится - когда все касается околовсяческих вопросов в сферическом ваккууму так вроде текст и более короткий можно. А вот как конкретного практического применения - так обычно главная проблема не сравнить эти два инта а достать оттуда где они лежат.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class TTreeNode{
       TList<TTreeNode*> FNodes;
       int value;
       ............    
       template <class traverser>void Traverse(traverser &result){ 
                 result<<value; 
                 for (int i=0;Nodes->Count;i++)Nodes->Items[i]->Traverse(result);
       };
       .............
} 
void main(){
      TTreeNode* Nodes;
      ..........
      TMax<int> Max;
      Nodes->Traverse(Max);
}

А вот так и по дереву максимум найдем.

Добавлено через 10 минут

Сообщение от Shamil1

Мы решаем задачу

Вот с этого и начнем - РЕШАЕМ ЗАДАЧУ - а не крутим непонятно что в сферическом вакууме которое потом пахнет исключительно копи-пастинг программингом.

Добавлено через 3 часа 52 минуты
[/CPP]

Сообщение от Shamil1

Если же вдруг понадобится, например, найти максимальное нескольких чисел, то это - известная абстракция, которая называется свёртка.

банальная до ужаса избитая ситуация - индексированный по субсетам RAW массив вертексов с известным страйдом, найти по каждаму сабсету макс значения по каждой координате x, y, z (для простоты координаты в начале вертекса):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Дано
struct TSubset{
    unsigned StartIndex;
    unsigned Count;
} 
int Stride; //для простоты в количествах атрибутов в вертексе  а не в байтах
DynamicArray<TSubsets> Subsets;
DynamicArray<int> Indices;
DynamicArray<float>  Vertices;
// каким то образом это дано заполнено.
typedef TMax<float>[3] TMax3f;
TMax3f *Maxes=new TMax3f[Subsets.Size];
for(int Subset=0;Subset<Subsets.Length;Subset++) 
     for(int Index=Subsets[Subset].StartIndex;
               Index<Subsets[Subset].StartIndex+Subsets[Subset].Count;
               Index++) 
          for(int Axe=0;Axe<3;Axe++) Maxes[Subset][Axe]<<Vertices[Indices[Index]*Stride+Axe];
//Выводим данные
delete Maxes;

Минимумы параллельно посчитать еще порядка 10 строк добавить (реализацию счетчика минимумов), и пару строк в самом траверсинге). А как вы с вашими свертками такую задачу решать будете? Надеюсь не сильно вас огорчу если скажу что методы траверсинга последовательностей не поддерживающие произвольный доступ окончательно вымерли вместе с ОЗУ на магнитной ленте? Поэтому сделать последовательный просмотр последовательности и его параметризировать - бред. Гораздо лучше сделать более-менее универсальные счетчики, и пользовать их в конструируемых траекториях обхода. Да кстати при этом и быстродействие выигрывает. У меня пока что в этих примерах только компайл-тайм полиморфизм используется, все на инлайнах.

@Shamil1 · 17.03.2016, 09:43

Сообщение от Fulcrum_013

Что под капотом у этой свертки?

Вы имеете ввиду код? Код зависит от сворачиваемого объекта.

Сообщение от Fulcrum_013

Который экономит кучу кода при его использовании.

Не заметил экономии. Ваше
for(TMax<Int> Max;Max.Count<Array.Length;Max<<Array[Max.Count]);
длиннее, чем моё
foldr1 max2 array

Но главное, чтобы понять, что делает Ваш код, нужно знать, что делает класс Max. В частности, нужно знать, что оператор << увеличивает Max.Count. Что делает мой код, понятно с первого взгляда даже без знания того, что делает функция max2: сворачивает (справа) объект array по функции max2.

Кликните здесь для просмотра всего текста

Это как в математике. Вместо того, чтобы писать "a₁ + a₂ + ... + a_n", вводят абстракцию "сумма" и специальный знак для её обозначения. Запись сразу становится короче и удобней.

И что вы будете делать есть понадобиться посчитать максимум квадратов или сумму или 2x + y и т.п.? Каждый раз писать новый класс на 40 строк кода?

@Fulcrum_013 · 17.03.2016, 10:13

Сообщение от Shamil1

Вы имеете ввиду код? Код зависит от сворачиваемого объекта.

То есть при изменении типа обхода вам нужно новый подкапотный вариант разрабатывать?

Добавлено через 17 минут

Сообщение от Shamil1

Не заметил экономии.

Имена переменных должны отражать суть хранимых в них значений. Экономит время разработки гораздо больше чем свертки.

Сообщение от Shamil1

Каждый раз писать новый класс на 40 строк кода?

Ну зачем же на 40? Можно выделить базовый и от него породить наследников, которые только счетной функцией отличаются. На некотором этапе если дальнейшее наращивание шаблонов грозит комбинаторным взрывом можно перейти к рантайм полиморфизму на виртуальных методах, и даже собирать в контейнер наборы счетчиков, экономя машинное время на обходе последовательности.
При этом у меня нет жесткой привязки к траектории обхода последовательности, которая простым списком с последовательным доступом далеко не исчерпывается, при этом запросто делать счет сразу по нескольким потоком и нескольких искомых значений. Ваши методы хороши для ОЗУ на магнитной ленте а не для современных задач. Да и даже на ленте задачи разные бывают. Подсчитайте к примеру отдельно максимумы в четных и нечетых позициях по отдельности за один проход вместе с их номерами.

@Shamil1 · 17.03.2016, 10:41

Сообщение от Fulcrum_013

не меняя самого кода подсчета посчитали максимум и номер максимума канкатенации 2-х различных последовательностей

foldr max2 (fold1r max2 stack) array

Сообщение от Fulcrum_013

готов боец для парааллеленья счета

В чём параллельность? В том, что считаем для двух последовательностей в разных переменных?

Сообщение от Fulcrum_013

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

Вы задачу сформулируйте, и я Вам напишу, как это делается без плясок с бубном.

Сообщение от Fulcrum_013

вот тут как минимум неоднозначность. Масимальное значение или номер максимального?

Я чётко написал "максимальное из двух чисел". И ни слова про номер.
(И когда я писал, вообще я имел ввиду произвольную функцию двух аргументов... то есть, что для результата можно задать ещё и "номер", это случайность...)

Сообщение от Fulcrum_013

так обычно главная проблема не сравнить эти два инта а достать оттуда где они лежат.
......
А вот так и по дереву максимум найдем.

И не только по дереву - по любому сворачиваемому объекту:
fold1r max2 tree

Сообщение от Fulcrum_013

А что тут типа не вызов списка с инициализацией класса который под капотом? Да кстати огромным недостатком этих ваших реализаций является то что списки из одного источника и т.д и т.п. Мало того, а сколько ваши свертки используют Indirect call и записи в стек на каждый элемент?

Инициализации классом "под капотом" тут нет.
Источник - любой, для которого определена свёртка.
Косвенных вызовов тоже нет.
В C# вызывается статический метод Aggregate некого статического класса, который (класс) нужен только потому, что в C# не существует функций (методов вне класса). И я даже названия этого класса не помню, так как мне не нужно его знать.
Теоретически, компилятор может этот вызов заинлайнить.

Добавлено через 10 минут

Сообщение от Fulcrum_013

Но не соответствует ГОСТ который требует максимальной универсальности алгоритмов

Вы на олимпиаде тоже так скажете: "Я не буду решать Вашу задачу, так как условие не соответсвует ГОСТу"?

Сообщение от Fulcrum_013

Вот с этого и начнем - РЕШАЕМ ЗАДАЧУ - а не крутим непонятно что в сферическом вакууме которое потом пахнет исключительно копи-пастинг программингом.

Во-первых, в Вашем высказывании было "для любой задачи", а не "для задачи такого-то класса". Поэтому я выбирал такую задачу, на которой использование ООП особенно нецелесообразно.
Если хотите, можем выбрать какую-нибудь типичную олимпиадную задачу и сравнить на ней.

@Igor3D · 17.03.2016, 10:46

Сообщение от Fulcrum_013

for(int Axe=0;Axe<3;Axe++) Maxes[Subset][Axe]<<Vertices[Indices[Index]*Stride+Axe];

Если уж так хотелось "пообобщать", то не лучше ли это делать на уровне вертексов, дописав friend оператор или просто полезную утилитку, напр

C++
1
2
3
4
inline Vertex MaxVer( const Vertex & v0, const Vertex & v1 )
{
 return Vertex(MAX(v0.x, v1.x), MAX(v0.y, v1.y), MAX(v0.z, v1.z));
}

Также stride неплохо бы оформить, напр

C++
1
2
3
4
inline Vertex & GetStrideVer( void * src, size_t index, size_t stride )
{
  return *(Vertex *)((char *) src + index * stride);
}

Такие простецкие штучки дают гораздо больший эффект чем городушка высосанных из пальца классов

@Fulcrum_013 · 17.03.2016, 10:48

Сообщение от Shamil1

Но главное, чтобы понять, что делает Ваш код, нужно знать, что делает класс Max.

А для того чтобы понять код всегда надо знать что делают его элементы.

Сообщение от Shamil1

бъект array по функции max2.

Точно так же для понимания вашего кода надо знать что делает функция Max2.

Зато создать в одну команду и за один проход посчитать 3*N экземпляров счетчика по разным частям массива - вот тут вам и придется вашу свертку как минимум N раз по всему массиву гонять и делать N реализаций функции max (ну или как минимум N замыканий если есть возможность номер элемента получать в каллбек-функцию.).
Это вобщем то и есть элементарная арифметика, которая говорит что вариантов обхода последрвательности бесконечное множество, не говоря о том что самих типов структур данных тоже по большому счету бесконечное множество. Соответсвенно на все случаи жизни свертками не запасешься. А вот количество основных операций над ними достаточно ограниченно.

@Igor3D · 17.03.2016, 11:17

Сообщение от Fulcrum_013

..вариантов обхода последрвательности бесконечное множество, не говоря о том что самих типов структур данных тоже по большому счету бесконечное множество. Соответсвенно на все случаи жизни свертками не запасешься. А вот количество основных операций над ними достаточно ограниченно.

Это очень популярная болезнь - увлечение общностью. Вы привели конкретный пример - подсчет макс по суб-мешам. Лично я не наблюдаю ровным счетом никаких выгод от использования Вашего класса. Зато неудобств хватает - кто такой оператор << ? Кто будет ловить исключения что Вы так легкомысленно испускаете? Ну а имена переменных с большой буквы - вчера с Паскаля пришли, что ли?

Возвращаясь к ООП. Вообще-то суб-меш - явная "сущность", а значит и класс. И подсчет bounding box - явно метод (константный).

@Fulcrum_013 · 17.03.2016, 12:22

Сообщение от Shamil1

Если хотите, можем выбрать какую-нибудь типичную олимпиадную задачу и сравнить на ней

Запросто. Условия задачи: есть черно/белый снимок планеты из космоса . Хранится в файле построчно. 0 соответсвует океану, 1 земле. Континентом называется любой участок суши (4-х связный) размером более 1 ячейки. Островом называется любая ячейка суши не имеющая по соседству только ячейки океана. Озером называется любой замкнутый водоем не имеющий выхода в мировой океан. Любая суша внутри озера считается островом в не зависимости от размера. Необходимо посчитать количество островов, континентов, озер по каждому континенту посчитать крайние точки, площадь территории, площадь занимаемую озерами, площадь озерных островов, крайние точки озер. Построить карту высот континентов и глубин озер. За высоту/глубину принимается расстояние до ближайшей точки берега. Указать высоту/глубину и координаты наиболее высоких горных вершин и наиболее глубоких озерных впадин как по планете, так и по каждому континету в отдельности. Указать наибольший по площади континент, а так же наибольшие 1. по площади 2 по объему воды озеро как по планете так и по каждому континенту. Ну пока что этого хватит. Моря заливы и полуострова пока опустим. А то давно олимпиада была, точных определений уже не помню. Да еще. По границам карты рамка из вод мирового океана.
Условия самой олимпиады - оценивается быстродействие и потребляемая алгоритмом память.
Это с областной олимпиады 1993-го года.
Еще одна олимпиадная задачка: Дано - любое устройство перемещаемое по земле собственным двигателем на ваш выбор. Необходимо: устройство самостоятельно без использования JPS (разрешается пользоваться любым навигационным оборудованием не принимающем сигналов с других искуственных объектов) должно проехать по навигационным точкам отмеченным на карте в пустыне Невада 120км из пункта А в пункт Б. Ограничение: на прохождение маршрута отводится продолжительность световго дня летом (примерно 14 часов). Во время движения по маршруту устройство должно обеспечивать избегание столкновений с людьми, животными (даже в случае нападений с их стороны) и другими транспортными средствами.
Олимпиада началась в районе 2000-го и продолжается по сегодняшний день. Главный приз более миллиона долларов (пока еще не разыгран). Тоже между прочим олимпиадное программирование.

Добавлено через 10 минут

Сообщение от Igor3D

Ну а имена переменных с большой буквы - вчера с Паскаля пришли, что ли

Та нет 20 лет как с Паскаля спрыгнул. Конвенция имен такая. Гораздо более удобная чем мелкомягкая. На самом деле она не паскалевская а борландовская. А паскалевской ее называют исключительно потому что борланд и его приемник Embarcodero уже более 35 лет абсолютные монополисты на рынке промышленного паскаля.

Добавлено через 14 минут

Сообщение от Igor3D

<<

Вообще то стандартный оператор вывода в поток.

Сообщение от Igor3D

то не лучше ли это делать на уровне вертексов

Представьте себе не лучше. Вернее оно лучше. Но только тогда когда формат вертекса известен на этапе компиляции.

Сообщение от Igor3D

Если уж так хотелось "пообобщать", то не лучше ли это делать на уровне вертексов, дописав friend оператор или просто полезную утилитку, например

Ну и зачем нам на каждом шаге конструировать в стеке вертекс (а тем более неизвестного при компиляции формата) а потом его переписывать в приемник

Сообщение от Igor3D

Кто будет ловить исключения что Вы так легкомысленно испускаете?

Отладчик. Они для того и нужны чтобы сразу попасть в сбойное место на сбойной итерации во время отладки.

Добавлено через 21 минуту

Сообщение от Igor3D

Возвращаясь к ООП. Вообще-то суб-меш - явная "сущность", а значит и класс. И подсчет bounding box - явно метод (константный).

То смотря где и смотря зачем и смотря как они в буфера уложены и где эти буфера находятся. В подавляющем большинстве случаев для сабсетов пользуют не классы а массив с указанием номера начального и конечного индекса. Во всяком случае тех которые хранятся в буферах видеокарты в общем буфере меша. Хотя бы потому что адрес по которому буфер при каждом локе мапируется в видеопамять не гарантированный. причем индекс буфер и вертекс буфер обычно разные буфера. поэтому и всеми операциями занимается более высокая сущность - меш.

Сообщение от Igor3D

И подсчет bounding box - явно метод (константный)

Метод. Только в большинстве случаев меша а не сабмеша. Тут другая логика - кто указатели на буфера имеет тот и считает. Меш сам по себе единое целое. Только покрашены части могут быть по разному. Вот собственно за эту покраску сабмеши и отвечают. т.е. хранят наборы точек переключения материалов. Еще одно назначение - разные наборы сабмешей могут опираясь на один вертексный буфер но разные группы индексов описывать разные ЛОД.

@Shamil1 · 17.03.2016, 12:37

Сообщение от Fulcrum_013

А для того чтобы понять код всегда надо знать что делают его элементы.

Сравните:

C++
1
for(TMax<int> Max;Max.Count<Array.Length;Max<<Array[Max.Count]);

и

C#
1
2
for(int i = 1; i < numbers.Count; i++)
        max = Max2(max, numbers[i]);

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

Сообщение от Fulcrum_013

Зато создать в одну команду и за один проход посчитать 3*N экземпляров счетчика по разным частям массива

Я не понял, что Вы имеете ввиду. Приведите пример того, что нужно сделать.

@Igor3D · 17.03.2016, 12:38

Сообщение от Fulcrum_013

Представьте себе не лучше. Вернее оно лучше. Но только тогда когда формат вертекса известен на этапе компиляции.

Сообщение от Fulcrum_013

Ну и зачем нам на каждом шаге конструировать в стеке вертекс (а тем более неизвестного при компиляции формата) а потом его переписывать в приемник

Поверьте, нет ничего более избитого, чем такие "детские болезни"

Ими страдают миллионы. Вместо того чтобы решать конкретную задачу максимально эффективно - человек впадает в манечку "общности" и/или "оптимизации".

Сообщение от Shamil1

Если хотите, можем выбрать какую-нибудь типичную олимпиадную задачу и сравнить на ней.

Хорошее предложение, а то пока только слова. Только я бы не делил задачи на "олимпиадные" и нет

Сообщение от Fulcrum_013

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

Речь об ОДНОЙ задаче. Can you please be more specific?

@Shamil1 · 17.03.2016, 12:44

Сообщение от Fulcrum_013

. Указать высоту/глубину и координаты наиболее высоких горных вершин и наиболее глубоких озерных впадин как по планете, так и по каждому континету в отдельности.

Откуда возьмутся эти значения, если для каждой клетки у нас "0 соответсвует океану, 1 земле".

Предлагаю не формулировать задачу самостоятельно, а привести ссылку (на задачу на авторитетном сайте). Например, на http://acm.timus.ru/, http://www.diofant.ru/ или какой-нибудь другой подобный.

@Igor3D · 17.03.2016, 13:51

Сообщение от Shamil1

Предлагаю не формулировать задачу самостоятельно, а привести ссылку (на задачу на авторитетном сайте). Например, на http://acm.timus.ru/, http://www.diofant.ru/ или какой-нибудь другой подобный.

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

@Shamil1 · 17.03.2016, 15:12

Сообщение от Igor3D

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

Сформулируйте задачу.

@Fulcrum_013 · 17.03.2016, 21:56

Сообщение от Igor3D

Речь об ОДНОЙ задаче

А это и есть ОДНА задача.

Добавлено через 40 секунд

Сообщение от Shamil1

Откуда возьмутся эти значения, если для каждой клетки у нас "0 соответсвует океану, 1 земле"

В качестве этих значений использовать минимальное расстояние от берега.

Добавлено через 3 минуты

Сообщение от Shamil1

Приведите пример того, что нужно сделать

Да по тому же примеру. Посчитать AABB по субмешам индексированного меша.

Добавлено через 12 минут

Сообщение от Igor3D

Вместо того чтобы решать конкретную задачу максимально эффективно - человек впадает в манечку "общности" и/или "оптимизации"

Вот и я об э

Сообщение от Shamil1

for(TMax<int> Max;Max.Count<Array.Length;Max<<Array[Max.Count]);

том. Свертка с каллбэк функцией и не гибко и не эффективно.

Сообщение от Shamil1

for(TMax<int> Max;Max.Count<Array.Length;Max<<Array[Max.Count]);

можно и так:

C++
1
for (int i=0;i<Array.Length;i++)Max<<Array[i];

А можно и вот так:

C++
1
for (int i=0;i<Array.Length;i++)(i&1?MaxOdd:MaxEven)<<Array[i];

@Shamil1 · 18.03.2016, 09:32

Сообщение от Fulcrum_013

Посчитать AABB по субмешам индексированного меша.

Мне этот жаргон не знаком. Я не хочу гадать, что у Вас там за ячейки и по какому свойству они индексированы.

Добавлено через 29 секунд

Сообщение от Fulcrum_013

Свертка с каллбэк функцией и не гибко и не эффективно.

Обоснуйте.
До сих пор в этой теме код, написанный с использованием свёртки наглядней и значительно короче.

Добавлено через 9 минут

C++
1
2
    for(int i = 1; i < numbers.Count; i++)
        max = Max2(max, numbers[i]);

распараллеливается добавлением одной OMP директивы

C#
1
max = numbers.Aggregate(Max2);

распараллеливается добавлением вызова одной функции

C++
1
for(TMax<int> Max;Max.Count<Array.Length;Max<<Array[Max.Count]);

Что нужно сделать, чтобы распараллелить этот код?

@Fulcrum_013 · 18.03.2016, 09:58

Сообщение от Shamil1

Что нужно сделать, чтобы распараллелить этот код?

А зачем, У вас что ядер больше чем элементов в массиве? тоже мне блин парралелетели. Параллелить нужно там где нужно.

Добавлено через 2 минуты
Ну а если так уж хочется попараллелить - то разделить массив на количество доступных ядер, каждому потоку дать свой кусок, со своим экзеземпляром TMax, а результаты из TMax потом объеденить.

@Shamil1 · 18.03.2016, 10:20

Сообщение от Fulcrum_013

А зачем, У вас что ядер больше чем элементов в массиве? тоже мне блин парралелетели. Параллелить нужно там где нужно.

В два потока посчитается почти в два раза быстрее.

Добавлено через 3 минуты

Сообщение от Fulcrum_013

В качестве этих значений использовать минимальное расстояние от берега.

А если берега нет? (все клетки - суша или все клетки - вода)
Что такое мировой океан? Может ли их быть ноль или несколько?

Какой ответ должна выдать программа при входе:
010
010
010

@Fulcrum_013 · 18.03.2016, 12:27

Сообщение от Shamil1

В два потока посчитается почти в два раза быстрее.

Во первых это если вам два ядра доступно безраздельно. Во вторых чтобы оно в два потока посчиталось, массив по любому нужно разделить на две части (ну или на n по количеству доступных ядер), произвести подсчет по каждой части по отдельности, потом найти максимальное из результатов. Т.к. операции последовательны (зависят от результата предыдущей), но при этом коммутативны. Были бы не были коммутативны, то вообще бы был перпендикуляр полный.

Добавлено через 3 минуты

Сообщение от Shamil1

Какой ответ должна выдать программа при входе:

Некорректные входные данные.
По условию - все клетки границы массива (рамка по периметру) - вода. Мировой океан-вся вода которая соединенна с рамкой (имеет 4-х связный проход);

Добавлено через 1 час 1 минуту

Сообщение от Shamil1

До сих пор в этой теме код, написанный с использованием свёртки наглядней и значительно короче.

Свертками всех нужных типов обхода не запасешся, а тем более даже в одномерный массив все возможные варианты не упихнешь, не то что в двухмерный или что то посложнее. У вас есть свертка для итерации в обратную сторону? Или четных/нечетных? Или матрицы по двойной спирали?

Новые блоги и статьи Все статьи Все блоги /
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .

@qwertyyyyyw 6 / 6 / 5 Регистрация: 29.01.2015 Сообщений: 467

	Как научиться олимпиадному программированию 15.03.2016, 07:08. Показов 6343. Ответов 63 Метки нет (Все метки) Что делать, если я уже более 5 лет пишу код в веб, c++, но, я не умею решать задачи из олимпиад? Какие сайты изучить? 0