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

@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

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .

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

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

Опции темы