👩🏿‍🔧 🤞🏼 🐯 रूसी कोड कप: पहले चरण के कार्यों का सबसे दिलचस्प 🧞 🏫 👐🏼

8 मई को, ऑल-रूसी प्रोग्रामिंग कप रूसी कोड कप का पहला क्वालीफिकेशन राउंड हुआ । राउंड के विजेता येवगेनी कपुन थे, जिन्होंने 130 मिनट के पेनल्टी टाइम के साथ सभी 5 समस्याओं को हल किया।

पहले क्वालीफाइंग दौर में कुल मिलाकर 756 लोगों ने हिस्सा लिया। दौर के परिणामों के अनुसार सर्वश्रेष्ठ 200 प्रतिभागियों को क्वालीफाइंग दौर में भाग लेने की अनुमति दी गई थी, जो 19 जून को आयोजित किया जाएगा।

14 और 15 मई को, दूसरा और तीसरा योग्यता राउंड आयोजित किया जाएगा, जिसमें 400 अन्य लोगों का चयन किया जाएगा।

इस लेख में हम आरसीसी के पहले चरण के विभिन्न आंकड़ों का विश्लेषण करेंगे, हम कार्यों का विश्लेषण करेंगे और दौरे के दौरान प्राप्त होने वाले सबसे अधिक पूछे जाने वाले प्रश्नों के उत्तर देंगे।

प्रतिभागियों को हल करने के लिए, जूरी ने 5 कार्यों का प्रस्ताव दिया। कम से कम एक समस्या को 691 प्रतिभागियों द्वारा हल किया गया था। समस्या A सबसे सरल निकला, 685 प्रतिभागियों ने इसे हल किया। सामान्य तौर पर, कार्यों के अनुसार सही निर्णय वितरित किए गए हैं:

आरेख 1. समस्याओं के सही समाधान की संख्या।

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

लेकिन समस्याओं को हल करने की उच्च गति को प्रदर्शित करने के लिए तीन हल की गई समस्याओं वाले प्रतिभागियों की आवश्यकता होती है। 200 वें स्थान का "कट-ऑफ" दंड के समय के अनुसार चला गया: तीन कार्यों के साथ क्वालीफाइंग दौर में प्रवेश करने के लिए 141 से अधिक नहीं के दंड का समय होना आवश्यक था, अर्थात् एक कार्य पर औसतन 23.5 मिनट खर्च करना।

आरेख 2. हल किए गए कार्यों की संख्या के आधार पर प्रतिभागियों की संख्या।

टास्क B: 1952 में सबसे बड़ी संख्या में प्रयास किए गए, जबकि उनमें से केवल 461, यानी लगभग 24% सफल रहे। सामान्य तौर पर, कार्यों पर सफल प्रयासों का प्रतिशत इस तरह दिखता है:

आरेख 3. कार्यों पर सफल प्रयासों का प्रतिशत।

यह देखा जा सकता है कि यद्यपि कम प्रतिभागियों ने समस्या सी को हल किया, लेकिन इससे उन्हें बी की तुलना में कम समस्याएं हुईं। इसी तरह, अधिक जटिल समस्या ई में डी के मुकाबले कम नुकसान थे।

यह उन प्रोग्रामिंग भाषाओं पर आंकड़े देखना दिलचस्प है जो रूसी कोड कप के प्रतिभागियों द्वारा उपयोग किए गए थे। यदि आप कुल मात्रा को पाई चार्ट में स्थानांतरित करते हैं, तो आपको निम्न चित्र मिलता है:

आरेख 4. प्रोग्रामिंग भाषा के आधार पर निर्णयों की संख्या।

जीएनयू सी एक बड़े अंतर से एक नेता है, जावा और सी # कुल मिलाकर लगभग तीन गुना कम है, अन्य भाषाओं में भी कम दृष्टिकोण बनाए गए हैं।

दिलचस्प बात यह है कि पाँचवाँ कार्य, जिसके लिए लंबे अंकगणित की आवश्यकता थी, मुख्य रूप से जावा में हल किया गया था:

सामान्य तौर पर, प्रतियोगिता के मिनटों द्वारा भेजे गए निर्णयों का वितरण निम्नलिखित चार्ट पर देखा जा सकता है:

चार्ट 4. प्रतियोगिता के मिनट के आधार पर दृष्टिकोणों की संख्या।

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

चार्ट 5. प्रतियोगिता के मिनट के आधार पर सफल दृष्टिकोण का प्रतिशत।

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

टास्क ए स्ट्रिंग कंसंट्रेशन
कई अनुप्रयोगों में, विभिन्न स्ट्रिंग ऑपरेशन आवश्यक हैं। दो काफी सामान्य ऑपरेशन लाइन फैले हुए हैं और दो या अधिक लाइनों का संघनन है।
स्ट्रिंग एस के उत्क्रमण के परिणामस्वरूप, स्ट्रिंग एस ^आर प्राप्त की जाती है, जिसमें एस के समान वर्ण होते हैं, लेकिन रिवर्स ऑर्डर में जा रहे हैं। उदाहरण के लिए, स्ट्रिंग "एबीसीडी" फैलाने के परिणामस्वरूप, स्ट्रिंग "एडकबा" प्राप्त की जाती है। आगे इस समस्या में, संकेतन s ^{R के} बजाय, अंकन (s) का उपयोग किया जाएगा।
दो तार s और t के मिलन के परिणामस्वरूप, हमें स्ट्रिंग s ^t मिलता है, जिसमें स्ट्रिंग s के अक्षर पहले लिखे जाते हैं, और फिर स्ट्रिंग t के अक्षर। इसी तरह, तीन, चार या अधिक तारों के संघनन को परिभाषित किया गया है। उदाहरण के लिए, स्ट्रिंग "एबीसी" और "कोडा" के परिणाम को स्ट्रिंग "एबीसीडा" में परिणामित करना है।
आपका काम कई लाइनों को समाप्‍त करने के परिणाम को निर्धारित करना है, जिनमें से कुछ को विस्तारित करने की आवश्यकता है।

इनपुट प्रारूप

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

आउटपुट स्वरूप

संघनन के परिणाम को प्रिंट करें।

निर्णय

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

हम रूसी कोड कप पर उपलब्ध सभी प्रोग्रामिंग भाषाओं में इस समस्या का समाधान प्रदान करेंगे। उसी समय, हम इस बात पर ध्यान देंगे कि मानक इनपुट स्ट्रीम से डेटा कैसे पढ़ा जाए - प्रतियोगिता के दौरान पूछे गए कई प्रतिभागियों ने इनपुट डेटा कहाँ से प्राप्त किया जाए, इसका सवाल है।

हम इष्टतम समाधान होने का दावा नहीं करते हैं, और इसके विपरीत भी, हमने विभिन्न भाषाओं में थोड़ा अलग समाधान देने की कोशिश की है।

जावा:

import java.io.*; public class concat_as { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader( new InputStreamReader(System.in)); String[] s = in.readLine().split("[()]"); for (int i = 0; i < s.length; i++) { if (i % 2 == 0) { System.out.print(s[i]); } else { System.out.print(new StringBuilder(s[i]).reverse()); } } } }

C ++:

 #include <string> #include <iostream> #include <algorithm> using namespace std; int main () { string s; cin >> s; int l = 0; while (l < s.length()) { if (s[l] == '(') { int r = l; while (s[r] != ')') r++; string tmp = s.substr(l + 1, r - l - 1); reverse(tmp.begin(), tmp.end()); cout << tmp; l = r + 1; } else { cout << s[l]; l++; } } return 0; }

सी #:

 using System; using System.Linq; class concat_as { static void Main(string[] args) { string s = Console.ReadLine(); int L, R; do { L = s.IndexOf("("); R = s.IndexOf(")"); if (L >= 0) { Console.Write(s.Substring(0, L)); Console.Write(new string( s.Substring(L + 1, R - L - 1).Reverse().ToArray())); s = s.Substring(R + 1); } } while (L >= 0); Console.WriteLine(s); } }

पर्ल:

 $s = <>; $s =~ s/\(([^)]*)\)/reverse($1)/eg; print $s

अजगर

 s = raw_input() ans = '' for t in s.split('('): if ')' in t: l = t.split(')') ans += l[0][::-1] + l[1] else: ans += t print ans

पीएचपी

 <?php $s = trim(fgets(STDIN)); $s = preg_replace('#\((\w+)\)#se', 'strrev("\1")', $s); echo "$s\n"; ?>

कृपया ध्यान दें कि इस समस्या का समाधान विशेष रूप से पर्ल और पीएचपी में सरल और कॉम्पैक्ट है।

