fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define N 100000
  4.  
  5. using namespace std;
  6.  
  7. int t, a;
  8. vector<string> robot;
  9.  
  10. string tans;
  11.  
  12. int solve(int idx, string ans, set<int> skip) {
  13.  
  14.   set<char> ch;
  15.  
  16. //tried all idx > 500 , < 500 , > 1000 etc
  17.   if (idx >= 500) {
  18.     return 0;
  19.   }
  20.   for (int i = 0; i < a; i++) {
  21.  
  22.     if(skip.find(i) != skip.end())
  23.         continue;
  24.  
  25.     if (idx < robot[i].length()) {
  26.       ch.insert(robot[i][idx]);
  27.     } else {
  28.       ch.insert(robot[i][idx % robot[i].length()]);
  29.     }
  30.   }
  31.  
  32. //also tried ch.size() == 0 return 0
  33.   if (ch.size() == 0)
  34.     return 1;
  35.  
  36.   if (ch.size() == 3)
  37.     return 0;
  38.  
  39.   if (ch.size() == 1) {
  40.     switch (*ch.begin()) {
  41.     case 'R':
  42.       ans += "P";
  43.       break;
  44.  
  45.     case 'P':
  46.       ans += "S";
  47.       break;
  48.  
  49.     case 'S':
  50.       ans += "R";
  51.     }
  52.     // cout << "ans:" << ans << "\n";
  53.     tans = ans;
  54.     return 1;
  55.   }
  56.   char curr[501];
  57.   int i = 0;
  58.   for (auto xx : ch) {
  59.     curr[i++] = xx;
  60.   }
  61.  
  62.   string cur(curr);
  63.  
  64.   if(cur.compare("PR") == 0){
  65.     for (int i = 0; i < a; i++) {
  66.  
  67.       if (robot[i][idx % robot[i].length()] == 'R') {
  68.         skip.insert(i);
  69.       }
  70.     }
  71.     return solve(idx + 1, ans + "P", skip);
  72.   }
  73.  
  74.  
  75.   if (cur.compare("RS") == 0){
  76.     for (int i = 0; i < a; i++) {
  77.  
  78.       if (robot[i][idx % robot[i].length()] == 'S') {
  79.         skip.insert(i);
  80.       }
  81.     }
  82.     return solve(idx + 1, ans + "R", skip);
  83.   }
  84.  
  85.  
  86.   if (cur.compare("PS") == 0){
  87.     for (int i = 0; i < a; i++) {
  88.  
  89.       if (robot[i][idx % robot[i].length()] == 'P') {
  90.         skip.insert(i);
  91.       }
  92.     }
  93.     return solve(idx + 1, ans + "S", skip);
  94.   }
  95.  
  96.     return 0;
  97. }
  98.  
  99. int main() {
  100.   // your code goes here
  101.   int tc = 1;
  102.   string s;
  103.   string ans;
  104.  
  105.   cin >> t;
  106.  
  107.   while (t--) {
  108.     cin >> a;
  109.     tans = ans = "";
  110.     for (int i = 0; i < a; i++) {
  111.       cin >> s;
  112.       robot.push_back(s);
  113.     }
  114.     set<int> st;
  115.     int x = solve(0, ans, st);
  116.  
  117.     if (x) {
  118.       cout << "Case #" << tc++ << ": " << tans << "\n";
  119.     } else {
  120.       cout << "Case #" << tc++ << ": IMPOSSIBLE"
  121.            << "\n";
  122.     }
  123.     robot.clear();
  124.     st.clear();
  125.   }
  126.  
  127.   return 0;
  128. }
  129.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3
1
RS
3
R
P
S
7
RS
RS
RS
RS
RS
RS
RS
stdout
copy 
Case #1: P
Case #2: IMPOSSIBLE
Case #3: P
https://ideone.com/KJ8ovE
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!