По стапките Објавувам проблеми од патеката Алгоритам (програмирање за класични спортови. За еден и пол час треба да решите три проблеми во Java, C#, C++ или Python.)
1. Пита за шест
Проблем изјава
Временското ограничување е 4 секунди.
Имаш пита. Кога се гледа одозгора, колачот има форма на (строго) конвексен многуаголник. Ви се дадени координатите на темињата во X и Y цели броеви.
Имаш пет пријатели. Сакате да ја поделите питата на шест парчиња со еднаква површина (но не мора иста форма). Се разбира, секој може да го направи тоа во пет намалувања, но само професионалец може да го направи тоа во три парчиња.
Пронајдете три засеци во прави линии низ една точка што ќе ја подели питата на шест еднакви делови. Печатете {x, y, d1, d2, d3}, каде што (x, y) е заедничка точка на сите три резови, а d1, d2, d3 се аглите на насоката на исечоците во радијани.
дефиницијаКласа: CakeForSix
Начин: сече
Параметри: int[], int[] Враќа: двојно[] Потпис на методот: двојно[] cut(int[] x, int[] y)
(проверете дали вашиот метод е јавен)
Белешки
- Позитивната насока по должината на оската x е 0 (радијани), позитивната насока долж y-оската е пи/2 (радијани).
- Сечењето во насока d е слично на пресекот во насока pi*k+d за кој било цел број k.
- Можете да излезете кои било насоки, тие не мора да бидат од [0, pi).
- Грејдерот ќе ја пресмета површината на вашите шест парчиња торта во двојки. Одговорот ќе биде прифатен ако релативната или апсолутната разлика меѓу нив е помала од 10^(-4).
- Поточно, X и Y нека бидат најмалите и најголемите од вашите шест области пресметани од одделението. Тогаш вашиот одговор ќе биде прифатен ако Y
- (Оригиналната верзија на проблемот користеше прецизност од 1e-7 наместо 1e-4. За да се реши овој проблем во архивата, границата на прецизност беше намалена поради присуството на случаи за повикување што веројатно би го направиле проблемот нерешлив со прецизност од 1e-7. Во идеален свет, границите не дозволуваат такви случаи и сè уште бараат висока прецизност, така што решавањето на проблемот со некоја општа нумеричка оптимизација не е лесно.)
Ограничувања
- x содржи од 3 до 50 елементи вклучително.
- y содржи ист број на елементи како и x.
- сите координати меѓу 0 и 10 вклучително
- x и y дефинираат конвексен многуаголник во спротивна насока од стрелките на часовникот.
оригинал на англиски
Изјава за проблем
Временското ограничување е 4 секунди.
Имаш торта. Гледано одозгора, колачот е (строго) конвексен многуаголник. Ви се дадени координатите на неговите темиња во int[]sx и y.
Имаш пет пријатели. Сега сакате да ја исечете тортата на шест парчиња со еднаква површина (но не мора да значи еднаква форма). Се разбира, секој може да го направи тоа во пет намалувања - но само вистински професионалец може да го направи тоа во три!
Пронајдете три резови со права линија што минуваат низ истата точка што ја сече тортата на шест подеднакво големи делови. Врати {x, y, d1, d2, d3}, каде што (x, y) е заедничката точка на трите пресеци, а d1, d2, d3 се нивните насоки во радијани.
дефиниција
Класа: CakeForSix
Начин: сече
Параметри: int[], int[] Враќа: двојно[] Потпис на методот: двојно[] cut(int[] x, int[] y)
(проверете дали вашиот метод е јавен)
забелешки
— Позитивната насока по оската x е 0 (радијани), позитивната насока долж оската y е пи/2 (радијани).
— Сечењето во насока d е исто како и пресекот во насока pi*k+d за кој било цел број k.
— Може да ги вратите сите насоки, тие не мора да бидат од [0,pi).
- Грејдерот ќе ги пресмета површините на вашите шест парчиња колачи во двојки. Одговорот ќе биде прифатен ако релативната или апсолутната разлика меѓу нив е помала од 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 корисници беа воздржани.
Извор: www.habr.com