641 - Do the Untwist

[ayaw]

this is my WA code:

Code: Select all

#include <stdio.h>
#include <string.h>
char text[30]="_abcdefghijklmnopqrstuvwxyz.";

int getCode(char ch) {
	int i;
	for(i=0;text[i]!=ch;i++);
	return i;
}
char getText(int code) {
	return text[code];
}

void untwist(int k, char *a) {
	int i,n,pcode;
	int plaincode[100], chipcode[100];
	n = strlen(a);
	for(i=0;i<n;i++) chipcode[i] = getCode(a[i]);
	for(i=0;i<n;i++) {
		pcode = chipcode[i];
		pcode += i;
		if(pcode>=28) pcode-=28;
		plaincode[k*i%n] = pcode;
	}
	for(i=0;i<n;i++) putchar(getText(plaincode[i]));
	putchar('\n');
}

main() {
	int k;
	char buf[100],buffer[100];
	while(1) {
		gets(buf);
		sscanf(buf,"%d %s",&k,buffer);
		if(k==0) return 0;
		untwist(k,buffer);
	}
}

[titid_gede]

anyone has critical input for this problem? i've got AC for this problem on another OJ, but WA here.

regards,

titid

[UFP2161]

Note: There are appear to be trailing spaces on some lines, so gets() will not work =( .. Argh! Spent like an hour trying to figure out why it didn't work, even though I encrypted a file and decrypted to the same file and everything was the same. Gah =P

[titid_gede]

yes, finally got AC after using scanf ("%s")
i think there is dirty input here...

[abdullah<cse du>]

Hi,

I can't understand the problem properly. For plain text 'cat' the output is 'cs.' It is ok. But for 'cs.' my program gives 'czq'. where,

plain code is : 3 19 27
cipher code : 3 26 17 (is the problem here!)

please describe it.

Thanks
ABDULLAH

[plamplam]

Guess what I did the same mistake at first. It was only when I finished coding tried the input 5 cs. and got the output czq or sth and I realized I was actually doing it WRONG because I didn't read the problem statement carefully. You did the same mistake. You have to convert the ciphertext back to plaincode and not vice versa! I doubt this will help you since it has been over 4 years...but may help future solvers.

Best wishes.

And btw...don't worry gets() works...no dirty inputs now (I think Carlos fixed it)

[kspilario]

ayaw,

I think

if(pcode>=28) pcode-=28;

should be

while(pcode>=28) pcode-=28;

[Quentin028]

I have a question regarding reversing the formula given in this task:

Code: Select all

ciphercode[i] = (plaincode[ki mod n] - i) mod 28

To obtain a plaincode from a ciphercode, some solutions I saw used the following reverse:

Code: Select all

plaincode[ki mod n] = (ciphercode[i] + i) mod 28

How is this derived from the first formula? I don't quite understand that. In addition, there have to be some assertions about the min. and max. value of those code values, right?

[brianfry713]

ciphercode and plaincode are always between 0 and 27 by definition. Taking any value mod 28 will always give a result between 0 and 27.
http://en.wikipedia.org/wiki/Modular_arithmetic

[metaphysis]

Test data generator.

Code: Select all

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int gcd(int a, int b)
{
    int t;
    while (a % b) t = a, a = b, b = t % b;
    return b;
}

int plaincode[80], ciphercode[80];

int main(int argc, char *argv[])
{
    string letters = "_abcdefghijklmnopqrstuvwxyz.";
    
    srand(time(NULL));
    for (int cases = 1; cases <= 100; cases++)
    {
        int n = rand() % 70 + 1;
        while (true)
        {
            int k = rand() % 300 + 1;
            if (gcd(k, n) == 1)
            {
                for (int i = 0; i < n; i++)
                    plaincode[i] = rand() % 28;

                for (int i = 0; i < n; i++)
                    ciphercode[i] = (plaincode[(k * i) % n] - i + 84) % 28;
                    
                cout << k << ' ';
                for (int i = 0; i < n; i++)
                    cout << letters[ciphercode[i]];
                cout << '\n';

                break;
            }
        }
    }
    cout << 0 << '\n';
    
    return 0;
}