🌹 👩🏻‍🤝‍👨🏼 ↖️ सीएस सेंटर 2018 नए साल की शाम प्रतियोगिता 🚵🏾 🧑🏼‍🤝‍🧑🏻 👊🏿

परिचय

अक्टूबर 2018 में पहले से ही, हमने 2017 के कार्यों ( यहां स्थितियां हैं) के साथ एडवेंट कैलेंडर को सहर्ष याद किया और इस साल क्या किया जा सकता है, इस बारे में सोचना शुरू कर दिया। कई योग्य विचारों में से, हमने एक विकल्प चुना जिसमें हम विभिन्न "आकर्षक" कार्यों का चयन करते हैं, जो एक सुंदर नए साल की कहानी से एकजुट होते हैं।

कुछ भी नहीं बचा था: वास्तव में, कार्यों को उठाएं, एक कहानी लिखें, एक लीडरबोर्ड के साथ एक वेबसाइट बनाएं, यैंडेक्स के साथ सुंदर और कसकर बुनना। सबसे अच्छा, और दिसंबर की शुरुआत में शुरू करें :-)

परिणाम

जैसा कि आप जानते हैं, भूख खाने के साथ आती है, और हमने कार्यों की सामग्री और उनके तकनीकी कार्यान्वयन की प्रक्रिया को शुरू किया। प्रत्येक सफल खोज आगे सुधार को प्रेरित करती है। नतीजतन, हमने एक कार्य के लिए एक अलग सर्वर खड़ा किया, दूसरे को एक अनुकूलन बनाया (हमारे पास अभी भी सटीक उत्तर नहीं है), खुद को संगीत रिकॉर्ड किया, वितरण को बहाल किया - हम बिल्कुल भी ऊब नहीं थे!

परिणाम है:

प्रतियोगिता में सत्यापन के साथ, अलग-अलग कठिनाई के 11 कार्य (+1 बोनस);
प्रतिभागियों के लिए बाहरी साइट ;
समस्याओं को हल करने के लिए 11 दिन (7 दिसंबर से 17 दिसंबर तक)।

रोचक तथ्य और कहानियाँ

780 प्रतिभागियों ने पंजीकरण किया, 333 लोगों ने हल करना शुरू किया, 203 लोगों ने कम से कम दो कार्यों को सफलतापूर्वक पारित किया।

प्रारंभ में, हमने एक अनपढ़ प्रतिभागी के लिए सात दिनों में सभी समस्याओं को हल करने के लिए शुद्ध समय का अनुमान लगाया और एक बहुत अनुभवी एक (उर्फ ताजा सीएस केंद्र स्नातक) के लिए दो दिन। सांता क्लॉस के पहले सहायक जिन्होंने सभी ग्यारह कार्यों को सही ढंग से हल किया था, एक दिन के बारे में पूरा हो गया था, दो ने दूसरे को प्रबंधित किया!

प्रतिभागियों में से एक का पत्र: “शुभ दोपहर! आपकी प्रतियोगिता के कारण, मैंने कार्यालय (40 लोगों) को विशेष रूप से सांता क्लॉज़ कॉफी के बारे में दूसरा काम रोक दिया, मुझे एक संकेत दें। हम सब बहुत तड़प रहे हैं। ”

पार्सिंग कार्य

यहां शर्तें।

टास्क डी "संगीत संदेश" (मिखाइल प्लॉटकिन)

यह समस्या को हल करने के लिए बहुत सरल है, एक न्यूनतम संगीत शिक्षा है।
लयबद्ध पैटर्न में सुराग खोजने के प्रयास से सफलता नहीं मिली। अगला विचार पियानो पर बैठना और उस धुन को चुनना था जिसे आपने सुना है। यह ला, डू, मी, सी, ला, री, नमक, एमआई निकला। इस तरह एक तिगुना फांक में:

