בעקבות אני מפרסם בעיות ממסלול האלגוריתם (תכנות ספורט קלאסי. תוך שעה וחצי אתה צריך לפתור שלוש בעיות ב-Java, C#, C++ או Python.)
1. פאי לשישה
הצהרת הבעיה
מגבלת הזמן היא 4 שניות.
יש לך פאי. כאשר הוא נצפה מלמעלה, לעוגה יש צורה של מצולע קמור (בקפדנות). נותנים לך את הקואורדינטות של הקודקודים ב- X ו- Y מספרים שלמים.
יש לך חמישה חברים. אתה רוצה לחלק את העוגה לשישה חתיכות שטח שווה (אך לאו דווקא אותה צורה). כמובן שכל אחד יכול לעשות את זה בחמישה חתכים, אבל רק מקצוען יכול לעשות זאת בשלושה חתכים.
מצא שלושה חתכים בקו ישר דרך נקודה אחת שתחלק את הפאי לשישה חלקים שווים. הדפס {x, y, d1, d2, d3}, כאשר (x, y) היא הנקודה המשותפת של כל שלושת החיתוכים, ו-d1, d2, d3 הן זוויות הכיוון של החיתוכים ברדיאנים.
הַגדָרָהכיתה: CakeForSix
שיטה: לחתוך
פרמטרים: int[], int[] מחזירה: double[] חתימת שיטה: double[] cut(int[] x, int[] y)
(ודא שהשיטה שלך ציבורית)
הערות
- הכיוון החיובי לאורך ציר ה-x הוא 0 (רדיאנים), הכיוון החיובי לאורך ציר ה-y הוא pi/2 (רדיאנים).
- חיתוך בכיוון d דומה לחיתוך בכיוון pi*k+d עבור כל מספר שלם k.
- אתה יכול להוציא כל כיוון, הם לא חייבים להיות מ-[0, pi).
- המחלקה תחשב את השטח של שש חתיכות העוגה שלך בכפולות. התשובה תתקבל אם ההפרש היחסי או המוחלט ביניהם קטן מ-10^(-4).
- ליתר דיוק, תן ל-X ול-Y להיות השטחים הקטנים והגדולים ביותר מבין ששת השטחים שלך שחושב על ידי המדרג. אז תתקבל תשובתך אם י
- (הגרסה המקורית של הבעיה השתמשה בדיוק של 1E-7 במקום 1E-4. כדי לפתור בעיה זו בארכיון, גבול הדיוק הורד בגלל נוכחותם של מקרי שיחה שעשויים להפוך את הבעיה ללא פתרונות לדיוק של 1E-7. בעולם אידיאלי, המגבלות אינן מאפשרות מקרים כאלה ועדיין דורשים דיוק גבוה, ולכן פתרון הבעיה עם אופטימיזציה מספרית כללית אינה קלה.)
הגבלות
- x מכיל בין 3 ל-50 אלמנטים כולל.
- y מכיל את אותו מספר אלמנטים כמו x.
- כל הקואורדינטות בין 0 ל-10 כולל
- x ו- y מגדירים מצולע קמור בכיוון נגד כיוון השעון.
מקורי באנגלית
הצהרת בעיה
מגבלת הזמן היא 4 שניות.
יש לך עוגה. במבט מלמעלה, העוגה היא מצולע קמור (באופן מוחלט). אתה מקבל את הקואורדינטות של הקודקודים שלו ב-int[]sx ו-y.
You have five friends. כעת אתה רוצה לחתוך את העוגה לשש חתיכות שטח שווה (אך לאו דווקא צורה שווה). Of course, anyone can do that in five cuts — but only a true pro can do it in three!
מצא שלושה חתכים בקו ישר העוברים באותה נקודה שחתכים את העוגה לששה חלקים גדולים לא פחות. חזור {x, y, d1, d2, d3}, כאשר (x, y) הוא הנקודה הנפוצה של שלושת החיתוכים, ו- d1, d2, d3 הם כיווניהם ברדיאנים.
הַגדָרָה
כיתה: CakeForSix
שיטה: לחתוך
פרמטרים: int[], int[] מחזירה: double[] חתימת שיטה: double[] cut(int[] x, int[] y)
(ודא שהשיטה שלך ציבורית)
הערות
- הכיוון החיובי לאורך ציר ה- X הוא 0 (רדיאנים), הכיוון החיובי לאורך ציר ה- Y הוא pi/2 (רדיאנים).
— חיתוך בכיוון d זהה לחיתוך בכיוון pi*k+d עבור כל מספר שלם k.
- אתה יכול להחזיר כל כיוון, הם לא חייבים להיות מ-[0,pi).
- תלמיד כיתה יחשב את אזורי ששת חתיכות העוגה שלך בזוגות. התשובה תתקבל אם ההבדל היחסי או המוחלט ביניהם הוא פחות מ -10^(-4).
- ליתר דיוק, תן ל- x ו- y להיות הקטנים והגדולים מבין ששת האזורים שלך, כפי שמחושב על ידי תלמיד כיתה. לאחר מכן, תשובתך תתקבל אם y <max (x + 10^(-4), x * (1 + 10^(-4))).
-(הגרסה המקורית של הבעיה בה נעשה שימוש ב- 1E-7 דיוק במקום 1E-4. לפתרון בעיה זו בארכיון, גבול הדיוק הורד בגלל קיומם של מקרי אתגר שסביר להניח שהפך את המשימה לבלתי ניתנת לפתרון עם 1E-7 Precision בעולם אידיאלי האילוצים לא יאפשרו מקרים כאלה ועדיין דורשים דיוק גבוה, כך שלא קל לפתור את הבעיה באמצעות אופטימיזציה מספרית כללית.)
אילוצים
- ל- 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 שעות
-
תוך יותר משעתיים
-
אחר
42 משתמשים הצביעו. 47 משתמשים נמנעו.
מקור: www.habr.com