fork 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.   if (idx > 1000) {
  17.     tans = ans;
  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.   if (ch.size() == 0)
  33.     return 0;
  34.  
  35.   if (ch.size() == 3)
  36.     return 0;
  37.  
  38.   if (ch.size() == 1) {
  39.     switch (*ch.begin()) {
  40.     case 'R':
  41.       ans += "P";
  42.       break;
  43.  
  44.     case 'P':
  45.       ans += "S";
  46.       break;
  47.  
  48.     case 'S':
  49.       ans += "R";
  50.     }
  51.     tans = ans;
  52.     return 1;
  53.   }
  54.   char curr[501];
  55.   int i = 0;
  56.   for (auto xx : ch) {
  57.     curr[i++] = xx;
  58.   }
  59.  
  60.   string cur(curr);
  61.  
  62.   if(cur.compare("PR") == 0){
  63.     for (int i = 0; i < a; i++) {
  64.  
  65.       if (robot[i][idx % robot[i].length()] == 'R') {
  66.         skip.insert(i);
  67.       }
  68.     }
  69.     return solve(idx + 1, ans + "P", skip);
  70.   }
  71.  
  72.  
  73.   if (cur.compare("RS") == 0){
  74.     for (int i = 0; i < a; i++) {
  75.  
  76.       if (robot[i][idx % robot[i].length()] == 'S') {
  77.         skip.insert(i);
  78.       }
  79.     }
  80.     return solve(idx + 1, ans + "R", skip);
  81.   }
  82.  
  83.  
  84.   if (cur.compare("PS") == 0){
  85.     for (int i = 0; i < a; i++) {
  86.  
  87.       if (robot[i][idx % robot[i].length()] == 'P') {
  88.         skip.insert(i);
  89.       }
  90.     }
  91.     return solve(idx + 1, ans + "S", skip);
  92.   }
  93.  
  94.     return 0;
  95. }
  96.  
  97. int main() {
  98.   // your code goes here
  99.   int tc = 1;
  100.   string s;
  101.   string ans;
  102.  
  103.   cin >> t;
  104.  
  105.   while (t--) {
  106.     cin >> a;
  107.     tans = ans = "";
  108.     for (int i = 0; i < a; i++) {
  109.       cin >> s;
  110.       robot.push_back(s);
  111.     }
  112.     set<int> st;
  113.     int x = solve(0, ans, st);
  114.  
  115.     if (x) {
  116.       cout << "Case #" << tc++ << ": " << tans << "\n";
  117.     } else {
  118.       cout << "Case #" << tc++ << ": IMPOSSIBLE"
  119.            << "\n";
  120.     }
  121.     robot.clear();
  122.     st.clear();
  123.   }
  124.  
  125.   return 0;
  126. }
  127.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1
2
PR
RP
stdout
copy 
Case #1: IMPOSSIBLE
https://ideone.com/zuLpnB
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!