10343 - Base64 Decoding

[Julien Cornebise]

Hi
Would it be possible that there is an error in the test set for the 10343d problem ?
I would usually never dare to ask such a thing, but given that this problem is brand new on the server, it could be possible, couldn't it ? Already 97 posts have been made (10 of mine), 72 of them Wrong Answer.
I'm looking for somebody who could assure me that the test set is good (getting an Accepted would be a good proof or for a judge to verify the test set... Once again, I usually would'nt ask such a thing, wouldn't the problem be brand new.
Thanks

[Ivor]

See sticky thread in misc section. There is a post about this problem.

Ivor

[Julien Cornebise]

Thanks a lot Hope it'll be fixed soon.

[Bistromath]

Hi,

I read all posts about problem 10343 but always get WA.

The description of the problem says that "Each dataset consists of a valid Base64 encoding of some (possibly binary) data".
But how can i take this binary data into account ?

Here the code i have submitted

Thanks for any help

[cpp]
#include <stdio.h>

char Buffer[200000] ;

class CBase64Decoding
{
public:
CBase64Decoding( const char* buffer ) ;

void Decode() const ;

protected:

inline void Putchar( unsigned char c ) const ;
void Flush() const ;
void Decode( const char*,int count ) const;
char Decode( char ) const ;

private:
const char* m_Buffer ;
mutable int m_OutCount ;
enum { OutSize = 1024 } ;
mutable unsigned char m_OutBuffer[OutSize] ;
} ;


CBase64Decoding::CBase64Decoding(const char* buffer)
: m_Buffer( buffer ),
m_OutCount(0 )
{
}

void CBase64Decoding::Decode() const
{
const char* c ;
for ( c = m_Buffer ; *c != 0 ; c+=4 )
{
int count = 3 ;
if ( c[3] == '=' )
{
count-- ;
if ( c[2] == '=' ) count-- ;
}
Decode( c, count ) ;
}
Putchar('#') ;
Flush() ;
}


void CBase64Decoding::Decode( const char* str, int count ) const
{
char dStr[4] ;
for ( int i = 0 ; i < count+1 ; ++i )
dStr = Decode( str ) ;
unsigned char c0 = ( dStr[0] << 2 ) | ( ( dStr[1] & 0x30 ) >> 4 ) ;
Putchar(c0 ) ;
if ( count == 1 )
return ;
unsigned char c1 = ( ( dStr[1] & 0x0F ) << 4 ) | ( ( dStr[2] & 0x3C ) >> 2 );
Putchar(c1 ) ;
if ( count == 2 )
return ;
unsigned char c2 = ( ( dStr[2] & 0x03 ) << 6 ) | dStr[3] ;
Putchar(c2 ) ;

}


char CBase64Decoding::Decode( char c ) const
{
if ( c >= 'A' && c <= 'Z' ) return c-'A' ;
if ( c >= 'a' && c <= 'z' ) return 26+c-'a' ;
if ( c >= '0' && c <= '9' ) return 52+c-'0' ;
if ( c == '+' ) return 62 ;
if ( c == '-' ) return 63 ;

return -1 ;
}

inline void CBase64Decoding::Putchar( unsigned char c ) const
{
m_OutBuffer[m_OutCount++] = c ;
if ( m_OutCount==OutSize)
{
fwrite( m_OutBuffer, OutSize, sizeof( unsigned char ), stdout) ;
m_OutCount=0 ;
}
}

void CBase64Decoding::Flush() const
{
if (m_OutCount>0)
{
fwrite( m_OutBuffer, m_OutCount, sizeof( unsigned char ), stdout) ;
m_OutCount=0 ;
}
}

inline bool ValidChar( char c )
{
return
( c >= 'A' && c <= 'Z' ) ||
( c >= 'a' && c <= 'z' ) ||
( c >= '0' && c <= '9' ) ||
( c == '+' ) ||
( c == '-' ) ||
( c == '=' ) ;
}


int main()
{
char c ;
char* pc ;
//_setmode( _fileno( stdout), _O_BINARY );
do
{
pc = Buffer;
while ( ( c = getchar() ) != '#' )
{
if ( ValidChar( c ) )
*pc++ = c ;
}

if ( pc != Buffer )
{
*pc = 0 ;
CBase64Decoding( Buffer).Decode() ;
}
} while ( pc != Buffer ) ;
}
[/cpp]

[..]

To Bistromath,

You used '-' in your code. However, the correct char for code 63 is '/'

[anupam]

yes that is the only mistake here.
thanks.

[Bistromath]

stupid mistake
thanks for your help
got AC now

[pipo]

hi...
I had summitted my source several times..
But. I always got RTE...
would you please tell why it is..??
And... would you tell me some inputs and outputs ?
would you tell me the approach for solving this problem.. ??
in my thought, this quiz is very terrible ...

my code is following...

Code: Select all

#include <stdio.h>

#define MAX 100

char mapping(char ch);

