ערכתי לאחרונה בתאריך 30.07.09 בשעה 19:45 בברכה, Deuce
לפני הרבה זמן פורסמה חידה (20.08.07):
https://rotter.name/cgi-bin/nor/dcboard.cgi?az=show_thread&om=14262&forum=progפותח האשכול עד היום לא פירסם תשובה, והיום אחד מחברי הפורום הפנה אותי לשם.
אני אסביר את החידה וחושב שהיא ראוייה ל-winner:
בעיר רחוקה החליטו לערוך בחירות לראשות העיר.
נסמן ב-M את מספר המתמודדים.
נסמן את מספר התושבים ב-N.
ידוע כי כל התושבים מצביעים למועמד אחד בלבד.
הנתונים נשמרים במערך בקובץ READONLY, כלומר - לא ניתן לשנותו.
הנתונים נשמרים במערך של הצבעות: (1,2,1,3,2,1,2,1,1). יש לקרוא את זה באופן הבא: הצבעה למועמד 1, הצבעה למועמד 2, הצבעה למועמד 1, הצבעה למועמד 3 וכו'. כלומר במקרה הזה יש לנו 9 הצבעות (N = 9) ל-3 מועמדים (M = 3).מנצח בבחירות הוא מתמודד שיש לו מעל ל-50 אחוז מהקולות. בדוגמא למעלה מתמודד מס' 1 ניצח.
החידה:
בהינתן קלט הכולל מערך RO כפי שתואר לעיל של הצבעות, מספר שלם N שמייצג את מספר ההצבעות ומספר שלם M שמייצג את מספר ההצבעות, להחזיר את מספר המועמד המנצח, או -1 במידה ולא קיים כזה.
אבל יש מספר הגבלות ;):
מותר לכם לעבור עם 10 משתנים פשוטים לכל היותר (בחידה המקורית ניתנו 5 משתנים, לא יודע אם זה כזה חשוב - נסו לפתור עם 5). משתנים פשוטים הכוונה בלי מחרוזות או מערכים וכו'.
שיהיה יעיל ככל האפשר - יותר יעיל מ-O של N*M.
נ.ב:
אני בעצמי לא יודע את הפתרון.
הצלחתי לפתור בסיבוכיות יעילה כאשר השתמשתי במשתנה מטיפוס long והנחתי שהוא יכול לאחסן את מה שאני מכניס לתוכו (שזה מספר דיי גדול).
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
