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

@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

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

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

	Проверить являются ли значения элементов массива суммой некоторых элементов из двух других массивов 05.10.2020, 21:56. Показов 4556. Ответов 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