Ardından Algoritma yolundan sorunları yayınlıyorum (klasik spor programlaması. Bir buçuk saat içinde Java, C#, C++ veya Python'da üç problemi çözmeniz gerekir.)
1. Altı kişilik pasta
Sorunun formüle edilmesi
Zaman sınırı 4 saniyedir.
Bir pastan var. Yukarıdan bakıldığında pasta (kesinlikle) dışbükey bir çokgen şekline sahiptir. X ve Y tamsayılarında köşelerin koordinatları size verilir.
Beş arkadaşın var. Pastayı eşit alana sahip altı parçaya bölmek istiyorsunuz (ancak aynı şekle sahip olması şart değil). Elbette herkes bunu beş kesimde yapabilir, ancak yalnızca bir profesyonel bunu üç kesimde yapabilir.
Pastayı altı eşit parçaya bölecek bir noktadan geçen düz çizgiler halinde üç kesik bulun. {x, y, d1, d2, d3}'ü yazdırın; burada (x, y), üç kesimin ortak noktasıdır ve d1, d2, d3, kesimlerin radyan cinsinden yön açılarıdır.
TanımSınıf: CakeForSix
Yöntem:kes
Parametreler: int[], int[] Döndürür: double[] Yöntem imzası: double[] Cut(int[] x, int[] y)
(yönteminizin herkese açık olduğundan emin olun)
Notlar
- X ekseni boyunca pozitif yön 0'dır (radyan), y ekseni boyunca pozitif yön ise pi/2'dir (radyan).
- Herhangi bir k tamsayısı için d yönündeki bir kesme, pi*k+d yönündeki bir kesmeye benzer.
- Herhangi bir yönün çıktısını alabilirsiniz; bunların [0, pi) aralığında olması gerekmez.
- Sınıflandırıcı altı dilim pastanızın alanını çiftler halinde hesaplayacaktır. Aralarındaki göreceli veya mutlak fark 10^(-4)'ten az ise cevap kabul edilecektir.
- Daha doğrusu, X ve Y, sınıflayıcı tarafından hesaplanan altı alanınızın en küçüğü ve en büyüğü olsun. O zaman cevabınız Y ise kabul edilecektir.
- (Sorunun orijinal versiyonu 1e-7 yerine 1e-4 hassasiyetini kullanıyordu. Arşivdeki bu sorunu çözmek için, sorunu muhtemelen hassasiyetle çözülemez hale getirecek çağrı durumlarının varlığı nedeniyle hassasiyet sınırı düşürüldü. İdeal bir dünyada, limitler bu tür durumlara izin vermez ve yine de yüksek hassasiyet gerektirir, bu nedenle problemi bazı genel sayısal optimizasyonlarla çözmek kolay değildir.)
Kısıtlamalar
- x, 3'ten 50'ye kadar öğe içerir.
- y, x ile aynı sayıda öğe içerir.
- 0 ile 10 arasındaki tüm koordinatlar (dahil)
- x ve y saat yönünün tersine bir dışbükey çokgen tanımlar.
İngilizce orijinali
Sorun bildirimi
Zaman sınırı 4 saniyedir.
Bir pastan var. Yukarıdan bakıldığında, pasta (kesinlikle) dışbükey bir çokgendir. int[]sx ve y'deki köşelerinin koordinatları size verilir.
Beş arkadaşın var. Şimdi pastayı eşit alana sahip altı parçaya kesmek istiyorsunuz (ancak eşit şekilde olması gerekmez). Elbette herkes bunu beş kesimde yapabilir; ancak yalnızca gerçek bir profesyonel bunu üç kesimde yapabilir!
Pastayı altı eşit büyük parçaya bölen aynı noktadan geçen üç düz çizgi kesiği bulun. {x, y, d1, d2, d3} değerini döndürün; burada (x, y) üç kesimin ortak noktasıdır ve d1, d2, d3 bunların radyan cinsinden yönleridir.
Tanım
Sınıf: CakeForSix
Yöntem:kes
Parametreler: int[], int[] Döndürür: double[] Yöntem imzası: double[] Cut(int[] x, int[] y)
(yönteminizin herkese açık olduğundan emin olun)
notlar
— X ekseni boyunca pozitif yön 0 (radyan), y ekseni boyunca pozitif yön ise pi/2'dir (radyan).
— Herhangi bir k tamsayısı için d yönündeki bir kesme, pi*k+d yönündeki bir kesmeyle aynıdır.
— Herhangi bir yöne dönebilirsiniz, bunların [0,pi)'den olması gerekmez.
— Sınıflandırıcı altı kek parçanızın alanlarını çiftler halinde hesaplayacaktır. Aralarındaki göreceli veya mutlak fark 10^(-4)'ten az ise cevap kabul edilecektir.
— Daha doğrusu, X ve Y'nin, not veren tarafından hesaplanan altı alanınızın en küçüğü ve en büyüğü olmasına izin verin. Daha sonra Y < max( X + 10^(-4), X * (1+10^(-4)) ) ise cevabınız kabul edilecektir.
— (Problemin orijinal versiyonu 1e-7 yerine 1e-4 hassasiyeti kullanıyordu. Arşivdeki bu sorunu çözmek için, görevi büyük olasılıkla 1e-7 hassasiyetle çözülemez hale getiren zorluk durumlarının varlığı nedeniyle hassasiyet sınırı düşürüldü. İdeal bir dünyada, kısıtlamalar bu tür durumlara izin vermez ve yine de yüksek hassasiyet gerektirir, dolayısıyla sorunu genel sayısal optimizasyon yoluyla çözmek kolay değildir.)
Kısıtlamalar
— x'in 3 ile 50 arasında öğesi olacaktır.
— y, x ile aynı sayıda öğeye sahip olacaktır.
— Tüm koordinatlar 0 ile 10,000 (dahil) arasında olacaktır.
— x ve y, saat yönünün tersine bir dışbükey çokgeni tanımlayacaktır.
Örnekler
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
İade:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Simetrik fakat düzensiz bir altıgen. Örnek cevap, onu yatay olarak ikiye kesmeye ve her parçayı üç parçaya bölen ortayı iki kez daha kesmeye karşılık gelir.
1)
{0, 1000, 0}
{0, 0, 1000}
İade:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Sağ üçgen. Yine simetri ekseni boyunca üç kesimden biriyle başlayabiliriz.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
İade:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Düzensiz beşgen.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Döndürür: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
45 derece döndürülmüş bir kare.
[]
Ankete sadece kayıtlı kullanıcılar katılabilir. Lütfen.
için sorunu çözdüm
-
10 dakikadan daha kısa sürede
-
10-30 dakika
-
30-60 dakika
-
1-2 saat
-
2 saatten fazla bir sürede
-
diğer
42 kullanıcı oy kullandı. 47 kişi çekimser kaldı.
Kaynak: habr.com