Ізде Алгоритм жолындағы есептерді шығарамын (Классикалық спорттық бағдарламалау. Бір жарым сағатта Java, C#, C++ немесе Python тілдерінде үш есепті шешу керек.)
1. Алтыға арналған бәліш
Мәселенің тұжырымы
Уақыт шегі - 4 секунд.
Сізде пирог бар. Жоғарыдан қарағанда, торт (қатаң) дөңес көпбұрыштың пішініне ие. Сізге X және Y бүтін сандарындағы шыңдардың координаталары берілген.
Сенің бес досың бар. Пирогты бірдей аумақтың алты бөлігіне бөлгіңіз келеді (бірақ бірдей пішінде болуы міндетті емес). Әрине, кез келген адам мұны бес кесуде жасай алады, бірақ оны үш кесуде тек кәсіби маман ғана жасай алады.
Пирогты алты тең бөлікке бөлетін бір нүкте арқылы түзу сызықтардағы үш кесінді табыңыз. {x, y, d1, d2, d3} басып шығарыңыз, мұндағы (x, y) барлық үш кесудің ортақ нүктесі, ал d1, d2, d3 - радиандағы қиықтардың бағыт бұрыштары.
анықтамаСынып: CakeForSix
Әдіс: кесу
Параметрлер: int[], int[] Қайтарады: double[] Әдіс қолтаңбасы: double[] cut(int[] x, int[] y)
(әдісіңіз жалпыға ортақ екеніне көз жеткізіңіз)
Ескертулер
- Х осі бойынша оң бағыт 0 (радиан), у осі бойынша оң бағыт pi/2 (радиан).
- d бағыттағы кесу кез келген k бүтін саны үшін pi*k+d бағыттағы кесуге ұқсас.
- Кез келген бағыттарды шығаруға болады, олар [0, pi) болуы міндетті емес.
- Грейдер сіздің алты дана тортыңыздың ауданын екі есе етіп есептейді. Жауап, егер олардың арасындағы салыстырмалы немесе абсолютті айырмашылық 10^(-4)-ден аз болса қабылданады.
- Дәлірек айтқанда, X және Y грейдер есептеген алты аймақтың ең кішісі және ең үлкені болсын. Сонда сіздің жауабыңыз қабылданады, егер Y
- (Мәселенің бастапқы нұсқасында 1e-7 орнына 1e-4 дәлдігі қолданылды. Мұрағаттағы бұл мәселені шешу үшін мәселені дәлдікпен шешу мүмкін емес ететін шақыру жағдайларының болуына байланысты дәлдік шегі төмендетілді. 1e-7. Идеал әлемде шектеулер мұндай жағдайларға жол бермейді және әлі де жоғары дәлдікті талап етеді, сондықтан мәселені кейбір жалпы сандық оңтайландыру арқылы шешу оңай емес.)
Шектеулер
- x құрамында 3-тен 50-ге дейін элементтер бар.
- y құрамында х сияқты элементтер саны бірдей.
- 0 мен 10 000 қоса алғанда арасындағы барлық координаттар
- x және y сағат тіліне қарсы бағытта дөңес көпбұрышты анықтайды.
ағылшын тілінде түпнұсқа
Проблемалық мәлімдеме
Уақыт шегі - 4 секунд.
Сізде торт бар. Жоғарыдан қарағанда, торт (қатаң) дөңес көпбұрыш болып табылады. Сізге оның төбелерінің координаталары int[]sx және y-де берілген.
Сенің бес досың бар. Енді тортты бірдей аумақтың алты бөлігіне кескіңіз келеді (бірақ міндетті түрде бірдей пішін емес). Әрине, кез келген адам мұны бес кесуде жасай алады, бірақ оны тек нағыз кәсіпқой үшеуінде жасай алады!
Тортты алты бірдей үлкен бөлікке кесетін бірдей нүкте арқылы өтетін үш түзу кесіндіні табыңыз. Қайтару {x, y, d1, d2, d3}, мұндағы (x, y) - үш кесіндінің ортақ нүктесі, ал d1, d2, d3 - олардың радиандағы бағыттары.
анықтама
Сынып: CakeForSix
Әдіс: кесу
Параметрлер: int[], int[] Қайтарады: double[] Әдіс қолтаңбасы: double[] cut(int[] x, int[] y)
(әдісіңіз жалпыға ортақ екеніне көз жеткізіңіз)
Ескертулер
— х осі бойынша оң бағыт 0 (радиан), у осі бойынша оң бағыт pi/2 (радиан).
— d бағыты бойынша кесу кез келген k бүтін саны үшін pi*k+d бағытындағы кесумен бірдей.
— Сіз кез келген бағытты қайтара аласыз, олар [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 элементтерінің саны х сияқты бірдей болады.
— Барлық координаттар 0 мен 10,000 XNUMX аралығында болады.
— 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