2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Разрезы прямоугольника
Сообщение03.11.2007, 08:31 


23/10/07
5
Мне задали задачу, а я не могу решить, помогите, пожалуйста

Разрезать прямоугольник размера X*Y на детали прямоугольной формы размера X1*Y1 и X2*Y2, чтобы отходы были минимальны. Возможны только вертикальные и горизонтальные разрезы. Т.е. после первого разреза получается два прямоугольника, которые в последствии также можно разрезать. Время на тест 1 секунда

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



Входные данные находятся в текстовом файле с именем input.txt:

Во входном файле шесть целых чисел (1<=X<=100, 1<=Y<=100, 1<=X1<=X, 1<=Y1<=Y, 1<=X2<=X, 1<=Y2<=Y).



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



Выходные данные должны быть записаны в текстовый файл с именем output.txt и иметь следующий формат:

единственное целое число равное минимальной сумме остатков.



Пример входных данных



10

10

2

9

3

4



Пример выходных данных



10

 Профиль  
                  
 
 
Сообщение04.11.2007, 18:16 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Чего-то подробностей не хватает. Например, после первого разреза получились два прямоугольника. Мы должны их дальше резать вместе (разрезание торта на блюде), или как угодно (скажем, дан квадрат 4 х 4. Первый разрез вертикальный, посередине. Второй в левом прямоугольнике, горизонтальный 1:3. А третий в правом, горизонтальный, опять посередине).

Что такое время на решение? И что значит сумма остатков? Площадь? Значит ли это, что нам всё равно, что мы накроим, лишь бы остатков поменьше?

Анизотропен ли прямоугольник? Т.е., нам даны X = 4, Y = 6, X1 = 3, Y1 = 2, X2 = 3, Y2 = 5. Какой в этом случае правильный ответ? 0?! или 6?

 Профиль  
                  
 
 
Сообщение10.11.2007, 02:03 


23/10/07
5
Цитата:
Анизотропен ли прямоугольник? Т.е., нам даны X = 4, Y = 6, X1 = 3, Y1 = 2, X2 = 3, Y2 = 5. Какой в этом случае правильный ответ? 0?! или 6?


Ответ: будет 6!!!

 Профиль  
                  
 
 
Сообщение10.11.2007, 03:37 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Отлично! А остальные вопросы (я насчитал ещё 4)?

 Профиль  
                  
 
 
Сообщение10.11.2007, 08:11 


23/10/07
5
Цитата:
А остальные вопросы (я насчитал ещё 4)?


:shock: :shock: :shock:

Какой алгоритм???? Как могу програмировать? Так, ещё думать!!!!!

 Профиль  
                  
 
 
Сообщение11.11.2007, 00:26 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
duabevnh писал(а):
Как могу програмировать?
Никак. Потому, что
duabevnh писал(а):
Какой алгоритм????
зависит от того, как Вы ответите на вопросы:
незваный гость писал(а):
(1) после первого разреза получились два прямоугольника. Мы должны их дальше резать вместе (разрезание торта на блюде), или как угодно (скажем, дан квадрат 4 х 4. Первый разрез вертикальный, посередине. Второй в левом прямоугольнике, горизонтальный 1:3. А третий в правом, горизонтальный, опять посередине).

(2) Что такое время на решение?

(3) И что значит сумма остатков? Площадь?

(4) Значит ли это, что нам всё равно, что мы накроим, лишь бы остатков поменьше?




duabevnh писал(а):
Так, ещё думать!!!!!
Тихо сам с собою, // Тихо сам с собою, // Я веду беседу.

Или это Вы другими командуете? Ну-ну…

 Профиль  
                  
 
 
Сообщение08.12.2007, 14:30 


23/10/07
5
Автор программа: Павел

Код:
#include <iostream>
#include <fstream>
using namespace std;
const int maxn = 100;
int ff[maxn][maxn];

int x1,y1,x2,y2;

