10343 - Base64 Decoding

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

Moderator: Board moderators

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

10343 - Base64 Decoding

Post by Julien Cornebise » Sun Aug 04, 2002 6:38 pm

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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Sun Aug 04, 2002 6:53 pm

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

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Thank you

Post by Julien Cornebise » Thu Aug 08, 2002 12:32 pm

Thanks a lot :) Hope it'll be fixed soon.

Bistromath
New poster
Posts: 16
Joined: Fri Oct 11, 2002 11:03 pm
Location: France

Post by Bistromath » Wed Nov 20, 2002 5:13 pm

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]

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Dec 20, 2002 9:12 am

To Bistromath,

You used '-' in your code. However, the correct char for code 63 is '/'
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Fri Dec 20, 2002 12:36 pm

yes that is the only mistake here.
thanks. :P
"Everything should be made simple, but not always simpler"

Bistromath
New poster
Posts: 16
Joined: Fri Oct 11, 2002 11:03 pm
Location: France

Post by Bistromath » Sun Dec 29, 2002 4:15 pm

stupid mistake :o
thanks for your help
got AC now :)

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

10343 RTE.. help please

Post by pipo » Tue Feb 01, 2005 7:55 am

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..

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Tue Feb 01, 2005 12:55 pm

hi
i have changed MAX 10005
and got WA

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

Post by pipo » Wed Feb 02, 2005 1:26 am

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
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

10343 WA... help please...

Post by pipo » Sun Feb 13, 2005 7:38 am

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
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Tue May 09, 2006 12:59 am

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.
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Mon Jun 05, 2006 10:20 pm

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) 
:lol: :lol:


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
Last edited by beloni on Tue Jun 13, 2006 4:40 pm, edited 2 times in total.
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Mon Jun 12, 2006 8:26 pm

hey men, please reply to me !!!

thanls
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Tue Jun 13, 2006 7:56 am

beloni wrote:

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' :D? [ 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.
Istiaque Ahmed [the LA-Z-BOy]

Post Reply

Return to “Volume 103 (10300-10399)”