मराठी कोडं - राजा, राणी आणि राक्षस!

रानभुली,
आपल्या कोठडीत कोणी हार ठेवला हे राजांना कळत नाही.
निम्या जणांनी एकत्रच असे केले तर आपल्या दारी कोणत्या राजाने हार ठेवला हे कुठल्या राजाला नाही कळणार.

आपल्याला कोठडीत नेमकं कोण येऊन हार ठेवून गेलं हे कळत नाही कोणालाच. >> ओहो. अच्छा म्हणजे त्यांना एकाच वेळी कंपल्सरी बाहेर पडायचे आहे तर.

रात्री ग्रोक ने जे उत्तर दिले होते तेच ऋन्मेषच्या उत्तरात आहे. त्यामुळं वेगळं काही तरी ट्राय केलं.

ग्रोकचे उत्तर.

ही एक अत्यंत रोचक आणि बुद्धिमत्तेची कसोटी पाहणारी समस्या आहे. राक्षसाने सादर केलेल्या आव्हानाचे स्वरूप पाहता, ही एक तर्कशुद्ध आणि रणनीतीवर आधारित समस्या आहे, ज्यामध्ये राजांना त्यांच्या राणींचे हार परत मिळवण्यासाठी एक अशी युक्ती शोधायची आहे जी कमीत कमी दिवसांत यशस्वी होईल आणि सर्वांची सुटका करेल. विक्रमसिंहाला, जो बुद्धिमान आणि चलाख आहे, अशी रणनीती आखावी लागेल जी राक्षसाच्या नियमांचे पालन करेल आणि तरीही सर्व राजांना त्यांच्या स्वतःच्या राणीचा हार शंभर टक्के खात्रीने मिळवून देईल.

### समस्येचे विश्लेषण
- **प्रमुख तथ्ये**:
1. प्रत्येक राजाला एक हार मिळेल, जो त्याच्या स्वतःच्या राणीचा *नसेल*.
2. प्रत्येक राजाला माहिती आहे की त्याच्या राणीचा हार कोणत्या दुसऱ्या राजाला दिला आहे.
3. दररोज कोठडीचे दरवाजे काही वेळासाठी उघडतात, तेव्हा राजे हार एकमेकांच्या कोठडीत ठेवू शकतात किंवा स्वतःकडे ठेवू शकतात.
4. कोठडीत कोण आलं, कोण गेलं हे कळणार नाही, आणि कोठडीत एकापेक्षा जास्त हार असू शकतात.
5. राजांना एकमेकांशी कोणत्याही प्रकारे संवाद साधता येणार नाही (नजरेने, खुणेने किंवा बोलून).
6. सर्व राजांना शंभर टक्के खात्री झाली की त्यांच्याकडे त्यांच्या स्वतःच्या राणीचा हार आहे, तेव्हा ते राक्षसाला सांगतील.
7. राक्षसाने कोठडीत बंद करण्यापूर्वी राजांना सल्लामसलत करण्यासाठी थोडा वेळ दिला आहे.
8. हार पाहून तो कोणत्या राणीचा आहे हे राजांना ओळखता येणार नाही, म्हणजेच हाराची ओळख फक्त राक्षसाच्या माहितीवर आणि रणनीतीवर अवलंबून आहे.

- **उद्दिष्ट**: कमीत कमी दिवसांत अशी रणनीती आखणे की प्रत्येक राजाला त्याच्या स्वतःच्या राणीचा हार मिळेल आणि त्याला याची शंभर टक्के खात्री असेल.

- **प्रमुख आव्हान**:
- प्रत्येक राजाला फक्त त्याच्या राणीचा हार कोणत्या दुसऱ्या राजाकडे आहे हे माहिती आहे, पण त्याच्याकडचा हार कोणत्या राणीचा आहे हे माहिती नाही.
- संवादाची शक्यता नाही, त्यामुळे रणनीती ही आधीच ठरवलेली आणि सर्वांना समजलेली असावी लागेल.
- प्रत्येक राजाला स्वतःच्या राणीचा हार मिळाला आहे याची खात्री हवी, आणि सर्व राजांची खात्री एकाच दिवशी व्हायला हवी, कारण राक्षसाला सर्वांनी एकत्र सांगायचे आहे.

