Official

B - Caesar Cipher Editorial by en_translator


If \(K \geq 26\), then the \(K\)-th successor of an English lowercase letter is equal to its \((K-26)\)-th successor, so we may assume that Takahashi chooses \(K\) such that \(0 \leq K \leq 25\).

Therefore, for each of the following \(26\) cases:

  • if Takahashi chose \(K = 0\);
  • if Takahashi chose \(K = 1\);
  • if Takahashi chose \(K = 2\);
  • \(\cdots\)
  • if Takahashi chose \(K = 25\),

check if “after Takahashi performs the operation on \(S\), it matches \(T\),” and output Yes if any of the \(26\) cases matches, or otherwise No, to get accepted for this problem.

In order to check if “after Takahashi performs the operation on \(S\), it matches \(T\),” we can simulate the actual operation that Takahashi would do. That is, it is sufficient to actually replace every character of given \(S\) with its \(K\)-th successor and check if it is equal to \(T\).

  • In order to “scan each character of \(S\)”, we can use loop structures, which are standard features of programming languages. For example, in C++, “for” statement will do.
  • In order to “replace the character with its \(K\)-th successor, we may use the fact that the ASCII codes of English lowercase alphabets a are z are consecutive.

We will show you in the end of this editorial a sample code in C++ as Sample Code 1.

There is an alternative way to solve this problem, which does not require inspecting \(26\) possible cases.

  • First, find the integer \(K_0\) such that the first character of \(T\) is the \(K_0\)-th successor of \(S\).
  • Then, it is possible that Takahashi’s operations will make \(S\) equal to \(T\) only if \(K = K_0\). Therefore, it is enough to check only \(K = K_0\) if “after Takahashi performs the operation on \(S\), it matches \(T\).” If it matches, then output Yes; otherwise output No; then you will get accepted for this problem.

We will introduce the sample code in this way as Sample Code 2.

Sample code 1

#include <iostream>
#include <string>
using namespace std;

int main(void)
{
  string s, t;
  cin >> s >> t;
  
  for(int k = 0; k <= 25; k++){
    string s2 = s;
    for(int i = 0; i < (int)s.size(); i++){
      s2[i] = ((s2[i]-'a')+k)%26 + 'a';
    }
    if(s2 == t){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  
  return 0;
}

Sample code 2

#include <iostream>
#include <string>
using namespace std;

int main(void)
{
  string s, t;
  cin >> s >> t;
  
  int k = (t[0]-s[0]+26) % 26;
  string s2 = s;
  for(int i = 0; i < (int)s.size(); i++){
    s2[i] = ((s2[i]-'a')+k)%26 + 'a';
  }
  if(s2 == t) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}

posted:
last update: