1998 - התחרות הארצית
1998 - השאלות
שאלות התחרויות הארציות מצורפות לחומר ההרשמה לתחרות. המתמודדים בתחרות יכולים לשמור לעצמם עותק מהשאלות. .גרסה מקוונת של השאלות תהיה זמינה בקרוב
1998 - פתרונות
שאלה 1 - ארבעה מטבעות
בשאלה מדובר על משחק שכולל ארבע מטבעות. לשם נוחות נקרא להם 1,2,3,4. הרעיון שמאחורי הפיתרון הוא שניתן לחלק את הרבעייה לשני זוגות 1-2 ו- 3-4. מטרתנו תהיה לשמור על מרחק זהה בין המטבעות בשני הזוגות וכך נשמור על שליטה במהלך המשחק. כלומר, המרחק בין 1 ל 2 יהיה שווה למרחק בין 3 ל 4
בכל פעם שהשחקן מזיז את מטבע 1, התוכנית תזיז את מטבע 2 באותו מרחק, כדי לשמור על אותו מרווח. כאשר השחקן יזיז את מטבע 2, התוכנית תזיז את 4 באותו מרחק, כדי להשוות את המרווח. גם כשהשחקן יזיז את 3, התוכנית תזיז את 4 באותה מידה, כדי לשמור את אותו מרווח. ואם השחקן יזיז את 4, התוכנית תזיז באותו מרחק את 2 כדי להשוות את המרווח
כדי שהתוכנית תוכל לשלוט במרווחים בצורה הזו, היא תבחר לשחק ראשונה אם המרווחים שונים ובצעד הראשון תאזן אותה, כלומר, תזיז את 2 אם המרחק בין 3 ו-4 קטן מזה של 1 ו-2 אחרת היא תזיז את 4. אם המרווח בתוך הזוגות שווה מראש, התוכנית תבחר לשחק שניה
| |
1
|
X
|
X
|
X
|
2
|
|
|
3
|
Y
|
Y
|
Y
|
4
|
|
...
|
The number of Xs should be equal to the number of
the Ys
('א. (15 נק
במשחק הזה השחקן שמוציא את 1 מפסיד, כי זה שאחריו יוכל להוציא את 2 ולנצח. אם התוכנית תפעל לפי האסטרטגיה שתוארה לעיל, היא תזיז רק את מטבעות 2 ו-4 ולכן היא לא תוציא את 1. במוקדם ובמאוחר, השחקן יאלץ להוציא את 1 ובמהלך העוקב, התוכנית תוציא את 2 ותנצח
('ב. (10 נק
כעת המטרה היא להוציא את מטבע 3, ולכן הצד שיוציא את 2 יפסיד. התוכנית תפעל שוב לפי אותה אסטרטגיה. כאשר השחקן יוציא את מטבע אחד, התוכנית תתיחס אליו כאילו הוא נמצא בתא שמאלי יותר מהתא השמאלי ביותר, ותמשיל לפעול על פי אותה אסטרטגיה. האסטרטגיה לעולם לא תאלץ את התוכנית להוציא את מטבע 2, כי גם כאשר מטבע 2 יהיה במשבצת השמאלית ביותר על הלוח, התוכנית תתיחס על המטבע כאל צמוד למטבע 1. במוקדם או במאוחר השחקן יאלץ להוציא את מטבע 2, ואז התוכנית תוכל להוציא את מטבע 3 ולנצח
|
-1
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
...
|
|
1
|
X
|
X
|
X
|
2
|
|
|
|
3
|
Y
|
Y
|
Y
|
4
|
|
|
...
|
Coin 1 is located outside the board at cell -1
שאלה 2 - כוורת
('א. (10 נק
:נתבונן בפרוצדורה הבאה
procedure paint(i,j: integer; old,new: integer);
begin
if (i in [1..m]) and (j in [1..n]) and (kaveret[i,j] = old) then begin
kaveret[i,j] := new;
paint(i-1,j,old,new);
paint(i,j-1,old,new);
paint(i+1,j-1,old,new);
paint(i+1,j,old,new);
paint(i,j+1,old,new);
paint(i-1,j+1,old,new);
end;
end; הפרוצדורה מקבלת בתור קלט קורדינטות בכוורת, "צבע" ישן, "צבע" חדש ו"צובעת" את כל האזור הישן בצבע החדש. הדבר נעשה באמצעות רקורסיה מורכבת, התא בכוורת נצבע, והפרוצדורה נקראת עבור כל התאים הסמוכים, יש לשים לב שבכוורת לכל תא יש שישה תאים סמוכים. כדי להבין את האופן בו הפרוצדורה פועלת מומלץ להעתיק אותה לפסקל ולעקוב אחרי הפעולה שלה. האופן בו מתבצעת הצביעה נקרא גם חיפוש לעומק
כעת, נחבר בין ה"צביעה" לכוורת. נתייחס לתאים שבים כאל צבועים בצבע 0 ולאיים כצבע 1. התא השמאלי העליון הוא בהכרח ים, לפי השאלה. נקרא לצביעה, כאשר נחליף את הצבע 0 בצבע 2, החל מהתא השמאלי העליון. כשתסתיים הצביעה, הים יהיה צבוע בצבע 2 ורק החללים בתוך האיים יהיו צבועים בצבע 0. כעת, נעבור על כל התאים בכוורת. כאשר ניתקל בצבע 0, סימן שמצאנו חלל בתוך אי. נוסיף אחד למונה החללים ונצבע את החלל בצבע 3, כדי לא לספור אותו שוב. כאשר ניתקל בצבע 1, סימן שמצאנו אי חדש, נוסיף אותו למונה האיים ונצבע את האי בצבע 4, כדי שלא נספור אותו שוב
('ב. (15 נק
.סעיף זה מורכב משני חלקים
החלק הראשון נעשה באמצעות חיפוש לרוחב. מתחילים מהאיים ומסמנים את כל התאים במרחק אחד, אחריהם אלה במרחק שתיים, וכן הלאה. כשאותו תא יקבל ערך משני איים שונים, נדע שהדרך הקצרה בינהם עוברת באותו תא
החלק השני נעשה ע"י מעבר על כל האיים, בכוורת שקיבלנו מסעיף א'. עלינו לשמור רק על תאי המסגרת של האיים, כלומר רק על תאים באיים שנוגעים בים החיצוני
שאלה 3 - עמודים
('א. (10 נק
זוהי השאלה הקשה בתחרות, היא נפתרת בפשטות בעזרת שיטה שנקראת תכנון דינמי
מתאמי נוחות כתבתי את פתרון השאלה באנגלית
.משתמשים במערך דו-מימדי
The cell [x,y] will hold the maximal strength between poles 1..x in A and poles 1..y in B.
[x,0] and [0,y] are initilized to 0.
For evrey x and y, [x,y] is the maximal value amoung [x-1,y], [x,y-1] and [x-1,y-1] + the cable from x to y. (That is we can either not use the x to y cable (option 1 and 2) or use the cable (option 3)).
The solution will be in cell [m,n].('ב.(15 נק
סעיף ב' נפתר באופן דומה
However, this time we should also check [x,y-1] + the cable from x to y, while finding the maximum. That's using more than one cable coming from x.
The list of cables can be easly founded by backtracking on the array.
שאלה 4 - משחק קפיצות
כדי להגיע לפתרון השאלה, מומלץ לנסות לשחק את המשחק
סעיף א' (10 נק') נעשה ע"י הקפצת אבן אחת מימין, שתיים משמאל, שלוש מימין וכן הלאה, ומתקבלת התקדמות בסירוגין
סעיף ב' (15 נק') קשה יותר ונעשה ע"י ריכוז כל האבנים מאותו צבע בצד אחד
yahavnu@yahoo.com
חזרה לדף 1998
האתר נכתב ע"י יהב נוסבאום