पहले तीन नोटों के बाद, एक छोटे से विराम के बाद, जैसे कि संगीत वाक्यांश को दो शब्दों में विभाजित करना। यह केवल पारंपरिक पत्र संकेतन (A = la, B = si, C = do, D = pe, E = mi, F = fa, G = नमक) में नोट लिखने के लिए बना रहा और दो शब्द खुले: ACE BADGE।

संगीत साक्षरता के किसी भी ज्ञान के बिना, एक समस्या को हल करना अधिक कठिन है। उदाहरण के लिए, कोई ध्वनि के प्रसंस्करण के लिए कुछ कार्यक्रम का उपयोग कर सकता है और या तो खुद नोट्स या हर्ट्ज में ध्वनियों की आवृत्तियों का पता लगा सकता है, और फिर पता लगा सकता है कि कौन सी आवृत्तियां नोटों के अनुरूप हैं।

विभाजकों के बिना एक साथ पत्र लिखने के लिए आवश्यक कार्य, इसलिए जवाब ACEBADGE है।

टास्क एफ "स्नोफ्लेक्स का बैग" (मिखाइल प्लॉटकिन)

प्रारंभिक त्रिभुज का क्षेत्रफल 1. अगला है, nth कदम पर, t_n त्रिभुज जोड़े जाते हैं, जिनमें से प्रत्येक का क्षेत्रफल s_n है। परिणामी आकृति का कुल क्षेत्रफल अनंत श्रृंखला के योग के रूप में व्यक्त किया जाता है:
S = 1 + = (t_n * s_n), n का योग 0 से ∞ (1) तक है
शून्य चरण में, t_0 = 3, s_0 = 1/9, क्योंकि त्रिभुज में 3 भुजाएँ होती हैं, जिनमें से प्रत्येक पर एक त्रिभुज मूल से 3 गुना छोटा होता है और इसलिए मूल त्रिभुज के क्षेत्रफल से 9 गुना छोटा क्षेत्र होता है।
प्रत्येक अगले चरण में, प्रत्येक पक्ष 4 पक्षों में तीन गुना छोटा हो जाता है, अर्थात
t_n = t_ {n-1} * 4 = t_0 * 4n = 3 * 4n,
s_n = s_ {n-1} * (1/9) = s_0 * (1/9) ^ n = 1/9 * (1/9) ^ n।

इसलिए, आवश्यक क्षेत्र:
S = 1 + = (t_n * s_n) = 1 + 1/3 * + ((4/9) ^ n), n का योग 0 से ∞ (2) तक है।

दूसरा कार्यकाल एक असीम रूप से घटती ज्यामितीय प्रगति का योग है। इसकी गणना करने के लिए, स्कूल सूत्र का उपयोग करें
/ ((4/9) ^ n) = 1 / (1 - 4/9) = 9/5।

सूत्र में प्रतिस्थापन (2), हमें उत्तर मिलता है:
एस = 1 + 1/3 * 9/5 = 8/5 = 1.6

टास्क जी और एल "मार्ग बनाया गया है" (अर्टिओम रोमानोव)

समाधान के लिए Artyom mehrunesartem का धन्यवाद! वैसे, समस्या G में इस्तेमाल किया गया ग्राफ़ लंदन अंडरग्राउंड पर आधारित है :)

इस समस्या को हल करने के लिए, हम चौड़ाई-प्रथम खोज के एक संशोधित संस्करण का उपयोग करेंगे। हमें एक काल्पनिक शीर्ष (स्रोत) मिलता है, जिससे हम ग्राफ के प्रत्येक शीर्ष पर शून्य भार के किनारों को खींचते हैं। प्रत्येक राज्य विशिष्ट रूप से स्रोत से पारित मार्ग से निर्धारित होता है। इसके अतिरिक्त, हम खर्च किए गए समय और प्राप्त आनंद को संग्रहीत करेंगे।

