Задача от яндекса на нахождение сумму случайных чисел массива

Question

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

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 &amp; 0xFFFFFFFF00000000ULL) | (X &gt;&gt; 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 &lt;&lt; &quot;Summa ravna = &quot; &lt;&lt; sum &lt;&lt; endl;
system(&quot;pause&quot;);
return 0;

}

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

Answer 1

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

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

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

5
1 2 3 3 4

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

10

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

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

Answer 2

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

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

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

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

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

Answer 3

Просто читаете, удаляете дубли и суммируете. Главное - тип 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;
    }

Answer 4

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

#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;
}