1

Пытаюсь решить данную задачу от яндекса (см. ниже)

P.S Я видел данный пост, но к сожалению ответа на свои вопросы я не нашёл. введите сюда описание изображения

Вопросы которые возникли у меня:

  1. Я не уверен, что правильно понял суть задачи, я ее понял так, что следует использовать ГСЧ для определения размера массива и и заполнения его случайными значениями, после чего следует вывести сумму случайных элементов массива, но правильно ли я понял суть задания?
  2. Как можно проконтролировать ограничение ресурсов ? (В моём случае в Visual Studio 2019)

Мой незавершенный код

#include <iostream>
#include <random>
#include <ctime>
#include <iomanip>
using namespace std;


class Random /*fold00*/
{
public:
    typedef int RandomValue;
    Random& operator = (int seed) { X = seed; return *this; }
    Random(int seed = 1) :X(seed) {};
    int operator()(int seed = 0)
    {
        const int MM = 2147483647;
        const int AA = 48271;
        const int QQ = 44488;
        const int RR = 3399;
        if (seed != 0) X = seed;
        X = AA * (X % QQ) - RR * (X / QQ);
        if (X < 0) X += MM;
        return X - 1;
    }
    // Не включая max
    int operator()(int min, int max)
    {
        return (*this)() % (max - min) + min;
    }
private:
    int X;
};

class Random64
{
    typedef unsigned long long uint64;
public:
    typedef uint64 RandomValue;
    Random64& operator = (uint64 seed) { X = seed; return *this; }
    Random64(uint64 seed = 0) :X(seed) {};
    uint64 operator()(uint64 seed = uint64(-1))
    {
        const uint64 a = 3202034522624059733ULL;
        const uint64 c = 1ULL;

        if (seed != uint64(-1)) X = seed;
        uint64 Y = a * X + c;
        X = a * Y + c;
        Y = (Y & 0xFFFFFFFF00000000ULL) | (X >> 32);
        return Y;
    }
    // Не включая max
    uint64 operator()(uint64 min, uint64 max)
    {
        return (*this)() % (max - min) + min;
    }
private:
    uint64 X;
};



int main()
{
    Random64 r(time(0));
    typedef long long int llint;
    int sum = 0;
    llint array_size = r(0, 100000);
    llint* mass_ptr = new llint[array_size];
    for (llint i = 0; i < array_size; i++)
    {
        mass_ptr[i] = r(0, 1000000000);
        cout << "array [" << i << "] = " << mass_ptr[i] << endl;
        if (i == 5)
        {
            sum = sum + mass_ptr[1] + mass_ptr[r(1, 3)];
        }
    }
 
    cout << "Summa ravna = " << sum << endl;
    system("pause");
    return 0;
}

P.S Я знаю что программа на данном этапе не выполняет даже своей сути (то как я понял) однако это некий прототип UPD: и как можно сократить этот алгоритм?

6
  • 1
    "я ее понял так, что следует использовать ГСЧ для определения размера массива и и заполнения его случайными значениями" - там же прямо написано, что массив подается на вход 18 дек 2019 в 9:10
  • @user7860670 Да, я вижу, но так как нам неизвестно какое число будет подаваться, разве это не значит, что оно может быть любым? (если удовлетворяет условию)
    – David
    18 дек 2019 в 9:11
  • 1
    Конечно оно может быть любым, и программа должна корректно обрабатывать любое число, удовлетворяющее условиям. 18 дек 2019 в 9:14
  • 1
    Вы бы эта... заголовок-то поправили. Случайные и различные (уникальные) - как бы не совсем одно и то же...
    – Akina
    18 дек 2019 в 9:18
  • @Akina а в чём различие?
    – David
    18 дек 2019 в 9:19

4 ответа 4

4

Отвечаю на ваши вопросы.

1 В задаче ЯСНО сказано, что входной файл, input.txt содержит входные данные. Ваша программа должна считать эти данные и вывести ответ в выходной файл. Ничего генерировать самому не нужно.

Например, во входном файле может быть такое:

5
1 2 3 3 4

То есть ваша программа считывает число 5, потом должна считать 5 чисел. Потом решить задачу и вывести ответ в файл output.txt:

10

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

2 Контроль ресурсов нужно выполнять самостоятельно. Завести массив на 100'000 элементов не так дорого по памяти, можете посчитать сами. Вы вполне укладываетесь в отведённые 256 Мб. Что касается времени работы, вам нужно попробовать погонять свой программу на компьютере на больших тестах, сделанных самостоятельно. Тогда поймёте, укладываетесь или нет. Когда вы отправите свою задачу им, они прогонят её на своих автоматических тестах (подставляя вашей программе разные файлы input.txt) и будут проверять, что она уложилась в отведённое время и выдала правильный ответ на каждом входном файле. То есть никаких специальных проверок в вашей программе на время и память делать не нужно.

9
  • ну я решил с помощью рандома и сделать тест при худшем условии, и при взятие максимумов удовлетворяющих условию, программа выполняется далеко не 2 секунды, а где - то полторы минуты, возможно я что - то не так понимаю
    – David
    18 дек 2019 в 9:18
  • @David , нужно составлять тесты отдельно, а не в самой программе, которая решает задачу. Ваша программа должна делать именно то, что написано: считывать из файла и выводить в файл. Потому что, во-первых, может быть вы долго именно генерируете, а, во-вторых, вас не возьмут в Яндекс, если увидят как вы поняли задачу :) Ну и потом, может у вас алгоритм решения неудачный?
    – Zealint
    18 дек 2019 в 9:21
  • ахах, согласен что не возьмут, я пока и не рвусь, просто данная задача поставила в ступор и уж очень хочется ее досконально разобрать
    – David
    18 дек 2019 в 9:23
  • @David , если действительно хочется, делайте что я вам говорю. Пишите код, которые делает три действия: (1) считывает данные из файла как надо. (2) вычисляет то, что требуется, (3) выводит ответ в другой файл. И ВСЁ! Когда сделаете, объясню что дальше.
    – Zealint
    18 дек 2019 в 9:24
  • а как именно проводить данные тесты, чтобы проверить соответствие по ограничениям?
    – David
    18 дек 2019 в 9:24
3

По просьбам трудящихся :)

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

int main()
{
    set<int> a; int n;
    cin >> n;
    for(int x, i = 0; i < n; ++i) { cin >> x; a.insert(x); }
    long long sum = 0;
    for(int x: a) sum = sum + x;
    cout << sum << endl;
}

Второй код - с вектором имени Mikhailo. Третий - его же код, но с вектором intов - нет смысла хранить исходные данные как long long, раз они не превышают миллиард. Ну, и последний вариант - мой, но set заменен на unordered_set. Итак, перейдем к результатам.

Я рассмотрел 4 варианта решения задачи -

  1. vector<long long>
  2. vector<int>
  3. set<int>
  4. unordered_set<int>

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

Все 4 программы отсчитали суммы одинаково.

Время засекал полностью - от начала запуска программы операционкой до полного выхода, результаты приведены в миллисекундах по 40 запускам. Память в kB- по результатам Diagnostic tools из VC++

5 и 6 - 3 и 4 с добавлением Alexey Nikolaev в комментариях:

    for(int x, i = 0; i < n; ++i) { 
        cin >> x;  
        if (a.insert(x).second) sum += x; }

Итого:

 Метод         1        2        3        4        5       6

 Время     77+-3    77+-7   102+-8    91+-6    98+-5   88+-6

Память       786      395     1567     1966

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

Могут быть и другие варианты решения, но суть та же - данные уже подготовлены за вас. Ваше дело - просто считать их.

