Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.69
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
#1

Задача про водопровод - C++

25.12.2011, 22:05. Просмотров 1637. Ответов 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
моя попытка решить:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <fstream>
using namespace std;
void main()
{ifstream wpipein; ofstream wpipeout;
int c[4],l[4]; int x1,y1,x2,y2,i,j,s=0,t=0,m;
int k;
wpipein.open("wpipein.txt"); wpipeout.open("wpipeout.txt");
wpipein>>x1>>y1>>x2>>y2>>k;
for (i=0; i<k; i++)
wpipein>>c[i]>>l[i];
for (i=0;i<k; i++)
for (j=0;j<k;j++)
{if ((abs(x1-x2)==s+c[i]*l[i])&&(abs(y1-y2)==t+c[j]*l[j])&&(c[k]>=c[i]+c[j]))
{s=c[i]*l[i]; t=c[j]*l[j];
if ((abs(x1-x2)%l[k]==0)&&(abs(y1-y2)%l[k]==0))
{m=abs(x1-x2)/l[k]+abs(y1-y2)/l[k];
if (m<=c[k]) wpipeout<<m; else wpipeout<<-1;
}}}}
скажите я вообще правильно рассуждаю?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.12.2011, 22:05     Задача про водопровод
Посмотрите здесь:

Задача водопровод - C++
Помогите решить олимпиадную задачу. Второй день бьюсь и никак не могу найти нормальный рабочий алгоритм

Задача про монеты - C++
Привет. Задача: По кругу расположено N монет гербами вверх и M монет гербами вниз. Обходя круг по ходу часовой стрелки, переворачивает...

задача про массивы - C++
упорядочить по убыванию положительные эл-ты массмва, сохраняя остальные эл-ты на прежних местах

Задача про Лестницу - C++
Условия формулируются так: Есть лестница высотой в n ступенек (плюс «нулевая» - площадка, где мы стоим вначале). На каждой ступеньке...

Задача про календарь - C++
Имеется задача: Два одноклассника Петя и Вася родились не ранее 1993 и не позднее 1994 года, причем, Петя старше Васи. Напишите...

Задача про фермера - C++
Фермер хочет построить на своей земле как можно больший по площади сарай. Но на его участке есть деревья и хозяйственные постройки, которые...