### समस्येचे स्वरूप
ही समस्या गणित आणि संगणक विज्ञानातील प्रसिद्ध **"गॉसिप प्रॉब्लेम"** किंवा **"डिस्ट्रिब्युटेड अल्गोरिदम"** प्रकारची आहे, ज्यामध्ये मर्यादित माहिती आणि संवादाच्या अभावात एक सामायिक ध्येय साध्य करायचे आहे. येथे, हारांचे वितरण हे एक **परम्युटेशन** आहे (प्रत्येक राजाला एक हार, आणि प्रत्येक राणीचा हार एका राजाकडे), आणि प्रत्येक राजाला त्याच्या राणीचा हार कोणाकडे आहे हे माहिती आहे. ही माहिती एक **डिरेक्टेड ग्राफ** तयार करते, जिथे प्रत्येक राज (नोड) एका दुसऱ्या राजाकडे (त्याच्या राणीचा हार असलेला राजा) निर्देश करतो. रणनीती अशी हवी की हे परम्युटेशन उलगडून प्रत्येक राजाला त्याचा हार मिळेल.

### विक्रमसिंहाची रणनीती
विक्रमसिंह, बुद्धिमान असल्याने, एक अशी रणनीती आखेल जी सर्व राजांना त्यांच्या राणींचे हार कमीत कमी दिवसांत मिळवून देईल. खालील रणनीती ही सर्वात कार्यक्षम आहे आणि राक्षसाच्या नियमांचे पालन करते:

#### रणनीती:
1. **सुरुवातीची सल्लामसलत**:
- राक्षसाने दिलेल्या सल्लामसलतीच्या वेळेत, विक्रमसिंह सर्व राजांना एकत्र बोलावतो आणि खालील रणनीती समजावून सांगतो.
- प्रत्येक राजाला त्याच्या कोठडीचा क्रमांक (उदा., 1, 2, ..., n) दिला जातो, आणि हारांना देखील तात्पुरता क्रमांक दिला जातो (जो राजाकडे आहे तो हार त्याच्या कोठडीच्या क्रमांकाशी जोडला जातो).

2. **रणनीतीचा आधार**:
- प्रत्येक राजाला माहिती आहे की त्याच्या राणीचा हार कोणत्या दुसऱ्या राजाकडे आहे. म्हणजेच, जर राजा \( R_i \) ला माहिती आहे की त्याच्या राणीचा हार राजा \( R_j \) कडे आहे, तर \( R_i \to R_j \) असा एक निर्देश (edge) आहे.
- हे सर्व निर्देश मिळून एक डिरेक्टेड ग्राफ तयार होतो, जिथे प्रत्येक नोड (राजा) फक्त एका दुसऱ्या नोडकडे निर्देश करतो, आणि प्रत्येक नोडला फक्त एक इनकमिंग निर्देश आहे. हे ग्राफ एक **परम्युटेशन** आहे, जे काही सायक्लिक (चक्रीय) संरचनांमध्ये विभागले जाऊ शकते.
- उदाहरणार्थ, जर 4 राजे असतील आणि परम्युटेशन असं असेल:
- \( R_1 \) चा हार \( R_2 \) कडे, \( R_2 \) चा हार \( R_3 \) कडे, \( R_3 \) चा हार \( R_4 \) कडे, \( R_4 \) चा हार \( R_1 \) कडे.
- हे एक चक्र आहे: \( R_1 \to R_2 \to R_3 \to R_4 \to R_1 \).

3. **दररोजची प्रक्रिया**:
- पहिल्या दिवशी, प्रत्येक राजा आपल्याकडील हार त्या राजाच्या कोठडीत ठेवतो ज्याला त्याच्या राणीचा हार आहे. म्हणजेच, जर \( R_i \) ला माहिती आहे की त्याच्या राणीचा हार \( R_j \) कडे आहे, तर \( R_i \) आपला हार \( R_j \) च्या कोठडीत ठेवतो.
- दुसऱ्या दिवशी, प्रत्येक राजा आपल्या कोठडीत आलेला हार (जर असेल तर) घेतो आणि पुन्हा त्याच राजाच्या कोठडीत ठेवतो ज्याला त्याच्या राणीचा हार आहे.
- ही प्रक्रिया दररोज पुनरावृत्ती होते: प्रत्येक राजा आपल्याकडील हार त्या राजाच्या कोठडीत ठेवतो ज्याला त्याच्या राणीचा हार आहे.

4. **काय घडतं**:
- प्रत्येक दिवशी, हार त्यांच्या मालकांच्या (राणींच्या) दिशेने एक पाऊल पुढे सरकतात.
- परम्युटेशनच्या चक्रीय संरचनेमुळे, प्रत्येक हार त्याच्या मूळ मालकाकडे (राणीच्या राजाकडे) परत येण्यासाठी जास्तीत जास्त \( n-1 \) दिवस लागतात, जिथे \( n \) ही राजांची संख्या आहे.
- \( n-1 \) दिवसांनंतर, प्रत्येक राजाकडे त्याच्या स्वतःच्या राणीचा हार असेल, आणि त्याला याची शंभर टक्के खात्री असेल, कारण रणनीतीनुसार हारांचे वितरण निश्चित आहे.

5. **अंमलबजावणी**:
- समजा \( n \) राजे आहेत. रणनीती अशी आहे:
- दिवस 1: प्रत्येक राजा आपला हार त्या राजाच्या कोठडीत ठेवतो ज्याला त्याच्या राणीचा हार आहे.
- दिवस 2 ते \( n-1 \): प्रत्येक राजा आपल्या कोठडीत आलेला हार (किंवा हार नसेल तर काहीही नाही) घेतो आणि पुन्हा त्या राजाच्या कोठडीत ठेवतो ज्याला त्याच्या राणीचा हार आहे.
- \( n-1 \) व्या दिवशी, प्रत्येक राजा आपल्या कोठडीत आलेला हार घेतो आणि तो त्याच्या स्वतःच्या राणीचा आहे याची खात्री करतो.
- \( n-1 \) व्या दिवसाच्या शेवटी, सर्व राजे राक्षसाला सांगतात की त्यांच्याकडे त्यांच्या स्वतःच्या राणीचे हार आहेत.

6. **खात्री कशी होते**:
- प्रत्येक राजाला माहिती आहे की सर्वजण रणनीतीचं पालन करत आहेत (कारण सल्लामसलतीत ठरलं आहे, आणि संवाद न करण्याचा नियम आहे).
- परम्युटेशनच्या संरचनेमुळे, \( n-1 \) दिवसांत प्रत्येक हार त्याच्या मूळ मालकाकडे परत येतो.
- जर \( n-1 \) दिवसांनंतर प्रत्येक राजाकडे एक हार असेल, तर तो त्याच्या स्वतःच्या राणीचा हार आहे, कारण रणनीती निश्चित आहे आणि सर्व हार एकाच वेळी त्यांच्या मालकांकडे परत येतात.

#### का काम करते?
- ही रणनीती सर्वात मोठ्या संभाव्य चक्राला (ज्याची लांबी \( n \)) हाताळू शकते. उदाहरणार्थ, जर परम्युटेशन एकच चक्र असेल (उदा., \( R_1 \to R_2 \to \dots \to R_n \to R_1 \)), तर प्रत्येक हाराला त्याच्या मालकाकडे परत यायला \( n-1 \) पायऱ्या लागतात.
- जर परम्युटेशनमध्ये अनेक छोटी चक्रे असतील, तर ती सर्व \( n-1 \) दिवसांत पूर्ण होतील, कारण कोणतेही चक्र \( n \) पेक्षा मोठे असू शकत नाही.
- रणनीती संवादाची गरज नाही, कारण प्रत्येक राजा स्वतंत्रपणे आपली कृती करतो, आणि सर्व कृती एकत्रितपणे परम्युटेशन उलगडतात.