8
  • я решил делать с помощью рандома, чтобы учитывать затрачиваемые значения программы при худшем случае. (Ведь можно подать на вход значение не однозначное и не двузначное, а например взять максимум, удовлетворяющий условию, после заполнить массив при худшем случае)
    – David
    18 дек 2019 в 9:16
  • @Harry, Ваш вариант с set и unordered_set можно немного ускорить, удалив второй прогон для суммирования и считать сумму в первом цикле, проверяя, что вернул метод insert. 19 дек 2019 в 3:50
  • @AlexeyNikolaev Улучшение имеется (см. дополненный ответ), но вектор все равно не обгоняет...
    – Harry
    19 дек 2019 в 7:40
  • @Harry, можно добавить ещё один хинт для ускорения, причем во все реализациях - оптимизировать работу потоков ввода-вывода путём развязывания (подглядел в курсе яндекса на coursera) добавить это в начало каждой реализации: std::ios::sync_with_stdio(false); std::cin.tie(nullptr); 19 дек 2019 в 8:24
  • @AlexeyNikolaev А вот это - готов спорить - не даст (по крайней мере в VC++) ничего. Но сейчас попробую на одном из вариантов.
    – Harry
    19 дек 2019 в 9:37
2

Просто читаете, удаляете дубли и суммируете. Главное - тип long long, чтобы все поместилось.

А по памяти - как оцента - у нас только вектор, не более 100000 элементов по 8 байт - итого порядка 800000 байт, меньше 1 мегабайта.

int main() {
    vector<long long> a;
    size_t n;
    cin >> n;
    a.reserve(n);
    copy_n(istream_iterator<long long>(cin), n, back_inserter(a));
    sort(a.begin(),a.end());
    cout<<accumulate(a.begin(),unique(a.begin(),a.end()),0ll)<<endl;
    }
5
  • Скорее всего Ваше решение не пройдет по времени на больших массивах, так как sort - очень затратная операция и в среднем её сложность N*log2(N), а в худших случаях N^2 плюс ещё два линейных прогона. Не с проста дано такое ограничение по памяти, подозреваю, что необходимо аккуратно использовать unordered_set для решения задачи. 18 дек 2019 в 10:52
  • @AlexeyNikolaev sort из стандартной библиотеки гарантирует O(NlogN), что для 100000 - очень быстро. А вектор по памяти точно меньше unordered_set, который по самой своей природе хэширования должен иметь лишнее пустое место. Жалко, с нами нет @Harry - тот бы тут же проверил экспериментально :)
    – Mikhajlo
    18 дек 2019 в 11:20
  • @Harry Не хотите попробовать разрешить наш спор экспериментально?..
    – Mikhajlo
    18 дек 2019 в 11:46
  • @Alexey Nikolaev , sort из STL действительно выполнена так, чтобы гарантировать линейно-логарифмическую сложность. Достигается это путём комбинирования нескольких алгоритмов в один. Если на пальцах: там qsort, который имеет отсечку по числу операций на каждом шаге, если это число превысило удвоенный логарифм числа элементов, вызывается другой алгоритм с гарантированным временем выполнения (heap-sort или merge-sort). Но это упрощённо я сказал.
    – Zealint
    18 дек 2019 в 12:18
  • Ну, если @AlexeyNikolaev не напишет что-то свое - ваше решение пока наилучшее... См. мой ответ.
    – Harry
    18 дек 2019 в 13:36
2

Выложу и свой костыль) на мой взгляд сорт и вектор самое быстрое решение.

#include <iostream>
#include <string>
#include <fstream>
#include <iterator>
#include <random>
#include <functional>
#include <vector>
#include <fstream>
#include <filesystem>
#include <numeric>


