Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум на CrossPlatform.RU _ Алгоритмы, задачи по программированию, логические игры _ Задачка - делим торт, поровну

Автор: ViGOur 20.5.2009, 10:47

У Вас с другом есть прямоугольный торт, из которого какой-то гад, к сожалению, уже вырезал (и съел) прямоугольный кусок. Ориентация и положение вырезанного куска могут быть совершенно произвольными. Как вам с другом разделить оставшийся торт на две равные части?

Автор: Влад 20.5.2009, 12:54

Способ 1:
- Скатываем (сминаем, как снежок) оставшуюся часть торта в шарик. Одной операцией делим получившийся шарик пополам (считаем, что это можно сделать точно).

Disclaimer: Вкусовые качества торта от этого не пострадают. О сохранении прямоугольной формы кусков - в исходном ТЗ требование не предъявляется :)

Автор: ViGOur 20.5.2009, 13:17

А чисто по человечески ты сам бы стал есть такой торт? :)
Потому думаю это не решение.

Кстати, по аське пришло от друга:

Цитата
14:16 GAlex: жестокие у вас люди. хотел-бы я посмотреть как он торт в шарик скатает.
:lol:

Автор: AD 20.5.2009, 13:21

Цитата(ViGOur @ 20.5.2009, 14:17) *
А чисто по человечески ты сам бы стал есть такой торт? :)
Потому думаю это не решение.

Почему? В задаче не оговаривалось ничего об изменении формы. Решение вполне приемлемое. Я бы съел такой торт, почему бы нет, главное, чтобы скатывали в шарик чистыми руками! :)

Автор: ViGOur 20.5.2009, 13:34

Цитата(AD @ 20.5.2009, 14:21) *
Почему?
Человек решивший эту задачу говорит, что это делается одной линией. :)

Я сам ее не решил пока.

Автор: Tonal 20.5.2009, 13:36

Отрезаем максимальные прямоугольники сверху и снизу дырки.
От оставшегося левого куска отрезаем максимальный левый прямоугольник, от правого - правый.
Вышло 4 разных прямоугольника и возможно 4 треугольника.
Площадь 2х левых треугольников = 2м правым - раздаём.
Прямоугольники делим любым способом (например наискосок). :)

Можно подумать как минимизировать количество разрезаний. :)

Автор: Andrew Selivanov 20.5.2009, 13:38

Вид боковой стороны торта...
http://img188.imageshack.us/my.php?image=tort.png
Кривовато получилось, но смысл такой :)

Автор: ViGOur 20.5.2009, 13:42

Ура, решил.
Но от вас пока правильного ответа не услышал. :)

Автор: D_K 20.5.2009, 13:46

Ну вообще-то можно торт разрезать по горизонтали ;)

Автор: ViGOur 20.5.2009, 13:52

И что, а если дырка находится с права сверху под углом 30 градусов, причем повернутая по диоганали. :)
Напоминаю, что

Цитата(ViGOur @ 20.5.2009, 11:47) *
Ориентация и положение вырезанного куска могут быть совершенно произвольными.


Ответ должен быть однозначным для всех ситуаций положения дырки.

Автор: AD 20.5.2009, 13:54

Цитата(ViGOur @ 20.5.2009, 14:52) *
И что, а если дырка находится с права сверху под углом 30 градусов, причем повернутая по диоганали. :)

Эдик, а как это? Ведь вырезали прямоугольник?

Автор: ViGOur 20.5.2009, 13:56

Например так:


Или еще как повернута или в другом месте торта вырезана.

Автор: D_K 20.5.2009, 14:00

ViGOur, то есть под "прямоугольником" ты имел в виду прямоугольный параллелепипед?
В общем, ТЗ было сформулировано нечетко :)

Автор: AD 20.5.2009, 14:00

а торт плоский что-ли? Или ты имеешь в виду, что дырка несквозная? Прости, просто если считать вариант ответа, что разрезали по толщине, то оно удовлетворяет условиям, если дырка сквозная.

Автор: ViGOur 20.5.2009, 14:02

Цитата(D_K @ 20.5.2009, 15:00) *
ты имел в виду прямоугольный параллелепипед?
Вроде того. Это не я формулировал, что было то и привел. :)

Цитата(AD @ 20.5.2009, 15:00) *
вариант ответа, что разрезали по толщине
Не верный ответ. У тортов ведь есть начинка, кому-то она достанется кому-то нет или вкусней... :)

Автор: AD 20.5.2009, 14:17

Ну вот так что ли:
[attachment=620:tort.JPG]

Автор: ViGOur 20.5.2009, 14:26

Не верно.

Автор: D_K 20.5.2009, 15:07

Так будет нормальная формулировка? Я, честно говоря, не совсем понимаю, каким образом мог быть вырезан кусок торта.

Автор: ViGOur 20.5.2009, 16:23

Честно говоря я думаю это и есть нормальная формулировка.
Если судить с точки зрения логики, то все в порядке. Мне уже правильно ответили несколько человек, не придираясь к точности формулировки. :)

Дам подсказку, резать нужно сверху торта.

Автор: Litkevich Yuriy 20.5.2009, 20:00

Цитата(Andrew Selivanov @ 20.5.2009, 17:38) *
Вид боковой стороны торта...
а ведь это идея! Только зигзаг не нужен, просто горизонтальная линия

Автор: ViGOur 20.5.2009, 20:05

Цитата(Litkevich Yuriy @ 20.5.2009, 21:00) *
Только зигзаг не нужен, просто горизонтальная линия
Уже предлагали. :)
Цитата(ViGOur @ 20.5.2009, 15:02) *
Не верный ответ. У тортов ведь есть начинка, кому-то она достанется кому-то нет или вкусней...

Автор: Tonal 21.5.2009, 7:32

Чем не устроило моё решение?

Автор: ViGOur 21.5.2009, 7:41

Цитата(Tonal @ 21.5.2009, 8:32) *
Чем не устроило моё решение?
Тем, что решение должно быть одно, на разные положения вырезанного куска. Да и слишком много действий.

Еще подсказка, вспоминаем школьные уроки геометрии. Мне хоть и за 30, но удалось вспомнить. :)

Автор: Tonal 21.5.2009, 8:53

Решение не зависит от положения вырезанного куска, хотя в некоторых его положениях какие-то из действий могут быть избыточны (вырождены).
Ну и в задаче не налагалось ограничение на количество действий. :)

П.С. Разрезы показаны красными линиями.
Треугольники r1, l2 и l1, r2 попарно равны.

 

Автор: ViGOur 21.5.2009, 9:09

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

p.s. У меня есть еще парочка интересных задачек. :)

Автор: Влад 21.5.2009, 13:26

Не, ну, если вам влом есть торт, скатанный в шарик.... :)

Вот способ 2: (Два разреза ножом. Рисовал на глазок, так что не обессудьте. Идея, думаю, ясна. Где именно резать - легко вычисляется даже без школьного курса геометрии. Но можно и с ним :) )



PS: через "дырку" можно резать и наискосок, по диагонали - как удобнее получится.

Автор: ViGOur 21.5.2009, 13:37

Не правильный ответ. Может быть так универсально разделить поровну и можно (в чем я сомневаюсь), но есть более оптимальный ответ. :)

Автор: Влад 21.5.2009, 14:07

Можно, можно. Зря сомневаешься. Доказывать с помощью теорем из школьного курса геометрии - мне лично влом.
Хорошо, вот вариант с одним косым разрезом (рисовал опять таки на глазок):


Автор: igor_bogomolov 21.5.2009, 14:15

Нужно провести линию через центры обоих прямоугольников. :)

Влад меня опередид, пока я художеством занимался.

 

Автор: ViGOur 21.5.2009, 14:46

Цитата(igor_bogomolov @ 21.5.2009, 15:15) *
Нужно провести линию через центры обоих прямоугольников.
Правильный ответ.
Прямая проведенная через центр пямоугольника делит его на две равные части. :)

p.s. так что, стоит создавать новый раздел: http://www.forum.crossplatform.ru/index.php?showtopic=2815 или нет?

Автор: D_K 21.5.2009, 16:15

