1. Этот сайт использует файлы cookie. Продолжая пользоваться данным сайтом, Вы соглашаетесь на использование нами Ваших файлов cookie. Узнать больше.
  2. Вы находитесь в сообществе Rubukkit. Мы - администраторы серверов Minecraft, разрабатываем собственные плагины и переводим на различные языки плагины наших коллег из других стран.
    Скрыть объявление
Скрыть объявление
В преддверии глобального обновления, мы проводим исследования, которые помогут нам сделать опыт пользования форумом ещё удобнее. Помогите нам, примите участие!

Коррупция - непобедима?

Тема в разделе "Оффтопик", создана пользователем LuckyZeeRo, 20 дек 2018.

Метки:
  1. IlyaHaker

    IlyaHaker Активный участник Пользователь

    Баллы:
    76
    Есть некое бинарное дерево поиска. У него есть корень. Левое и правое поддерево тоже являются бинарными деревьями. Вводится число, если оно меньше корня - переходим в левое поддерево, если больше - в правое рекурсивно. И если нашелся NULL, то запишем туда. Если хочешь узнать подробнее - погугли "бинарное дерево поиска"
     
  2. Code

    Code Старожил Пользователь

    Баллы:
    123
    Имя в Minecraft:
    _Gizmo
    в каком месте перебор 100000 элементов (максимум по условию задачи) выбивается за 1/10 секунды?)) мне просто интересно, как ты считал.
    поиск минимума в массиве делается за 1 проход по массиву. скорость процессора сейчас измеряется в гигагерцах. это миллиард операций в секунду. а у тебя даже миллиона чисел нет. поиск минимума произойдет мгновенно.
    в целях оптимизации всего алгоритма (чтобы не искать минимум каждый раз) так же предлагается массив отсортировать. сортируем в данном случае с помощью multiset. сортировка занимает чуть дольше времени, чем поиск минимума, но тоже быстро. в 100 миллисекунд укладывается легко.
     
  3. jwplaster

    jwplaster Старожил Пользователь

    Баллы:
    173
    Skype:
    jwplaster.smartworld
    Имя в Minecraft:
    QviNSteN
    ну, я банально вбил код считать элементы + перебрать их, и закинул код в компилятор на сайте (C#), и крч половина вариантов просто не прошла по времени ору
     
  4. Code

    Code Старожил Пользователь

    Баллы:
    123
    Имя в Minecraft:
    _Gizmo
    я не знаю че ты там за код написал, ТС скинул свой код через multiset, по времени он только в последний тест немного не уложился. если ты написал тупой перебор всех комбинаций с поиском максимума, то конечно это медленно
     
  5. jwplaster

    jwplaster Старожил Пользователь

    Баллы:
    173
    Skype:
    jwplaster.smartworld
    Имя в Minecraft:
    QviNSteN
    Нет, просто у него плюсы. На c# на считывание идет больше времени, чем в плюсах. Но они же должны были это учесть при создании задачи, вот о чем я
     
  6. Reality_SC

    Reality_SC Старожил Пользователь

    Баллы:
    123
    Имя в Minecraft:
    Reality_SC
    Возможно, что для разных языков на одну и ту же задачу установлены разные ограничения по памяти/времени...
     
  7. jwplaster

    jwplaster Старожил Пользователь

    Баллы:
    173
    Skype:
    jwplaster.smartworld
    Имя в Minecraft:
    QviNSteN
    Если бы... всё так же в 0.1 секунду
     
  8. IlyaHaker

    IlyaHaker Активный участник Пользователь

    Баллы:
    76
    Скинь чтоли сюда, что ты там понаписал
     
  9. dreadfaly

    dreadfaly Активный участник Пользователь

    Баллы:
    76
    Имя в Minecraft:
    dolphif
    Епт, спасибо за годный сайт :rolleyes:
     
  10. jwplaster

    jwplaster Старожил Пользователь

    Баллы:
    173
    Skype:
    jwplaster.smartworld
    Имя в Minecraft:
    QviNSteN
    Да там просто дичь какая-то.
    Он мне выдаёт "Ошибка выполнения", не "Неправильный ответ" даже, а именно ошибку. Ору.
    хотя щас прогнал около сотни рандомных вариантов в цикле и всё ок .-.

    Кто знает C#, сами гляньте хд

    Код:
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace ConsoleApp13
    {
        class Program
        {
            static void Main(string[] args)
            {
    
                double[] NP = Array.ConvertAll(Console.ReadLine().Split(' '), double.Parse);
                double p = 1 - ((double)NP[1] / 100.0);
                List<double> mass = Array.ConvertAll(Console.ReadLine().Split(' '), double.Parse).OrderBy(j => j).ToList();
    
    //Дальше алгоритм прост: ебашим цикл священной инквизиции, удаляя приплюсованные элементы. Саму плюсовщину мы заранее ещё и в процентную преобразуем.
    Ну и в самом начале всё выставляем "на вырост". Да, i=-1 нужна хрень, без неё ничо не работает, хз почему, но цикл сразу решает единицу прибавить и крщ мне просто лень с этим разбираться
    
                for(int i = 0;  i <NP[0]-1; i++)
                {
                    mass = mass.OrderBy(j => j).ToList();
                    mass[i] += mass[i + 1];
                    mass[i] *= p;
                    mass.RemoveAt(i + 1);
                    NP[0]--;
                    i = -1;
                }
    
    //а тут "типаправильное" округление
    
                 Console.WriteLine("{0:0.00}", Math.Round(mass[0],2));
            }
        }
    }
    На сайте указано, что тип это значит, что в конце выполнения программы оно не вернуло 0... ору.
     
    Последнее редактирование: 10 янв 2019
  11. jwplaster

    jwplaster Старожил Пользователь

    Баллы:
    173
    Skype:
    jwplaster.smartworld
    Имя в Minecraft:
    QviNSteN
    а, да я тупо рекурсию создал так хддд я как раз те рандомные варианты прописывал для самопроверки и крщ забыл удалить отправку метода рандома лл

    Сам дурак крч)
     
  12. IlyaHaker

    IlyaHaker Активный участник Пользователь

    Баллы:
    76
    Индус detected
    И да, у тебя код долгий от того, что ты каждый раз сортируешь свой список, а не от функций ввода-вывода
     
  13. Code

    Code Старожил Пользователь

    Баллы:
    123
    Имя в Minecraft:
    _Gizmo
    ну значит у тебя крашится прога
    на строке
    List<double> mass = Array.ConvertAll(Console.ReadLine().Split(' '), double.Parse).OrderBy(j => j).ToList();
    я в сишарпе не силен, не могу сказать почему.
    едрить программист от бога)
    у тебя на каждой итерации i = 0, поэтому for можно заменить на while (NP[0] > 1), i на 0, а i + 1 на 1
    ну и сортировать заново список каждый раз - сверхразум
     
  14. Code

    Code Старожил Пользователь

    Баллы:
    123
    Имя в Minecraft:
    _Gizmo
    понял, там где-то пустая строка затесалась
    вот так не падает
    Код:
    List<double> mass = new List<double>();
    foreach (String s in Console.ReadLine().Split())
    {
        if (!string.IsNullOrEmpty(s)) {
            mass.Add(double.Parse(s));
        }
    }
    
    полный код, но по времени из-за кучи сортировок это треш
    Код:
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace ConsoleApp13
    {
        class Program
        {
            static void Main(string[] args)
            {
    
                double[] NP = Array.ConvertAll(Console.ReadLine().Split(' '), double.Parse);
                double p = 1 - ((double)NP[1] / 100.0);
                List<double> mass = new List<double>();
                foreach (String s in Console.ReadLine().Split())
                {
                    if (!string.IsNullOrEmpty(s)) {
                        mass.Add(double.Parse(s));
                    }
                }
    
                while(NP[0] > 1)
                {
                    mass = mass.OrderBy(j => j).ToList();
                    mass[0] += mass[1];
                    mass[0] *= p;
                    mass.RemoveAt(1);
                    NP[0]--;
                }
    
                 Console.WriteLine("{0:0.00}", Math.Round(mass[0],2));
            }
        }
    }
    
     
  15. IlyaHaker

    IlyaHaker Активный участник Пользователь

    Баллы:
    76
    Да не, ты што, Code, это все из-за долгого считывания в C#!
     
  16. Code

    Code Старожил Пользователь

    Баллы:
    123
    Имя в Minecraft:
    _Gizmo
    :D
     
  17. jwplaster

    jwplaster Старожил Пользователь

    Баллы:
    173
    Skype:
    jwplaster.smartworld
    Имя в Minecraft:
    QviNSteN
    Смотри пример:
    5 0
    5 4 3 1 2 => 1 2 3 4 5
    Начинаем суммировать:
    1+2=3. Удаляем 2й
    3 3 4 5
    Дальше
    6 4 5
    Если я не буду опять её сортировать, у меня выйдет
    10 5
    А должно выйти
    6 9
    Потому что проценты и блабла
     
  18. IlyaHaker

    IlyaHaker Активный участник Пользователь

    Баллы:
    76
    но multiset же сам сортирует. Если такого в C# нет такого - можешь сделать с помощью RB дерева
    Сортировка идет при вводе
     
  19. jwplaster

    jwplaster Старожил Пользователь

    Баллы:
    173
    Skype:
    jwplaster.smartworld
    Имя в Minecraft:
    QviNSteN
    Ну вот я и слелал сортировку после каждого суммирования
     
  20. Code

    Code Старожил Пользователь

    Баллы:
    123
    Имя в Minecraft:
    _Gizmo
    я дико извиняюсь, но хочется уже с приличных слов перейти на неприличные.
    я прекрасно понимаю зачем ты делаешь сортировку. но изменив алгоритм можно обойтись и без нее.
    тебе уже предложили алгоритм, который по сути делает то же самое (берет 2 минимальных, складывает, кладет обратно) только без постоянных сортировок.
    multiset всегда отсортирован. не потому что он после каждой вставки сортирует сам себя, а потому что у него такая структура, что вставка элемента происходит быстро и не нарушает сортированность. читай про деревья поиска.
    если ты все равно не понимаешь что конкретно дает использование multiset то просто перестань парить людям мозги в этой теме. почитай лучше книжку по алгоритмам и структурам данных
     

Поделиться этой страницей