void main(void)
{
	char encode[MAX];
	char decode[MAX];
	char temp;
	int i, j, k, len;
	int extra;

	while ( 1 ) 
	{
		i = 0;

		while ( (temp = getchar()) != '#' )
		{
			if ( (temp = mapping(temp)) != -1 ) 
				encode[i++] = temp;
		}
		encode[i] = '#';
		
		if ( encode[0] == '#' ) 
			break;
		
		extra = i % 4;

		while ( extra-- )
			encode[i++] = '=';

		len = i;

		for ( i = j = 0 ; i < len ; i += 4 ) 
		{
			k = i;

			// first
			temp = encode[k] << 2;
			k++;
			temp += (encode[k] & 0x30) >> 4;
			decode[j++] = temp;

			// second
			temp = (encode[k] & 0x0f) << 4;
			k++;
			temp += (encode[k] & 0x3d) >> 2;
			decode[j++] = temp;

			// third
			temp = (encode[k] & 0x03) << 6;
			k++;
			temp += (encode[k] & 0x3f);
			decode[j++] = temp;

		}

		decode[j] = 0;

		printf("%s#", decode);
	}			
}	

char mapping(char ch)
{
	if ( ch == '+' ) 
		return 62;
	else if ( ch == '/' ) 
		return 63;
	else if ( 'A' <= ch && ch <= 'Z' ) 
		return ch - 'A';
	else if ( 'a' <= ch && ch <= 'z' ) 
		return ch - 'a' + 26;
	else if ( '0' <= ch && ch <= '9' ) 
		return ch - '0' + 52;
	else if ( ch == '=' ) 
		return 0;
	else 
		return -1;
}

thanks a lot..

[mohiul alam prince]

hi
i have changed MAX 10005
and got WA

[pipo]

hi...
thanks...

but... according to the problem

The encoded output stream must be represented in lines of no more than 76 characters each

when i set the value of MAX to 100, why RTE ???

and.. when the value of MAX is 10005, why WA ???

in my opinion, the algorithm is right...

would you explain the reason ?

[pipo]

greetings....
i have submitted my source several times...
but, i always got WA...
i dont really know why it is wrong..
who help me ?
please explain to me the reason..
the source is .....

Code: Select all

#include <stdio.h>

#define MAX 11000

unsigned char mapping(char ch);

void main(void)
{
	unsigned char encode[MAX];
	unsigned char decode[MAX];
	unsigned char temp;
	int i, j, k, len;
	int equal_cnt;

	while ( 1 ) 
	{
		equal_cnt = i = 0;

		while ( 1 ) 
		{
			temp = mapping(getchar());
			
			if ( temp == 255 ) 
				continue;

			if ( temp == '=' ) 
			{
				equal_cnt++;
				encode[i++] = 0;
			}
			else
				encode[i++] = temp;

			if ( temp == '#' ) 
				break;
		};

		if ( encode[0] == '#' ) 
			break;

		encode[i-1] = 0;

		len = i-1;
		
		for ( i = j = 0 ; i < len ; i += 4 ) 
		{
			k = i;

//			printf("%c%c%c%c --> ", encode[k], encode[k+1], encode[k+2], encode[k+3]);

			// first
			temp = encode[k] << 2;
			k++;
			temp += (encode[k] & 0x30) >> 4;
			decode[j++] = temp;

			// second
			temp = (encode[k] & 0x0f) << 4;
			k++;
			temp += (encode[k] & 0x3d) >> 2;
			decode[j++] = temp;

			// third
			temp = (encode[k] & 0x03) << 6;
			k++;
			temp += (encode[k] & 0x3f);
			decode[j++] = temp;

//			printf("%c%c%c\n", decode[j-3], decode[j-2], decode[j-1]);
		}

		j = j - equal_cnt;

		decode[j++] = '#';
		decode[j] = 0;

		fwrite(decode, j, sizeof(char), stdout);
	}			
}	

unsigned char mapping(char ch)
{
	if ( ch == '+' ) 
		return 62;
	else if ( ch == '/' ) 
		return 63;
	else if ( 'A' <= ch && ch <= 'Z' ) 
		return ch - 'A';
	else if ( 'a' <= ch && ch <= 'z' ) 
		return ch - 'a' + 26;
	else if ( '0' <= ch && ch <= '9' ) 
		return ch - '0' + 52;
	else if ( ch == '=' ) 
		return '=';
	else if ( ch == '#' ) 
		return '#';
	else
		return 255;
}

[beloni]

well...
note that your input is char by char:
dont forget that '\n' is a character, so if there is a line with 76 chars + '\n', the next lines can have many chars more.

[beloni]

hello, my WA code is following:

Code: Select all