टास्क बी टैरिफ्स
वर्तमान में, लगभग हर मोबाइल ऑपरेटर के पास टैरिफ की एक विस्तृत श्रृंखला है जो प्रत्येक व्यक्ति को अपने लिए सबसे उपयुक्त चुनने की अनुमति देती है। दुर्भाग्य से, इस विकल्प को मैन्युअल रूप से बनाना बहुत मुश्किल है।

मोबाइल ऑपरेटरों में से एक पर, प्रत्येक टैरिफ को तीन नंबरों की विशेषता होती है: सदस्यता शुल्क ci (रूबल में सेट), समय की न्यूनतम प्रभार्य इकाई t _i (सेकंड में सेट), न्यूनतम प्रभार्य समय इकाई पीआई की लागत (कोपल्क्स में सेट, एक रूबल में 100 kopecks)। प्रति माह कॉल की कुल लागत में मासिक शुल्क और प्रत्येक आउटगोइंग कॉल की लागत शामिल होती है। I-th टैरिफ का उपयोग करते समय कॉल लागत की गणना निम्नानुसार की जाती है: टॉक टाइम को T सेकंड होने दें। यदि टी <टी _i , तो कॉल लागत शून्य है। अन्यथा, कॉल लागत पी _i के k के उत्पाद के बराबर है, जहां k न्यूनतम पूर्णांक है जैसे कि k • t _{i i i} ।

महीने के दौरान सब्सक्राइबर के आउटगोइंग कॉल के टैरिफ और आंकड़ों का विवरण दिया गया है - उनकी संख्या m और अवधि d ₁ , ..., d _m सेकंड में। एक टैरिफ खोजना आवश्यक है, जिस पर इन कॉल्स की कुल लागत न्यूनतम होगी।

इनपुट प्रारूप

पहली पंक्ति में दो पूर्णांक n और m होते हैं - क्रमशः, ग्राहक के टैरिफ और आउटगोइंग कॉल की संख्या (1 ≤ n, m ≤ 100)। अगली एन लाइनों में से प्रत्येक में एक टैरिफ का वर्णन है और इसमें तीन पूर्णांक शामिल हैं: c _i (0 ≤ c _i ) 100), t _i (1 (t _i ≤ 3600), p _i (0 _i p _i ≤ 1000)।

अंतिम पंक्ति में m पूर्णांक d ₁ , ..., d _m (1 ≤ di for 3600 सभी के लिए i से 1 m) है।

आउटपुट स्वरूप

एक नंबर प्रिंट करें - टैरिफ नंबर, जिसका उपयोग करते समय प्रश्न में महीने के लिए ग्राहक की आउटगोइंग कॉल की कुल लागत न्यूनतम है। टैरिफ को पूर्णांक के साथ 1 से n तक क्रमबद्ध किया जाता है, जिसमें वे इनपुट फ़ाइल में निर्दिष्ट होते हैं। यदि कई ऐसे टैरिफ हैं, तो उनमें से किसी की संख्या को प्रिंट करें।

निर्णय

इस कार्य ने शर्तों को पढ़ते समय प्रतिभागियों की चौकसी के लिए परीक्षण किया। इस कार्य में दो मुख्य "सूक्ष्म" बिंदु हैं: सदस्यता शुल्क रूबल में सेट है, और कॉलोप्स में कॉल की लागत, साथ ही टॉक टाइम को गोल करने की ख़ासियत: एक चार्ज यूनिट से कम बातचीत शून्य पर गोल है, और एक चार्ज यूनिट पर एक वार्तालाप को गोल किया गया है।
यदि आप इन दो बिंदुओं को नोटिस करते हैं, तो समाधान सीधे दिए गए टैरिफ में से प्रत्येक पर कॉल की लागत की गणना को लागू करना है और इष्टतम को चुनना है।

समस्या सी। के। क्रमबद्ध

छांटने का कार्य आरोही या अवरोही क्रम में दी गई संख्याओं (या अन्य वस्तुओं) की व्यवस्था करना है। इस कार्य के लिए काफी कुछ विकल्प हैं, जिनमें से कई के लिए बहुत ही कुशल एल्गोरिदम मौजूद हैं। इन एल्गोरिदम का एक महत्वपूर्ण पैरामीटर ऑर्डर करने के लिए आवश्यक सरणी तत्वों के आदान-प्रदान की संख्या है।

अगला, हम छँटाई विकल्प पर विचार करेंगे, जिसे हम k- छँटाई कहेंगे। इस विकल्प में, एक ऑपरेशन के लिए अनुमति दी जाती है (जिसे के-एक्सचेंज कहा जाता है) संख्या के साथ सरणी के दो तत्वों के मूल्यों को स्वैप करने के लिए जो कि के द्वारा बिल्कुल भिन्न होते हैं। उदाहरण के लिए, यदि मूल सरणी में प्रपत्र है [6, 10, 4, 1, 2], और k = 3, तो इस सरणी को दो कार्यों में आरोही क्रम में क्रमबद्ध किया जा सकता है (पहले एक्सचेंज के बाद, सरणी का रूप होगा [1, 10, 4, 6] , 2], और दूसरे के बाद - [1, 2, 4, 6, 10])।

