Ayaq izlərində Problemləri Alqoritm trekindən dərc edirəm (klassik idman proqramlaşdırması. Bir saat yarım ərzində Java, C#, C++ və ya Python dillərində üç məsələni həll etməlisiniz.)
1. Altılıq tort
Problem problemi
Vaxt limiti 4 saniyədir.
Sizdə tort var. Yuxarıdan baxdıqda, tort (ciddi) qabarıq çoxbucaqlı formasına malikdir. Sizə X və Y tam ədədlərində təpələrin koordinatları verilir.
Beş dostunuz var. Piroqu bərabər sahədə altı hissəyə bölmək istəyirsiniz (lakin eyni formada olması şərt deyil). Əlbəttə ki, hər kəs bunu beş kəsikdə edə bilər, ancaq üç kəsikdə bunu yalnız peşəkar edə bilər.
Piroqu altı bərabər hissəyə böləcək bir nöqtədən keçən düz xətlərdə üç kəsik tapın. {x, y, d1, d2, d3} çap edin, burada (x, y) hər üç kəsimin ortaq nöqtəsidir, d1, d2, d3 isə radyanla kəsiklərin istiqamət bucaqlarıdır.
TərifSinif: CakeForSix
Metod: kəsmək
Parametrlər: int[], int[] Qaytarır: double[] Metod imzası: double[] cut(int[] x, int[] y)
(metodunuzun açıq olduğundan əmin olun)
Qeydlər
- X oxu boyunca müsbət istiqamət 0 (radian), y oxu boyunca müsbət istiqamət pi/2 (radian) təşkil edir.
- d istiqamətində kəsmə istənilən k tam ədədi üçün pi*k+d istiqamətində kəsimə bənzəyir.
- İstənilən istiqaməti çıxara bilərsiniz, onlar [0, pi) olmalıdır.
- Qreyder altı ədəd tortunuzun sahəsini ikiqat hesablayacaq. Aralarındakı nisbi və ya mütləq fərq 10^(-4)-dən az olarsa cavab qəbul ediləcək.
- Daha doğrusu, X və Y qreyder tərəfindən hesablanmış altı sahənizdən ən kiçik və ən böyüyü olsun. O zaman cavabınız Y olarsa qəbul olunacaq
- (Məsələnin orijinal versiyasında 1e-7 əvəzinə 1e-4 dəqiqliyindən istifadə edilib. Arxivdə bu problemi həll etmək üçün problemi dəqiqliklə həll olunmaz hala gətirəcək çağırış hallarının olması səbəbindən dəqiqlik həddi aşağı salındı. 1e-7. İdeal dünyada məhdudiyyətlər belə hallara imkan vermir və hələ də yüksək dəqiqlik tələb edir, ona görə də problemi bəzi ümumi ədədi optimallaşdırma ilə həll etmək asan deyil.)
Məhdudiyyətlər
- x 3-dən 50-yə qədər elementdən ibarətdir.
- y x ilə eyni sayda elementdən ibarətdir.
- 0 və 10 daxil olmaqla bütün koordinatlar
- x və y saat əqrəbinin əksi istiqamətində qabarıq çoxbucaqlı müəyyən edir.
Orijinal ingilis dilində
Problem bəyanat
Vaxt limiti 4 saniyədir.
Sizdə tort var. Yuxarıdan göründüyü kimi, tort (ciddi) qabarıq çoxbucaqlıdır. Sizə int[]sx və y-də onun təpələrinin koordinatları verilir.
Beş dostunuz var. İndi tortu altı bərabər hissəyə kəsmək istəyirsiniz (lakin eyni formada olması şərt deyil). Əlbəttə ki, hər kəs bunu beş kəsmədə edə bilər - ancaq əsl peşəkar bunu üçdə edə bilər!
Tortu altı bərabər böyük hissəyə kəsən eyni nöqtədən keçən üç düz xətt kəsikini tapın. Qayıdın {x, y, d1, d2, d3}, burada (x, y) üç kəsimin ortaq nöqtəsidir və d1, d2, d3 onların radyandakı istiqamətləridir.
Tərif
Sinif: CakeForSix
Metod: kəsmək
Parametrlər: int[], int[] Qaytarır: double[] Metod imzası: double[] cut(int[] x, int[] y)
(metodunuzun açıq olduğundan əmin olun)
Qeydlər
— X oxu boyunca müsbət istiqamət 0 (radian), y oxu boyunca müsbət istiqamət pi/2 (radian) təşkil edir.
— d istiqamətində kəsmə istənilən k tam ədədi üçün pi*k+d istiqamətində kəsmə ilə eynidir.
— İstənilən istiqaməti qaytara bilərsiniz, onlar [0,pi]-dən olmalıdır.
— Qreyder altı tort parçanızın sahələrini ikiqat hesablayacaq. Aralarındakı nisbi və ya mütləq fərq 10^(-4)-dən az olarsa cavab qəbul ediləcək.
— Daha doğrusu, qreyderin hesabladığı kimi, X və Y altı sahənizdən ən kiçiki və ən böyüyü olsun. Əgər Y < max( X + 10^(-4), X * (1+10^(-4)) ) olarsa, cavabınız qəbul ediləcək.
— (Məsələnin orijinal versiyasında 1e-7 yerinə 1e-4 dəqiqliyindən istifadə edilmişdir. Arxivdə bu problemi həll etmək üçün 1e-7 dəqiqliyi ilə tapşırığı həll etmək mümkün olmayan problem hallarının mövcudluğuna görə dəqiqlik həddi aşağı salındı. İdeal bir dünyada məhdudiyyətlər belə hallara imkan verməz və hələ də yüksək dəqiqlik tələb edir, belə ki, problemi bəzi ümumi ədədi optimallaşdırma ilə həll etmək asan deyil.)
Məhdudiyyətlər
— x daxil olmaqla 3 ilə 50 arasında elementə malik olacaq.
— y, x ilə eyni sayda elementə sahib olacaq.
— Bütün koordinatlar 0 ilə 10,000 arasında olacaq, daxil olmaqla.
— x və y qabarıq çoxbucaqlını saat əqrəbinin əksinə olaraq təsvir edəcək.
Nümunələr
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Returns:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Simmetrik, lakin nizamsız altıbucaqlı. Nümunə cavabı onu üfüqi olaraq yarıya kəsməyə və hər bir parçanı üç hissəyə bölən mərkəzdən iki digər kəsik etməyə uyğundur.
1)
{0, 1000, 0}
{0, 0, 1000}
Returns:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Sağ üçbucaq. Yenə də simmetriya oxu boyunca üç kəsikdən biri ilə başlaya bilərik.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Returns:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Düzensiz beşbucaqlı.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Qaytarır: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Kvadrat 45 dərəcə fırlandı.
[]
Sorğuda yalnız qeydiyyatdan keçmiş istifadəçilər iştirak edə bilər. xahiş edirəm.
üçün problemi həll etdim
-
10 dəqiqədən az müddətdə
-
10-30 dəqiqə
-
30-60 dəqiqə
-
1-2 saat
-
2 saatdan çox müddətdə
-
digər
42 istifadəçi səs verib. 47 istifadəçi bitərəf qalıb.
Mənbə: www.habr.com