پيچري تي آئون الگورٿم ٽريڪ مان مسئلا شايع ڪريان ٿو (ڪلاسيڪل اسپورٽس پروگرامنگ. اڌ ڪلاڪ ۾ توهان کي جاوا، C#، C++ يا Python ۾ ٽي مسئلا حل ڪرڻ گهرجن.)
1. ڇهن لاء پائي
مسئلو جي ترتيب
وقت جي حد 4 سيڪنڊ آهي.
توهان وٽ هڪ پائي آهي. جڏهن مٿي کان ڏٺو ويو، ڪيڪ هڪ (سخت) محدب قطب جي شڪل رکي ٿو. توهان کي X ۽ Y انٽيجرز ۾ عمودي جا همراه ڏنا ويا آهن.
توهان جا پنج دوست آهن. توھان چاھيو ٿا پائي کي ورهائڻ جي ڇھ ٽڪرن ۾ برابر علائقي جي (پر ضروري نه آھي ساڳي شڪل). يقينن، ڪو به اهو ڪري سگهي ٿو پنجن ڪٽ ۾، پر صرف هڪ پرو اهو ڪري سگهي ٿو ٽن ڪٽ ۾.
هڪ نقطي ذريعي سڌي لائين ۾ ٽي ڪٽ ڳوليو جيڪي پائي کي ڇهن برابر حصن ۾ ورهائيندا. ڇاپيو {x, y, d1, d2, d3}، جتي (x, y) ٽنهي ڪٽن جو عام نقطو آهي، ۽ d1، d2، d3 شعاعن ۾ ڪٽ جا طرفدار زاويه آهن.
سمجھاڻيڪلاس: ڪيڪ فار سيڪس
طريقو: ڪٽڻ
پيرا ميٽرس: int[]، int[] ريٽرن: ڊبل[] طريقو دستخط: ڊبل[] ڪٽ(int[] x، int[] y)
(پڪ ڪريو توهان جو طريقو عوامي آهي)
نوٽ
- x-axis سان گڏ مثبت طرف 0 (radians) آھي، y-axis سان گڏ مثبت طرف pi/2 (radians) آھي.
- ڊي سمت ۾ هڪ ڪٽ 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 انهن جون هدايتون شعاعن ۾ آهن.
سمجھاڻي
ڪلاس: ڪيڪ فار سيڪس
طريقو: ڪٽڻ
پيرا ميٽرس: int[]، int[] ريٽرن: ڊبل[] طريقو دستخط: ڊبل[] ڪٽ(int[] x، int[] y)
(پڪ ڪريو توهان جو طريقو عوامي آهي)
نوٽ
- x محور سان گڏ مثبت طرف 0 (ريڊين) آھي، y محور سان مثبت طرف آھي pi/2 (ريڊين).
- d ۾ هڪ ڪٽ ساڳيو آهي جيئن ڪنهن به انٽيجر k لاءِ طرف pi*k+d ۾ ڪٽ.
- توھان ڪي به ھدايتون واپس ڪري سگھو ٿا، انھن کي [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