DQojaW5jbHVkZSA8c3RkaW8uaD4NCg0KDQppbn
QgZ2V0aW5kZXgoIGNoYXIgY2ggKQ0Kew0KCWlm
KCBjaCA+PSAnQScgJiYgY2ggPD0gJ1onICkNCgkJ
cmV0dXJuICggY2ggLSAnQScgKTsNCgllbHNlIGlmIC
ggY2ggPj0gJ2EnICYmIGNoIDw9ICd6JyApDQoJCXJ
ldHVybiAoIGNoIC0gJ2EnICkgKyAyNjsNCgllbHNlIGlm
KCBjaCA+PSAnMCcgJiYgY2ggPD0gJzknICkNCgkJcm
V0dXJuICggY2ggLSAnMCcgKSArIDUyOw0KCWVsc2U
gaWYoIGNoID09ICcrJyApDQoJCXJldHVybiA2MjsNCgll
bHNlIGlmKCBjaCA9PSAnLycgKQ0KCQlyZXR1cm4gNjM
7DQoJZWxzZSBpZiggY2ggPT0gJz0nICkNCgkJcmV0d
XJuIDEwMDsNCgllbHNlDQoJCXJldHVybiAtMTsNCn0NC
g0KDQp2b2lkIGRlY29kZSggY29uc3QgaW50ICpncm91cCAp
DQp7DQoJY2hhciByZXMgPSBncm91cFswXTsNCglyZXMgPDw9I
DI7DQoJcmVzIHw9IGdyb3VwWzFdID4+IDQ7DQoJcHV0Y2hhcihyZXMpO
w0KDQoJcmVzID0gZ3JvdXBbMV0gJiAweDAwMEY7DQoJcmVzIDw8PSA0Ow
0KCWlmKCBncm91cFsyXSAhPSAxMDAgKQ0KCQl7DQoJCQlyZXMgfD0gZ3JvdX
BbMl0gPj4gMjsNCgkJCXB1dGNoYXIocmVzKTsNCgkJCWlmKCBncm91cFszXSAhP
SAxMDAgKQ0KCQkJCXsNCgkJCQkJcmVzID0gZ3JvdXBbMl0gJiAweDAwMDM7DQ
oJCQkJCXJlcyA8PD0gNjsNCgkJCQkJcmVzIHw9IGdyb3VwWzNdOw0KCQkJCQlwdXRjaGFy
KHJlcyk7DQoJCQkJfQ0KCQl9DQp9DQoNCg0KaW50IG1haW4oKQ0Kew0KCWludC
BzaXplID0gMCwgZ3JvdXBbNF07DQoJY2hhciBwcmV2ID0gMCwgY2g7DQoNCgl
3aGlsZSggc2NhbmYoICIlYyIsICZjaCApID09IDEgKQ0KCQl
7DQoJCQlpZiggZ2V0aW5kZXgoY2gpID49IDAgKQ0KCQkJCX
sNCgkJCQkJaWYoIHNpemUgPT0gMyApDQoJCQkJCQl7DQoJCQ
kJCQkJZ3JvdXBbM10gPSBnZXRpbmRleChjaCk7DQoJCQkJCQkJc2l6
ZSA9IDA7DQoJCQkJCQkJZGVjb2RlKCBncm91cCApOw0KCQkJCQkJfQ0
KCQkJCQllbHNlDQoJCQkJCQlncm91cFtzaXplKytdID0gZ2V0aW5kZXgoY2gpOw0KCQkJCQlwcmV2ID0gY2
g7DQoJCQ
kJfQ0KCQkJZWxzZSBpZiggY2ggPT0gJyMnICYmIHByZXYgIT0gJyMnICkNCgkJCQl7DQoJCQkJCXByaW50ZiggI
iMiICk7DQoJCQkJCXByZXYgPSBjaDsNCgkJCQl9DQoJCX
0NCg0KCXJldHVybiAwOw0KfQkJCQkNCg==

(after I got AC, I've put my code base64 encoded, hehe) 

for the input file:

VGhpc0lzVGVzdA==
#
QSBUZXN0IElucHV0W3so
KX1d
##
SG9sZCBtZSBub3cNCkknbSBzaXggZmVldCBmcm9tIHRoZSBlZGdlLi4=


#
Z2Fkb3VrZW4gbm8gcGMhISE=#

#######

my program gives the output:

ThisIsTest#A Test Input[{()}]#Hold me now
I'm six feet from the edge..#gadouken no pc!!!#

(whitout a '\n' caracter at end of line)

what is wrong ???
thanks

[beloni]

hey men, please reply to me !!!

thanls

[the LA-Z-BOy]

Code: Select all

#include <stdio.h>


int getindex( char ch )
{
	if( ch >= 'A' && ch <= 'Z' )
		return ( ch - 'A' );
	else if ( ch >= 'A' && ch <= 'z' )
		return ( ch - 'a' ) + 26;
.....

as you might have seen it already ... else if (ch >='A' && ch <='z')... shouldn't it be 'a' instead of 'A' ? [ and there are characters possible between 'Z' and 'a' in ascii exclusive]

moverover... don't print any newline at the end .... it will give you Wrong Answer... and please remove your code after you've got Accepted.