"Battle Live": גמר ICPC בפורטו

היום גמר תחרות התכנות הבינלאומית ICPC 2019 יתקיים בעיר פורטו שבפורטוגל. נציגי אוניברסיטת ITMO וצוותים נוספים מאוניברסיטאות ברוסיה, סין, הודו, ארה"ב ומדינות נוספות ייקחו בה חלק. בואו נספר לכם ביתר פירוט.

icpcnews /flickr/ CC BY / תמונות מגמר ICPC-2016 בפוקט

מה זה ICPC

ICPC היא תחרות תכנות בינלאומית בין סטודנטים. הם מתקיימים למעלה מ-40 שנה - הגמר הראשון עבר עוד ב-1977. הבחירה מתבצעת במספר שלבים. האוניברסיטאות מחולקות לפי אזור (אירופה, אסיה, אפריקה, אמריקה וכו'). כל אחד מהם מארח שלבי ביניים, בפרט את חצי הגמר של צפון אירו-אסיה התקיים באוניברסיטה שלנו. מנצחי השלבים האזוריים משתתפים בגמר.

ב-ICPC צוותים של שלושה משתתפים מתבקשים לפתור מספר בעיות באמצעות מחשב אחד (לא מחובר לאינטרנט). כך, בנוסף למיומנויות התכנות, נבחנים גם כישורי עבודת צוות.

צוותי אוניברסיטת ITMO זכו שבע פעמים בפרס הראשי של ICPC. זהו שיא מוחלט שעומד על כנו כבר שנים רבות. הם יתנגשו בקרב על גביע ה-ICPC 2019 135 קבוצות מכל רחבי כדור הארץ. אוניברסיטת ITMO מיוצגת השנה על ידי איליה פודורמניך, סטניסלב נאומוב и רומן קורובקוב.

איך יתקיים הגמר?

במהלך התחרות, צוותים יקבל מחשב אחד לשלושה אנשים. הוא מריץ את אובונטו 18.04 ויש לו vi/vim, gvim, emacs, gedit, geany ו- kate מותקנים מראש. אתה יכול לכתוב תוכניות ב-Python, Kotlin, Java או C++.

כאשר צוות פותר בעיה, הוא מעביר אותה לשרת הבדיקות, אשר מעריך את הקוד. המשתתפים אינם יודעים אילו בדיקות המכונה מבצעת. אם כולם מצליחים, הצוות מקבל נקודות בונוס. אחרת, נוצרת שגיאה והתלמידים נשלחים לתקן את הקוד.

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

icpcnews /flickr/ CC BY / תמונות מגמר ICPC-2016 בפוקט

דוגמאות למשימות

מטרות האליפות דורשות תיאום וריכוז קבוצתי. בנוסף, הם בודקים ידע באלגוריתמים מתמטיים בודדים. הנה דוגמה למשימה שהוצעה למשתתפי ICPC 2018:

בטיפוגרפיה יש מונח "נהר" - זהו רצף של רווחים בין מילים, שנוצר ממספר שורות טקסט. מומחה מסוים לנהר (באמת) רוצה לפרסם ספר. הוא רוצה שהנהרות הטיפוגרפיים הארוכים ביותר "ייווצרו" על הדף בעת הדפסה בגופן חד-רווח. על המשתתפים היה לקבוע את רוחב השדות שבהם יתקיים תנאי זה.

בקלט, התוכנית קיבלה מספר שלם n (2 ≤ n ≤ 2), הקובע את מספר המילים בטקסט. לאחר מכן, הוזן הטקסט: מילים בשורה אחת הופרדו ברווח אחד ולא יכלו להיות מורכבות מיותר מ-500 תווים.

ביציאה, התוכנית הייתה צריכה להראות את רוחב השדות שבהם נוצר ה"נהר" הארוך ביותר ואת אורכו של נהר זה.

הרשימה המלאה חזרה מאז שנה שעברה וגם פתרונות להם עם הסברים ניתן למצוא באתר ICPC. שם. יש ארכיון עם בדיקות, שאליו "נחשפו" תוכניות המשתתפים.

אז היום אחר הצהריים באתר האליפות ו - ערוץ יוטיוב יתקיים שידור חי מהמקום. זמין כעת הקלטות לפני המופע.

מה עוד יש לנו בבלוג על Habré:

• שידור מקוון של ACM ICPC: איך זה עובד
• מבחר ספרים על איך ללמוד, לחשוב ולקבל החלטות אפקטיביות
• סטטוסקופ חכם הוא פרויקט סטארט-אפ מהמאיץ של אוניברסיטת ITMO

מקור: www.habr.com