हम एक निश्चित आकार के साथ एक प्राथमिकता कतार शुरू करते हैं, जिसमें हम राज्य डालेंगे। कतार में स्थितियों के आकलन के रूप में, हम प्राप्त समय के लिए प्राप्त खुशी के अनुपात का उपयोग करेंगे। यह आकलन सही नहीं है, लेकिन इस कार्य में अच्छे परिणाम दिखाई दिए।
प्रत्येक चरण में, हम राज्य को कतार से सर्वश्रेष्ठ अनुमान के साथ प्राप्त करेंगे और इससे बने राज्यों को कतार में रखेंगे। इस दृष्टिकोण के साथ, अंतिम परिणाम प्राप्त करने में एक लंबा समय लगेगा।

समाधान को गति देने के लिए, हम चरण दर चरण उत्तर की तलाश करेंगे। प्रत्येक चरण में, मार्ग में अगले शीर्ष की खोज करने के लिए, हम कतार को साफ करेंगे और उसमें वर्तमान स्थिति डालेंगे। फिर हम एक निश्चित संख्या में कदम उठाएंगे, साथ ही साथ उस राज्य को अपडेट करेंगे जो सबसे बड़ी राशि देता है। पथ के अगले शीर्ष के रूप में, हम परिणामस्वरूप स्थिति के मार्ग में वर्तमान स्थिति के अंतिम शीर्ष का अनुसरण करते हुए क्रिया को लेते हैं जो सबसे बड़ी मात्रा में आनंद देता है। हम तब तक किए गए कार्यों को दोहराते हैं जब तक हम वर्तमान स्थिति में सुधार नहीं कर सकते।

संभव सुधार

सर्वश्रेष्ठ ह्यूरिस्टिक्स का उपयोग करें।
एल्गोरिथ्म के इस कार्यान्वयन के साथ, अतिरिक्त राज्य दिखाई देंगे, क्योंकि प्रत्येक चरण में हम उन सभी राज्यों को जोड़ देंगे जो वर्तमान से आ सकते हैं। इसे रोकने के लिए, Dijkstra एल्गोरिथ्म का उपयोग करते हुए, ग्राफ के प्रत्येक शीर्ष के लिए, आप सबसे पहले अन्य सभी चक्करों के लिए सबसे छोटे रास्तों के एक पेड़ का निर्माण कर सकते हैं और एक चरण में संक्रमण नहीं कर सकते हैं, लेकिन निर्माण किए गए पेड़ के साथ जब तक हम कोने तक नहीं पहुंचते हैं।

इन परिवर्तनों ने महत्वपूर्ण सुधार नहीं दिया, सबसे अधिक संभावना इस तथ्य के कारण है कि केवल एक बंद परीक्षण था, और विभिन्न उत्पन्न परीक्षणों का एक समूह नहीं था।

टास्क I "बियर्स-डिजिटाइज़र" (अलेक्जेंडर समोफलोव)

आइए सेवा के स्रोत कोड को देखें ।

उपयोगकर्ता के लिए उपलब्ध सभी आईडी की एक सूची /data प्राप्त की जा सकती है।
यदि कोई आईडी है, तो पता /data/id लिए अनुरोध का उपयोग करके डेटा प्राप्त किया जा सकता है।
डेटा तक पहुंचने के लिए, प्रमाणीकरण के लिए सेवा को टोकन की आवश्यकता होती है। हमारे पास एक उपलब्ध टोकन है , लेकिन यह समाप्त हो गया है और सेवा अब इसे स्वीकार नहीं करती है।

आइए कोड में देखें कि ये टोकन कैसे उत्पन्न होते हैं । टोकन JSON को फ़ॉर्म { “userId” : “id”, expireDate: “date”} को एन्क्रिप्ट करके और फिर इसे बेस 64 में एन्कोडिंग करके प्राप्त किया जाता है। एन्क्रिप्शन के लिए सेवा RSA का उपयोग करती है, और सार्वजनिक कुंजी अनुरोध /key पर प्राप्त की जा सकती है।

आइए एक निवेदन करें: e = 30593, n = 66043। चूंकि n काफी छोटा है, फिर हम आसानी से निजी कुंजी की गणना कर सकते हैं।

