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

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

Войти
Регистрация
Восстановить пароль
 
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
#1

Листы жести - минимальную площадь - C++

27.04.2012, 15:14. Просмотров 950. Ответов 13
Метки нет (Все метки)

Задача

На складе хранятся прямоугольные листы жести разных размеров. Листы расположены горизонтально на полу. Для экономии поверхности, они накладываются друг на друга, но так, чтобы лист лежащий выше, в целом размере был размещен на листе, который находится под ним. Кладовщик заботится о том, чтобы соответствующие края листов жести были параллельными, а в середины листов создавали единую стопку, лежа на одной вертикали. Чтобы приспособиться к листу жести, который находится ниже можно поворачивать его на 90 градусов вокруг центра.

Задание:

Напишите программу, которая для данных листов жести обсчитает минимальную площадь пола, учитывая вышеназванные требования.

Входные данные:

Стандартный вход содержит несколько наборов данных. Первая строка содержит один набор, неотъемлемое целое n (n <= 200) которое указывает на количество листов в проблеме. Если он равен 0, это означает конец данных. В последующих строках n содержит два положительных целых числа, означающие размеры листов в наборе данных.

Выходные данные

Стандартный выход содержит следующие строки, в которых указывается одно число, которое означает минимальную площадь поверх пола, требующейся для размещения листов согласно требованиям склада.

Пример

Для входных данных:
2
3 5
4 4
3
5 4
2 5
4 4
0

Правильный ответ:
31
30

Вот мой код программы:
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
57
58
59
#include <iostream>
#include <fstream>
#define N 200
 
using namespace std; 
int main()
{
    ifstream in("input.txt");
    if (!in)
    {
        cerr<< "There's no such file";
        return 1;
    }
    ofstream out("output.txt");
    
    int w_tab[N];    
    int h_tab[N];
    int s_tab[N];
    int id, w, h;
    while (!in.eof())
    {
        in>> id;
        if (id == 0) break;
        for (int i = 0; i < id; i++)
        {
            in>> w>> h;
            w_tab[i]=w;
            h_tab[i]=h;
            
            
            for (int j = 1; j < id; j++)
            {
                if(w_tab[j]<=w_tab[j+1] && h_tab[j]<=h_tab[j+1]){
                
                w_tab[j]=w_tab[j+1];
                w_tab[j+1]=0;
                
                h_tab[j]=h_tab[j+1];
                h_tab[j+1]=0;          
                }
                
                else if(w_tab[j]<=h_tab[j+1] && h_tab[j]<=w_tab[j+1]){
 
                w_tab[j]=w_tab[j+1];
                w_tab[j+1]=0;
                
                h_tab[j]=h_tab[j+1];
                h_tab[j+1]=0;          
                }
                     
            } 
            //out<< w_tab[i]<< h_tab[i]<<"\n"; 
            s_tab[i] += w_tab[i] * h_tab[i];
            out<< s_tab[i]<< "\n";  
            }
    }
    out.close();
    return 0;
}
Помогите решить эту задачку!

Проблема в с работой над массивами не могу понять в чем моя проблема и в файл output.txt тоже сохраняет мусор.

Спасибо!
1
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2012, 15:14
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Листы жести - минимальную площадь (C++):

Найти минимальную площадь прямоугольника из набора - C++
Данное целое число N и набор из N прямоугольников , заданных своими сторонами - парами чисел ( а , b ) . Найти минимальную площадь...

Квадрат с вершинами из первого множества накрывает все точки второго множества и имеет минимальную площадь - C++
Даны два множества точек на плоскости. Выбрать четыре различных точки первого множества так, чтобы квадрат с вершинами в этих точках...

Найти площадь грани, площадь полной поверхности и объем куба - C++
Дана длина ребра куба. Найти площадь грани, площадь полной поверхности и объем куба. Результаты вывести на экран с пояснительным текстом.

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

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

Определить площадь круга и площадь заштрихованных областей - C++
Помогите с ответом, как сделать задачу: Напишите функцию double circle_area(double R) которая узнает площадь круга, . С помощью...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
JokerNN
132 / 128 / 36
Регистрация: 29.12.2011
Сообщений: 359
27.04.2012, 17:20 #2
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
#include <iostream>
#include <fstream>
//real steel
using namespace std;
 
void swap (int *a, int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
 
void special_bubblesort(int arr[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size - i; ++j) {
            if(arr[j][0] > arr[j-1][0] || (arr[j][0] == arr[j-1][0] && arr[j][1] > arr[j-1][1])) {
                swap(&arr[j][0], &arr[j-1][0]);
                swap(&arr[j][1], &arr[j-1][1]);
            }
        }
    }
}
 
int area(int arr[][2], int size)
{
    int area=arr[0][0]*arr[0][1];
    for(int i=1; i < size; ++i)
    {
        if ((arr[i][0] > arr[i-1][0] && arr[i][0] > arr[i-1][1]) || (arr[i][1]>arr[i-1][0] && arr[i][1] > arr[i-1][1])) area+=arr[i][0]*arr[i][1];
    }
    return area;
}
 
int main()
{
    int n;
    ifstream in("input.txt");
    ofstream out("output.txt");
    in>>n;
    while (n)
    {
        int parameters[n][2];
        for (int i=0; i<n; ++i) in>>parameters[i][0]>>parameters[i][1];
        special_bubblesort(parameters, n);
        out<<area(parameters, n)<<endl;
        in>>n;
    }
    in.close();
    out.close();
    return 0;
}
Вроде бы так, но на 100% алгоритм не тестировал, ещё не сделал проверки на открытие\закрытие файла, верность данных, программа предполагает, что всё введено корректно и файлы открылись.

По алгоритму: сортируем массив с размерами листов по неубыванию, в качестве старшего разряда выступает 1й параметр, младшего - 2й. Т.е. 2й данный вами пример будет отсортирован как (5,4) (4,4) (2,5) (по аналогии 54, 44, 25). Затем эти листы складываются друг на друга, если следующий лист не может быть положен на предыдущий - он кладётся рядом. В точности алгоритма, повторюсь на 100% не уверен (возможно стоит сначала их повернуть таким образом, чтобы длина обязательно была больше/равна ширине). На ваших данных сработало всё как надо. Если что, вечером, придя домой, доделаю.
2
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
27.04.2012, 21:01  [ТС] #3
Для этих входных данных

2
3 5
4 4
3
5 4
2 5
4 4
4
4 4
5 3
4 4
5 3
3
5 5
4 4
6 5
5
5 5
4 4
5 6
5 5
6 5
0
ответ должен быть

31
30
31
30
30

а программа выдает

31
30
15
30
30

то есть для

4
4 4
5 3
4 4
5 3

должно быть 31 а есть 15

для
7
3 2
2 3
4 4
4 2
2 4
4 4
5 5

должно быть 25 а есть 33
спасибо за помощь вы мне очень помогли!
0
JokerNN
132 / 128 / 36
Регистрация: 29.12.2011
Сообщений: 359
28.04.2012, 14:29 #4
Цитата Сообщение от shchurkoroman Посмотреть сообщение
спасибо за помощь вы мне очень помогли!
sarcasm?)
А вообще позор мне за хитросделанную сортировку) Переделал, теперь сортирует по убыванию площади листа, эта версия прошла все вышеобозначенные тесты) Сразу извиняйте меня, сам я тестировать свой код не привык)
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
#include <iostream>
#include <fstream>
//real steel 2
using namespace std;
 
void swap (int *a, int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
 
void special_bubblesort(int arr[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size-i; ++j) {
            if(arr[j][0]*arr[j][1] > arr[j-1][0]*arr[j-1][1]) {
                swap(&arr[j][0], &arr[j-1][0]);
                swap(&arr[j][1], &arr[j-1][1]);
            }
        }
    }
}
 
int area(int arr[][2], int size)
{
    int area=arr[0][0]*arr[0][1];
    for(int i=1; i < size; ++i)
    {
        if ((arr[i][0] > arr[i-1][0] && arr[i][0] > arr[i-1][1]) || (arr[i][1] > arr[i-1][0] && arr[i][1] > arr[i-1][1])) area += arr[i][0]*arr[i][1];
    }
    return area;
}
 
int main()
{
    int n;
    ifstream in("input.txt");
    ofstream out("output.txt");
    in>>n;
    while (n)
    {
        int parameters[n][2];
        for (int i=0; i<n; ++i) in>>parameters[i][0]>>parameters[i][1];
        special_bubblesort(parameters, n);
        out<<area(parameters, n)<<endl;
        in>>n;
    }
    in.close();
    out.close();
    return 0;
}
2
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
28.04.2012, 14:59  [ТС] #5
Спасибо большое!
0
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
05.06.2012, 19:14  [ТС] #6
Всем привет доработал программу но НЕ ДО КОНЦА
вот код:

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <fstream>
 
using namespace std;
 
void swap (int *a, int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
 
void bubblesort(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=0; j < size-i; ++j) {
            if(tab[j][1]<tab[j][0]){
                swap(&tab[j][0], &tab[j][1]);
            }
        }
    }
}
 
void bubblesort1(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size-i; ++j) {
            if(tab[j][0]>tab[j-1][0]) {
                swap(&tab[j][0], &tab[j-1][0]);
                swap(&tab[j][1], &tab[j-1][1]);
            }
        }
    }
}
 
void bubblesort2(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size-i; ++j) {
            if(tab[j][0]*tab[j][1] > tab[j-1][0]*tab[j-1][1]) {
                swap(&tab[j][0], &tab[j-1][0]);
                swap(&tab[j][1], &tab[j-1][1]);
            }
        }
    }
}
 
int square(int tab[][2], int size)
{
    int square=tab[0][0]*tab[0][1];
    for(int i=1; i < size; ++i)
    {
        if ((tab[i][0] > tab[i-1][0] && tab[i][0] > tab[i-1][1]) || (tab[i][1] > tab[i-1][0] && tab[i][1] > tab[i-1][1])) square += tab[i][0]*tab[i][1];
    }
    return square;
}
 
int main()
{
    int n,k;
    
    cin>>k;
    while (k)
    {
        int rozmiar[k][2];
        for (int i=0; i<k; ++i) cin>>rozmiar[i][0]>>rozmiar[i][1];
        bubblesort(rozmiar, k);
        bubblesort1(rozmiar, k);
        bubblesort2(rozmiar, k);
        cout<<square(rozmiar, k)<<endl;
        cin>>k;
    }
 
    ifstream in("Bin.txt");
    ofstream out("Bout.txt");
    if(in == NULL)    {    
    printf (" Blad odczytu pliku Bin.txt\n");
    return 0;
    }
    in>>n;
    while (n)
    {
        int rozmiar[n][2];
        for (int i=0; i<n; ++i) in>>rozmiar[i][0]>>rozmiar[i][1];
        bubblesort(rozmiar, n);
        bubblesort1(rozmiar, n);
        bubblesort2(rozmiar, n);
        out<<square(rozmiar, n)<<endl;
        in>>n;
    }
    in.close();
    out.close();
 
    return 0;
}

для данных

14
20 1
1 19
2 9
2 10
1 15
4 5
9 2
1 8
2 7
2 9
7 2
2 3
4 4
4 3

12
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
7 5
2 4

12
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
7 5
9 4
0

результат должен быть

150
143
196

А у меня
83
143
136
Помогите решыть даную проблему!

Добавлено через 48 минут
Цитата Сообщение от shchurkoroman Посмотреть сообщение
Всем привет доработал программу но НЕ ДО КОНЦА
вот код:

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <fstream>
 
using namespace std;
 
void swap (int *a, int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
 
void bubblesort(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=0; j < size-i; ++j) {
            if(tab[j][1]<tab[j][0]){
                swap(&tab[j][0], &tab[j][1]);
            }
        }
    }
}
 
void bubblesort1(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size-i; ++j) {
            if(tab[j][0]>tab[j-1][0]) {
                swap(&tab[j][0], &tab[j-1][0]);
                swap(&tab[j][1], &tab[j-1][1]);
            }
        }
    }
}
 
void bubblesort2(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size-i; ++j) {
            if(tab[j][0]*tab[j][1] > tab[j-1][0]*tab[j-1][1]) {
                swap(&tab[j][0], &tab[j-1][0]);
                swap(&tab[j][1], &tab[j-1][1]);
            }
        }
    }
}
 
int square(int tab[][2], int size)
{
    int square=tab[0][0]*tab[0][1];
    for(int i=1; i < size; ++i)
    {
        if ((tab[i][0] > tab[i-1][0] && tab[i][0] > tab[i-1][1]) || (tab[i][1] > tab[i-1][0] && tab[i][1] > tab[i-1][1])) square += tab[i][0]*tab[i][1];
    }
    return square;
}
 
int main()
{
    int n,k;
    
    cin>>k;
    while (k)
    {
        int rozmiar[k][2];
        for (int i=0; i<k; ++i) cin>>rozmiar[i][0]>>rozmiar[i][1];
        bubblesort(rozmiar, k);
        bubblesort1(rozmiar, k);
        bubblesort2(rozmiar, k);
        cout<<square(rozmiar, k)<<endl;
        cin>>k;
    }
 
    ifstream in("Bin.txt");
    ofstream out("Bout.txt");
    if(in == NULL)    {    
    printf (" Blad odczytu pliku Bin.txt\n");
    return 0;
    }
    in>>n;
    while (n)
    {
        int rozmiar[n][2];
        for (int i=0; i<n; ++i) in>>rozmiar[i][0]>>rozmiar[i][1];
        bubblesort(rozmiar, n);
        bubblesort1(rozmiar, n);
        bubblesort2(rozmiar, n);
        out<<square(rozmiar, n)<<endl;
        in>>n;
    }
    in.close();
    out.close();
 
    return 0;
}

для данных

14
20 1
1 19
2 9
2 10
1 15
4 5
9 2
1 8
2 7
2 9
7 2
2 3
4 4
4 3

12
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
7 5
2 4

12
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
7 5
9 4
0

результат должен быть

150
143
196

А у меня
83
143
136
Помогите решыть даную проблему!
Проблема в сортировке только где она? Помогите разобраться!
1
JokerNN
132 / 128 / 36
Регистрация: 29.12.2011
Сообщений: 359
05.06.2012, 20:47 #7
Зачем целых 3 сортировки?) Думается мне сначала надо отсортировать по убыванию площади, затем просто каждый лист "повернуть" так чтобы длинная кромка была всегда слева, например, потом пытаться складывать и, если одна из сторон больше чем у листа ниже - то кладём рядом, могу на выходных доделать, сейчас, к сожалению, у самого сессия.

P.S. Nice Prepod
0
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
05.06.2012, 20:56  [ТС] #8
Для данных

3
1 20
4 5
10 2

программа не работает для этого там 3 сортировки!
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.06.2012, 06:10 #9
shchurkoroman, Пробуйте такой алгоритм:
При считывании очередного набора данных, например:
Цитата Сообщение от shchurkoroman Посмотреть сообщение
3
1 20
4 5
10 2
, высчитываете общую площадь всех листов S.
Затем сортируете листы по площади. Потом проход по листам начиная с минимальной площади. Для каждого текущего листа делаете так:
ищите в предыдущих листах, лист максимальной площади, который может поместиться на текущий лист. Если такой лист найден, то из S вычитаете его площадь, а сам такой найденный лист удаляете совсем.
По окончании прохода выводите значение S.
0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
06.06.2012, 07:04 #10
Цитата Сообщение от shchurkoroman Посмотреть сообщение
На складе хранятся прямоугольные листы жести разных размеров. Листы расположены горизонтально на полу. Для экономии поверхности, они накладываются друг на друга, но так, чтобы лист лежащий выше, в целом размере был размещен на листе, который находится под ним. Кладовщик заботится о том, чтобы соответствующие края листов жести были параллельными, а в середины листов создавали единую стопку, лежа на одной вертикали. Чтобы приспособиться к листу жести, который находится ниже можно поворачивать его на 90 градусов вокруг центра.
Все листы сложить на самый большой.
0
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
07.06.2012, 22:45  [ТС] #11
Здравствуйте подправил задачу но все таки

для набора данных:

14
20 1
1 19
2 9
2 10
1 15
4 5
9 2
1 8
2 7
2 9
7 2
2 3
4 4
4 3

ответ 60

а программа выдает 168

Вот код программы помогите разобраться как сделать этот алгоритм

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <fstream>
 
using namespace std;
 
void swap (int *a, int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
 
void bubblesort(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=0; j < size-i; ++j) {
            if(tab[j][1]<tab[j][0]){
                swap(&tab[j][0], &tab[j][1]);
            }
        }
    }
}
 
void bubblesort1(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size-i; ++j) {
            if(tab[j][0]*tab[j][1] > tab[j-1][0]*tab[j-1][1]) {
                swap(&tab[j][0], &tab[j-1][0]);
                swap(&tab[j][1], &tab[j-1][1]);
            }
        }
    }
}
 
int square(int tab[][2], int size)
{
    int z=0;
    int h,w;
    int square=tab[0][0]*tab[0][1];
    for(int i=1; i < size; ++i)
    {
         if (tab[i][0] <= tab[i-1][0] && tab[i][1] <= tab[i-1][1])
         {
                       
         }
         
         else
         {
         if(z==0)
         {
         square += tab[i][0]*tab[i][1];
         z=1;
         h=tab[i][0];
         w=tab[i][1];
         }
         
         if(z>0)
         {
         if (tab[i][0] <= h && tab[i][1] <= w)
         {
         h=tab[i][0];
         w=tab[i][1];             
         }
         
         else
         {
         square += tab[i][0]*tab[i][1];
         h=tab[i][0];
         w=tab[i][1];
         }   
         }
         }
    }
    return square;
}
 
