پگڈنڈی پر۔ میں الگورتھم ٹریک سے مسائل شائع کرتا ہوں۔ (کلاسیکل اسپورٹس پروگرامنگ۔ ڈیڑھ گھنٹے میں آپ کو جاوا، C#، C++ یا Python میں تین مسائل حل کرنے ہوں گے۔)
1. چھ کے لیے پائی
مسئلہ کی تشکیل
وقت کی حد 4 سیکنڈ ہے۔
آپ کے پاس ایک پائی ہے۔ جب اوپر سے دیکھا جائے تو کیک کی شکل (سختی سے) محدب کثیرالاضلاع کی ہوتی ہے۔ آپ کو X اور Y انٹیجرز میں عمودی خطوط کے نقاط دیے گئے ہیں۔
آپ کے پانچ دوست ہیں۔ آپ پائی کو برابر علاقے کے چھ ٹکڑوں میں تقسیم کرنا چاہتے ہیں (لیکن ضروری نہیں کہ ایک ہی شکل ہو)۔ بے شک، کوئی بھی اسے پانچ کٹس میں کر سکتا ہے، لیکن صرف ایک پرو اسے تین کٹس میں کر سکتا ہے۔
ایک نقطہ کے ذریعے سیدھی لائنوں میں تین کٹ تلاش کریں جو پائی کو چھ برابر حصوں میں تقسیم کرے گا۔ پرنٹ کریں {x, y, d1, d2, d3}، جہاں (x, y) تینوں کٹ کا مشترکہ نقطہ ہے، اور d1، d2، d3 ریڈینز میں کٹوتیوں کے سمت زاویہ ہیں۔
ڈیفینیشنکلاس: کیک فار سکس
طریقہ: کاٹ لیں۔
پیرامیٹرز: int[], int[] ریٹرن: ڈبل[] طریقہ دستخط: double[] cut(int[] x, int[] y)
(یقینی بنائیں کہ آپ کا طریقہ عوامی ہے)
نوٹس
- x-axis کے ساتھ مثبت سمت 0 (radians) ہے، y-axis کے ساتھ مثبت سمت pi/2 (ریڈینز) ہے۔
- d سمت میں کٹ کسی بھی عدد k کے لیے pi*k+d سمت میں کٹ کی طرح ہے۔
- آپ کسی بھی سمت کو آؤٹ پٹ کر سکتے ہیں، ان کا [0، pi) سے ہونا ضروری نہیں ہے۔
- گریڈر آپ کے کیک کے چھ ٹکڑوں کے رقبے کو ڈبلز میں شمار کرے گا۔ جواب قبول کیا جائے گا اگر ان کے درمیان رشتہ دار یا مطلق فرق 10^(-4) سے کم ہو۔
- مزید واضح طور پر، X اور Y کو گریڈر کے حساب سے آپ کے چھ علاقوں میں سب سے چھوٹا اور سب سے بڑا ہونے دیں۔ پھر آپ کا جواب قبول کیا جائے گا اگر Y
- (مسئلہ کے اصل ورژن میں 1e-7 کے بجائے 1e-4 کی درستگی کا استعمال کیا گیا ہے۔ محفوظ شدہ دستاویزات میں اس مسئلے کو حل کرنے کے لیے، کالنگ کیسز کی موجودگی کی وجہ سے درستگی کی حد کو کم کر دیا گیا تھا جو ممکنہ طور پر درستگی کے ساتھ مسئلہ کو ناقابل حل بنا دے گا۔ ایک مثالی دنیا میں، حدیں ایسے معاملات کی اجازت نہیں دیتی ہیں اور پھر بھی زیادہ درستگی کی ضرورت ہوتی ہے، اس لیے کچھ عمومی عددی اصلاح کے ساتھ مسئلہ کو حل کرنا آسان نہیں ہے۔)
پابندیاں
- 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[] ریٹرن: ڈبل[] طریقہ دستخط: double[] cut(int[] x, int[] y)
(یقینی بنائیں کہ آپ کا طریقہ عوامی ہے)
نوٹس
- ایکس محور کے ساتھ مثبت سمت 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