'שלב ג
השלב האחרון בבחירת הנבחרת
לאחר האימונים המקוונים, עוברי שלב ב' יוזמנו לשלב ג'. שלב זה נעשה בפורמט דומה לזה של האולימפיאדה, הוא אורך 4 שעות ויש בו 3-4 שאלות אלגוריתמיות, שהפתרון להן יכול גם להשתמש בנושאים שלמדנו באימונים המקוונים, שעליכם לתכנת להן אלגוריתם יעיל. כ-40 תלמידים עוברים את שלב זה והופכים להיות חלק אינטגרלי מנבחרת ישראל במדעי המחשב!
דוגמה למבנה שאלת שלב ג'
השאלות בשלב ג' דומות מאוד לשאלות בשלב ב', אבל עם מספר הבדלים מהותיים:
- בשלב ג' נתונים החסמים על הקלטים, ומגבלות זמן וזכרון.
- בנוסף, מתוארות תתי משימות עם חסמים קלים יותר והניקוד החלקי שלהן.
- אתם יכולים לחשב (לפי מה שלומדים באימונים המקוונים בין השלבים) איזו סיבוכיות של אלגוריתם יכולה להתאים לכל תת משימה, ולהבין לאן עליכם לשאוף :)
- המבחן נעשה במערכת הבדיקות, אליה מגישים קוד, והקוד נבדק אוטומטית עם פידבק מיידי, כך שבזמן המבחן עצמו אתם יודעים מה הציון שלכם, אם נכשלתם בחלק מהבדיקות על מה נחשלתם (זמן ריצה, זכרון או תשובה שגויה), ואתם יכולים לתקן (ההגשה הכי גבוהה היא זו שנחשבת).
למשל, השאלה שראינו כהמחשה לשאלת שלב א' וב', יכולה להופיע בשלב ג' בסגנון הבא:
לסבתא סמית יש n תפוחים במשקלים שונים.
יש לה גם משקל חשמלי, שהיא יכולה לשים עליו תפוחים (המשקל מספיק גדול גם כדי לשים את כל התפוחים עליו), והמשקל מראה לה על הצג את המשקל הכולל של התפוחים שעליו, בגרמים.
סבתא סמית רוצה לדעת מה המספר החיובי השלם הקטן ביותר שהיא לא יכולה לגרום למשקל להציג (או במילים אחרות – שלא יכול להווצר על ידי חיבור של משקלים של תפוחים שיש לה).
עזרו לסבתא סמית, וכתבו עבורה תוכנית שתפתור את הבעיה.
קלט:
שורת הקלט הראשונה מכילה מספר שלם חיובי יחיד n - מספר התפוחים שיש לסבתא סמית
שורת הקלט השניה מכילה n מספרים מופרדים ברווחים - w1,...,wn, משקלי התפוחים שיש לסבתא סמית (wi הוא משקל התפוח ה-i)
פלט:
עליכם להדפיס שורת פלט אחת עם מספר יחיד - המספר החיובי השלם הקטן ביותר שסבתא סמית לא יכולה לגרום למשקל להציג
חסמים:
n ≤ 10 000 000 וחיובי
wi ≤ 1000 000 000 וחיובי, לכל i מ-1 עד n
תת משימות:
1. (10 נקודות) n ≤ 10
2. (30 נקודות) n ≤ 5 000
3. (60 נקודות) ללא מגבלות נוספות.
מגבלות:
זמן ריצה: שניה אחת
זכרון: 512MB
וכדי לפתור אותה ל-100, יש לכתוב קוד שעבור החסמים הכי גדולים (עד 10 מליון תפוחים בגדלים מ-1 עד מליארד) משתמש בלכל היותר 512MB ומסיים לרוץ תוך שניה.
באימונים ראינו שפתרון ב-O(n log n) כמו הפתרון שראינו בעמוד על שלב ב' מתאים לגודל הקלט ולחסם זמן הריצה, ונוכל פשוט לתכנת ולהגיש אותו.
למשל, ב-++C:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n;
cin >> n;
vector<int> apple(n);
for (int i = 0; i < n; ++i) {
cin >> apple[i];
}
sort(apple.begin(), apple.end());
int sum = 0;
for (auto w : apple) {
if (w > sum + 1) {
cout << sum + 1 << endl;
return 0;
}
sum += w;
}
cout << sum + 1 << endl;
return 0;
}