ការប្រកួតប្រជែង TopCoder Open 2019៖ កាត់នំជាប្រាំមួយបំណែក

នៅ​ក្នុង​ការ​បោះ​ជំហាន​ "របស់យើងបានឈ្នះ: TopCoder Open 2019" ខ្ញុំបោះផ្សាយបញ្ហាពីបទ Algorithm (កម្មវិធីកីឡាបុរាណ។ ក្នុងរយៈពេលមួយម៉ោងកន្លះ អ្នកត្រូវដោះស្រាយបញ្ហាបីនៅក្នុង Java, C#, C++ ឬ Python។)

1. ចំណិតសម្រាប់ប្រាំមួយ។

ការបង្កើតបញ្ហា

ពេលវេលាកំណត់គឺ 4 វិនាទី។

អ្នកមាននំមួយ។ នៅពេលមើលពីខាងលើ នំនេះមានរាងជាពហុកោណប៉ោង (យ៉ាងតឹងរ៉ឹង)។ អ្នក​ត្រូវ​បាន​ផ្ដល់​កូអរដោនេ​នៃ​ចំណុច​កំពូល​ក្នុង​ចំនួន X និង Y ។

អ្នកមានមិត្តប្រាំនាក់។ អ្នកចង់បែងចែកចំណិតទៅជាប្រាំមួយបំណែកនៃផ្ទៃដីស្មើគ្នា (ប៉ុន្តែមិនចាំបាច់មានរាងដូចគ្នាទេ) ។ ជាការពិតណាស់ នរណាម្នាក់អាចធ្វើវាបាន XNUMX ដង ប៉ុន្តែមានតែអ្នកជំនាញទេដែលអាចធ្វើវាបានបីដង។

ស្វែងរកការកាត់ចំនួនបីនៅក្នុងបន្ទាត់ត្រង់តាមរយៈចំណុចមួយដែលនឹងបែងចែកចំណិតជាប្រាំមួយផ្នែកស្មើគ្នា។ បោះពុម្ព {x, y, d1, d2, d3} ដែល (x, y) គឺជាចំណុចទូទៅនៃការកាត់ទាំងបី ហើយ d1, d2, d3 គឺជាមុំទិសដៅនៃការកាត់ជារ៉ាដ្យង់។

និយមន័យថ្នាក់៖ CakeForSix
វិធីសាស្រ្ត: កាត់
ប៉ារ៉ាម៉ែត្រ៖ int[], int[] ត្រឡប់៖ ទ្វេ[] ហត្ថលេខាវិធីសាស្ត្រ៖ ទ្វេ[] កាត់(int[] x, int[] y)
(ត្រូវប្រាកដថាវិធីសាស្ត្ររបស់អ្នកជាសាធារណៈ)

ចំណាំ

• ទិសដៅវិជ្ជមានតាមអ័ក្ស x គឺ 0 (រ៉ាដ្យង់) ទិសដៅវិជ្ជមានតាមអ័ក្ស y គឺ pi/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[] ត្រឡប់៖ ទ្វេ[] ហត្ថលេខាវិធីសាស្ត្រ៖ ទ្វេ[] កាត់(int[] x, int[] y)
(ត្រូវប្រាកដថាវិធីសាស្ត្ររបស់អ្នកជាសាធារណៈ)

ភក្ដិកំណត់ត្រាកំណត់
- ទិសដៅវិជ្ជមានតាមអ័ក្ស x គឺ 0 (រ៉ាដ្យង់) ទិសដៅវិជ្ជមានតាមអ័ក្ស y គឺ pi/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)

{៧, ៨, ៩}
{៧, ៨, ៩}
ត្រឡប់៖
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }

ត្រីកោណកែង។ ជាថ្មីម្តងទៀតយើងអាចចាប់ផ្តើមជាមួយនឹងការកាត់មួយក្នុងចំណោមបីកាត់តាមអ័ក្សស៊ីមេទ្រី។

2)

{៥០, ៥០, ៥០, ០, ០}
{៥០, ៥០, ៥០, ០, ០}
ត្រឡប់៖
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }

ប៉ង់តាហ្គោនមិនទៀងទាត់។

3)

{១០.០, ២៥.០, ៤៥.០, ៧០.០}
{១០.០, ២៥.០, ៤៥.០, ៧០.០}
ត្រឡប់មកវិញ៖ {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }

ការ៉េមួយបង្វិល 45 ដឺក្រេ។

[ប្រភព]

មានតែអ្នកប្រើប្រាស់ដែលបានចុះឈ្មោះប៉ុណ្ណោះដែលអាចចូលរួមក្នុងការស្ទង់មតិនេះ។ ចូលសូម។

ខ្ញុំបានដោះស្រាយបញ្ហាសម្រាប់

• ក្នុងរយៈពេលតិចជាង ៥ នាទី

• 10-30 នាទី

• 30-60 នាទី

• 1-2 ម៉ោង

• ក្នុងរយៈពេលជាង 2 ម៉ោង។

• ផ្សេងទៀត

អ្នកប្រើប្រាស់ 42 នាក់បានបោះឆ្នោត។ អ្នកប្រើប្រាស់ ៧៨ នាក់ត្រូវបានហាមឃាត់។

ប្រភព: www.habr.com