C - Conversion of Encrypted Messages
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は、友人の青木君と秘密のメッセージをやり取りするために、独自の暗号化ルールを考えました。
メッセージは英小文字からなる文字列で表されます。メッセージを「暗号化」する操作は次のように定義されます：
- 文字列の各文字について、その文字のアルファベット順での位置（
a= 1,b= 2, ...,z= 26 ）を求める。 - 文字列に含まれるすべての文字の位置の合計値 S を計算する。
- S が奇数ならば、元の文字列を反転したものが暗号化後のメッセージとなる。
- S が偶数ならば、元の文字列の各文字を、アルファベット順で 1 つ後ろの文字に置き換えたものが暗号化後のメッセージとなる（ただし
zはaに戻る）。
高橋君は N 個のメッセージを青木君に送ろうとしています。それぞれのメッセージに対して暗号化操作をちょうど K 回繰り返し適用した結果を求めてください。
制約
- N, K は整数である
- 1 \leq N \leq 10^5
- 1 \leq K \leq 10^{18}
- W_i は英小文字からなる文字列である
- 1 \leq |W_i| \leq 2 \times 10^6
- \displaystyle \sum_{i=1}^{N} |W_i| \leq 2 \times 10^6
入力
N K W_1 W_2 : W_N
- 1 行目には、メッセージの個数を表す N と、暗号化操作の回数を表す K が、スペース区切りで与えられる。
- 2 行目から N 行では、各メッセージを表す文字列 W_i が 1 行に 1 つずつ与えられる。
- 1 + i 行目には、 i 番目のメッセージ W_i が与えられる。
出力
N 行出力せよ。 i 行目には、メッセージ W_i に暗号化操作を K 回適用した結果の文字列を出力せよ。
入力例 1
3 1 abc ab z
出力例 1
bcd ba a
入力例 2
4 2 a b az xyz
出力例 2
a c az xyz
入力例 3
6 7 atcoder programming secret message zzzzzz abcdefghijklmnopqrstuvwxyz
出力例 3
budpefs gnimmargorp zljyla egassem gggggg zyxwvutsrqponmlkjihgfedcba
入力例 4
12 1000000000000000000 loremipsumdolorsitamet thequickbrownfoxjumpsoverthelazydog zzzzzzzzzzzzzzzzzzzzzzzzzz aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa cryptographictransformation competitiveprogrammingcontest oddandevenparitycheck wraparoundfromztoa reversethestringwhenodd shiftletterswheneven longmessagewithmanylowercaseletters abcxyzabcxyzabcxyzabcxyzabcxyz
出力例 4
zcfsawdgiarczcfgwhoash thequickbrownfoxjumpsoverthelazydog nnnnnnnnnnnnnnnnnnnnnnnnnn oooooooooooooooooooooooooooooo opjubnspgtobsudjiqbshpuqzsd utfuopdhojnnbshpsqfwjujufqnpd oddandevenparitycheck wraparoundfromztoa reversethestringwhenodd shiftletterswheneven tsfuufmftbdsfxpmzobniujxfhbttfnhopm abcxyzabcxyzabcxyzabcxyzabcxyz
入力例 5
1 1000000000000000000 z
出力例 5
a
Score : 366 pts
Problem Statement
Takahashi thought of his own encryption rule to exchange secret messages with his friend Aoki.
A message is represented by a string of lowercase English letters. The operation to "encrypt" a message is defined as follows:
- For each character in the string, find its position in the alphabet (
a= 1,b= 2, ...,z= 26). - Calculate the sum S of the positions of all characters in the string.
- If S is odd, the encrypted message is the original string reversed.
- If S is even, the encrypted message is obtained by replacing each character of the original string with the next character in alphabetical order (however,
zwraps around toa).
Takahashi wants to send N messages to Aoki. For each message, find the result of applying this encryption operation exactly K times.
Constraints
- N, K are integers.
- 1 \leq N \leq 10^5
- 1 \leq K \leq 10^{18}
- W_i is a string consisting of lowercase English letters.
- 1 \leq |W_i| \leq 2 \times 10^6
- \displaystyle \sum_{i=1}^{N} |W_i| \leq 2 \times 10^6
Input
N K W_1 W_2 : W_N
- The first line contains N, the number of messages, and K, the number of encryption operations, separated by a space.
- The next N lines contain the strings W_i representing each message, one per line.
- The (1 + i)-th line contains the i-th message W_i.
Output
Print N lines. The i-th line should contain the string resulting from applying the encryption operation K times to the message W_i.
Sample Input 1
3 1 abc ab z
Sample Output 1
bcd ba a
Sample Input 2
4 2 a b az xyz
Sample Output 2
a c az xyz
Sample Input 3
6 7 atcoder programming secret message zzzzzz abcdefghijklmnopqrstuvwxyz
Sample Output 3
budpefs gnimmargorp zljyla egassem gggggg zyxwvutsrqponmlkjihgfedcba
Sample Input 4
12 1000000000000000000 loremipsumdolorsitamet thequickbrownfoxjumpsoverthelazydog zzzzzzzzzzzzzzzzzzzzzzzzzz aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa cryptographictransformation competitiveprogrammingcontest oddandevenparitycheck wraparoundfromztoa reversethestringwhenodd shiftletterswheneven longmessagewithmanylowercaseletters abcxyzabcxyzabcxyzabcxyzabcxyz
Sample Output 4
zcfsawdgiarczcfgwhoash thequickbrownfoxjumpsoverthelazydog nnnnnnnnnnnnnnnnnnnnnnnnnn oooooooooooooooooooooooooooooo opjubnspgtobsudjiqbshpuqzsd utfuopdhojnnbshpsqfwjujufqnpd oddandevenparitycheck wraparoundfromztoa reversethestringwhenodd shiftletterswheneven tsfuufmftbdsfxpmzobniujxfhbttfnhopm abcxyzabcxyzabcxyzabcxyzabcxyz
Sample Input 5
1 1000000000000000000 z
Sample Output 5
a