ടോപ്‌കോഡർ ഓപ്പൺ 2019 വെല്ലുവിളി: പൈ ആറ് കഷണങ്ങളായി മുറിക്കുക

നടപ്പാതയിൽ “ഞങ്ങൾ വിജയിച്ചു: ടോപ്‌കോഡർ ഓപ്പൺ 2019” അൽഗോരിതം ട്രാക്കിൽ നിന്നുള്ള പ്രശ്നങ്ങൾ ഞാൻ പ്രസിദ്ധീകരിക്കുന്നു (ക്ലാസിക്കൽ സ്പോർട്സ് പ്രോഗ്രാമിംഗ്. ഒന്നര മണിക്കൂറിനുള്ളിൽ നിങ്ങൾ ജാവ, C#, C++ അല്ലെങ്കിൽ പൈത്തൺ എന്നിവയിലെ മൂന്ന് പ്രശ്നങ്ങൾ പരിഹരിക്കേണ്ടതുണ്ട്.)

1. ആറിന് പൈ

പ്രശ്ന പ്രസ്താവന

സമയപരിധി 4 സെക്കൻഡാണ്.

നിങ്ങൾക്ക് ഒരു പൈ ഉണ്ട്. മുകളിൽ നിന്ന് നോക്കുമ്പോൾ, കേക്കിന് (കർശനമായി) കുത്തനെയുള്ള ബഹുഭുജത്തിന്റെ ആകൃതിയുണ്ട്. നിങ്ങൾക്ക് X, Y പൂർണ്ണസംഖ്യകളിലെ ലംബങ്ങളുടെ കോർഡിനേറ്റുകൾ നൽകിയിരിക്കുന്നു.

നിങ്ങൾക്ക് അഞ്ച് സുഹൃത്തുക്കളുണ്ട്. നിങ്ങൾ പൈയെ തുല്യ വിസ്തീർണ്ണമുള്ള ആറ് കഷണങ്ങളായി വിഭജിക്കാൻ ആഗ്രഹിക്കുന്നു (എന്നാൽ ഒരേ ആകൃതിയിൽ ആയിരിക്കണമെന്നില്ല). തീർച്ചയായും, ആർക്കുവേണമെങ്കിലും അഞ്ച് കട്ട് ആയി ഇത് ചെയ്യാൻ കഴിയും, എന്നാൽ ഒരു പ്രോക്ക് മാത്രമേ മൂന്ന് കട്ടുകളിൽ ഇത് ചെയ്യാൻ കഴിയൂ.

പൈയെ ആറ് തുല്യ ഭാഗങ്ങളായി വിഭജിക്കുന്ന ഒരു പോയിന്റിലൂടെ നേർരേഖയിൽ മൂന്ന് മുറിവുകൾ കണ്ടെത്തുക. പ്രിന്റ് {x, y, d1, d2, d3}, ഇവിടെ (x, y) മൂന്ന് മുറിവുകളുടെയും പൊതുവായ പോയിന്റാണ്, കൂടാതെ d1, d2, d3 എന്നിവയാണ് റേഡിയനുകളിലെ മുറിവുകളുടെ ദിശാകോണുകൾ.

നിര്വചനംക്ലാസ്: CakeForSix
രീതി: മുറിക്കുക
പാരാമീറ്ററുകൾ: int[], int[] റിട്ടേണുകൾ: ഇരട്ട[] രീതി ഒപ്പ്: ഇരട്ട[] കട്ട് (int[] x, int[] y)
(നിങ്ങളുടെ രീതി പൊതുവായതാണെന്ന് ഉറപ്പാക്കുക)

കുറിപ്പുകൾ

• x-അക്ഷത്തിനൊപ്പം പോസിറ്റീവ് ദിശ 0 ആണ് (റേഡിയൻസ്), y-അക്ഷത്തിനൊപ്പം പോസിറ്റീവ് ദിശ പൈ/2 (റേഡിയൻസ്) ആണ്.
• d ദിശയിലുള്ള ഒരു കട്ട്, ഏതെങ്കിലും പൂർണ്ണസംഖ്യ k യുടെ pi*k+d ദിശയിലുള്ള ഒരു കട്ട് പോലെയാണ്.
• നിങ്ങൾക്ക് ഏത് ദിശകളും ഔട്ട്‌പുട്ട് ചെയ്യാൻ കഴിയും, അവ [0, pi) ൽ നിന്ന് ആയിരിക്കണമെന്നില്ല.
• ഗ്രേഡർ നിങ്ങളുടെ ആറ് കേക്കിന്റെ വിസ്തീർണ്ണം ഇരട്ടിയായി കണക്കാക്കും. അവ തമ്മിലുള്ള ആപേക്ഷികമോ കേവലമോ ആയ വ്യത്യാസം 10^(-4) ൽ കുറവാണെങ്കിൽ ഉത്തരം സ്വീകരിക്കും.
• കൂടുതൽ കൃത്യമായി പറഞ്ഞാൽ, ഗ്രേഡർ കണക്കാക്കിയ നിങ്ങളുടെ ആറ് ഏരിയകളിൽ ഏറ്റവും ചെറുതും വലുതുമായത് X ഉം Y ഉം ആകട്ടെ. Y എങ്കിൽ നിങ്ങളുടെ ഉത്തരം സ്വീകരിക്കപ്പെടും
• (പ്രശ്നത്തിന്റെ യഥാർത്ഥ പതിപ്പ് 1e-7-ന് പകരം 1e-4 ന്റെ കൃത്യതയാണ് ഉപയോഗിച്ചത്. ആർക്കൈവിൽ ഈ പ്രശ്നം പരിഹരിക്കാൻ, ഒരു കൃത്യതയോടെ പ്രശ്നം പരിഹരിക്കാനാകാത്തതാക്കാൻ സാധ്യതയുള്ള കോളിംഗ് കേസുകൾ ഉള്ളതിനാൽ കൃത്യമായ പരിധി കുറച്ചു. 1e-7. ഒരു അനുയോജ്യമായ ലോകത്ത്, പരിധികൾ അത്തരം സന്ദർഭങ്ങളെ അനുവദിക്കുന്നില്ല, ഇപ്പോഴും ഉയർന്ന കൃത്യത ആവശ്യമാണ്, അതിനാൽ പൊതുവായ ചില സംഖ്യാ ഒപ്റ്റിമൈസേഷൻ ഉപയോഗിച്ച് പ്രശ്നം പരിഹരിക്കുന്നത് എളുപ്പമല്ല.)

നിയന്ത്രണങ്ങൾ

• x-ൽ 3 മുതൽ 50 വരെയുള്ള ഘടകങ്ങൾ ഉൾപ്പെടുന്നു.
• x ന്റെ അതേ എണ്ണം മൂലകങ്ങൾ y-ൽ അടങ്ങിയിരിക്കുന്നു.
• 0 മുതൽ 10 വരെയുള്ള എല്ലാ കോർഡിനേറ്റുകളും ഉൾപ്പെടുന്നു
• x, y എന്നിവ എതിർ ഘടികാരദിശയിൽ ഒരു കോൺവെക്സ് ബഹുഭുജത്തെ നിർവ്വചിക്കുന്നു.

ഒറിജിനൽ ഇംഗ്ലീഷിൽ

പ്രശ്നം പ്രസ്താവന

സമയ പരിധി 4 സെക്കൻഡ് ആണ്.

നിങ്ങൾക്ക് ഒരു കേക്ക് ഉണ്ട്. മുകളിൽ നിന്ന് നോക്കിയാൽ, കേക്ക് ഒരു (കർശനമായി) കുത്തനെയുള്ള ബഹുഭുജമാണ്. നിങ്ങൾക്ക് അതിന്റെ ശീർഷകങ്ങളുടെ കോർഡിനേറ്റുകൾ int[]sx, y എന്നിവയിൽ നൽകിയിരിക്കുന്നു.

നിങ്ങൾക്ക് അഞ്ച് സുഹൃത്തുക്കളുണ്ട്. നിങ്ങൾ ഇപ്പോൾ കേക്ക് തുല്യ വിസ്തീർണ്ണമുള്ള ആറ് കഷ്ണങ്ങളാക്കി മുറിക്കാൻ ആഗ്രഹിക്കുന്നു (എന്നാൽ തുല്യ ആകൃതി അല്ല). തീർച്ചയായും, ആർക്കുവേണമെങ്കിലും അത് അഞ്ച് മുറികളിൽ ചെയ്യാൻ കഴിയും - എന്നാൽ ഒരു യഥാർത്ഥ പ്രൊഫഷണലിന് മാത്രമേ ഇത് മൂന്നിൽ ചെയ്യാൻ കഴിയൂ!

കേക്ക് ആറ് തുല്യ ഭാഗങ്ങളായി മുറിച്ച അതേ പോയിന്റിലൂടെ കടന്നുപോകുന്ന മൂന്ന് നേർരേഖയിലുള്ള മുറിവുകൾ കണ്ടെത്തുക. റിട്ടേൺ {x, y, d1, d2, d3}, ഇവിടെ (x, y) മൂന്ന് മുറിവുകളുടെ പൊതു പോയിന്റും d1, d2, d3 എന്നിവ റേഡിയനുകളിൽ അവയുടെ ദിശകളുമാണ്.

നിര്വചനം

ക്ലാസ്: CakeForSix
രീതി: മുറിക്കുക
പാരാമീറ്ററുകൾ: int[], int[] റിട്ടേണുകൾ: ഇരട്ട[] രീതി ഒപ്പ്: ഇരട്ട[] കട്ട് (int[] x, int[] y)
(നിങ്ങളുടെ രീതി പൊതുവായതാണെന്ന് ഉറപ്പാക്കുക)

കുറിപ്പുകൾ
— x അക്ഷത്തിനൊപ്പം പോസിറ്റീവ് ദിശ 0 (റേഡിയൻസ്), y അക്ഷത്തിൽ പോസിറ്റീവ് ദിശ 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 ന് 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-മിനിറ്റ് മിനിറ്റ്

• 1-XNUM മണിക്കൂറുകൾ

• 2 മണിക്കൂറിൽ കൂടുതൽ

• മറ്റുള്ളവ

42 ഉപയോക്താക്കൾ വോട്ട് ചെയ്തു. 47 ഉപയോക്താക്കൾ വിട്ടുനിന്നു.

അവലംബം: www.habr.com