641 - Do the Untwist

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
ayaw
New poster
Posts: 18
Joined: Fri May 23, 2003 3:52 pm
Contact:

641 - Do the Untwist

Post by ayaw » Mon May 26, 2003 1:26 pm

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);
	}
}

peace...

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

641 - do the untwist

Post by titid_gede » Sat Aug 09, 2003 5:31 pm

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

regards,

titid
Kalo mau kaya, buat apa sekolah?

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Tue Aug 26, 2003 6:25 pm

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
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Wed Aug 27, 2003 3:33 pm

yes, finally got AC after using scanf ("%s")
i think there is dirty input here...
Kalo mau kaya, buat apa sekolah?

abdullah<cse du>
New poster
Posts: 39
Joined: Mon Dec 04, 2006 2:18 pm
Location: Bangladesh(CSE DU)
Contact:

Post by abdullah<cse du> » Fri Aug 10, 2007 2:27 pm

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
We were in past, we are in past and we will go in past.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 641 - Do the Untwist

Post by plamplam » Thu Oct 06, 2011 8:42 pm

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)
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

kspilario
New poster
Posts: 3
Joined: Mon Jun 20, 2011 3:53 pm

Re: 641 - Do the Untwist

Post by kspilario » Thu Nov 24, 2011 6:08 pm

ayaw,

I think

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

should be

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

Quentin028
New poster
Posts: 1
Joined: Sat Dec 13, 2014 5:12 pm
Location: Poland

Re: 641 - Do the Untwist

Post by Quentin028 » Sat Dec 13, 2014 6:01 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 641 - Do the Untwist

Post by brianfry713 » Tue Dec 16, 2014 12:01 am

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
Check input and AC output for thousands of problems on uDebug!

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 641 - Do the Untwist

Post by metaphysis » Mon Aug 29, 2016 9:53 am

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;
}

Post Reply

Return to “Volume 6 (600-699)”