128 - Software CRC

[MeteorRain]

actually, empty string works on my windows too. i use dev-C++ with its gcc compiler.

after added the parantheses, i tried "RFC: 793" but got "81 A2" instead of "10A 21" or "0A 21"... but all sample input works.
i'm completedly confused >"<

[chunyi81]

Sorry about that. My mistake. However, I can only say your program fails for this input. You will have to find the mistake in your code yourself.

[MeteorRain]

Sorry about that. My mistake. However, I can only say your program fails for this input. You will have to find the mistake in your code yourself.

thank you for your help. i found the mistake and have corrected it.
i now have these results:

Code: Select all

this is a test
77 FD

00 00
A
0C 86
RFC: 793
0A 21

but still WA T_T
so anymore idea? thanks.

[drewsome]

Try using unsigned int instead of int. 34942 << 16 = overflow

[Stummer]

What's the formula for this problem?

[Dohan Kim]

I cannot understand this problem too. Please help me!!!!!!

[amaro]

The empty string still gives me correct output on my university's Unix server for MeteorRain's code, after putting the shift in parantheses.

This test case from a past thread will reveal the error in both WA programs in this thread:

Input:

Code: Select all

RFC: 793
#

ar2rd's program output:

Code: Select all

10A 21

MeteorRain's program output:

Code: Select all

81 A2

But correct output should be:

Code: Select all

0A 21

In fact, the correct output for that string is 3A 01 (my code gave MeteorRain's solution before, then I corrected it to match 0A 21 and got WA, then finally found an overflow and it worked with 3A 01). The other answers are probably overflows, try using a unsigned int.

[Zaspire]

Code: Select all

                  c=getchar();
		crc=0;
		while (c!='\n')
		{
			crc<<=8;
			crc+=c;
			crc%=34943;
			c=getchar();
		}
		crc=(crc<<16)%34943;
		if (crc) crc=34943-crc;

[Stummer]

Thanks a lot, Zaspire, but I am getting WA
This is my code:

Code: Select all

#include <iostream.h>
#include <stdio.h>
int main()
{
	char c;
	int crc,m=34943;
	for(;;)
	{
		c=getchar();
		if(c=='#') break;
		crc=0; 
		while(c!='\n') 
		{ 
		   crc<<=8; 
		   crc+=c; 
		   crc%=34943;
		   c=getchar(); 
		} 
		crc=(crc<<16)%34943; 
		if(crc) crc=34943-crc; 
		printf("%02X %02X\n",crc/256,crc%256); 
	}
	return 0;
}

[898989]

Sorry i did not read any thing just i read ar2rd code
I do not know you get accepted or not..In any case
This line is your problem "m = (m<<16)%G; "
If you think carefull before this step the largest value for m is g-1
Shifting this value 16 make an overflow
To avoid it and get accepted just

Code: Select all

m = (m<<8)%G; 
m = (m<<8)%G;

[bongssi]

I got time limit exceed at 128.
I used big_mod calculation, using for question number 374(big mod). Of course, 374 is accepted.
I tried very very long string, but it works fast!!! I REALLY don't know why my program got TLE...
Here's my code. Plz help me~;;; and I didn't ignore blanks...

-----------------------------------------------------------------------

#include <stdio.h>
#include <math.h>
#include <string.h>

int big_mod(int B, int P, int M){ /* This function returns the value of (B^P)%M */

if(P == 0) return 1;
else if(P%2==0) return (int)pow(big_mod(B, P/2, M), 2) % M;
else return (((int)pow(big_mod(B, P/2, M), 2) % M) * (B % M)) % M;
}

int main(void){

int i, msg_value, crc_value, digit;
char message[1025];

while(1){

message[0] = '\0';
scanf("%[^\n]", message);
getchar();
if(message[0] == '#') break;

msg_value = 0;

for(i=0; i<strlen(message); i++){

msg_value = (msg_value + (message * big_mod(256, strlen(message)-1+2-i, 34943) % 34943)) % 34943;
}

crc_value = (34943 - msg_value) % 34943;

/*
printf("%x\n", crc_value);
*/

for(i=3; i>=0; i--){

if(i==1) printf(" ");
digit = crc_value / (int)pow(16, i);

if(digit > 9) printf("%c", digit+55);
else printf("%d", digit);

crc_value %= (int)pow(16, i);
}
printf("\n");
}

return 0;
}

[soddy]

since u r reading character by character a string like "# is a way" will exit ur program
another bug u hv is crc<<16 may return value outside standard int

[Crypto]

I do not understand the problem.

Would you please explain why the input 'A' corresponds to the output '00 00'?

[chrisadam]

The CRC value is chosen so that ``m2'' when divided by a certain 16-bit value ``g'' leaves a remainder of 0. This makes it easy for the receiving program to determine whether the message has been corrupted by transmission errors. It simply divides any message received by ``g''. If the remainder of the division is zero, it is assumed that no error has occurred.
You notice that most of the suggested values of ``g'' in the book are odd, but don't see any other similarities, so you select the value 34943 for ``g'' (the generator value).
Input and Output
You are to devise an algorithm for calculating the CRC value corresponding to any message that might be sent. To test this algorithm you will write a program which reads lines (each line being all characters up to, but not including the end of line character) as input, and for each line calculates the CRC value for the message contained in the line, and writes the numeric value of the CRC bytes (in hexadecimal notation) on an output line. Each input line will contain no more than 1024 ASCII characters. The input is terminated by a line that contains a # in column 1. Note that each CRC printed should be in the range 0 to 34942 (decimal).


___________________________________________________________________________


Want to get-on Google's first page and loads of traffic to your website? Hire a SEO specialist from Ocean Groups[url=http://oceangroups.org/] seo specialist [/url]

[at5anpo3]

Actually, this is indeed a horrible problem.
That is because the judge doesn't have valid input for it.
As per problem text:

Code: Select all

 Each input line will contain no more than 1024 ASCII characters

Actually there are lines with more than 65535 characters in the judgement data set. I am slightly annoyed by this.

Best Regards,
Andrei Porumb