128  Software CRC
Moderator: Board moderators

 New poster
 Posts: 3
 Joined: Sat Mar 18, 2006 7:00 am

 New poster
 Posts: 3
 Joined: Sat Mar 18, 2006 7:00 am
thank you for your help. i found the mistake and have corrected it.chunyi81 wrote: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.
i now have these results:
Code: Select all
this is a test
77 FD
00 00
A
0C 86
RFC: 793
0A 21
so anymore idea? thanks.
this is a horrible problem
Try using unsigned int instead of int. 34942 << 16 = overflow
Need Help. Problem 128
What's the formula for this problem?
Last edited by Stummer on Tue Jul 11, 2006 3:30 pm, edited 1 time in total.
Obersturmfuhrer H. Stummer
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.chunyi81 wrote: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:ar2rd's program output:Code: Select all
RFC: 793 #
MeteorRain's program output:Code: Select all
10A 21
But correct output should be:Code: Select all
81 A2
Code: Select all
0A 21
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=34943crc;
Thanks a lot, Zaspire, but I am getting WA
This is my code:
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=34943crc;
printf("%02X %02X\n",crc/256,crc%256);
}
return 0;
}
Obersturmfuhrer H. Stummer

 Learning poster
 Posts: 83
 Joined: Wed Feb 01, 2006 12:59 pm
 Location: (Fcicu) Egypt
 Contact:
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 g1
Shifting this value 16 make an overflow
To avoid it and get accepted just
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 g1
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;
Sleep enough after death, it is the time to work.
Mostafa Saad
Mostafa Saad
128(Software CRC) TLE;;;
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+2i, 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;
}
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+2i, 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;
}
I cannot understand the problem.
I do not understand the problem.
Would you please explain why the input 'A' corresponds to the output '00 00'?
Would you please explain why the input 'A' corresponds to the output '00 00'?
Re: 128(Software CRC) TLE;;;
The CRC value is chosen so that ``m2'' when divided by a certain 16bit 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 geton 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]
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 geton 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]
Re: 128 Software CRC
Actually, this is indeed a horrible problem.
That is because the judge doesn't have valid input for it.
As per problem text:
Actually there are lines with more than 65535 characters in the judgement data set. I am slightly annoyed by this.
Best Regards,
Andrei Porumb
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
Best Regards,
Andrei Porumb