int f(int x, int y){
   
   if (ff[x][y]!= -1)
      return ff[x][y];
   
   int res = x*y;
   
   if (x>x1)
      res = min(res, f(x1,y)+f(x-x1,y));
   if (x>y1)
      res = min(res, f(y1,y)+f(x-y1,y));
   if (x>x2)
      res = min(res, f(x2,y)+f(x-x2,y));
   if (x>y2)
      res = min(res, f(y2,y)+f(x-y2,y));
   if (y>y1)
      res = min(res, f(x,y1)+f(x,y-y1));
   if (y>x1)
      res = min(res, f(x,x1)+f(x,y-x1));
   if (y>y2)
      res = min(res, f(x,y2)+f(x,y-y2));
   if (y>x2)
      res = min(res, f(x,x2)+f(x,y-x2));
   return res;
}

int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
   int x,y;
   int a[6];
   if(fin.is_open()){
      for(int i=0;i<6;i++)
         fin>>a[i];
      x=a[0];
      y=a[1];
      x1=a[2];
      y1=a[3];
      x2=a[4];
      y2=a[5];
   }
   for (int i=0;i<=x;i++)
      for (int j=0;j<=y;j++)
         ff[i][j]=-1;

   ff[x1][y1]=0;
   ff[x2][y2]=0;
   ff[y1][x1]=0;
   ff[y2][x2]=0;
   fout<<f(x,y)<<endl;

   return 0;
}


Программа работает нормально для малых массивы, Например:
x==40
y==50
x1==5
y1==6
x2==7
y2==8
выходных данных: 0

x==3
y==100
x1==2
y1==8
x2==3
y2==6
выходных данных: 12;

Но оценка очень плохо!!!!!!!!!!! Как можно быстрее? У кого есть лучщий алгоритм?

 Профиль  
                  
 
 
Сообщение08.12.2007, 19:31 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
А может, дело не только во времени? Вы, например, тот тест, который я Вам давал гоняли?

С другой стороны, зачем Вам другой алгорифм? Перепишите без рекурсии, и, думаю, Ваша программа достаточно ускорится. На моём компе (семи лет отроду) на Python (интерпретатор!!!) решение семи задач по два раза заняло 230 мс.

Добавлено спустя 7 минут 25 секунд:

Ах, да. Найдёт ли Ваша программа ответ, если остатков нет: 6, 4, 3, 4, 3, 4

А! вот ещё любопытный тест: 5, 5, 2, 3, 3, 2. Может быть, от Вас хотят 1? А получается 7?

~~~

Я думаю, вот поэтому и очень плохо.

 Профиль  
                  
 
 
Сообщение09.12.2007, 12:29 


23/10/07
5
Цитата:
Перепишите без рекурсии


Может быть и так!!!

5, 5, 2, 3, 3, 2. Конечно получается 7!!!

6, 4, 3, 4, 3, 4 Конечно получается 0!!!

Вот результат получается от программа!!

Ну например:
x==40
y==50
x1==5
y1==6
x2==7
y2==8

x==3
y==100
x1==2
y1==8
x2==3
y2==6

На моем программе дольго очень идет!!!
Может быт перебор алгоритм лучше :idea:

 Профиль  
                  
 
 
Сообщение10.12.2007, 19:17 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
duabevnh писал(а):
Вот результат получается от программа!!

На моем программе дольго очень идет!!!
Может быт перебор алгоритм лучше

Моя твоя понимай нету.

Так что пишите нормально, Вы же можете.

duabevnh писал(а):
Цитата:
Перепишите без рекурсии
Может быть и так!!!

Так за чем же дело встало? Если Вы написали эту программу, Вы понимаете, как она работает. А значит, и как её переписать. Без рекурсии она в чём-то медленнее, в чём-то быстрее.

А что Ваш вариант долго работает — так для этого есть отладчик. Посмотрите по шагам, что делает Ваша программа. Или напечатайте трассу вызовов и возвращаемых значений.

duabevnh писал(а):
Конечно получается 7!!!

У программ нет «конечно». У них есть ожидаемый результат. Для меня, например, 1 тоже хороший результат, поэтому важно понять, чего от Вас хотят.

У Вас с этим (с разницей между выдаваемым и ожидаемым результатом) явно туго. Например, на мой давнишний вопрос Вы ответили одно, а Ваша программа выдаёт другое. И?!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group