ऐसा करने के लिए, हम n को मुख्य कारकों में निरूपित करते हैं: 211 * 313।
हम n:) (n) = (211 - 1) (313 - 1) = 65520 के Euler फ़ंक्शन की गणना करते हैं ।
हमें d = e-1 (mod φ (n)) = 257 मिलता है।
उलटा तत्व मोडुलो की गणना उन्नत यूक्लिडियन एल्गोरिथ्म का उपयोग करके की जा सकती है ।

निजी कुंजी की गणना करने के बाद, हम हमारे लिए उपलब्ध टोकन को डिक्रिप्ट करते हैं।
हमें निम्नलिखित JSON: {"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2018-12-06T14:38:00.898026+00:00"}

ध्यान दें कि यह उपयोगकर्ता के लिए सेवा के लिए पर्याप्त है जो दिए गए userId के साथ मौजूद है और सर्वर पर मौजूदा समय से कम होने के लिए समाप्त हो रहा है।
यानी userId को जानकर हम एक नया वैध टोकन उत्पन्न कर सकते हैं।
ऐसा करने के लिए, परीक्षा पास करने के लिए पर्याप्त बड़ी समाप्ति लें - उदाहरण के लिए
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2100-01-01T12:00:00.000000+00:00"} ।

हम सार्वजनिक कुंजी का उपयोग करके अपने नए टोकन को एन्क्रिप्ट करते हैं।
/data लिए अनुरोध करने के बाद, हमें पता चलता है कि उपयोगकर्ता ने 1 से 4 तक के पहचानकर्ताओं के साथ संदेश बनाए हैं।
हम उन सभी को सुलझा लेंगे।
उनमें से एक अद्भुत वाक्यांश है: नया साल दरवाजे पर दस्तक दे रहा है, इसे जल्द ही खोलें! ।

कुछ अन्य समस्याओं को हल करने के लिए सुझाव (आर्टीम रोमानोव से)

टास्क "अक्षरों के साथ सुरक्षित"

आप देख सकते हैं कि हर बीस कदम पर आपको एक ही नंबर मिलेगा।

टास्क बी "प्रोफेसर का रहस्य"

लोकप्रियता के क्रम में शब्दों को क्रमबद्ध करें। आप देख सकते हैं कि प्रत्येक बाद का शब्द लगभग 2, 3, 4 आदि में होता है। सबसे लोकप्रिय शब्द से कई गुना कम। अब आप उत्तर को पुनर्स्थापित कर सकते हैं।

टास्क सी "कंप्यूटर आपदा"

व्हॉट्सएप प्रोग्रामिंग भाषा के बारे में सोचें।

टास्क जे "बंगाल"

संभावित प्लेसमेंट:

समस्या K "फ्रॉस्टी पैटर्न"

इस समस्या को हल करने के लिए, आप किसी भी सुविधाजनक त्रिकोण का चयन कर सकते हैं, उदाहरण के लिए सही एक, और इसके लिए उत्तर की गणना करें।

धन्यवाद

विचार से लेकर कार्यान्वयन तक की पूरी प्रक्रिया को काटिया लेबेदेव द्वारा संचालित और समन्वित किया गया था। कात्या अरमोनोवा, अलीना मोझिना, साशा कोमिसारोव और मैंने उन्हें कार्यों को पूरा करने में मदद की। लियोशा टॉलस्टिकोव ने तीन जटिल चेकर्स लिखा, साशा कोमिसारोव और शेरोज़ा ज़ेरेवचुक ने एक सर्वर बनाया, सिवाटो और सरोज़ोज़ा ने निस्वार्थ रूप से कार्यों के साथ एक सुंदर वेबसाइट बनाई: प्रत्येक प्रतिभागी अपनी प्रगति और लीडरबोर्ड देख सकता है।

सीएस सेंटर 2018 नए साल की शाम प्रतियोगिता

परिचय

परिणाम

रोचक तथ्य और कहानियाँ

पार्सिंग कार्य

धन्यवाद

More articles: