Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Алгоритм

3.2K
29 января 2003 года
gdy
1 / / 29.01.2003
Если кто может, помогите решить задачу(на С++ или Pascal).Мучаюсь уже месяц и все-равно не получается!
Ограничение по времени: 5 секунд
Ограничение по памяти: 1000K


Вступление
- Брат мой, Магистр Ордена хочет узнать завтра о результатах наших многолетних изысканий. Он хочет видеть, ни много, ни мало, Суммирующую Машину! Даже более того: он хочет, чтобы наша Машина — всего лишь машина — продемонстрировала свое постижение Таинства Суммы настолько глубоко, насколько это возможно. Он хочет, чтобы Машина нашла каких-нибудь два числа, дающих в сумме священное число 10000!
- Тс-с-с! Но это же безумство, граничащее с кощунством! Как Машина может ВЫЧИСЛИТЬ священное число? Двадцать семь лет мы работаем над ней, и смогли только лишь научить ее отвечать на вопрос: «Больше сумма двух введенных чисел, чем 10000, или меньше?». Но разве может смертный найти два таких числа, чтобы их сумма оказалась равна 10000?
- И все же нам придется сделать это с помощью нашей Машины, пусть она и неспособна на это. Иначе у нас будут… ну, скажем так, крупные неприятности, если кипящее масло можно назвать таким словом. Впрочем, у меня есть идея. Помнишь, на той неделе мы ввели в Машину числа –7 и 13, она ответила, что их Сумма меньше 10000. Я не знаю, как это проверить, но нам ничего не остается, как доверять созданию наших рук. Что, если теперь мы возьмем число большее, чем –7 и снова запустим Машину? И будем так делать снова и снова, пока не найдем такое число, которое в сумме с 13 даст 10000! Надо только подготовить список возрастающих чисел.
- Не верю я в эту идею… Давай лучше начнем с суммы, заведомо большей, чем Священное число и будем уменьшать одно из слагаемых, так у нас больше шансов избегнуть кипяще… крупных неприятностей.
Так ни о чем и не договорившись, Братья разошлись по своим кельям. К следующему дню, каждый из них подготовил такой список чисел, который, по его мнению, мог бы их спасти… Смогут ли спасти их оба списка вместе?
Задача
Ваша программа должна определять, можно ли из двух списков целых чисел выбрать по одному числу так, чтобы в сумме они составили 10000.
Исходные данные
На взоде даны два списка - один, потом другой. Формат каждого из этих списков таков: в первой строчке записано количество Ni чисел в i-том списке, далее в Ni строчках по одному числу в строке записаны сами списки. Выполняются неравенства 1 <= Ni <= 50000, все элементы списков лежат в диапазоне от –32768 до 32767. Первый список упорядочен по возрастанию, второй – по убыванию.
Результат
На выходе следует записать YES, если из списков можно выбрать по числу, которые в сумме дадут 10000 и NO в противном случае.
Пример исходных данных
4
-175
19
19
10424
3
8951
-424
-788
Пример результата
YES
2.0K
29 января 2003 года
Veey
23 / / 10.12.2002
Задачка довольно простая.
для наглядности возьмем твой пример.
первый список из четырех элементов. назовем его А
-175
19
19
10424
второй список из трех элементов. назовем его B
8951
-424
-788
Берем первый элемент первого списка (A[1]) и складываем его с первым элемнтом второго (B[1]) списка.
-175+8951=8776 получившееся число меньше 10000
значит берем следующий элемент из первого списка (А)
19+8951=8970 < 10000
следующий элемент из А
19+8951=8970 < 10000
снова следующий элемент из А
10424+8951=19375 > 10000
Значит берем следующий элемент из списка B
10424+(-424)=10000 уррррррра пишем Yes и выходим
если в каком-нибудь из списков элементы закончатся раньше чем найдено 10000 пешем No и тоже выходим
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог