در رد پای من مشکلات را از مسیر الگوریتم منتشر می کنم (برنامه نویسی ورزش های کلاسیک. در یک ساعت و نیم باید سه مسئله را در جاوا، سی شارپ، سی پلاس پلاس یا پایتون حل کنید.)
1. پای برای شش
بیانیه مشکل
محدودیت زمانی 4 ثانیه است.
شما یک پای دارید. وقتی از بالا نگاه کنید، کیک شکل یک چند ضلعی محدب (به شدت) دارد. مختصات رئوس در اعداد صحیح X و Y به شما داده می شود.
شما پنج دوست دارید. شما می خواهید پای را به شش تکه با مساحت مساوی (اما نه لزوماً یک شکل) تقسیم کنید. البته، هر کسی می تواند آن را در پنج برش انجام دهد، اما فقط یک حرفه ای می تواند آن را در سه برش انجام دهد.
سه برش در خطوط مستقیم از یک نقطه پیدا کنید که پای را به شش قسمت مساوی تقسیم کند. چاپ {x, y, d1, d2, d3} که (x,y) نقطه مشترک هر سه برش است و d1, d2, d3 زوایای جهت برش ها بر حسب رادیان هستند.
تعریفکلاس: CakeForSix
روش: برش
پارامترها: int[]، int[] برمی‌گرداند: double[] امضای روش: double[] cut(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[] برمی‌گرداند: double[] امضای روش: double[] cut(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)
{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