पूर्णांकों की एक सरणी ₁ , ..., _{n दी गई है} । आपका कार्य इस सरणी को गैर-घटते क्रम में आदेश देने के लिए आवश्यक न्यूनतम एक्सचेंजों का निर्धारण करना है।

इनपुट प्रारूप

पहली पंक्ति में एक पूर्णांक n (1 ≤ n) 300) होता है। दूसरी पंक्ति में एन पूर्णांक a1, ..., (a (1 ≤ ai all 109 सभी के लिए 1 से n) है। तीसरी पंक्ति में पूर्णांक k (1 ≤ k - n - 1) होता है।
आउटपुट स्वरूप

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

निर्णय

स्थिति मोडुलो k के शेष भाग के आधार पर, सरणी को k भागों में विभाजित करें। इन भागों में से प्रत्येक में, पड़ोसी तत्व कश्मीर की दूरी पर हैं, इसलिए उन्हें एक दूसरे के साथ आदान-प्रदान किया जा सकता है। सरणी के विभिन्न भागों के तत्वों का आपस में आदान-प्रदान नहीं किया जा सकता है।

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

यह समझने के लिए बना रहता है कि सरणी को छाँटने के लिए न्यूनतम कार्यों की क्या आवश्यकता है यदि इसे केवल पड़ोसी तत्वों (अर्थात् ऐसे कार्यों को हमें प्रत्येक भागों को क्रमबद्ध करना होगा) के आदान-प्रदान की अनुमति है यह पता चलता है कि बुलबुला द्वारा सामान्य छंटाई द्वारा न्यूनतम संख्या में क्रियाएं की जाती हैं। आज्ञा देना लंबाई की सरणी हो [0..n - 1], जिसे आप सॉर्ट करना चाहते हैं। तब एक्सचेंजों की वांछित संख्या निम्नलिखित एल्गोरिदम निष्पादित करती है:

for i from 0 to n – 1:
for j from 0 to n – 2:
if a[j] > a[j + 1]:
swap(a[j], a[j + 1])

हम इसे साबित करते हैं: इसके लिए हम सरणी के निम्नलिखित विशेषता पर विचार करते हैं, जिसे व्युत्क्रम की संख्या कहा जाता है: पदों की संख्या (i, j) , जहां मैं < j और [i]> a [j] । स्पष्ट रूप से, एक क्रमबद्ध सरणी में, व्युत्क्रमों की संख्या शून्य है। दूसरी ओर, दो पड़ोसी तत्वों का आदान-प्रदान ऐसे जोड़े की संख्या को एक से अधिक नहीं बदल सकता है। इस मामले में, प्रत्येक एक्सचेंज में बुलबुले द्वारा छंटनी प्रति इकाई व्युत्क्रम संख्या को कम करती है।

इसलिए, बुलबुले द्वारा छंटाई में एक्सचेंजों की संख्या सरणी में व्युत्क्रमों की संख्या के बराबर है, अर्थात, सरणी को सॉर्ट करने के लिए किए जाने वाले एक्सचेंजों की न्यूनतम संख्या होनी चाहिए।

समस्या डी। रेल्स

रेलवे का एक महत्वपूर्ण पैरामीटर ट्रैक गेज है - दो रेलों के बीच की दूरी जिसके साथ ट्रेन यात्रा करती है। यह वह पैरामीटर है जो रेल और अन्य कारों के प्रकारों को निर्धारित करता है जो रेल से यात्रा कर सकते हैं।

हाल ही में, RCC-0805 ग्रह के लिए एक अंतरिक्ष अभियान में पता चला कि इस ग्रह पर रेलवे हैं। एक रेलवे डिपो भी मिला था, लेकिन गेज निर्धारित करना अभी तक संभव नहीं था। तथ्य यह है कि इस ग्रह पर रेलवे स्लीपर्स के बिना रखी गई थी, इसलिए यह निर्धारित करना कि कौन से रेल एक-दूसरे के अनुरूप हैं, यह हमेशा आसान नहीं होता है।

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

इनपुट प्रारूप

पहली पंक्ति में पूर्णांक n (1 ≤ n contains 2000) होता है। अगली 2n लाइनों में से प्रत्येक में चार पूर्णांक x _{, 1,} y _{i, 1,} x _{i, 2,} y _{i, 2 हैं} - दो अलग-अलग बिंदुओं का निर्देशांक जिसके माध्यम से रेल गुजरती है। सभी निर्देशांक निरपेक्ष मूल्य में 1000 से अधिक नहीं हैं। विभिन्न रेल के अनुरूप सीधी रेखाएं मेल नहीं खाती हैं।

आउटपुट स्वरूप

एक वास्तविक संख्या प्रिंट करें - सबसे छोटा संभव गेज। इसे 10 ^-6 से खराब नहीं होने वाली सटीकता के साथ निर्धारित किया जाना चाहिए।
यदि किसी भी गेज पर रेलों को जोड़े में तोड़ना असंभव है, तो कार्य की आवश्यकताओं को पूरा करना असंभव है, संख्या .1 प्रिंट करें।

निर्णय।

सबसे पहले, हम पंक्ति की दिशा में रेलों को समतुल्यता वर्गों में विभाजित करते हैं - समानांतर रेखाएं एक वर्ग में आ जाएंगी। उसके बाद, प्रत्येक कक्षा में, हम इस वर्ग के लिए सभी संभव स्वीकार्य गेज मान पाते हैं। उत्तर सबसे छोटी संभव दूरी है, जो सभी वर्गों के लिए उपयुक्त है।

अब समाधान के प्रत्येक चरण पर अधिक विस्तार से विचार करें।

तुल्यता वर्गों द्वारा लाइनों को वितरित करने के लिए, हम प्रत्येक लाइनों के समीकरण का निर्माण करते हैं। अंक (x ₁ , y ₁ ), (x ₂ , y ₂ ) से रेखा को गुजरने दें। फिर फॉर्म कुल्हाड़ी + द्वारा + c = 0 के अपने समीकरण इस प्रकार पाए जा सकते हैं: a = y ₁ - y ₂ , b = x ₂ - x ₁ , c = - (ax ₁ + by ₁ )। अब यह ए, बी और सी को विभाजित करके लाइन के गुणांक को सामान्य करने के लिए उपयोगी है

। अब प्रत्येक पंक्ति के दो निरूपण हैं: गुणांक को -1 से गुणा करना। प्रत्येक पंक्ति के लिए एक एकल समीकरण होने के लिए, अतिरिक्त रूप से शर्तों की आवश्यकता है "" ए> 0 या (ए = 0 और बी> 0)। जब यह आवश्यकता पूरी हो जाती है, तो समानांतर रेखाओं में समान जोड़ी (ए, बी) होती है। इस प्रतिनिधित्व में, लाइनों के बीच की दूरी की गणना करना भी सुविधाजनक है: दो समानांतर रेखाओं ax + by + c ₁ = 0 और ax + by + c ₂ = 0, दूरी है | c ₁ - c ₂ |

समानांतर रेखाओं के वर्ग पर विचार करें। उन्हें गुणांक c द्वारा क्रमबद्ध करें। पहली पंक्ति पर विचार करें - इसे इस वर्ग की अन्य लाइनों में से एक के साथ जोड़ा जाता है। हम इस रेखा पर चलते हैं। बता दें कि उनके बीच की दूरी d के बराबर है। अब, बेसब्री से दूरी पर स्थित जोड़े में लाइनों के एक विभाजन का निर्माण करें। यदि यह किया जा सकता है, तो d किसी दिए गए वर्ग के लिए ट्रैक की चौड़ाई हो सकती है। हम आरोही क्रम में लाइनों पर विचार करेंगे c। यदि अगली सीधी रेखा c = c _{i में} अभी तक एक जोड़ी नहीं है, तो इसे c = c _i + d के साथ थोड़ी दूरी पर समानांतर होना चाहिए। यदि ऐसी कोई रेखा है, तो हम इसे प्रश्न के साथ एक जोड़े में जोड़ते हैं। युग्मन को दो-सूचक विधि का उपयोग करके रैखिक समय में महसूस किया जा सकता है: यह ध्यान देने के लिए पर्याप्त है कि सी + डी भी बढ़ती सी के साथ बढ़ता है।

अंत में, उत्तर की तलाश करने पर विचार करें: प्रत्येक वर्ग के लिए संभावित उत्तरों की सूची दें। स्वाभाविक रूप से, वे आरोही क्रम में क्रमबद्ध हैं। ऐसी दो सूचियों को एक पास में आसानी से पार किया जा सकता है। सभी सूचियों के प्रतिच्छेदन को पूरा करने के बाद, उनकी लंबाई के योग के समानुपाती समय में, हमें एक प्रतिच्छेदन सूची मिलती है, जिसका न्यूनतम तत्व समस्या का उत्तर है।

आइए हम एल्गोरिथ्म के चलने के समय का विश्लेषण करें। वर्गीकरण O (n) में किया जाता है। आकार k के दिए गए वर्ग के लिए, स्वीकार्य दूरी की एक सूची O (k ² ) में बनाई गई है और इसकी लंबाई k से अधिक नहीं है। इसलिए, अंतिम चरण O (n) में किया जाता है, और O (n ² ) में संपूर्ण एल्गोरिथ्म।

समस्या ई। संख्या का अनुमान है

हाल ही में, एक लोकप्रिय सामाजिक नेटवर्क में, एप्लिकेशन "संख्या का अनुमान लगाओ!" दिखाई दिया। इसके उपयोगकर्ताओं को एक गेम की पेशकश की जाती है, जिसके प्रत्येक स्तर पर इसके बारे में कुछ जानकारी से छिपे हुए नंबर को निर्धारित करना आवश्यक है।

विशेष रूप से, सबसे कठिन स्तरों में, तर्कसंगत संख्या x (0 <x <1) का अनुमान लगाना आवश्यक है, जो ज्ञात है कि इसके दशमलव अंकन में एक प्राकृतिक संख्या k द्वारा गुणा करने के परिणामस्वरूप, ठीक एक परिवर्तन हुआ - इसमें i-th और दशमलव बिंदु के बाद j- वें अंक (संख्याएं बाएं से दाएं दिशा में एक से क्रमांकित होती हैं)। इस स्थिति में, दशमलव बिंदु का अंक नहीं बदला गया है, अर्थात, असमानता 0 <k _x <1 पूरी हो गई है। ध्यान दें कि शुरू में दशमलव एक्स में दशमलव बिंदु के बाद असीम रूप से कई अंक हो सकते हैं।

आपका कार्य एक प्रोग्राम लिखना है जो संख्याओं के x का मान i, j, k से निर्धारित करेगा।

इनपुट प्रारूप

पहली पंक्ति में तीन पूर्णांक i, j, k (1 j i <j 2 1000; 2 ≤ k। 109) हैं।

आउटपुट स्वरूप

यदि वांछित संख्या मौजूद है, तो दो पूर्णांक प्रिंट करें - अंशांक और वांछित संख्या को परिभाषित करने वाले अप्रासंगिक अंश का भाजक b (a, b> 0)। अन्यथा, वाक्यांश न समाधान का उत्पादन।

निर्णय

मान लीजिए कि शुरू में आंकड़ा s ith स्थिति में है और आंकड़ा स्थिति j स्थान पर है। फिर, k द्वारा गुणा करने के बाद, संख्या x - 10 ^–i s + 10 ^–i t - 10 ^–i t + 10 ^–i s है। इसलिए, वांछित संख्या समीकरण kx = x - 10 ^–i s + 10 ^–i t - 10 ^–i t + 10 ^–i s का एक हल है।

ध्यान दें, वास्तव में, समाधान एस और टी के विशिष्ट मूल्यों पर निर्भर नहीं करता है, लेकिन केवल उनके अंतर पर: (k - 1) x = (10 ^-i - 10 ^–i ) (t - s)। इसके अलावा, एस <टी। इसलिए, यह 1 से 9 तक के अंतर (t - s) को अलग करने के लिए पर्याप्त है। प्रत्येक अंतर मान के लिए, हम समीकरण का हल खोजते हैं और इसकी जांच करते हैं: हम यह सुनिश्चित करते हैं कि जब संख्या k से गुणा की जाती है, तो दशमलव संकेतन में i-th और j-th पदों पर अंक स्थानों में, और पूर्णांक भाग शून्य के बराबर रहता है।

सत्यापन आवश्यक है, क्योंकि स्थानान्तरण के कारण, उपरोक्त समीकरण का हल समस्या के समाधान के अनुरूप नहीं हो सकता है।

अक्सर पूछे जाने वाले प्रश्न उत्तर दिए गए

प्रतियोगिता के दौरान प्रतिभागी निर्णायक मंडल को प्रश्न भेज सकते थे। कुछ प्रश्न विशेष रूप से अक्सर मिलते थे, और हमने उन्हें इस लेख में उत्तर देने का निर्णय लिया।

प्रश्न: क्या स्रोत कोड या संकलित फ़ाइल को सत्यापन के लिए भेजा जाना चाहिए?
उत्तर: सत्यापन के लिए स्रोत कोड भेजा जाना चाहिए। परीक्षण प्रणाली स्वयं प्रतिभागी के निर्णय को संकलित करती है, कमांड लाइन रूसी कोड कप के नियमों में निर्दिष्ट हैं

प्रश्न: मुझे डेटा कहां से दर्ज करना चाहिए?
उत्तर: तथाकथित मानक इनपुट स्ट्रीम से डेटा दर्ज किया जाना चाहिए। यह कीबोर्ड इनपुट से मेल खाती है, यदि आप एक प्रोग्राम चलाते हैं जो अतिरिक्त मापदंडों के बिना एक मानक इनपुट स्ट्रीम से डेटा पढ़ता है, तो कीबोर्ड से इनपुट किया जाएगा।
उसी समय, निम्न-स्तरीय कीबोर्ड इनपुट, जैसे किस्ट्रोक्स का विश्लेषण करना या कीस्ट्रोक्स के बारे में ऑपरेटिंग सिस्टम संदेश प्राप्त करना, गलत दृष्टिकोण है। पढ़ें "कंसोल से होना चाहिए।"

प्रश्न: मुझे जवाब कहां दर्ज करना चाहिए?
उत्तर मानक आउटपुट स्ट्रीम पर आउटपुट होना चाहिए (डिफ़ॉल्ट रूप से, इसे स्क्रीन पर भेजा जाता है)। फिर, आपको निम्न-स्तरीय टूल के साथ ऐसा करने की कोशिश नहीं करनी चाहिए।

यहां एक मानक इनपुट स्ट्रीम पढ़ने और सभी प्रोग्रामिंग भाषाओं में एक मानक आउटपुट स्ट्रीम लिखने के उदाहरण हैं जो रूसी कोड कप पर समर्थित हैं।

जावा

इनपुट के लिए, System.in स्ट्रीम का उपयोग करें। जावा में पार्सिंग इनपुट के लिए सबसे सुविधाजनक साधन बफ़रड्रेडर और स्कैनर कक्षाएं हैं। BufferedReader पढ़ने में तेज़ है और आपको बड़ी मात्रा में डेटा लाइन द्वारा जल्दी से पढ़ने की अनुमति देता है। नियमित अभिव्यक्ति के उपयोग के कारण स्कैनर धीमा है, लेकिन यह इनपुट स्ट्रिंग के बहुत लचीले पार्सिंग की अनुमति देता है, उदाहरण के लिए, इनपुट से एक नंबर पढ़ना।

BufferedReader का उपयोग करके एक मानक इनपुट स्ट्रीम से पढ़ने के लिए, प्रोग्राम में लाइन लिखें:

बफ़रड्रेडर इन = नया बफ़रडर (नया इनपुटस्ट्रीमरएडर (सिस्टम.इन));

स्कैनर का उपयोग करते हुए एक मानक इनपुट स्ट्रीम से पढ़ने के लिए, प्रोग्राम में लाइन लिखें:

स्कैनर में नया स्कैनर (System.in);

आउटपुट के लिए, System.out का उपयोग करें। उसी समय, System.out गैर-कैशिंग (तुरंत इसके बफर को फ्लश करता है), यदि आपको बड़ी मात्रा में जानकारी प्रदर्शित करने की आवश्यकता है, तो इसे PrintWriter में लपेटना बेहतर है।

सी ++

आप क्लासिक सी में टाइप करने के लिए स्कैनफ का उपयोग कर सकते हैं। यह फ़ंक्शन एक मानक इनपुट स्ट्रीम से डेटा पढ़ता है।
धाराओं के माध्यम से इनपुट सिनेमा स्ट्रीम का उपयोग करके किया जाता है। डिफ़ॉल्ट रूप से, यह मानक इनपुट स्ट्रीम के लिए कॉन्फ़िगर किया गया है। कृपया ध्यान दें कि स्कैन का उपयोग करके इनपुट की तुलना में धाराओं का उपयोग करना काफी धीमा है, इसलिए कार्यक्रम में बड़ी मात्रा में डेटा पढ़ने का समय नहीं हो सकता है।
आउटपुट के लिए, फिर से, आप क्लासिक प्रिंटफ या स्ट्रीमिंग कॉउट का उपयोग कर सकते हैं। सभी प्रदर्शन नोट वैध रहते हैं और प्रिंटफ उनके लिए तेज़ है।

C #

इनपुट के लिए कंसोल का उपयोग करें। Console.ReadLine () इनपुट की अगली पंक्ति पढ़ता है। इसे पार्स करने के लिए, विभाजन () विधि का उपयोग करें। डेटा को संख्याओं में परिवर्तित करना रूपांतरित वर्ग द्वारा किया जाता है।
कंसोल का उपयोग आउटपुट के लिए भी किया जाना चाहिए। उदाहरण के लिए, संख्या x को आउटपुट करने के लिए, आप Console.WriteLine (x) लिख सकते हैं।

अजगर

इनपुट के लिए, आप इनपुट या raw_input फ़ंक्शन का उपयोग कर सकते हैं। आप sys.stdin फ़ाइल डिस्क्रिप्टर का भी उपयोग कर सकते हैं, जो मानक इनपुट के लिए कॉन्फ़िगर किया गया है।
हम आउटपुट के लिए प्रिंट का उपयोग करने की सलाह देते हैं।

पर्ल

पर्ल में मानक इनपुट से इनपुट <> कमांड के साथ किया जाता है। यह कमांड एक फाइल से एक लाइन पढ़ता है और इसे वापस करता है।
हम आउटपुट के लिए प्रिंट का उपयोग करने की सलाह देते हैं।

पीएचपी

PHP में मानक इनपुट से इनपुट STDIN विवरणक से किया जाता है। अगली पंक्ति को माना जा सकता है, उदाहरण के लिए, फॉक्स कमांड के साथ।
आउटपुट के लिए, आप प्रिंट या इको का उपयोग कर सकते हैं।

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

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

प्रश्न: क्या उदाहरण में परीक्षण सही है?
उत्तर: उदाहरण में परीक्षण आमतौर पर सही है - यह कई लोगों द्वारा जांचा जाता है, जिसमें कई लोग शामिल हैं जो समस्याओं को पहले से ही जानने के बिना हल करते हैं। यदि यह आपको लगता है कि परीक्षण उदाहरण गलत है, तो स्थिति को अधिक सावधानी से पढ़ें, शायद आप कुछ गलत समझ रहे हैं।
यदि आप अभी भी सोचते हैं कि उदाहरण गलत है, तो अनुरोध में एक विस्तृत विवरण शामिल करें कि आप उदाहरण को गलत क्यों मानते हैं, कौन सा उत्तर सही है, आपको क्या लगता है कि यह गलत या अस्पष्ट है।

प्रश्न: क्या समस्या एक्स में 239 वां परीक्षण सही है?
उत्तर: सबसे अधिक संभावना है कि परीक्षण सही है। यदि आपको लगता है कि परीक्षा गलत है, तो लिखिए कि आपको ऐसा क्यों लगता है। यह सवाल पूछने के लिए बस व्यर्थ है "क्या ऐसा एक परीक्षण सही है?" - «» - , .

: , ?
: , .

!

Russian Code Cup

रूसी कोड कप: पहले चरण के कार्यों का सबसे दिलचस्प

More articles: