मान लीजिए, 2n अक्षरों की संख्या है और उनमें से प्रत्येक पर 1 से n के बीच एक पूर्णांक संख्या लिखी गई है। ठीक दो अक्षर ऐसे होते हैं जिन पर समान संख्या लिखी होती है। इन अक्षरों को m स्टैक्स में व्यवस्थित किया गया है और स्टैक i पर अक्षर स्टैक [i] हैं। हमारा काम सभी स्टैक को निम्नलिखित तरीके से खाली करना है
-
हमें किन्हीं दो स्टैक्स को चुनना है और उन दोनों में से ऊपर के अक्षर को हटाना है।
-
हमने जो अक्षर निकाले हैं, उन दोनों पर एक ही नंबर होना चाहिए।
अगर हम इस तरह से एम स्टैक खाली कर सकते हैं, तो हम सही प्रिंट करते हैं या अन्यथा हम झूठी वापसी करते हैं।
इसलिए, यदि इनपुट n =3, m =2, स्टैक्स ={{2, 1, 3}, {2, 1, 3}} जैसा है, तो आउटपुट सही होगा।
दो ढेर हैं और प्रत्येक ढेर में अक्षर हैं जिन पर क्रमशः संख्या 2, 1, 3 लिखी गई है। तो, हम दो स्टैक से हटा सकते हैं और उन्हें दिए गए तरीके से खाली कर सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
Define one 2D array dp
Define an array tvec
for initialize i := 0, when i < m, update (increase i by 1), do:
k := size of stacks[i]
for initialize j := 0, when j < k, update (increase j by 1), do:
if j < 0, then:
insert p at the end of dp[stacks[i, j]]
(increase tvec[p] by 1)
p := stacks[i, j]
Define an array tp
for initialize i := 1, when i <= n, update (increase i by 1), do:
Define one queue q
insert i into q
while (q is not empty), do:
if not tp[first element of q] and tvec[first element of q] is same as 0, then:
for each element next in dp[first element of q], do:
(decrease tvec[next] by 1)
insert next into q
tp[first element of q] := true
delete first element from q
for initialize i := 1, when i <= n, update (increase i by 1), do:
if tvec[i] is not equal to 0, then:
return false
return true उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
bool solve(int n, int m, vector<vector<int>> stacks){
vector<vector<int>> dp(n + 1);
vector<int> tvec(n + 1);
for(int i = 0; i < m; i++){
int k = stacks[i].size();
int p;
for(int j = 0; j < k; j++){
if(j > 0){
dp[stacks[i][j]].push_back(p);
tvec[p]++;
}
p = stacks[i][j];
}
}
vector<bool> tp(n + 1);
for(int i = 1; i <= n; i++){
queue<int> q;
q.push(i);
while(!q.empty()){
if(!tp[q.front()] && tvec[q.front()] == 0){
for(auto next: dp[q.front()]){
tvec[next]--;
q.push(next);
}
tp[q.front()]=true;
}
q.pop();
}
}
for(int i = 1; i <= n; i++){
if(tvec[i] != 0){
return false;
}
}
return true;
}
int main() {
int n = 3, m = 2;
vector<vector<int>> stacks = {{2, 1, 3}, {2, 1, 3}};
cout<< solve(n, m, stacks);
return 0;
} इनपुट
3, 2, {{2, 1, 3}, {2, 1, 3}} आउटपुट
1