По следам публикую задачи с трека Algorithm (классическо спортно програмиране. За един час и половина трябва да решите три задачи на Java, C#, C++ или Python.)
1. Торта за шестима
Формулиране на задачата
Времеви лимит — 4 секунди.
Имате торта. Ако я гледате отгоре, тортата има форма (строго) изпъкнал многоъгълник. Дават ви координати на върховете в цели числа X и Y.
Имате пет приятели. Искате да разделите тортата на шест равни части (но не непременно с еднаква форма). Разбира се, всеки може да го направи с пет разреза, но само професионалист може да направи това с три разреза.
Намерете три разреза с прави линии, преминаващи през една точка, които разделят тортата на шест равни по площ части. Изведете {x, y, d1, d2, d3}, където (x, y) е общата точка на трите разреза, а d1, d2, d3 са ъглите на направление на разрезите в радиани.
ОпределениеКлас: CakeForSix
Метод: cut
Параметри: int[], int[]
Връща: double[]
Подпис на метода: double[] cut(int[] x, int[] y)
(уверете се, че методът ви е публичен)
Бележки
- Положителното направление по ос x е 0 (радиан), положителното направление по ос y е pi/2 (радиан).
- Разрез в посока d е аналогичен на разрез в посока pi*k+d за всяко цяло число k.
- Можете да извеждате всякакви направления, те не е задължително да бъдат от [0, pi).
- Грейдерът ще изчисли площите на вашите шест парчета торта в doubles. Отговорът ще бъде приет, ако относителната или абсолютната разлика между тях е по-малка от 10^(-4).
- По-точно, нека X и Y бъдат най-малките и най-големите от вашите шест области, изчислени от грейсера. Тогава вашият отговор ще бъде приет, ако Y < max (X + 10^(-4), X * 1 + 10^(-4))).
- (В първоначалната версия на задачата се използваше точност 1e-7 вместо 1e-4. За решаването на този проблем в архива пределът на точността беше намален поради наличието на случаи на извикване, които вероятно правят задачата неразрешима с точност 1e-7. В идеалния свят ограниченията не допускат такива случаи и все още изискват висока точност, така че решаването на проблема с помощта на обща числова оптимизация не е лесно.)
Ограничения
- x съдържа от 3 до 50 елемента включително.
- y съдържа толкова елементи, колкото и x.
- всички координати между 0 и 10 000 включително
- x и y задават изпъкнал многоъгълник в посока против часовниковата стрелка.
Оригинал на английски
Изложение на проблема
Времеви лимит е 4 секунди.
Имаш торта. Виждана отгоре, тортът е (строго) изпъкнал многоъгълник. Дадени са ти координатите на върховете му в int[]s x и y.
Имаш пет приятели. Сега искаш да нарежеш тортата на шест парчета с равна площ (но не задължително с равна форма). Разбира се, всеки може да го направи за пет разреза — но само истински професионалист може да го направи за три!
Намери три прави разреза, преминаващи през една и съща точка, които разделят тортата на шест равни части. Върни {x, y, d1, d2, d3}, където (x, y) е общата точка на трите разреза, а d1, d2, d3 са техните направления в радиани.
Определение
Клас: CakeForSix
Метод: cut
Параметри: int[], int[]
Връща: double[]
Подпис на метода: double[] cut(int[] x, int[] y)
(уверете се, че методът ви е публичен)
Забележки
— Положителното направление по ос x е 0 (радиани), положителното направление по ос y е pi/2 (радиани).
— Разрезът в направление d е същият като разрезът в направление pi*k+d за всяко цяло число k.
— Можеш да върнеш всякакви направления, те не трябва да са от [0,pi).
— Оценяващият ще изчисли площите на шестте парчета торта в тип double. Отговорът ще бъде приет, ако относителната или абсолютната разлика между тях е по-малка от 10^(-4).
— По-конкретно, нека X и Y бъдат най-малката и най-голямата от шестте ти площи, както е изчислено от оценяващия. Тогава, твоят отговор ще бъде приет, ако Y < max(X + 10^(-4), X * (1 + 10^(-4))).
— (Оригиналната версия на задачата използваше прецизност 1e-7 вместо 1e-4. За решаването на тази задача в архива, лимитът на прецизност беше понижен поради наличието на предизвикателни случаи, които най-вероятно правят задачата неразрешима с прецизност 1e-7. В идеалния свят ограниченията не биха позволили такива случаи и биха изисквали висока прецизност, така че да не е лесно да се реши задачата чрез обща числена оптимизация.)
Ограничения
— x ще има между 3 и 50 елемента, включително.
— y ще има същия брой елементи като x.
— Всички координати ще бъдат между 0 и 10,000, включително.
— x и y ще опишат изпъкнал многоъгълник в посока против часовниковата стрелка.
Примери
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Връща:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Симетричен, но не правилен шестоъгълник. Примерното решение отговаря на разрязването му наполовина по хоризонтала и изпълнението на два други разреза по центъра, които разделят всяка част на три.
1)
{0, 1000, 0}
{0, 0, 1000}
Връща:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Правоъгълен триъгълник. Отново можем да започнем с един от трите разреза по ос на симетрия.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Връща:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Неправилен петъгълник.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Връща: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Квадрат, завъртян на 45 градуса.
[]
Само регистрирани потребители могат да участват в анкетата. , моля.
Реших задачата за
по-малко от 10 минути
10-30 минути
30-60 минути
1-2 часа
повече от 2 часа
друго
Гласували 42 потребителя. Въздържали се 47 потребители.
Източник: habr.com
