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

@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.

Новые блоги и статьи Все статьи Все блоги /
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

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

	космический зоопарк 12.03.2013, 08:59. Показов 2683. Ответов 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

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

Решение