30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
|
||||||
1 | ||||||
Задача про водопровод25.12.2011, 22:05. Показов 3709. Ответов 22
Метки нет (Все метки)
Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (x1, y1), а вторая - в точке (x2, y2).
К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 градусов. Требуется, зная длины отрезков труб L1, L2, ..., LK и количество отрезков каждой длины C1, C2, ..., CK, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно. Ограничения: 1 <= K <= 4, 1 <= x1, y1, x2, y2, Li <= 1000, 1 <= Ci <= 10, все числа целые, время 3 с. Ввод из файла wpipe.in. В первой строке находятся числа x1, y1, x2, y2, K, затем 2K чисел: L1, L2, ..., LK, C1, C2, ..., CK. Вывод в файл wpipe.out. Вывести одно число - минимальное количество нужных отрезков труб или -1, если соединение невозможно. Примеры Ввод 1 Ввод 2 5 5 5 6 1 2 10 20 10 60 50 2 70 30 2 2 Вывод 1 Вывод 2 -1 4 моя попытка решить:
0
|
25.12.2011, 22:05 | |
Ответы с готовыми решениями:
22
Задача водопровод Задача про дату! Задача про Лестницу Задача про гостей |
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
26.12.2011, 06:23 | 2 |
нет.
Сначало ошибки в коде (см комментарии): и в двух строчках ниже тоже самое. Теперь переформулирую задачу: Есть два расстояния: abs(x1-x2) и abs(y1-y2) и есть K труб длиннами: L1, L2, ..., LK и их количество C1, C2, ..., CK Задача: можно ли набрать из заданного набора труб два расстояния - abs(x1-x2) и abs(y1-y2). Если можно, то вывести результат, в котором количество труб используемых в заданном наборе будет минимальным.
0
|
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
|
|
26.12.2011, 12:07 [ТС] | 3 |
то есть должно выполняться условие:
abs(x1-x2)+abs(y1-y2)==c[i]*l[i]+c[j]*l[j]; а как мы определим когда количество труб будет минимальным?
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
26.12.2011, 15:58 | 4 |
не обязательно. И скорее всего чаще нет, чем да.
Должно выполняться следующее условие: abs(x1-x2)= l[0]*x0 + l[1]*x1 + ... + l[k-1]*xk-1 abs(y1-y2)= l[0]*y0 + l[1]*y1 + ... + l[k-1]*yk-1 xi и yi лежат в диапазоне от 0 до c[i] Причем для любого i должно соблюдаться условие xi+yi<=c[i]
1
|
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
|
|
27.12.2011, 09:37 [ТС] | 5 |
извините за тупые вопросы, но объясните как можно это все на c++ реализовать
несовсем понимаю откуда эти x[i], y[i] брать да еще связать с c[i]
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
27.12.2011, 10:09 | 6 |
Есть например 3 трубы длинной 2
и 2 трубы длинной 17 Нужно из них набрать 2 отрезка: один длинной 19, второй длинной 4. Такие отрезки можно набрать: Первый (длинной 19) набираем так: одна труба длинной 17 и одна труба длинной 2 Второй (длинной 4) набираем так: две трубы длинной 2 Но с таким набором труб нельзя например набрать: - два отрезка длинной 19 и 6 (не хватит труб длинной 2) - два отрезка длинной 19 и 5 (из заданных труб невозможно набрать длинну 5) Попробуйте сначало понять смысл задачи, только потом попробуйте ее реализовать. Если не получится помогу.
0
|
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
|
|
27.12.2011, 13:45 [ТС] | 7 |
то есть x[i], y[i] это "нужные нам трубы"?
Добавлено через 2 часа 39 минут отрезком вы называете то что нужно найти получается?
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
27.12.2011, 14:18 | 8 |
0
|
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
|
||||||
27.12.2011, 23:08 [ТС] | 9 | |||||
как нужно учесть условие минимальности количества нужных отрезков труб
Добавлено через 1 час 29 минут
почему то проблема с выводом, то есть он неправильно выводит..
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
28.12.2011, 05:43 | 10 | |||||
Давайте попробуем рекурсией:
0
|
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
|
|
28.12.2011, 09:48 [ТС] | 11 |
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
28.12.2011, 11:55 | 12 | |||||
эти случаи описать можете? Или можете дать ссылку на тестирующую систему?
Добавлено через 22 минуты Вот так попробуйте:
0
|
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
|
|
28.12.2011, 13:43 [ТС] | 13 |
http://ipc.susu.ac.ru/workplace-4.html
Добавлено через 9 минут правда не в этой системе дело я сам вручную ввожу также как в примере то есть 5 5 5 6 1 2 10 и должно выводить -1 а она то выводит
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
28.12.2011, 13:47 | 14 |
у меня последний вариант получил AC.
Только нужно в коде поменять название файлов ввода вывода, на те которые используются в тестирующей системе.
0
|
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
|
|
28.12.2011, 17:45 [ТС] | 15 |
спасибо большое теперь действительно все работает
Добавлено через 3 часа 48 минут извините а вы не могли бы подробно разобрать процедуру rec а именно : какие аргументы она принимает за что они отвечают, ну и в общем принцип весь что откуда... преподаватель очень строго все будет проверять сказал
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
28.12.2011, 19:07 | 16 |
могу. но только если вы сами полностью поняли условие задачи (иначе это будет объяснение в никуда).
Сможете объяснить почему в тесте: 20 10 60 50 2 70 30 2 2 ответ 4 ?
0
|
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
|
|
28.12.2011, 19:15 [ТС] | 17 |
потому что из данных двух наборов мы можем собрать 4 трубы тем добравшись из точки (x1,y1) до точки (x2,y2)
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
28.12.2011, 19:24 | 18 |
ответ на 5.
а какие трубы и как используются? Чтобы понять как решается задача, самое первое - нужно понять условие. Этот тест и есть понимание условия. Я могу сейчас написать комментарии к функции rec(), но 100% что вы не поймете смысл этой функции, пока не поймете самого задания.
0
|
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
|
|
28.12.2011, 19:39 [ТС] | 19 |
трубы собираются из заданных нам отрезков соответствующих длин
то есть мы берем самую длинную трубу и примеряемся так скажем (строим горизонтальную составляющую), затем также примеряемся по вертикали, и если мы добрались до (x2,y2) то значит можно построить такой водопровод. количество труб в будем не больше c суммых всех отрезков если я правильно понимаю
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
28.12.2011, 19:56 | 20 | |||||
ладно, все понятно, вот комментарии:
0
|
28.12.2011, 19:56 | |
28.12.2011, 19:56 | |
Помогаю со студенческими работами здесь
20
Задача про зайца Задача про ракету задача про массивы Задача про пассажиров Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |