космический зоопарк

@Mixty · Регистрация: 19.10.2012

Студворк — интернет-сервис помощи студентам

Космический зоопарк
Time limit = 5 секунд(ы)
Memory limit = 33000 Kb
Шёл 2130-й год. Колонисты с планеты Земля приземлились на одну из планет системы Альфа Центавра. Их миссия состояла в исследовании ближайших звёзд и планет. Основав несколько космических поселений, они сформировали высокоразвитое общество. Теперь, 14 лет спустя, они обнаружили, что в некоторых ближайших галактиках существует жизнь. К тому же галактики, в которых обнаружена жизнь, расположены так, что образуют 3-хмерную прямоугольную матрицу. Вы можете полагать, что существует прямоугольный параллелепипед, разделённый на ячейки по 1 галактике в каждой ячейке. Измерения параллелепипеда — целые числа M, N и D, причём 1 ≤ M,N,D ≤ 20, а каждая ячейка — это куб со стороной 1. Правительство Альфа Центавра решило построить космический зоопарк. Формы жизни в различных галактиках различны, поэтому если галактика становится частью зоопарка, то она получает некоторую прибыль (которая различна для разных галактик). Главный экономист космического поселения мистер Иванофф подсчитал годовую прибыль для каждой галактики. Современные технологии строительства космических объектов требуют, чтобы космический зоопарк был прямоугольным параллелепипедом со сторонами, параллельными сторонам параллелепипеда, ограничивающего галактики. Имея результаты подсчётов, которые проделал мистер Иванофф, определите наибольшую прибыль (или наименьший убыток), которую может получить правительство Альфа Центавра от строительства такого зоопарка.
Зная числа в ячейках, на которые разбит прямоугольный параллепипед, вмещающий рассматриваемые галактики, определите содержащийся в нём параллелепипед с максимальной суммой чисел в нём. Вы можете считать, что сумма чисел в любом таком включённом параллепипеде меньше 32000.
Вход В первой строке содержится 3 числа: M, N, D, такие что 1 ≤ M,N,D ≤ 20. Далее следует D блоков, каждый блок содержит M строк по N целых чисел, представляющих собой прибыль соответствующих галактик. Значения прибылей или убытков (что соответствует отрицательной прибыли) по величине не превосходят 500.
Выход Вывод должен содержать одно число — максимально возможную прибыль (или минимальный убыток).

Помогите кто может. Голова не варит совсем.

Одиночка · 13.03.2013, 09:00

Хочу уточнить. Параллелепипед зоопарка должен содержаться внутри параллелепипеда, ограничевающего галактики. И может включать хоть их все (если у всех прибыль положительна). Именно при наличии отрицательных прибылей (убытков) включение всех может быть менее выгодно чем выбор только части. Я правильно понял?

Добавлено через 8 часов 24 минуты
Пока при 20х20х20 получилось почти 17 секунд. Подумаю как оптимизировать.

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

Кликните здесь для просмотра всего текста

Delphi
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
program Project2;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils, Windows;
 
Var
  tt : LongWord;
  m,n,d : Integer;
  mt,nt,dt : Integer;
 
  f : TextFile;
  i,j,k,t,i1,j1,k1,Pr : Integer;
  Matr : Array[1..20,1..20,1..20] Of Integer; //32000 байт
begin
  AssignFile(f,'Input.txt');
  If Not FileExists('Input.txt') Then
  //Если файла нет
  Begin
    //Создать файл
    m:=20;
    n:=20;
    d:=20;
    Rewrite(f);
    WriteLn(f,m:3,n:3,d:3);
    Randomize;
    For i:=1 To d Do
    For j:=1 To m Do
    Begin
      For k:=1 To n Do
      Begin
        t:=Random(1001)-500;
        Write(f,t:5);
      End;
      WriteLn(f);
    End;
    Close(f);
  End;
 
  //Ввод данных
  Reset(f);
  ReadLn(f,m,n,d);
  Randomize;
  For i:=1 To d Do
  For j:=1 To m Do
  For k:=1 To n Do
  Read(f,Matr[i,j,k]);
  Close(f);
 
  //Обработка
  tt:=GetTickCount; //Время начала
  Pr:=-MaxInt;
  For dt:=1 To d Do //Циклы по размерам внутреннего параллелепипеда
  For mt:=1 To m Do
  For nt:=1 To n Do
  For i:=1 To d-dt+1 Do //Циклы по перемещению параллелепипеда внутри главного
  For j:=1 To m-mt+1 Do
  For k:=1 To n-nt+1 Do
  Begin
    t:=0;
    For i1:=i To i+dt-1 Do //Циклы по подсчёту суммы внутри внутреннего пл
    For j1:=j To j+mt-1 Do
    For k1:=k To k+nt-1 Do
    t:=t+Matr[i1,j1,k1];
    If t>Pr Then Pr:=t;
  End;
  WriteLn('Vremya vypolneniya: ',GetTickCount-tt);
  WriteLn(tt);
  ReadLn;
end.

Одиночка · 14.03.2013, 22:10

Оптимизировал. Время выполнения на матрице 20х20х20 меньше 4-х секунд. Используемая память чуть больше 32000 байт.

Кликните здесь для просмотра всего текста

Delphi
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
program Project2;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils, Windows;
 
Var
  tt : LongWord;
  m,n,d : Integer;
  mt,nt,dt : Integer;
 
  f : TextFile;
  i,j,k,t,i1,j1,k1 : Integer;
  Pr,Pd,Pm,Pn,Pdt,Pmt,Pnt : Integer;
  Matr : Array[1..20,1..20,1..20] Of Integer; //32000 байт
  drr,mrr,nrr,dir,mir,nir : Integer;
begin
  AssignFile(f,'Input.txt');
  If Not FileExists('Input.txt') Then
  //Если файла нет
  Begin
    //Создать файл
    m:=20;
    n:=20;
    d:=20;
    Rewrite(f);
    WriteLn(f,m:3,n:3,d:3);
    Randomize;
    For i:=1 To d Do
    For j:=1 To m Do
    Begin
      For k:=1 To n Do
      Begin
        t:=Random(1001)-500;
        Write(f,t:5);
      End;
      WriteLn(f);
    End;
    Close(f);
  End;
 
  tt:=GetTickCount; //Время начала
  //Ввод данных
  Reset(f);
  ReadLn(f,m,n,d);
  For i:=1 To d Do
  For j:=1 To m Do
  For k:=1 To n Do
  Read(f,Matr[j,k,i]);
  Close(f);
 
  //Обработка
  drr:=1; mrr:=1; nrr:=1;
  dir:=1; mir:=1; nir:=1;
  Pd:=0;
  For i:=1 To m Do //Циклы по перемещению параллелепипеда внутри главного
  For j:=1 To n Do
  For k:=1 To d Do
  Pd:=Pd+Matr[i,j,k]; //Полная сумма пл, ограничивающего галактики
 
  Pr:=Pd;
  For dt:=d DownTo 1 Do //Цикл уменьшения размерности d внутреннего пл
  Begin
    Pm:=Pd;
    For mt:=m DownTo 1 Do //Цикл уменьшения размерности m внутреннего пл
    Begin
      Pn:=Pm;
      For nt:=n DownTo 1 Do //Цикл уменьшения размерности n внутреннего пл
      Begin
        Pdt:=Pn;
        For i:=1 To d-dt+1 Do //Цикл по перемещению пл по размерности d внутри главного
        Begin
          Pmt:=Pdt;
          For j:=1 To m-mt+1 Do //Цикл по перемещению пл по размерности m внутри главного
          Begin
            Pnt:=Pmt;
            For k:=1 To n-nt+1 Do //Цикл по перемещению пл по размерности n внутри главного
            Begin
              If Pnt>Pr Then
              Begin
                Pr:=Pnt;
                //Параметры внутреннего пл для подсчёта суммы простым алгоритмом
                drr:=dt;
                mrr:=mt;
                nrr:=nt;
                dir:=i;
                mir:=j;
                nir:=k;
              End;
 
              //Пересчёт суммы с учётом перемещения по размерности n
              For i1:=i To i+dt-1 Do
              For j1:=j To j+mt-1 Do
              Pnt:=Pnt-Matr[j1,k,i1]+Matr[j1,k+nt,i1];
            End;
            //Пересчёт суммы с учётом перемещения по размерности m
            For i1:=i To i+dt-1 Do
            For j1:=1 To nt Do
            Pmt:=Pmt-Matr[j,j1,i1]+Matr[j+mt,j1,i1];
          End;
          //Пересчёт суммы с учётом перемещения по размерности d
          For i1:=1 To mt Do
          For j1:=1 To nt Do
          Pdt:=Pdt-Matr[i1,j1,i]+Matr[i1,j1,i+dt];
        End;
        //Пересчёт суммы с учётом уменьшения размерности n
        For i:=1 To dt Do
        For j:=1 To mt Do
        Pn:=Pn-Matr[j,nt,i];
      End;
      //Пересчёт суммы с учётом уменьшения размерности m
      For i:=1 To dt Do
      For j:=1 To n Do
      Pm:=Pm-Matr[mt,j,i];
    End;
    //Пересчёт суммы с учётом уменьшения размерности d
    For i:=1 To m Do
    For j:=1 To n Do
    Pd:=Pd-Matr[i,j,dt];
  End;
  WriteLn(Pr);
  AssignFile(f,'Output.txt');
  Rewrite(f);
  WriteLn(f,Pr); //Выдали в файл
  Close(f);
  //Проверка...
  Pr:=0;
  For i:=dir To dir+drr-1 Do
  For j:=mir To mir+mrr-1 Do
  For k:=nir To nir+nrr-1 Do
  Pr:=Pr+Matr[j,k,i];
  WriteLn(Pr,'  - proverka prostym algoritmom');
  WriteLn('Vremya vypolneniya: ',GetTickCount-tt);
 
  ReadLn;
end.

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: показать затраченные материалы за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В качестве. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

@Mixty 1 / 1 / 0 Регистрация: 19.10.2012 Сообщений: 51

	космический зоопарк 12.03.2013, 08:59. Показов 2704. Ответов 2 Метки нет (Все метки) Космический зоопарк Time limit = 5 секунд(ы) Memory limit = 33000 Kb Шёл 2130-й год. Колонисты с планеты Земля приземлились на одну из планет системы Альфа Центавра. Их миссия состояла в исследовании ближайших звёзд и планет. Основав несколько космических поселений, они сформировали высокоразвитое общество. Теперь, 14 лет спустя, они обнаружили, что в некоторых ближайших галактиках существует жизнь. К тому же галактики, в которых обнаружена жизнь, расположены так, что образуют 3-хмерную прямоугольную матрицу. Вы можете полагать, что существует прямоугольный параллелепипед, разделённый на ячейки по 1 галактике в каждой ячейке. Измерения параллелепипеда — целые числа M, N и D, причём 1 ≤ M,N,D ≤ 20, а каждая ячейка — это куб со стороной 1. Правительство Альфа Центавра решило построить космический зоопарк. Формы жизни в различных галактиках различны, поэтому если галактика становится частью зоопарка, то она получает некоторую прибыль (которая различна для разных галактик). Главный экономист космического поселения мистер Иванофф подсчитал годовую прибыль для каждой галактики. Современные технологии строительства космических объектов требуют, чтобы космический зоопарк был прямоугольным параллелепипедом со сторонами, параллельными сторонам параллелепипеда, ограничивающего галактики. Имея результаты подсчётов, которые проделал мистер Иванофф, определите наибольшую прибыль (или наименьший убыток), которую может получить правительство Альфа Центавра от строительства такого зоопарка. Зная числа в ячейках, на которые разбит прямоугольный параллепипед, вмещающий рассматриваемые галактики, определите содержащийся в нём параллелепипед с максимальной суммой чисел в нём. Вы можете считать, что сумма чисел в любом таком включённом параллепипеде меньше 32000. Вход В первой строке содержится 3 числа: M, N, D, такие что 1 ≤ M,N,D ≤ 20. Далее следует D блоков, каждый блок содержит M строк по N целых чисел, представляющих собой прибыль соответствующих галактик. Значения прибылей или убытков (что соответствует отрицательной прибыли) по величине не превосходят 500. Выход Вывод должен содержать одно число — максимально возможную прибыль (или минимальный убыток). Помогите кто может. Голова не варит совсем. 0

Опции темы

космический зоопарк

Решение