Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
azbest
41 / 41 / 8
Регистрация: 12.03.2013
Сообщений: 148
#1

Разработать программу для определения объема оставшейся воды в теле, если оно полностью погружается в воду основанием вниз, а затем поднимается. - C++

09.02.2014, 00:10. Просмотров 286. Ответов 3
Метки нет (Все метки)

Есть олимпиадная задача. Помогите пожалуйста с алгоритмом если кто знает.

Сплошное тело составлено из параллелепипедов с основанием 1 x 1, установленных на прямоугольное основание размером МхN. Высоты параллелепипедов заданы матрицей A (MхN). Элементы матрицы — натуральные числа. Нижнее основание тела горизонтально.
Разработать программу для определения объема оставшейся воды в теле, если оно полностью погружается в воду основанием вниз, а затем поднимается.

Входные данные. Текстовые файлы, которые в первой строке содержит значения M и N. Затем построчно задана матрица A. В каждой строке значения разделены одним или несколькими пробелами. Данные в файле заданы корректно, например:
3 6
2 2 2 1 2 1
2 1 2 2 1 2
2 2 2 1 2 1

Ответ:
2
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.02.2014, 00:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Разработать программу для определения объема оставшейся воды в теле, если оно полностью погружается в воду основанием вниз, а затем поднимается. (C++):

Составить программу для определения площади трапеции с высотой h, основанием а и противолежащей стороной b - PascalABC.NET
помогите пожалуйста

Составить программу для определения полной площади, объема и массы детали - Pascal
Cоставить программу для определения полной площади, объема и массы детали. ...

Разработать программу для определения максимального массива - C#
Разработать программу для определения максимального массива. Только чтоб попроще как-то выглядела) Заранее спасибо!!!

Разработать программу для определения кратчайшего слова в тексте - C++
Разработать программу для определения кратчайшего слова в тексте.

Разработать программу для определения суммы бесконечного ряда с точностью E - Pascal
Разработать программу для определения суммы бесконечного ряда с точностью E.Вывести значение суммы и число членов ряда,вошедших в сумму. ...

Разработать алгоритм и программу для определения кратчайшего слова в тексте - C++
Разработать алгоритм и программу для определения кратчайшего слова в тексте

3
Eldies
90 / 81 / 28
Регистрация: 06.02.2014
Сообщений: 120
09.02.2014, 01:18 #2
Можно как бы смоделировать процесс утекания воды.
Завести еще одну матрицу такого же размера, в каждую ячейку, кроме крайних поместить максимальное значение из первой матрицы. В крайние ячейки - то, что находится в соответствующей ячейке первой матрицы.

и делать
C++
1
2
3
4
5
6
7
8
9
10
11
12
for(int i = 1; i < N-1; ++i)
    for(int j = 1; j < M-1; ++j)
    {
        int minNeighbour = INT_MAX;
        minNeighbour = min(minNeighbour, matrix2[i][j+1]);
        minNeighbour = min(minNeighbour, matrix2[i][j-1]);
        minNeighbour = min(minNeighbour, matrix2[i+1][j]);
        minNeighbour = min(minNeighbour, matrix2[i-1][j]);
 
        if (minNeighbour < matrix2[i][j] && matrix2[i][j] > matrix1[i][j])
            matrix2[i][j] = max(matrix1[i][j], minNeighbour);
    }
пока что-то меняется.

Потом просто сложить разности соответствующих ячеек из двух матриц - это и будет объем воды.
0
azbest
41 / 41 / 8
Регистрация: 12.03.2013
Сообщений: 148
09.02.2014, 02:07  [ТС] #3
Ответ хороший, что называется "в лоб". Но думаю что если задача олимпиадная, то такой вариант не пройдет тест по скорости. Если числа M и N будут порядка 10^5.
0
Eldies
90 / 81 / 28
Регистрация: 06.02.2014
Сообщений: 120
09.02.2014, 02:27 #4
Можно и по-другому.
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
54
55
56
int solve(int N, int M, std::vector<std::vector<int>>& matrix1)
{
    int maxValue = 0;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < M; ++j)
            maxValue = max(maxValue, matrix1[i][j]);
 
    std::vector<std::vector<int>> matrix2(N);
    for(int i=0;i<N;++i)
        matrix2[i].resize(M,maxValue);
 
    std::set<std::pair<int,int>> pset;
 
    for(int i=0;i<N;++i)
    {
        pset.insert(std::pair<int,int>(i,0));
        pset.insert(std::pair<int,int>(i,M-1));
    }
    for(int j=0;j<M;++j)
    {
        pset.insert(std::pair<int,int>(0,j));
        pset.insert(std::pair<int,int>(N-1,j));
    }
 
    while(pset.size() > 0)
    {
        std::pair<int,int> point = *pset.begin();
        pset.erase(pset.begin());
        int i = point.first;
        int j = point.second;
 
        int minNeighbour = INT_MAX;
        if (j == 0 || j == M-1 || i == 0 || i == N-1) minNeighbour = 0;
        if (j < M-1)    minNeighbour = min(minNeighbour, matrix2[i][j+1]);
        if (j > 0)      minNeighbour = min(minNeighbour, matrix2[i][j-1]);
        if (i < N-1)    minNeighbour = min(minNeighbour, matrix2[i+1][j]);
        if (i > 0)      minNeighbour = min(minNeighbour, matrix2[i-1][j]);
 
        if (minNeighbour < matrix2[i][j] && matrix2[i][j] > matrix1[i][j])
        {
            matrix2[i][j] = max(matrix1[i][j], minNeighbour);
 
            if (j < M-1)    pset.insert(std::pair<int,int>(i,j+1));
            if (j > 0)      pset.insert(std::pair<int,int>(i,j-1));
            if (i < N-1)    pset.insert(std::pair<int,int>(i+1,j));
            if (i > 0)      pset.insert(std::pair<int,int>(i-1,j));
        }
    }
 
    int result = 0;
    for(int i = 1; i < N-1; ++i)
        for(int j = 1; j < M-1; ++j)
            result += matrix2[i][j] - matrix1[i][j];
 
    return result;
}
Не http://www.cyberforum.ru/cgi-bin/latex.cgi?O(N^2M^2) в худшем случае, а http://www.cyberforum.ru/cgi-bin/latex.cgi?O(NM).
И решения, которое было бы асимптотически лучше, очевидно, не существует.
Дальнейшая оптимизация, конечно, возможна, но, если нет конкретных ограничений на параметры и время, смысла ей заниматься тоже особо нет.
2
09.02.2014, 02:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.02.2014, 02:27
Привет! Вот еще темы с ответами:

Разработать алгоритм расчета и программу на Pascal для определения значений функции - Pascal ABC
1 формула 2 условие

Разработать программу для определения и вывода на экран неотрицательных значений функции - Pascal
Помогите понять и растолковать условие. Все бы хорошо, но меня путает это словосочетание - &quot;неотрицательных значений функции&quot;. Здесь...

Разработать алгоритм и программу для определения процента гласных символов в тексте! - C++
Разработать алгоритм и программу для определения процента гласных символов в тексте.Нужно переделать чтоб ввод был с клавиатуры.Заранее...

Разработать программу для определения процента повторения заданного слова в тексте - C++
люди помогите решить ! Завтра экзамен надо сдать лабу. Вот задача Разработать программу для определения процента повторения заданного...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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