#### कमीत कमी दिवस
- जर \( n \) राजे असतील, तर जास्तीत जास्त \( n-1 \) दिवस लागतात.
- \( n-1 \) पेक्षा कमी दिवसांत हे साध्य करणं अशक्य आहे, कारण सर्वात मोठ्या चक्राला (लांबी \( n \)) पूर्ण होण्यासाठी \( n-1 \) पायऱ्या लागतात, आणि कोणताही संवाद नसल्याने माहितीचा प्रसार हळूहळू होतो.

### उदाहरण
समजा 4 राजे आहेत: \( R_1, R_2, R_3, R_4 \), आणि परम्युटेशन असं आहे:
- \( R_1 \) चा हार \( R_2 \) कडे, \( R_2 \) चा हार \( R_3 \) कडे, \( R_3 \) चा हार \( R_4 \) कडे, \( R_4 \) चा हार \( R_1 \) कडे.
- राक्षसाने हार वितरित केले: \( R_1 \) कडे \( H_4 \), \( R_2 \) कडे \( H_1 \), \( R_3 \) कडे \( H_2 \), \( R_4 \) कडे \( H_3 \).

**दिवस 1**:
- \( R_1 \) (ज्याला माहिती आहे की त्याचा हार \( R_2 \) कडे आहे) \( H_4 \) ला \( R_2 \) च्या कोठडीत ठेवतो.
- \( R_2 \) (ज्याला माहिती आहे की त्याचा हार \( R_3 \) कडे आहे) \( H_1 \) ला \( R_3 \) च्या कोठडीत ठेवतो.
- \( R_3 \) (ज्याला माहिती आहे की त्याचा हार \( R_4 \) कडे आहे) \( H_2 \) ला \( R_4 \) च्या कोठडीत ठेवतो.
- \( R_4 \) (ज्याला माहिती आहे की त्याचा हार \( R_1 \) कडे आहे) \( H_3 \) ला \( R_1 \) च्या कोठडीत ठेवतो.

**दिवस 1 च्या शेवटी**:
- \( R_1 \) च्या कोठडीत: \( H_3 \)
- \( R_2 \) च्या कोठडीत: \( H_4 \)
- \( R_3 \) च्या कोठडीत: \( H_1 \)
- \( R_4 \) च्या कोठडीत: \( H_2 \)

**दिवस 2**:
- \( R_1 \) \( H_3 \) घेतो आणि \( R_2 \) च्या कोठडीत ठेवतो.
- \( R_2 \) \( H_4 \) घेतो आणि \( R_3 \) च्या कोठडीत ठेवतो.
- \( R_3 \) \( H_1 \) घेतो आणि \( R_4 \) च्या कोठडीत ठेवतो.
- \( R_4 \) \( H_2 \) घेतो आणि \( R_1 \) च्या कोठडीत ठेवतो.

**दिवस 2 च्या शेवटी**:
- \( R_1 \) च्या कोठडीत: \( H_2 \)
- \( R_2 \) च्या कोठडीत: \( H_3 \)
- \( R_3 \) च्या कोठडीत: \( H_4 \)
- \( R_4 \) च्या कोठडीत: \( H_1 \)

**दिवस 3**:
- \( R_1 \) \( H_2 \) घेतो आणि \( R_2 \) च्या कोठडीत ठेवतो.
- \( R_2 \) \( H_3 \) घेतो आणि \( R_3 \) च्या कोठडीत ठेवतो.
- \( R_3 \) \( H_4 \) घेतो आणि \( R_4 \) च्या कोठडीत ठेवतो.
- \( R_4 \) \( H_1 \) घेतो आणि \( R_1 \) च्या कोठडीत ठेवतो.

**दिवस 3 च्या शेवटी**:
- \( R_1 \) च्या कोठडीत: \( H_1 \)
- \( R_2 \) च्या कोठडीत: \( H_2 \)
- \( R_3 \) च्या कोठडीत: \( H_3 \)
- \( R_4 \) च्या कोठडीत: \( H_4 \)

आता प्रत्येक राजाकडे त्याच्या स्वतःच्या राणीचा हार आहे, आणि रणनीतीनुसार त्यांना याची खात्री आहे. ते राक्षसाला सांगतात, आणि राक्षस सर्वांची सुटका करतो.

### अंतिम उत्तर
विक्रमसिंहाने सर्व राजांना सल्लामसलतीत ही रणनीती सांगितली: प्रत्येक राजा दररोज आपल्याकडील हार त्या राजाच्या कोठडीत ठेवेल ज्याला त्याच्या राणीचा हार आहे. ही प्रक्रिया \( n-1 \) दिवस चालेल, जिथे \( n \) ही राजांची संख्या आहे. \( n-1 \) व्या दिवशी, प्रत्येक राजाकडे त्याच्या स्वतःच्या राणीचा हार असेल, आणि सर्वांना याची शंभर टक्के खात्री असेल. त्यानंतर ते राक्षसाला सांगतील, आणि सर्वांची सुखरूप मुक्तता होईल.

# विक्रमसिंहाची रणनीती

## समस्येचे स्वरूप
राक्षसाने सर्व राजांना त्यांच्या राणींचे हार परत मिळवण्याचे आव्हान दिले आहे. प्रत्येक राजाला त्याच्या राणीचा हार कोणत्या दुसऱ्या राजाकडे आहे हे माहिती आहे, आणि दररोज ते हार एकमेकांच्या कोठडीत ठेवू शकतात. संवादाची शक्यता नाही, आणि सर्व राजांना शंभर टक्के खात्री झाल्यावरच राक्षसाला सांगायचे आहे.

## रणनीती
1. **सल्लामसलत**:
- राक्षसाने दिलेल्या वेळेत, विक्रमसिंह सर्व राजांना एकत्र बोलावतो.
- प्रत्येक राजाला त्याच्या कोठडीचा क्रमांक (1, 2, ..., n) दिला जातो.
- सर्व राजांना खालील रणनीती समजावली जाते.

2. **प्रक्रिया**:
- **दिवस 1**: प्रत्येक राजा आपल्याकडील हार त्या राजाच्या कोठडीत ठेवतो ज्याला त्याच्या राणीचा हार आहे.
- **दिवस 2 ते n-1**: प्रत्येक राजा आपल्या कोठडीत आलेला हार (किंवा हार नसेल तर काहीही नाही) घेतो आणि पुन्हा त्या राजाच्या कोठडीत ठेवतो ज्याला त्याच्या राणीचा हार आहे.
- **दिवस n-1**: प्रत्येक राजा आपल्या कोठडीत आलेला हार घेतो, जो त्याच्या स्वतःच्या राणीचा असेल.

3. **परिणाम**:
- \( n-1 \) दिवसांनंतर, प्रत्येक राजाकडे त्याच्या स्वतःच्या राणीचा हार असेल.
- सर्व राजांना रणनीतीनुसार याची शंभर टक्के खात्री असेल.
- ते राक्षसाला सांगतात, आणि राक्षस सर्वांची सुखरूप मुक्तता करतो.

## का काम करते?
- हारांचे वितरण एक परम्युटेशन आहे, जे चक्रीय संरचनांमध्ये विभागले जाते.
- प्रत्येक दिवशी हार त्यांच्या मालकांच्या दिशेने एक पाऊल पुढे सरकतात.
- जास्तीत जास्त \( n-1 \) दिवसांत सर्व हार त्यांच्या मालकांकडे परत येतात.
- रणनीती निश्चित आहे, त्यामुळे प्रत्येक राजाला खात्री असते.

## कमीत कमी दिवस
- \( n \) राजांसाठी, जास्तीत जास्त \( n-1 \) दिवस लागतात.
- \( n-1 \) पेक्षा कमी दिवसांत हे साध्य करणं अशक्य आहे, कारण सर्वात मोठ्या चक्राला \( n-1 \) पायऱ्या लागतात.

खूपच मजा आली या कोड्यांचा विचार करायला. अजून येऊ देत. धन्यवाद .

अभिनंदन माबोचक आणि ऋन्मेष.
कोडे सोडवले नाही तरी तुमची उत्तरे समजावून घेतानाच मजा आली.
आणि मस्तच कोडे होते चीकू नेहमीप्रमाणे.