class timeCounter {
#ifdef __linux__
public:
    timeCounter() : start(std::chrono::high_resolution_clock().now()),
        end(std::chrono::high_resolution_clock().now()) {};
    ~timeCounter() {
        end = std::chrono::high_resolution_clock().now();
        auto d = end - start;
        std::cout << std::chrono::duration<double, std::ratio_multiply<std::chrono::seconds::period, std::milli>>(d).count() << " ms" << std::endl;
    }

private:
    std::chrono::time_point<std::chrono::_V2::system_clock> start, end;
#endif // __linux__

#ifdef _WIN32
public:
    timeCounter() : start(std::chrono::steady_clock::now()) {}
    ~timeCounter() {
        auto end{ std::chrono::steady_clock::now() };
        auto d = end - start;
        std::cout << std::chrono::duration<double, std::ratio_multiply<std::chrono::seconds::period, std::milli>>(d).count() << " ms" << std::endl;
    }

private:
    std::chrono::time_point<std::chrono::steady_clock> start;
#endif // _WIN32

};


std::filesystem::path GetNewCurrentFilePath(std::string file_name) {
    auto path{ std::filesystem::current_path() };
    path = path / file_name;
    if (std::filesystem::exists(path)) {
        std::filesystem::remove(path);
    }

    return path;
}


std::filesystem::path GetFilePath(std::string file_name) {
    auto path{ std::filesystem::current_path() };
    path = path / file_name;
    if (!std::filesystem::exists(path)) {
        throw std::runtime_error{ "Error : File not found! : " + path.string() };
    }

    return path;
}


void GenData(std::string file_name, std::size_t size, std::size_t low_bord, std::size_t high_bord) {
    timeCounter tc{};
    auto path{ GetNewCurrentFilePath(file_name) };

    std::ofstream out_stream(path, std::ios::out);
    if (!out_stream.is_open()) {
        throw std::runtime_error{ "Error open file" };
    }

    std::ostream_iterator<uint64_t>{out_stream, "\n"} = size;

    std::ostream_iterator<uint64_t> out_it(out_stream, " ");

    std::vector<uint64_t> v(size);
    std::mt19937_64 generator(std::random_device{}());
    std::uniform_int_distribution<> uid(low_bord, high_bord);
    auto gen{ std::bind(uid, generator) };
    std::generate(std::begin(v), std::end(v), gen);

    std::copy(std::begin(v), std::end(v), out_it);

    out_stream.close();
}


uint64_t Processing(std::string file_name) {
    timeCounter tc{};

    uint64_t ret{};

    auto path{ GetFilePath(file_name) };

    std::ifstream in_stream(path, std::ios::in | std::ifstream::binary);
    if (!in_stream.is_open()) {
        throw std::runtime_error{ "Error open file" };
    }
    std::istream_iterator<uint64_t> in_iter{ in_stream };
    std::istream_iterator<uint64_t> in_end{};

    uint64_t size{*in_iter };

    std::vector<uint64_t> v{};
    v.reserve(size);

    std::copy(++in_iter, in_end, std::back_inserter(v));

    if (std::is_sorted(std::begin(v), std::end(v))) {
        std::cout << "sorted" << std::endl;
    }

    std::cout << "size : " << v.size() << std::endl;

    std::sort(std::begin(v), std::end(v));

    if (std::is_sorted(std::begin(v), std::end(v))) {
        std::cout << "sorted" << std::endl;
    }

    auto last = std::unique(v.begin(), v.end());
    v.erase(last, v.end());

    std::cout << "size after erase: " << v.size() << std::endl;
    if (std::is_sorted(std::begin(v), std::end(v))) {
        std::cout << "sorted" << std::endl;
    }

    ret = std::accumulate(std::begin(v), std::end(v), 0);

    return ret;
}


int main() {

    std::string file_name("data");
    std::size_t size{ 100'000 };
    std::size_t low_bor{ 0 };
    std::size_t high_bord{ 1'000'000'000 };

    GenData(file_name, size, low_bor, high_bord);

    std::cout << Processing(file_name) << std::endl;

    return 0;
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.