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

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

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

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

09.02.2014, 00:10. Просмотров 278. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.02.2014, 00:10     Разработать программу для определения объема оставшейся воды в теле, если оно полностью погружается в воду основанием вниз, а затем поднимается.
Посмотрите здесь:

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

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

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

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

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

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

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

Разработать алгоритм и программу для определения количества слов в введенном тексте, которые начинаются на буквой "А" - C++
Разработать алгоритм и программу для определения количества слов в введенном тексте, которые начинаются буквой "А". Считать, что слова в...

Задача на определение объема невытекшей воды из формы тела, заданной матрицей - C++
Фоpма тела задана матpицей А pазмеpности M x N. Элементы матpицы - натуpальные числа. Элемент А ( i,j ) соответствует высоте гоpизонтальной...

Разработать функцию для определения и расчёта площади пятиугольника. По координатным точкам. (х1,у1) и т.д - C++
Даны вещественные числа х1,у1,х2,у2...х5,у5. Найти площадь пятиугольника, вершины которого имеют координаты (х1.у2) и т.д. Разработать...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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);
    }
пока что-то меняется.

Потом просто сложить разности соответствующих ячеек из двух матриц - это и будет объем воды.
azbest
41 / 41 / 8
Регистрация: 12.03.2013
Сообщений: 148
09.02.2014, 02:07  [ТС]     Разработать программу для определения объема оставшейся воды в теле, если оно полностью погружается в воду основанием вниз, а затем поднимается. #3
Ответ хороший, что называется "в лоб". Но думаю что если задача олимпиадная, то такой вариант не пройдет тест по скорости. Если числа M и N будут порядка 10^5.
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).
И решения, которое было бы асимптотически лучше, очевидно, не существует.
Дальнейшая оптимизация, конечно, возможна, но, если нет конкретных ограничений на параметры и время, смысла ей заниматься тоже особо нет.
Yandex
Объявления
09.02.2014, 02:27     Разработать программу для определения объема оставшейся воды в теле, если оно полностью погружается в воду основанием вниз, а затем поднимается.
Ответ Создать тему
Опции темы

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