Я не знаю как Вам, а мне проще скатать оставшийся тортик в шарик, чем искать в нем центры двух прямоугольных параллелепипедов.
Кроме того, кусок можно отхватить такой, что форма торта просто невостановима.

Цитата(ViGOur @ 21.5.2009, 15:46) *
Прямая проведенная через центр пямоугольника делит его на две равные части. :)

У нас вроде как трехмерное пространство :)

Цитата(ViGOur @ 21.5.2009, 15:46) *
p.s. так что, стоит создавать новый раздел: http://www.forum.crossplatform.ru/index.php?showtopic=2815 или нет?

Обязательно. Только формулировать их нужно корректно ;)
Хотя можно решать, например, в теме о разных языках программирования. Можно будет сравнивать решения, представленные на разных языках.

Автор: AD 21.5.2009, 16:20

Цитата(D_K @ 21.5.2009, 17:15) *
Обязательно. Только формулировать их нужно корректно ;)
Хотя можно решать, например, в теме о разных языках программирования. Можно будет сравнивать решения, представленные на разных языках.

Да ладно к формулировке-то придираться! :)

А на счет второго пункта - нафиг. Лучше решать так задачки!

Эдик, создавай раздел. Ток не каждый день новую задачку помещай. Все-таки и работать надо! :)

Автор: ViGOur 21.5.2009, 16:22

Цитата(AD @ 21.5.2009, 17:20) *
Ток не каждый день новую задачку помещай. Все-таки и работать надо! :)
:lol:

Автор: D_K 21.5.2009, 16:25

Цитата(AD @ 21.5.2009, 17:20) *
Цитата(D_K @ 21.5.2009, 17:15) *
Обязательно. Только формулировать их нужно корректно ;)
Хотя можно решать, например, в теме о разных языках программирования. Можно будет сравнивать решения, представленные на разных языках.

Да ладно к формулировке-то придираться! :)

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

Автор: Tonal 21.5.2009, 20:49

Пошел не день рождения к знакомой пятикласнице - с ходу решила (про центры). :)

Автор: Litkevich Yuriy 21.5.2009, 20:51

Цитата(Tonal @ 22.5.2009, 0:49) *
Пошел не день рождения к знакомой пятикласнице - с ходу решила (про центры).
значит понимает, что изучает.

Автор: ViGOur 22.5.2009, 8:01

Цитата(Tonal @ 21.5.2009, 21:49) *
Пошел не день рождения к знакомой пятикласнице - с ходу решила (про центры). :)
Вот, что значит школа! :)

Автор: Tonal 22.5.2009, 10:49

Не, школа тут не причём.
Просто её родители самостоятельно занимаются воспитанием и образованием своих детей.
Школа хорошо если не мешает, да и то не всегда. :-\

Автор: Andrew Selivanov 29.5.2009, 10:11

Цитата(Litkevich Yuriy @ 20.5.2009, 21:00) *
Цитата(Andrew Selivanov @ 20.5.2009, 17:38) *
Вид боковой стороны торта...
а ведь это идея! Только зигзаг не нужен, просто горизонтальная линия

Зигзаг нужен, если начинка в глубину торта неоднородна (два слоя сгущёнки ближе к верхней части торта, твёрдый корж ближе к нижней) :)

Автор: ViGOur 29.5.2009, 11:44

Andrew Selivanov, ну уже выяснили какой правильный ответ, а в этом зигзаге еще минус в том, что у кого-то на один треугольник может быть меньше. Да и какой ювелирной точностью нужно обладать, чтобы так ровно вырезать. В правильном же ответе, это в разу проще. :)

Автор: scoute 25.12.2009, 17:25

Цитата(ViGOur @ 22.5.2009, 8:01) *
Цитата(Tonal @ 21.5.2009, 21:49) *
Пошел не день рождения к знакомой пятикласнице - с ходу решила (про центры). :)
Вот, что значит школа! :)

Это не школа, это сообразительность, привитая правильным воспитанием, +женский ум налету гибче почти всегда.


Вот выложил http://www.forum.crossplatform.ru/index.php?showtopic=4021, но немного другое решение там.

Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)