OJ Board

I think you should use bit-wise operations instead of time-consuming multiplication. For example, instead of
[cpp]
a = a*256;
[/cpp]
you should use

[cpp]
a = a<<8;
[/cpp]

and instead of
[cpp]
a = a*256*256;
[/cpp]
you should use

[cpp]
a = a<<16;
[/cpp]

that should speed up your code.
this is how your code should look like

[cpp]
#include<iostream>
#include<string>
using namespace std;

string output(int a){
string result,no="0123456789ABCDEF";
for(int j=1;j<=4;a>>=4,j++){
int i=a%16;
result=no+result;
}
return result.substr(0,2)+" "+result.substr(2);
}

int main(){
string buffer;
int i;
while(true){
string buffer;
char bu;
while(cin.get(bu)){
if(bu=='\n')
break;
buffer=buffer+bu;
}
if(buffer[0]=='#')
return 0;
int length=buffer.length(),base=0,checksum;
if(length==0){
cout<<"00 00"<<endl;
continue;
}
for(i=0;i<length;i++)
base=(base<<8+buffer)%34943;
base=(base<<16)%34943;
checksum= (base==0?base:(34943-base));
cout<<output(checksum)<<endl;
}
return 0;
}[/cpp]

strange. I tried your code, but it is still giving me time limit exceeded. I think you should try do do something about output function. It seems to be a bit-time consuming.

anyway, this code doesn't give that time limit error, but it still gives WA. I think our problem is in this place
[cpp]
while(cin.get(bu)){
if(bu=='\n')
break;
buffer=buffer+bu;
}

[/cpp]
have a look at how I've done it. I don't know what you are waiting for in the above while loop. I think your program gets stuck at that place.

[cpp]
#include<fstream>
#include<iostream>
#include<string>
#include<stdio.h>

using namespace std;

int main(){
string buffer;
int i;

int nLowerByteCRC;
int nHigherByteCRC;
char bu;
char chStr[1024];

int length,base,checksum;
while(1)
{
memset(chStr,0,1024);
cin.getline(chStr,1024);
buffer = chStr;

if(buffer[0]=='#')
return 0;

length=buffer.length();
base=0;

if(length==0){
cout<<"00 00"<<endl;
continue;
}
for(i=0;i<length;i++)
base=(base<< 8 )|(buffer)%34943;
base=(base<<16)%34943;
checksum= (base==0?base:(34943-base));

nHigherByteCRC = checksum >>8;
nLowerByteCRC = checksum & (int)(0x00FF);
printf("%02X %02X\n",nHigherByteCRC,nLowerByteCRC);

}
return 0;
} [/cpp][/cpp][cpp][/cpp]

come on, Guys! I've been waiting for an answer for ages.

Thanks to all.
I have solved the problem:)

boatfish wrote:Thanks to all.
I have solved the problem:)

mmm. could you please email me your code, because I don't know why it gives me this rubbish WA.

guys, please! help.

Input: Your output:

Ivan Golubev wrote:Input:

Code: Select all

RFC: 793
#

Your output:

Code: Select all

10A 21

thanks. can anybody tell me why is it happening? actually, when I change long to unsigned it gives correct results.
I am just wondering why is it happening.

I can't believe I made this rubbish mistake. it was all because of this line
[cpp]
nHigherByteCRC = CRC>>8;
[/cpp]
it should be this
[cpp]
nHigherByteCRC = (int)(0x00ff) & (CRC>>8 );
[/cpp]
unbelievable.
thanks, Ваня.

Besides, can anybody tell me why am I getting presentation error now?
the output is below.

thanks.[cpp]
#include <fstream>
#include <string>
#include <iostream>
#include <iomanip>
#include <memory>
#include <stdio.h>

using namespace std;

typedef unsigned char BOOL;

const BOOL FALSE = 0;
const BOOL TRUE = 1;

int main();
long Reminder(char *chMessage,int nDWLen,long lnGenerator);

int main()
{

const long lnGenerator = 34943;
const int nAddLetters = 4;
const int nDataLen = 1024 + nAddLetters + 2;// 1024- for the data,
// 2 - for Redundancy Error
// 4 - for correcting the data length (make even)


long r;
long CRC;
int tAdd,tBegin,rem;
int nLowerByteCRC;
int nHigherByteCRC;
int num = 0;

char chData[nDataLen];
char *chMessage = NULL;
BOOL fl = TRUE;
int nReadLen = 0;
int nMessageLen= 0;

//ifstream fin ("input.txt");
//ofstream fout("output.txt");

while(fl)
{

memset((void *)chData,0,(size_t)(nDataLen*sizeof(chData[0])));
//fin.getline(&chData[nAddLetters],nDataLen);
cin.getline(&chData[nAddLetters],nDataLen,'\n');
nReadLen = strlen(&chData[nAddLetters]);


if('#' == chData [nAddLetters])
{
fl = FALSE;
}
else
{
rem = (nReadLen + 2)% 4;
tAdd = (!rem) ? 0 : (4 - rem); // number of letters to add
tBegin = (!rem) ? 4 : rem ; // where the message will start
nMessageLen = nReadLen + 2 + tAdd ; // message length
chMessage = (char *)&chData[tBegin];

// calculate CRC

r = Reminder(chMessage,(nMessageLen>>2),lnGenerator);
CRC = (0 == r) ? 0 : (lnGenerator - r);

nHigherByteCRC = (int)(0x00FF) & (CRC>>8 );
nLowerByteCRC = CRC & (int)(0x00FF);
//printf("%02X %02X \n",nHigherByteCRC,nLowerByteCRC);
cout.fill('0');
//fout.setf(ios_base::hex,ios_base::showbase);
cout<<hex<<setw(2)<<nHigherByteCRC<<" ";
cout<<hex<<setw(2)<<nLowerByteCRC <<endl;//<<dec<<++num<<endl;

}


}


//fin.close();
//fout.close();
return (0);
}

long Reminder(char *chMessage,int nDWLen,long lnGenerator)
{
long r;
long t;
int i;

const int nIter = 2*nDWLen - 1;
r = (int)chMessage[0];
r<<= 8;
r |= chMessage[1];


for(i = 1; i <= nIter; i++)
{
t = r;
t<<= 16;
t |= (((int)chMessage[i*2])<<8 ) | ((int)chMessage[i*2 + 1]);
r = t % lnGenerator;
}

return (long)r;
}
[/cpp]

i also got WA, anything wrong??

here is it :

try to output your answers in the file, I mean for all the strings length from 0 to 1024 and compare them with the output of my program as I got AC, though with presenation error.
That's what I did and really helped.

Hi guys. I did problem number 128 in JAVA, only to get a TLE (as is common with java).

Anyway, so I converted my program directly to C++ code, only to find it doesn't work the same. I think you'll agree the conversion is quite straight forward. Please, if someone can make a suggestion I'd be greatful.

Both programs are below, as well as the offending input....

[java]import java.io.IOException;

class Main {
static final long generator = 34943;

public static void main(String[] args) {
String input;
while((input = readLine(2048)) != null) {
if(input.length() == 0) {
System.out.println("00 00");
continue;
}

if(input.charAt(0) == '#') System.exit(0);

long crc = 0;
for(int i = 0; i < input.length(); i++)
crc = ((crc << 8) + input.charAt(i)) % generator;
crc = (crc << 16) % generator;
if(crc != 0) crc = generator - crc;
long hiByte = crc >> 8;
long loByte = crc - (hiByte << 8);

String h = Long.toHexString(hiByte).toUpperCase();
String l = Long.toHexString(loByte).toUpperCase();
System.out.println((h.length() < 2 ? "0" : "") + h + " " +
(l.length() < 2 ? "0" : "") + l);
}
}

static String readLine(int maxLg) {
byte[] lin = new byte[maxLg];
int lg = 0, car = -1;
while(lg < maxLg) {
try{car = System.in.read();}
catch(IOException e) {return null;}
if(car<0 || car=='\n') break;
lin[lg++] += car;
}
if(car<0 && lg==0) return null;
return new String(lin, 0, lg).trim();
}
}[/java]

[cpp]#include <iostream>
#include <string>

#define MAX_INPUT 1024
#define GENERATOR 34943

using namespace std;

int main() {
char in[MAX_INPUT];
while(cin.getline(in, MAX_INPUT, '\n')) {
int len = strlen(in);

if(in[len-1] == '\r') len--;

if(len == 0) {
cout << "00 00" << endl;
continue;
}

if(in[0] == '#') return 0;

long crc = 0;
for(int i = 0; i < len; i++)
crc = ((crc << 8) + in) % GENERATOR;
crc = (crc << 16) % GENERATOR;
if(crc) crc = GENERATOR - crc;

long hiByte = crc >> 8;
long loByte = crc - (hiByte << 8);

cout.fill('0');
cout.width(2);
cout.setf(ios::uppercase);
cout << hex << hiByte << " " << loByte << endl;
}
return 0;
}[/cpp]

And these programs seem to give identical output for all input sets except the following:

That's 1023 stars, FYI (just remove the returns so its all on one line). Can anyone see why both programs give different output? Am I overflowing anywhere?

Oops. I figured out where the problem was... It turns out that, although my JAVA program works fine using simple ints (which is what I used first), the C++ program must use unsigned longs.

Anyway, problem solved once again!

PS, there's a deliberate bug inserted in my program so no one can submit it.