задача про МКАД - C++
Ребята,помогите решить задачу: Длина Московской кольцевой автомобильной дороги —109 километров. Байкер Вася стартует с нулевого километра...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2011, 19:07     Задача про водопровод #16
Цитата Сообщение от crewww Посмотреть сообщение
извините а вы не могли бы подробно разобрать процедуру rec
могу. но только если вы сами полностью поняли условие задачи (иначе это будет объяснение в никуда).
Сможете объяснить почему в тесте:
20 10 60 50 2 70 30 2 2
ответ 4
?
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
28.12.2011, 19:15  [ТС]     Задача про водопровод #17
Цитата Сообщение от valeriikozlov Посмотреть сообщение
могу. но только если вы сами полностью поняли условие задачи (иначе это будет объяснение в никуда).
Сможете объяснить почему в тесте:
20 10 60 50 2 70 30 2 2
ответ 4
?
потому что из данных двух наборов мы можем собрать 4 трубы тем добравшись из точки (x1,y1) до точки (x2,y2)
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2011, 19:24     Задача про водопровод #18
Цитата Сообщение от crewww Посмотреть сообщение
потому что из данных двух наборов мы можем собрать 4 трубы тем добравшись из точки (x1,y1) до точки (x2,y2)
ответ на 5.
а какие трубы и как используются?
Чтобы понять как решается задача, самое первое - нужно понять условие. Этот тест и есть понимание условия. Я могу сейчас написать комментарии к функции rec(), но 100% что вы не поймете смысл этой функции, пока не поймете самого задания.
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
28.12.2011, 19:39  [ТС]     Задача про водопровод #19
Цитата Сообщение от valeriikozlov Посмотреть сообщение
ответ на 5.
а какие трубы и как используются?
Чтобы понять как решается задача, самое первое - нужно понять условие. Этот тест и есть понимание условия. Я могу сейчас написать комментарии к функции rec(), но 100% что вы не поймете смысл этой функции, пока не поймете самого задания.
трубы собираются из заданных нам отрезков соответствующих длин
то есть мы берем самую длинную трубу и примеряемся так скажем (строим горизонтальную составляющую), затем также примеряемся по вертикали, и если мы добрались до (x2,y2) то значит можно построить такой водопровод. количество труб в будем не больше c суммых всех отрезков если я правильно понимаю
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2011, 19:56     Задача про водопровод #20
Цитата Сообщение от crewww Посмотреть сообщение
трубы собираются из заданных нам отрезков соответствующих длин
то есть мы берем самую длинную трубу и примеряемся так скажем (строим горизонтальную составляющую), затем также примеряемся по вертикали, и если мы добрались до (x2,y2) то значит можно построить такой водопровод. количество труб в будем не больше c суммых всех отрезков если я правильно понимаю
ладно, все понятно, вот комментарии:
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
void rec(int sum, int fl, int pred, int col)// sum - сумма уже набранной длины (для первого или для второго отрезка), 
//fl==0 если набираем длину для первого отрезка, fl==1 если набираем длину для второго отрезка
// индекс труб, которые перебираем на данном вызове rec()
// col - количество труб, которые уже использовали для достижения текущего значения
{
        
        if(fl==1)// если набираем вторую длину
        {
                if(sum==y1)// если вторую длину набрали
                {
                        if(res==-1)// если результата еще не было
                                res=col;// то результат равен col
                        else// если результат уже был
                        {
                                if(res>col)// если полученное значение меньше записанного результата
                                        res=col;// то результат равен этому значению
                        }
                        return;// возврат из функции
                }
                if(pred==k)// если достигли конца массива струбами
                        return;// возврат из функции
                int i;
                for(i=0; i<=c[pred]; i++)// перебираем трубы с текущим индексом (pred)
                {
 
                        rec(sum+i*l[pred], fl, pred+1, col+i);// то прибавляем их длину
                                                if(i!=0)
                                                        rec(sum-i*l[pred], fl, pred+1, col+i);// то убавляем их длину
                }
        }
        else// если набираем первую длину
        {
                if(sum==x1)// если первую длину набрали
                {
                        rec(0, 1, 0, col);// начинаем набирать вторую длину
                }
                else
                {
                        if(pred==k)// если достигли конца массива струбами
                                return;// возврат из функции
                        int i, tmp=c[pred];
                        for(i=0; i<=tmp; i++)// перебираем трубы с текущим индексом (pred)
                        {
                                c[pred]=tmp-i;// убавляем значение задействованных труб
                                rec(sum+i*l[pred], fl, pred+1, col+i);// то прибавляем их длину
                                                                if(i!=0)
                                                                        rec(sum-i*l[pred], fl, pred+1, col+i);/ то убавляем их длину
                                c[pred]=tmp;// в конце восстанавливаем значение
                        }
                }
        }
 
}
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
28.12.2011, 20:43  [ТС]     Задача про водопровод #21
Цитата Сообщение от valeriikozlov Посмотреть сообщение
ладно, все понятно, вот комментарии:
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
void rec(int sum, int fl, int pred, int col)// sum - сумма уже набранной длины (для первого или для второго отрезка), 
//fl==0 если набираем длину для первого отрезка, fl==1 если набираем длину для второго отрезка
// индекс труб, которые перебираем на данном вызове rec()
// col - количество труб, которые уже использовали для достижения текущего значения
{
        
        if(fl==1)// если набираем вторую длину
        {
                if(sum==y1)// если вторую длину набрали
                {
                        if(res==-1)// если результата еще не было
                                res=col;// то результат равен col
                        else// если результат уже был
                        {
                                if(res>col)// если полученное значение меньше записанного результата
                                        res=col;// то результат равен этому значению
                        }
                        return;// возврат из функции
                }
                if(pred==k)// если достигли конца массива струбами
                        return;// возврат из функции
                int i;
                for(i=0; i<=c[pred]; i++)// перебираем трубы с текущим индексом (pred)
                {
 
                        rec(sum+i*l[pred], fl, pred+1, col+i);// то прибавляем их длину
                                                if(i!=0)
                                                        rec(sum-i*l[pred], fl, pred+1, col+i);// то убавляем их длину
                }
        }
        else// если набираем первую длину
        {
                if(sum==x1)// если первую длину набрали
                {
                        rec(0, 1, 0, col);// начинаем набирать вторую длину
                }
                else
                {
                        if(pred==k)// если достигли конца массива струбами
                                return;// возврат из функции
                        int i, tmp=c[pred];
                        for(i=0; i<=tmp; i++)// перебираем трубы с текущим индексом (pred)
                        {
                                c[pred]=tmp-i;// убавляем значение задействованных труб
                                rec(sum+i*l[pred], fl, pred+1, col+i);// то прибавляем их длину
                                                                if(i!=0)
                                                                        rec(sum-i*l[pred], fl, pred+1, col+i);/ то убавляем их длину
                                c[pred]=tmp;// в конце восстанавливаем значение
                        }
                }
        }
 
}
спасибо
могли бы вы пояснить последний момент по поводу return; как пояснить смысл этого оператора? боюсь меня могут спросить об этом, ведь нам не показывали что можно в процедуре использовать данный оператор

Добавлено через 34 минуты
и еще вопрос pred - это индекс труб которые уже использовали для достижения текущего значения
тогда fl - переменная определяющая какую трубу мы набираем в данный момент
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2011, 05:50     Задача про водопровод #22
Цитата Сообщение от crewww Посмотреть сообщение
могли бы вы пояснить последний момент по поводу return; как пояснить смысл этого оператора?
этот оператор не дает выполняться остальному коду в функции, и возвращает нас в точку, откуда функция была вызвана.

Цитата Сообщение от crewww Посмотреть сообщение
и еще вопрос pred - это индекс труб которые уже использовали для достижения текущего значения
тогда fl - переменная определяющая какую трубу мы набираем в данный момент
pred - это индекс труб которые сейчас используем для достижения текущего значения
Да, fl - переменная определяющая какую трубу мы набираем в данный момент
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2011, 06:15     Задача про водопровод
Еще ссылки по теме:

Задача про рюкзак - C++
Всем привет! Есть программа, которая решает задачу про рюкзак. Когда у меня количество &quot;предметов&quot; 5 или 10, то все работает хорошо....

Задача про банку - C++
Вася живет в стране Осьляндии, где, как всем известно, люди хранят деньги в банках. На совершеннолетие родители подарили Васе новую чистую...

Задача про год - C++
Есть такая задача. Дано число k (от 1 до 365). присвоить значение n (от 0 до 6) в зависимости от того, на какой день недели приходиться...

Задача про гостей - C++
Задача: представьте, что вы намерены пригласить к себе шестерых гостей, но за вашим столом могут поместиться всего лишь 4 человека....

Задача про синусоиду - C++
Велосипедист Павлуша выехал на широкую дорогу. Но ехать иначе, чем по закону синусоиды, ему никак не удавалось. Юный спортсмен стартовал в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
29.12.2011, 06:15  [ТС]     Задача про водопровод #23
огромное спасибо за помощь
Yandex
Объявления
29.12.2011, 06:15     Задача про водопровод
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru