בימים אלה מתחילה תחרות ליגת התכנות לתיכונים 2012/13 (High School Programming League). לרוע המזל, אף על פי שאין מניעה עקרונית או טכנית, נראה שגם הפעם אין ייצוג ישראלי בתחרות המקוונת הזו, שלמרות שמה פתוחה למעשה למתחרים מכל הגילאים ומכל רחבי העולם.
אחד ממארגני התחרות הוא ידידי-דרך-האינטרנט, פרופ' לוקאש קושנר מהאוניברסיטה הטכנולוגית של גדנסק, שהוא גם מהאחראים לפרויקט הקומפיילר המקוון ideone.com (שכתבתי עליו כאן). באישורו של לוקאש, בחרתי להביא לכם חידת תכנות אחת מתוך התחרות. הרמה היא של הסבב הראשון בלבד, רק כדי שתבינו על מה מדובר. אם בא לכם להשחיז את כישורי התכנות, או להסיר מהם חלודה, זו ההזדמנות – ואם תמהרו תוכלו גם להספיק להירשם לתחרות (ההרשמה נסגרת ב-5 באוקטובר). המטרה היא לכתוב תוכנית שלמה, בכל שפה שתבחרו, שתקבל קלט ותפיק פלט בהתאם לפירוט. בהצלחה!
בעיית המלבן התוחם המינימלי
חשבו את המלבן התוחם המינימלי שמקיף אוסף נתון של אובייקטים דו-ממדיים. כלומר, מלבן מיושר לפי הצירים שמכיל את כל האובייקטים שצוינו, והוא בעל השטח המינימלי מבין כל המלבנים שמקיימים דרישות אלה.
הקלט
ראשית, תקבלו את הערך t (קטן מ-100), שהוא מספר המקרים לבדיקה.
כל מקרה מתחיל בערך מספרי שלם n (קטן מ-100) – מספר האובייקטים באוסף. n השורות הבאות בקלט הן התיאורים של האובייקטים עצמם. כל אובייקט מתואר באמצעות תו אחד ומספר פרמטרים:
- נקודה: p x y (לפי הסדר משמאל לימין), כאשר x ו-y הם קואורדינטות של נקודה.
- עיגול: c x y r, כאשר x ו-y הם קואורדינטות מרכז העיגול, ו-r הוא הרדיוס שלו.
- קטע קו: l x1 y1 x2 y2, כאשר xi ו-yi הם הקואורדינטות של קצה i של הקטע.
בין מקרה בדיקה אחד לאחר מפרידה שורה ריקה.
הפלט
עבור כל אחד ממקרי הבדיקה, יש להוציא כפלט ארבעה מספרים – הקואורדינטות של שתי הנקודות שמייצגות את הפינה התחתונה השמאלית והעליונה הימנית של המלבן המינימלי, לפי סדר זה: קואורדינטת ה-x של הפינה השמאלית התחתונה, אחריה קואורדינטת y של הפינה השמאלית התחתונה, קואורדינטת x של הפינה הימנית העליונה ולסיום קואורדינטת y של הפינה הימנית העליונה.
אפשר להניח שכל הפרמטרים של האובייקטים הם מספרים שלמים, ושכולם תחומים בהכרח בתוך מלבן שמשתרע בין 1000- ל-1000 בכל אחד משני הצירים.
דוגמה
קלט: 3 1 p 3 3 2 c 10 10 20 c 20 20 10 1 l 0 0 100 20 פלט: 3 3 3 3 -10 -10 30 30 0 0 100 20
קדימה, לעבודה! 🙂
מישהו ניסה לפתור את החידות האחרות? אני עבדתי הרבה על השלישית, עם העצרת, ולא הצלחתי. החישובים פשוט לא עובדים, בכל טיפוס משתנים שניסיתי לעבוד איתו. גם עם BigInteger ו-BigDecimal (בג'אווה), אני מאבד חלק מהמידע.
לא התעמקתי בחידה השלישית, אבל ברור שהפתרון הוא טריק מתמטי כלשהו ולא חישוב ישיר, וסביר להניח שאפילו לא צריך טיפוסי משתנים חריגים. הם זרקו מספיק רמזים שם בשביל לתת לך כיוון להתחלה.
שלום. הייתי שמח לדעת מהי מסגרת הזמן לשאלה כזו ובאיזו שפה כותבים את הקוד. בכל מקרה הנה הפתרון שלי בפייתון (לקח כשעה לתכנת) ****** אזהרת ספויילר ******* class Shape: def __init__(self, params): self.params = params class Circle(Shape): def get(self): x,y,r = self.params return (x+r, y+r), (x-r, y-r) class Line(Shape): def get(self): x1, y1, x2, y2 = self.params return (max(x1,x2), max(y1,y2)), (min(x1,x2), min(y1,y2)) class Point(Shape): def get(self): x,y = self.params return (x,y),(x,y) def parse(): f = open(r'c:\temp\input', 'r') t = int(f.readline()) res = [] for _ in range(t): prob = [] n = int(f.readline()) for _ in range(n): arr = f.readline().split('… לקרוא עוד »
אני חושב שאין הגבלת זמן משמעותית (כמה ימים), ושבעיקרון מותר לכתוב בכל שפה שהקומפיילר המקוון שלהם מכיר (ויש שם כמה מוזרות מאד).
אבל שוב, זה רק השלב הראשון, שאלות שהן יותר לסינון מתחרים רציניים 🙂
סיימתי 🙂
הפלט אצלך רשום מימין לשמאל.
צודק! היה בלבול בתגיות ה-HTML והוא תוקן, עכשיו זה כמו שצריך.
ועכשיו, שים ***אזהרת ספוילר!*** למעלה וספר לנו מה הלב של האלגוריתם שלך… 😉
***אזהרת ספוילר!***
בכל מקרה אני מאתחל את הפינה השמאלית התחתונה להיות הימנית העליונה, ואת הימנית העליונה להיות השמאלית התחתונה, ואז עבור כל צורה אני משנה את הקואורדינטות בעת הצורך. למשל, קואורדינטת ה-X של הפינה הימנית העליונה תהיה הערך הגדול מתוך הערך הקודם, וקואורדינטת ה-X של הפינה הימנית העליונה של הצורה הנוכחית. במקרה של קטע (L), יש לבדוק את שתי הפינות של הצורה.
כרגיל, פוסט מצויין ומעניין!!!
אהבתי את התרגיל הנחמד, יצירתי ביותר.
תודה על המידע על התחרות, מעולם לא שמעתי עליה…
מקווה לעוד חידושים רבים 🙂