רוטר - חידה קטנה

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"חידה קטנה"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #14262	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 14262

sHuMpI

00:49 20.08.07

חידה קטנה

עבר עריכה לאחרונה בתאריך 24.08.07 בשעה 18:10 על-ידי Net_Boy (סגן מנהל)

בעיר רחוקה החליטו לערוך בחירות לראשות העיר.
כל תושבי העיר יכולים להתמודד אם הם רוצים. (כלומר ישנם M מתמודדים)
כל תושבי העיר מצביעים בבחירות (כלומר N מצביעים)
הנתונים נשמרים במערך בקובץ READONLY, לא ניתן לשנותו.
הנתונים נשמרים בצורה כזאת (1,2,1,3,2,1,2,1,1)
כאמור כאן M = 3 וN = 9.
מנצח בבחירות הוא מתמודד שיש לו מעל ל50 אחוז מהקולות. בדוגמא למעלה מתמודד מס' 1 ניצח.
המשימה שלכם לבנות אלגוריתם שמגלה האם מישהו ניצח בבחירות. אם כן כמובן להגיד מי הוא.
תנסו לעשות זאת בסיבוכיות זמן הכי טובה שאתם יכולים (אחרי שתתנו את התשובה אני יגיד אם אפשר בסיבוכיות טובה יותר)
מותר לכם לעבור עם חמישה משתנים בלבד
כלומר, אין לכם מערך בגודל N או מחסנית וכו'.
5 משתנים פשוטים בלבד...!

בהצלחה, מקווה שהבנתם ומצטער על ההסבר הקודם אני מקווה שעכשיו זה יותר מובן

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
החידה במקור הרבה הרבה הרבה יותר קשה	sHuMpI	20.08.07 18:37	1
יאללה נו מי התותח של הפורום	sHuMpI	23.08.07 19:42	2
תביא את המקור...	lesik	23.08.07 23:02	3
גבר ההסבר שלך ממש גרוע, לא הבנתי כלום.	עידן_הכלי	24.08.07 09:35	4
מחזק.	IcqBoy	24.08.07 10:05	5
ניסיון להסבר חדש...הנתונים המקוריים של החידה	sHuMpI	24.08.07 14:10	6
בעיניי הכי קל הדבר הבא:	idan192	24.08.07 14:44	7
אחי מצטער לא הבנת נכון את התרגיל	sHuMpI	24.08.07 16:27	8
נו, אז זה פחות עבודה ממה שרשמתי, זה שזה לא O של 1... וצודק.	idan192	24.08.07 17:05	9
אבל זה עדיין לא הפתרון של החידה	sHuMpI	24.08.07 20:52	10

sHuMpI

18:37 20.08.07

1. החידה במקור הרבה הרבה הרבה יותר קשה
בתגובה להודעה מספר 0

הקלתי מאד עליכם יאללה אני מחכה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

sHuMpI

19:42 23.08.07

2. יאללה נו מי התותח של הפורום
בתגובה להודעה מספר 0

חחח

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

lesik

23:02 23.08.07

3. תביא את המקור...
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

עידן_הכלי

09:35 24.08.07

4. גבר ההסבר שלך ממש גרוע, לא הבנתי כלום.
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IcqBoy

10:05 24.08.07

5. מחזק.
בתגובה להודעה מספר 4

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

sHuMpI

14:10 24.08.07

6. ניסיון להסבר חדש...הנתונים המקוריים של החידה
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 24.08.07 בשעה 14:16 בברכה, sHuMpI

ד"א...שאלו אותי את זה אז קשה לי לנסח את זה כמו שצריך.

