Проверить являются ли значения элементов массива суммой некоторых элементов из двух других массивов

@driypeen · Регистрация: 05.10.2020

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

Задача: Заданы два массива A[1..N] и B[1..M]. Так же задана последовательность чисел C1, C2, ..., CK. Для каждого Ci выведите YES если его можно представить как сумму элемента массива A и элемента массива B, и NO в противном случае. Все элементы массивов и последовательностей во входном файле от -10^8 до 10^8.
В каждом массиве (последовательности) от 0 до 10000 элементов.
ограничение времени на тест: 1 сек.
ограничение памяти на тест: 65536 KB.
Построение массива со всеми возможными суммами - вылет по памяти. Вывод - делать перебор, не строя новых массивов. Пробовал отсортировать сначала четные, зачем нечетные - не укладываюсь. Обычный код двумя вложенными циклами, очевидно, тоже не катит по времени. Тема задачи - сортировка. Поэтому сначала отсортировал два исходных массива, и во вложенном цикле шел, пока a[i] + b[j] <= x. Все равно долго. Подскажите алгоритм, пожалуйста.

@_Ivana · 18.10.2020, 19:57

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

Тема задачи - сортировка.

Именно

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
#include <iostream>
#include <cstdlib>
#include <ctime>
#include<bits/stdc++.h> 
 
const int S = 10000, Z = 100000000;
int N, M, K, A[S], B[S], C[S];
 
int ge(int x, int l, int r) {
    int c = (l+r)/2;
    return l==r ? ( B[r]<x ? r+1 : B[r]==x ? -1 : r ) : B[c]<x ? ge(x, c+1, r) : ge(x, l, c);
}
 
bool f(int x, int l, int r, int p, int q) {
    if (l>r || p>q) return 0;
    int c=(l+r)/2, t = ge(x-A[c], p, q);
    return t<0 || f(x, l, c-1, t, q) || f(x, c+1, r, p, t-1) ;
}
 
int main() {
    std::cin >> N >> M >> K;
    srand((unsigned) time(0));
    for (int i=0; i<N; i++) A[i] = rand() % (2*Z) - Z;
    for (int i=0; i<M; i++) B[i] = rand() % (2*Z) - Z;
    for (int i=0; i<K; i++) C[i] = rand() % (2*Z) - Z;
    std::sort(A, A+N);
    std::sort(B, B+M);
    for (int i=0; i<K; i++) std::cout << (f(C[i], 0, N-1, 0, M-1) ? "YES" : "NO") << "\n";
}

@Vladimir. · 19.10.2020, 00:46

Не по теме:

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

Именно

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

IGPIGP · 19.10.2020, 00:50

Сообщение от Vladimir.

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

а зачем пишете тогда,если лень? Уверенность откуда? Чем диктуется?

@Vladimir. · 19.10.2020, 01:09

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

Уверенность откуда? Чем диктуется?

потому что вот это return l==r ? ( B[r]<x ? r+1 : B[r]==x ? -1 : r ) : B[c]<x ? ge(x, c+1, r) : ge(x, l, c); очень похоже на рекурсивную реализацию двух итераторов. Вы уже предлагали не функциональное решение пару страниц назад - оно имело лучший результат, но, примерно, в 4 секунды.

Не по теме:

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

а зачем пишете тогда,если лень?

Затем, что перед выдачей решения, можно было ge и f поменять на что-то вразумительное или хотя бы в двух словах прокомментировать код.

IGPIGP · 19.10.2020, 02:02

Сообщение от Vladimir.

Затем, что перед выдачей решения, можно было ge и f поменять на что-то вразумительное или хотя бы в двух словах прокомментировать код.

Такой код комментировать - пустое занятие. Вы или читаете его или нет. Я не спорю, - это трудно читать. Но это не повод ругаться, имхо.

Не по теме:

А я за то люблю _Ivana,
Что головушка кудрява (полна извилин)

@_Ivana · 19.10.2020, 02:20

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

Чем диктуется?

Любой может скопировать кота, запустить в онлайн компиляторе, и увидеть время выполнения - полторы секунды. Для трех массивов по 10000. Чуть не укладывается, да. Но если переписать императивно без рекурсий, может и влезет в секунду. Зато кот красив и алгоритм интересен.

@Vladimir. · 19.10.2020, 02:48

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

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

Да, примерно так и сделал в перерывах на перекур. Видимо, придется посмотреть.

@Vladimir. · 19.10.2020, 03:22

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
Море в объективе kumehtar 06.07.2026 Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.	Оказывается, Unreal Engine позволяет качество на порядки выше, чем было в Lineedge Etyuhibosecyu 05.07.2026 Жаль, конечно, что я не узнал об этом, пока Lineedge существовала, а то бы Noname2331 написал, что волки превращаются в пиксельную кашу, а я бы его попросил скачать какую-нибудь бриллиантовую или Pro. . .	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .
Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .

@driypeen 0 / 0 / 0 Регистрация: 05.10.2020 Сообщений: 15

	Проверить являются ли значения элементов массива суммой некоторых элементов из двух других массивов 05.10.2020, 21:56. Показов 4380. Ответов 47 Метки нет (Все метки) Задача: Заданы два массива A[1..N] и B[1..M]. Так же задана последовательность чисел C1, C2, ..., CK. Для каждого Ci выведите YES если его можно представить как сумму элемента массива A и элемента массива B, и NO в противном случае. Все элементы массивов и последовательностей во входном файле от -10^8 до 10^8. В каждом массиве (последовательности) от 0 до 10000 элементов. ограничение времени на тест: 1 сек. ограничение памяти на тест: 65536 KB. Построение массива со всеми возможными суммами - вылет по памяти. Вывод - делать перебор, не строя новых массивов. Пробовал отсортировать сначала четные, зачем нечетные - не укладываюсь. Обычный код двумя вложенными циклами, очевидно, тоже не катит по времени. Тема задачи - сортировка. Поэтому сначала отсортировал два исходных массива, и во вложенном цикле шел, пока a[i] + b[j] <= x. Все равно долго. Подскажите алгоритм, пожалуйста. 0

@Vladimir.
	19.10.2020, 03:22
	Не по теме: был не прав, погорячился. Ожидал что-то раза в три больше. 0