İzlərdə Alqoritm izlərindən tapşırıqları dərc edirəm (klassik idman proqramlaşdırması. Bir buçuk saat ərzində Java, C#, C++ və ya Python-da üç tapşırığı həll etmək lazımdır.)
1. Altılıq tort
Məsələnin qoyulması
Zaman limiti — 4 saniyə.
Sizin bir tortunuz var. Yuxarıdan baxanda tortun forması (strict) konveks çoxbucaqdır. Sizə tam ədədlərlə X və Y koordinatları verilmişdir.
Beş dostunuz var. Tortu altı bərabər sahəyə (amma mütləq eyni formada olmamaqla) bölmək istəyirsiniz. Təbii ki, bunu beş kəsimdə etmək mümkündür, amma yalnız bir peşəkar bunu üç kəsimdə edə bilər.
Eyni nöqtədən keçən üç düz xətt kəsimini tapın ki, tortu altı bərabər sahəyə bölür. {x, y, d1, d2, d3} qaytarın, burada (x, y) — bütün üç kəsimin ortaq nöqtəsi, d1, d2, d3 — kəsimlərin radianlardakı istiqamətləridir.
TəsnifatSinif: CakeForSix
Metod: cut
Parametrlər: int[], int[]
Qayıtma: double[]
Metod imzası: double[] cut(int[] x, int[] y)
(metodunuzun public 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) hesab edilir.
- d istiqamətində kəsim, hər hansı bir tam ədəd k üçün pi*k+d istiqamətində olan kəsimə bərabərdir.
- İstənilən istiqamətləri qayıda bilərsiniz, onlar mütləq [0, pi) intervalından olmalıdır.
- Qreyder kəsdiyiniz altı tort parçasının sahələrini double kimi hesablayacaq. Cavab, əgər aralarındakı nisbət və ya mütləq fərq 10^(-4) -dən kiçikdirsə qəbul ediləcək.
- Daha dəqiq, X və Y, qreyder tərəfindən hesablanmış altı sahənizin ən kiçik və ən böyük olanlarıdır. Onda cavabınız qəbul ediləcək, əgər Y < max (X+10^(-4), X*1+10^(-4))).
- (Məsələnin ilkin versiyasında dəqiqlik 1e-7 yerinə 1e-4 istifadə olunmuşdu. Bu problemdən yaranan ixtira qeyri-mümkün situasiyalara gətirib çıxardığı üçün arxivdə dəqiqlik həddi aşağı salındı. İdeal dünyada məhdudiyyətlər belə halları qadağan edir və hələ də yüksək dəqiqlik tələb edir, buna görə də bir ortaq sayısal optimizasiya ilə problemi həll etmək asan deyil.)
Məhdudiyyətlər
- x 3-dən 50 elementə qədər ola bilər, daxil olmaqla.
- y x ilə eyni sayda elementə malikdir.
- bütün koordinatlar 0-dan 10 000-ə qədər, daxil olmaqla
- x və y, saat əksinə dövr edərək konveks çoxbucağı təyin edir.
İngilis dilində orijinal
Problem Təsviri
Zaman limiti 4 saniyədir.
Sizin bir tortunuz var. Yuxarıdan baxanda tort (strict) konveks çoxbucaqdır. Sizə onun zirvələrinin koordinatları int[] x və y-də verilir.
Beş dostunuz var. İndi tortu altı bərabər sahədə (amma mütləq eyni formada olmamaqla) kəsmək istəyirsiniz. Təbii ki, bunu beş kəsimdə etmək mümkündür — amma yalnız bir həqiqi peşəkar bunu üçdə edə bilər!
Eyni nöqtədən keçən üç düz xətt kəsimini tapın ki, tortu altı eyni böyüklükdə parçalara kəsin. {x, y, d1, d2, d3} qaytarın, burada (x, y) üç kəsimin ortaq nöqtəsi, d1, d2, d3 isə onların radianlardakı istiqamətləridir.
Təsnifat
Sinif: CakeForSix
Metod: cut
Parametrlər: int[], int[]
Qayıtma: double[]
Metod imzası: double[] cut(int[] x, int[] y)
(metodunuzun public 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)dir.
— d istiqamətində olan kəsim, istənilən tam ədəd k üçün pi*k+d istiqamətində olan kəsimə bərabərdir.
— İstənilən istiqamətləri qayıda bilərsiniz, onlar mütləq [0, pi) intervalından olmamalıdır.
— Grader, altı pastanın alanlarını ondalık olarak hesaplayacaktır. Cevap, aralarındaki mutlak veya nispi fark 10^(-4)'ten azsa kabul edilecektir.
— Daha kesin olarak, X ve Y, grader tarafından hesaplanan altı alanınızın en küçüğü ve en büyüğüdür. Dolayısıyla, cevabınız Y < max(X + 10^(-4), X * (1+10^(-4))) ise kabul edilecektir.
— (Problemin orijinal versiyonu 1e-7 hassasiyet kullanıyordu, 1e-4 yerine. Bu arşivdeki problem için, çözülemeyen challenge durumlarının varlığı sebebiyle hassasiyet limiti düşürüldü. İdeal bir dünyada, kısıtlamalar böyle durumları engellemeli ve yine yüksek hassasiyet talep etmelidir, böylece problemi genel sayısal optimizasyonla çözmek kolay olmamalıdır.)
Kısıtlamalar
— x, 3 ile 50 arasında içerik barındırır, dahil.
— y, x ile aynı sayıda içerik barındıracaktır.
— Tüm koordinatlar 0 ile 10.000 arasında, dahil.
— x ve y, saat yönünün tersine sıralanmış bir konveks çokgeni tarif edecektir.
Nümunələr
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Dönen:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Simetrik ama düzgün olmayan bir altıgen. Örnek bir cevap, onu yatay olarak ikiye kesmek ve her parçayı üç parçaya bölen iki kesim daha yapmaktır.
1)
{0, 1000, 0}
{0, 0, 1000}
Dönen:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Dik üçgen. Yine, simetri ekseni boyunca üç kesimden birine başlayabiliriz.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Dönen:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Düzgün olmayan bir beşgen.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Dönen: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705}
45 derece döndürülmüş bir kare.
[]
Yalnız qeydiyyatdan keçmiş istifadəçilər sorğuda iştirak edə bilərlər. , xahiş edirəm.
Problemi çözdüm
10 dakikadan kısa sürede
10-30 dakika
30-60 dakika
1-2 saat
2 saatten fazla
diğer
41 kullanıcı oy kullandı. 47 kullanıcı çekimser kaldı.
Mənbə: habr.com
