• Объясните как посчитать график отношений RoR?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Судя по всему, у вам надо поставить звездочки в клетках i,j, если R[i][j] или если существует k, т.ч. R[i][k] и R[k][j].

    Видимо, "RoR" означает "связаны R напрямую или через одного". Я уж и не помню, как эта операция называется математически.

    Решение в лоб: завдеите массив для графика ответа и вычисляйте каждое значение поотдельности. Во-первых, если есть отношение во входном R в этой же ячейке. Во-вторых, напишите третий вложенный цикл, который переберет все промежуточные элементы, и установите ответ в true (или звездочку там поставьте), если оно есть хотя бы в одном R[i][k] и R[k][j] одновременно.
    Ответ написан
    5 комментариев
  • Почему нельзя использовать std::function как аргумет шаблонной функции?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Потому что лямбда не ялвяется std::function. Компилятор, вообще говоря, может лямбду привести к типу std::function, но не в вашем случае. Вам надо, например, самим преобразовать лямбду в std::function:
    std::function<bool(int, int)> comp = [](int left, int right)
      {
        return left < right;
      };
      Sort(vec, comp);


    Сам компилятор тут это сделать не может, потому что ему тип к которму приводить-то неизвестен - он зависит от параметра шаблона T.

    Можно, еще, например, указать компилятору параметры шаблона, тогда все скомпилируется:
    Sort<int>(vec, [](int left, int right)
      {
        return left < right;
      });


    Но лучший вариант - не использовать std::function в шаблоне. Просто используйте какой-то typename U, у которого вы продполагаете существует operator(int, int). Если туда передать не function и не лябмду, оно не скомпилится:

    template <typename T, typename U>
    void Sort(std::vector<T>& vector, U comparison) {
        // Используете comparison, как-будто это std::function:
        if (comparison(1, 1)) return;
    };
    
    
    int main()
    {
      std::vector<int> vec = { 1, 2, 3, 4, 5, 7, 6, 9 ,8 };
    
      Sort(vec, [](int left, int right) -> bool
      {
        return left < right;
      });
        return 0;
    }
    Ответ написан
    Комментировать
  • Почему умножение матрицы 8x8 медленнее чем 10x10?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Скорее всего тут дело в кеше процессора. После первых запусков так получилось, что данные оказались в кеше.

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

    Ну и главное, выполнять такое короткое действие всего один раз - это вообще моветон. Надо выполнить его сотню тысяч раз и потом общее время делить на количество запусков. Иначе вы меряете случайный шум в основном. Может тут вам просто все время (не)везет и вот так третий тест оказывается быстрее остальных.
    Ответ написан
    3 комментария
  • Почему недоступны приватные поля для дружественного метода?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    А есть вообще такая вещь, как дружественный метод в C++? Я вот тут что-то не вижу такого варианта.

    Вот дружественные функции там есть, да.

    И в вашем коде компилятор видит, что есть какая-то функция TakeApple в namespace Human. Метод класса Human он тут не замечает вообще. Ну и там, понятное дело, нет никакого доступа к приватным членам класса Apple.

    Вам надо или помечать дружественным весь класс Human, или выносить ваш код в отдельную функцию, которая будет дружественная обоим классам.
    Ответ написан
    3 комментария
  • Как решить задание без использования правила Лопиталя?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Раскройте sin(6x) по формуле синуса двойного и потом тройного углов. В итоге 2sinx - 1 и в числителе и в знаменателе сократится.
    Ответ написан
  • Возникает ошибка, но не знаю какая?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Посмотрите на ограничения в задаче. Введите вашей программе максимальный тест: 15 монеток и сумму примерно в 1000000000. Ваша программа попробует съесть дюжину гигабайт памяти и упадет.
    Ответ написан
  • Как это решать?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Тут очень большая сумма и очень мало монет. Поэтомуэту задачу надо решать полным перебором.

    Рекурсивная функция получает, например, сколько первых типов монет можно использовать и какую сумму надо набрать. Возвращает список монет. Внутри надо перебрать сколько раз последняя сонета береться: от 0 до 2 раз. Оставшаяся сумма рекурсивно собирается оставшимеся монетами (минус один к количеству типов, ведь последний мы уже использовали). Если рекурсивная функция что-то собрала, добавляем к ее ответу 0-2 теущие монеты и вощвращаем.

    Это отработает за 3^15*15 = 215233605 операций. Обычно это проходит. Можно соптимизировать: не брать текущую монету, если она слишком большая, останавливать перебор, если сумма первых монет недостаточна. Ну, или соптимизировать до 2^15*15: подсчитайте все возможные суммы, если можно брать по 1 монете. Таким же перебором или вообще циклом с битовой маской. Отсортируйте список из 32 тысяч чисел и проверьте, а есть ли там 2 числа, дающие искомую сумму (двумя указателями: двинули один раз левый, двигаем правый пока сумма слишком большая).

    Отдельно надо проверить, надо ли выводить -1 в ответ (сумма всех монет меньше N).
    Ответ написан
    Комментировать
  • Почему не работает ввод?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Попробуйте ваши строки на экран выводить. Нет ли там всяких лишних пробелов или переводов строк? Завершается ли программа, если ввести только конечную фразу? А если вы вводите что-то вроде "abc. Dragon flew away!", то строка будет " Dragon flew away!".
    Ответ написан
    Комментировать
  • Проверка редких кейсов в логике игр?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Эта проверка - элементарна. Поле и так все в памяти хранится. Просто посмотреть, что за тип биома там и есть ли там уже провод - это один if. Это наносекунды процессорного времени
    Ответ написан
    Комментировать
  • Модель F(x) с разрывом типа «скачок»?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Сила трения. Имеет разрыв в v=0. Ездили когда-нибудь в автобусе или метро каком-нибудь? Пробовали не держаться за поручни? Вот когда оно тормозит, вас вперед тянет некая сила, которая внезапно обрывается, когда транспорт полностью останавливается. Вот это оно фактически. Сила трения действует на транспорт, вам, с вашей точки зрения, кажется, что это вас тянет вперед (хотя это корпус автобуса тянет назад). Но в момент достижения нулевой скорости эта сила трения становится резко равной нулю.
    Ответ написан
    4 комментария
  • Где ошибка в коде?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Проблема в том, что strtok нельзя вот так использовать вложенно. Вы когда разбиваете строку по пробелам, вы ломаете состояние доя разбития по строкам. Выделите сначала все строки.

    Но вообще, тут не надо никаких strtok. Нельзя строки сразу читать через scanf, например? А вообще, лучше читать число и символ. И там в зависимостм от символа или начинать новую строку, или нет.
    Ответ написан
    Комментировать
  • Как графически показать эквивалентность двух множеств?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Наверно, на графике XY нарисовать обе функйции зависимости. Отметить отрезки допустимых x на OX, вертикальными линиями соединить концы отрезков с функцией зависимости, от точек пересечения горизонтальными линиями получить отрезок значений на оси OY. Если множества на оси OY совпали, то они эквивалентны (Спойлер: тут они не совпали. Например, инфинумом первого множества является 1, а второго - 27).
    Ответ написан
  • Почему любую булеву функцию можно представить в виде СДНФ или СКНФ?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Потому что эти формы - это тупо перечисление всех наборов входных значений, которые дают истину, или ложь (в другой форме). В СДНФ вы получаете слагаемые, объедененные через ИЛИ. Каждое слагаемое через И задает все переменные так, что только вот в конкретном наборе входных данных это слагаемое будет истинно. Раз они все через ИЛИ соединены, то вся функция истинна только если входные значение из нужного набора. Аналогично СКНФ - но там каждая скобочка истина, если входные переменные не равны набору, на котором функция должна давать ложь.
    Ответ написан
    Комментировать
  • Как сделать логику распространения файла?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Используйте вспомогательный аккаунт для заливки данных на гитхаб.
    Ответ написан
    1 комментарий
  • Графическая библиотека для C++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Судя по всему, вы про винду спрашиваете. Надо использовать всякие виндовые апи. Помимо GDI+ есть возможность работы через DirectX (c Win8) и WindowsGraphicsCapture (с Win10). С этим можно получать скриншот в текстурах. Потом можно прям на GPU их с шаблонами сравнивать, что будет на порядки быстрее работы с отдельными пикселями.
    Ответ написан
    2 комментария
  • Алгоритм построения многоугольника из исходного квадрата и пересекающих его линий?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Для начала, надо бы уточнить условие. Ибо непясно, по какому принципу выбирается, какая из двух отсекаемых прямой половин берется в ответ.

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

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

    Эта задача решается за O(n log n). Задайте каждую прямую в виде ax+by+c=0. Т.ч. вектор {a,b} выпущенный с прямой, торчит в сторону полуплоскости, которую надо взять. Если вдруг не так, то надо поменять знак у всех трех коэффициентов.

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

    В каждом множестве построим ломанную, отделяющую нужную область. Это будет выпуклая область с двумя бесконечными лучами в конце.

    Потом отсортируйте все прямые по углу наклона вектора {a,b}. Это можно сделать без тригонометрии, сравнивая векторы по векторному произведению. Ну, или просто какую-нибудь функцию вроде atan2() используйте.

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

    Потом добавляем полуплоскости по одной. Пока последняя вершина на ломанной не лежит в нужной полуплоскости, выбрасываем ее. Для этого убираем из обоих стеков последний элемент. Это можно проверить, просто подставив координаты точки в уравнение ax+by+c. Если даст отрицательное значение - выбрасываем.
    Если точек не осталось, или точка лежит где надо, то новую прямую надо пересечь с последней прямой. Точку пересечения и новую прямую добавляем в стек.

    В конце мы получили две ломанные, огибающие нужное пространство сверху и снизу. Надо их пересечь.
    Для этого выкинием сверхней ломанной все крайние точки, которые отсекаются последней и первой прямой в нижней ломанной. И наоборот. В конце, пересечения двух бесконечных лучей слева и справа добавляем в ответ.
    Ответ написан
    Комментировать
  • Безопасен ли сайт paimon.moe?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Проблема этой команды в том, что она отключает все системы безопасности, потом запускает скрипт из интернета по ссылке. Этот скрипт может и измениться в будущем. Т.ч. даже если оно безопасно прямо сейчас, оно может использоваться для кражи всего в любой момент.

    Код по ссылке сейчас вроде не делает ничего страшного. Он проверяет какой-то файл, вероятно, принадлежащий Геншину, берет оттуда какие-то URL адреса, делает к ним запросы, и на основе ответов выбирает какой-то url, который и выдает вам и просит вставить на paimon.moe.

    Я бы посоветовал не запускать вот ту команду, что вам дают, а использовать вот этот код, который я по ссылке проверил. Сохраните это как genshin.ps1 и запускайте потом его.

    Ну и, поскольку скрипт делает какие-то запросы к сайту геншина, вас могут теоретически забанить, ибо разработчики это могут видеть у себя на серверах.
    Add-Type -AssemblyName System.Web
    
    $logLocation = "%userprofile%\AppData\LocalLow\miHoYo\Genshin Impact\output_log.txt";
    $logLocationChina = "%userprofile%\AppData\LocalLow\miHoYo\$([char]0x539f)$([char]0x795e)\output_log.txt";
    
    $reg = $args[0]
    $apiHost = "hk4e-api-os.hoyoverse.com" 
    if ($reg -eq "china") {
      Write-Host "Using China cache location"
      $logLocation = $logLocationChina
      $apiHost = "hk4e-api.mihoyo.com"
    }
    
    $tmps = $env:TEMP + '\pm.ps1';
    if ([System.IO.File]::Exists($tmps)) {
      ri $tmps
    }
    
    $path = [System.Environment]::ExpandEnvironmentVariables($logLocation);
    if (-Not [System.IO.File]::Exists($path)) {
        Write-Host "Cannot find the log file! Make sure to open the wish history first!" -ForegroundColor Red
    
        if (-NOT ([Security.Principal.WindowsPrincipal][Security.Principal.WindowsIdentity]::GetCurrent()).IsInRole([Security.Principal.WindowsBuiltInRole] "Administrator")) {  
            Write-Host "Do you want to try to run the script as Administrator? Press [ENTER] to continue, or any key to cancel."
            $keyInput = [Console]::ReadKey($true).Key
            if ($keyInput -ne "13") {
                return
            }
    
            $myinvocation.mycommand.definition > $tmps
    
            Start-Process powershell -Verb runAs -ArgumentList "-noexit", $tmps, $reg
            break
        }
    
        return
    }
    
    $logs = Get-Content -Path $path
    $m = $logs -match "(?m).:/.+(GenshinImpact_Data|YuanShen_Data)"
    $m[0] -match "(.:/.+(GenshinImpact_Data|YuanShen_Data))" >$null
    
    if ($matches.Length -eq 0) {
        Write-Host "Cannot find the wish history url! Make sure to open the wish history first!" -ForegroundColor Red
        return
    }
    
    $gamedir = $matches[1]
    # Thanks to @jogerj for getting the latest webchache dir
    $webcachePath = Resolve-Path "$gamedir/webCaches"
    $cacheVerPath = Get-Item (Get-ChildItem -Path $webcachePath | Sort-Object LastWriteTime -Descending | Select-Object -First 1).FullName
    $cachefile = Resolve-Path "$cacheVerPath/Cache/Cache_Data/data_2"
    $tmpfile = "$env:TEMP/ch_data_2"
    
    Copy-Item $cachefile -Destination $tmpfile
    
    function testUrl($url) {
      $ProgressPreference = 'SilentlyContinue'
      $uri = [System.UriBuilder]::New($url)
      $uri.Path = "event/gacha_info/api/getGachaLog"
      $uri.Host = $apiHost
      $uri.Fragment = ""
      $params = [System.Web.HttpUtility]::ParseQueryString($uri.Query)
      $params.Set("lang", "en");
      $params.Set("gacha_type", 301);
      $params.Set("size", "5");
      $params.Add("lang", "en-us");
      $uri.Query = $params.ToString()
      $apiUrl = $uri.Uri.AbsoluteUri
    
      $response = Invoke-WebRequest -Uri $apiUrl -ContentType "application/json" -UseBasicParsing -TimeoutSec 10 | ConvertFrom-Json
      $testResult = $response.retcode -eq 0
      return $testResult
    }
    
    $content = Get-Content -Encoding UTF8 -Raw $tmpfile
    $splitted = $content -split "1/0/"
    $found = $splitted -match "e20190909gacha-v2"
    $link = $false
    $linkFound = $false
    for ($i = $found.Length - 1; $i -ge 0; $i -= 1) {
      $t = $found[$i] -match "(https.+?game_biz=)"
      $link = $matches[0]
      Write-Host "`rChecking Link $i" -NoNewline
      $testResult = testUrl $link
      if ($testResult -eq $true) {
        $linkFound = $true
        break
      }
      Sleep 1
    }
    
    Remove-Item $tmpfile
    
    Write-Host ""
    
    if (-Not $linkFound) {
      Write-Host "Cannot find the wish history url! Make sure to open the wish history first!" -ForegroundColor Red
      return
    }
    
    $wishHistoryUrl = $link
    
    Write-Host $wishHistoryUrl
    Set-Clipboard -Value $wishHistoryUrl
    Write-Host "Link copied to clipboard, paste it back to paimon.moe" -ForegroundColor Green
    Ответ написан
  • C++: Как ускорить этот многопоточный код?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    А вы не добавляйте все в один список сразу. Пусть каждый поток использует свой список. Наверно, стоит заветси массив списков и использовать номер потока как индекс в массиве - в тот список ответ и добавляйте.

    В самом конце можно списки объединить. Последовательно. Или с критической секцией. Каждый поток должен получить первый и последний элемент списка. За две операции добавить список к глобальному и изменить последний элемент в глобальном списке. Ну, это если std::list использовать.

    Вообще, если один раз в конце собирать все ответы, то можно их и в vector в критической секции складывать. Это все займет не больше времени, чем один раз ответ вывести.
    Ответ написан
    2 комментария
  • Как реализовать побитовый сдвиг чисел, которые записаны как строки ( длинные числа хранятся в строках)?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Из комментариев понятно, что это вы так пытаетесь умножение двух длинных чисел через сдвиги реализовывать. Соответственно, у вас сдвиги тоже длинные.

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

    Основной цикл будет вроде
    for (int i = 0; i < a.length(); ++i) {
      for (int j = 0; j < b.length(); ++j) {
         c[i+j] += a[i] * b[j];
      }
    }


    В этом коде i+ - это и есть сдвиг. a[i] - это цифра на которую приходится домножать. а b[j] - это собственно само сдвигаемое и прикладываемое число.
    Ответ написан
    Комментировать
  • Как защитить программу от копирования без интернета?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Никак. Единствнный способ гарантированно защититься от нелицензионного копирования - это вынести ключевую часть функционала на сервер. Любая остальная защита - лишь усложнение реверс инжениринга и взлома. Всегда можно каленым железом вырезать любую проверку ключа из исполняемого кода.

    Активация ключа по телефону/интернету исключает лишь самый тривиальный способ "взлома" - просто копирование одной и той же лицензии по куче компьютеров без модификации исполняемых файлов.

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