int main()
{
    int n,k;
    cin>>k;
    while (k)
    {
        int rozmiar[k][2];
        for (int i=0; i<k; ++i) cin>>rozmiar[i][0]>>rozmiar[i][1];
        bubblesort(rozmiar, k);
        bubblesort1(rozmiar, k);
        cout<<square(rozmiar, k)<<endl;
        cin>>k;
    }
 
    ifstream in("Bin.txt");
    ofstream out("Bout.txt");
    if(in == NULL)    {    
    printf (" Blad odczytu pliku Bin.txt\n");
    return 0;
    }
    in>>n;
    while (n)
    {
        int rozmiar[n][2];
        for (int i=0; i<n; ++i) in>>rozmiar[i][0]>>rozmiar[i][1];
        bubblesort(rozmiar, n);
        bubblesort1(rozmiar, n);
        out<<square(rozmiar, n)<<endl;
        in>>n;
    }
    in.close();
    out.close();
 
    return 0;
}
Помогите пожалуйста а то ума не приложу как сделать эту программу
0
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
07.06.2012, 22:46  [ТС] #12
Как решить эту проблему!
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.06.2012, 23:30 #13
пробуйте сдавать:
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
57
58
59
#include <iostream>
#include <fstream>
 
using namespace std;
 
 
int main()
{
    int n,i,j,s,rozmiar[200][2],pl[200],t,m;
    bool a[200];
    ifstream in("Bin.txt");
    ofstream out("Bout.txt");
    if(in == NULL)    {    
    printf (" Blad odczytu pliku Bin.txt\n");
    return 0;
    }
    while (true)
    {
        in>>n;
        if(n==0)
            break;
        s=0;
        for (i=0; i<n; ++i)
        {
            in>>rozmiar[i][0]>>rozmiar[i][1];
            a[i]=false;             
            pl[i]=rozmiar[i][0]*rozmiar[i][1];
            s+=pl[i];
        }
        for(i=0; i<n-1; i++)
        {
            m=i;
            for(j=i+1; j<n; j++)
                if(pl[m]>pl[j])
                    m=j;
            t=pl[i]; pl[i]=pl[m]; pl[m]=t;
            t=rozmiar[i][1]; rozmiar[i][1]=rozmiar[m][1]; rozmiar[m][1]=t;
            t=rozmiar[i][0]; rozmiar[i][0]=rozmiar[m][0]; rozmiar[m][0]=t;
        }
        for(i=1; i<n; i++)
        {
            t=-1;
            for(j=0; j<i; j++)
                if(((rozmiar[i][1]>=rozmiar[j][1] && rozmiar[i][0]>=rozmiar[j][0]) ||
                    (rozmiar[i][1]>=rozmiar[j][0] && rozmiar[i][0]>=rozmiar[j][1])) && !a[j])
                    t=j;    
            if(t!=-1)
            {
                s-=pl[t];
                a[t]=true;
            }
        }        
        out<<s<<endl;       
    }
    in.close();
    out.close();
 
    return 0;
}
кстати в ранее приведенных тестах есть ошибки:
Цитата Сообщение от shchurkoroman Посмотреть сообщение
12
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
7 5
9 4
0
результат должен быть
196
на самом деле результат должен быть: 171:
вот эта часть:
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
укладывается друг на друга и остается здесь только 10*10=100
+ 7*5+9*4=171
1
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
08.06.2012, 01:42  [ТС] #14
Спасибо огромное! Программа работает идеально)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2012, 01:42
Привет! Вот еще темы с ответами:

Составить базу данных о квартирах дома (от 6 до 12). Для каждой квартиры указать номер, жилую площадь, общую площадь, количество жильцов... - C++
Составить базу данных о квартирах дома (от 6 до 12). Для каждой квартиры указать номер, жилую площадь, общую площадь, количество жильцов,...

Два треугольника заданы координатами своих вершин A,B,C. Вычислить площадь треугольника и определить какой треугольник имеет большую площадь - C++
Два треугольника заданы координатами своих вершин A,B,C. Вычислить площадь треугольника и определить какой треугольник имеет большую...

Сравнить площадь круга и площадь квадрата , которые заданы сответствено радиусом r и стороной квадрата a - C++
сравнить площадь круга и площадь квадрата , которые заданы сответствено радиусом r и стороной квадрата a

Найти x и y и минимальную сумму x и y - C++
дано k чисел T(0) T(1)..T(k) найти x и y, где 1&lt;=x&lt;y&lt;=k, и минимальную сумму x и y T(x)..T(y)


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
08.06.2012, 01:42
Ответ Создать тему
Опции темы

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