בעיר רחוקה החליטו לערוך בחירות לראשות העיר.
כל תושבי העיר יכולים להתמודד אם הם רוצים. (כלומר ישנם M מתמודדים)
כל תושבי העיר מצביעים בבחירות (כלומר N מצביעים)
הנתונים נשמרים במערך בקובץ READONLY, לא ניתן לשנותו.
הנתונים נשמרים בצורה כזאת (1,2,1,3,2,1,2,1,1)
כאמור כאן M = 3 וN = 9.
מנצח בבחירות הוא מתמודד שיש לו מעל ל50 אחוז מהקולות. בדוגמא למעלה מתמודד מס' 1 ניצח.
המשימה שלכם לבנות אלגוריתם שמגלה האם מישהו ניצח בבחירות. אם כן כמובן להגיד מי הוא.
תנסו לעשות זאת בסיבוכיות זמן הכי טובה שאתם יכולים (אחרי שתתנו את התשובה אני יגיד אם אפשר בסיבוכיות טובה יותר)
מותר לכם לעבור עם חמישה משתנים בלבד
כלומר, אין לכם מערך בגודל N או מחסנית וכו'.
5 משתנים פשוטים בלבד...!

בהצלחה, מקווה שהבנתם ומצטער על ההסבר הקודם אני מקווה שעכשיו זה יותר מובן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

idan192

14:44 24.08.07

7. בעיניי הכי קל הדבר הבא:
בתגובה להודעה מספר 6

ערכתי לאחרונה בתאריך 24.08.07 בשעה 14:46 בברכה, idan192

מערך, M, N, עוד מערך ועוד קאונטר = 5 משתנים.
מערך הראשון הוא חד מימדי באורך N (נקבע את אורכו עם malloc).
המערך השני גם חד מימדי באורך M (וכנ"ל).
נכניס אינפוט עם getchar/scanf ככה שסיפרה-סיפרה תכנס כל פעם לתא אחר במערך הראשון.
ברגע שאני רואה מס' "1", למשל, אז תא מס' "1" במערך מעלה את הערך שלו 1++.
כנ"ל לגבי 2, 3 וכו'.... (ובסיום הקלט לא לשכוח 0\)
בסיום יצירת המערך השני נאפס את N ו-M. ה-N יהיה הערך המספרי של אותו תא ו-M יהיה מס' התא והקאונטר יאסוף את ערכי התאים שעברתי במערך בלי קשר.
נשאל: ערך 2 גדול מערך תא 1? אם כן - מס' התא יהיה M וערכו המספרי יהיה N.
נשאל, ערך N > N-1? אם כן - כנ"ל.
בסיום נקבל מס' תא (N) מנצח. את הערך M שלו נחלק בקאונטר - אם הוא גדול מ-50% ניתן OUTPUT של ניצח, אחרת של מוביל אך לא עבר את אחוז החסימה.

תתקנו אותי אם אני טועה, אבל הסיבוכיות המקום כאן היא אוו של N^2 והזמן היא אוו של 1.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

sHuMpI

16:27 24.08.07

8. אחי מצטער לא הבנת נכון את התרגיל
בתגובה להודעה מספר 7

אתה מקבל את המערך.
הוא נמצא בקובץ READ ONLY. אתה לא יכול לשנות אותו!
הסיבוכיות מקום שלך צצריכה להיות O(1) בלבד! כאמור מותר לך להשתמש בחמישה משתנים. לא במערך, מחסנית וכו'.
הדבר היחיד שאתה יכול לעשות עם המערך הנתון שלך שנמצא בקובץ READ ONLY הוא לקרוא את התאים ממנו...
אתה מקבל את הקובץ אחרי שהבחירות הסתיימו ולא בזמן הבחירות כל פעם שיש מצביע נוסף...

ובקשר לתרגיל שעשית.
הסיבוכיות זמן של היא o(N) והסיבוכיות מקום היא O)N(

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

idan192

17:05 24.08.07

9. נו, אז זה פחות עבודה ממה שרשמתי, זה שזה לא O של 1... וצודק.
בתגובה להודעה מספר 8

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

sHuMpI

20:52 24.08.07

10. אבל זה עדיין לא הפתרון של החידה
בתגובה להודעה מספר 9

כי אסור לך להשתמש במערך...
זה לא חידה פשוטה...ממש לא

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד