389 - Basically Speaking

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

Moderator: Board moderators

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

For

Code: Select all

0000000000000000000000000000 2 15
1111111111111111111111111111 2 16
0111111111111111111111111111 2 16
my program returns

Code: Select all

      0
     7F
     3F

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish »

there.. i got the bug! :D
obviously the correct output is

Code: Select all

0
FFFFFFF
7FFFFFF
if u can think of it .. u can do it in software.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

Sorry, but I'm afraid you did not find the bug!

Your output is exactly the output I got before changing my program.

As that version received a WA, I thought that if the calculator has a 7-digit-display, only the first seven input characters should be retained which led the output posted above.

But thanks a lot for your post, now at least I know that my first version was correct in that respect.

Added July, 9th

To sum things up, here's my current input and output:

input:

Code: Select all

   -12   10 10
   -12 10                                   2
12345678 10 10
     1111000   2  10
     1111000   2  16
     2102101   3    10
   2102101   3 15
    12312      4     2
     1A 15  2
   1234567  10     16
     ABCD  16 15
        0  2     15
     ABCD   16 16
   000000F 16       10
        1A 15 15
    0000000  16 10
    0000000  16      16
    0000000  10 10
          0  16 10
          00  16      16
         000  10 10
65536 10 2
64 10 2
1111111 2 16
111111 2                        2
63 10 2
1111111 2 2
127 10 2
11111111 2 2
255 10 2
0000000000000000000000000000 2 15
1111111111111111111111111111 2 16
0111111111111111111111111111 2 16
output:

Code: Select all

    -12
  -1100
  ERROR
    120
     78
   1765
    7CA
  ERROR
  11001
 12D687
   D071
      0
   ABCD
     15
     1A
      0
      0
      0
      0
      0
      0
  ERROR
1000000
     7F
 111111
 111111
1111111
1111111
  ERROR
  ERROR
      0
FFFFFFF
7FFFFFF

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish »

..cant think of any other possibilties ..:( but i can give u my code if u want

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

Six months later:

I've solved all other simple base conversion problems, but this one still does not work.

Could somebody please verify the following input/output and, if possible, post some really strange data (I've already tested some randomly generated input.)

input:

Code: Select all

000ABCD 16 15
1111000  2 10
1111000  2 16
2102101  3 10
2102101  3 15
  12312  4  2


     1A 15  2
1234567 10 16
   ABCD 16 15

0000000000000000000000000000 2 15
1111111111111111111111111111 2 16
0111111111111111111111111111 2 16
1111111111111111111111111111 16 2
0111111111111111111111111111 16 2

  -12   10 10
   -12 10                                   2
12345678 10 10
     1111000   2  10
     1111000   2  16
     2102101   3    10
   2102101   3 15
    12312      4     2
     1A 15  2
   1234567  10     16
     ABCD  16 15
        0  2     15
     ABCD   16 16
   000000F 16       10
        1A 15 15
    0000000  16 10
    0000000  16      16
    0000000  10 10
          0  16 10
          00  16      16
         000  10 10
         65536 10 2
64 10 2
1111111 2 16
111111 2                        2
63 10 2
1111111 2 2
127 10 2
11111111 2 2
255 10 2
output:

Code: Select all

   D071
    120
     78
   1765
    7CA
  ERROR
  11001
 12D687
   D071
      0
FFFFFFF
7FFFFFF
  ERROR
  ERROR
    -12
  -1100
  ERROR
    120
     78
   1765
    7CA
  ERROR
  11001
 12D687
   D071
      0
   ABCD
     15
     1A
      0
      0
      0
      0
      0
      0
  ERROR
1000000
     7F
 111111
 111111
1111111
1111111
  ERROR
  ERROR

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

There are NO NEGATIVE INTEGERS in the input. As for the rest, your output is correct, according to my AC solution.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

to mf: Thanks for answering

Ok, if there are no negative integers in the input, my program won't print any, so that couldn't possibly be the cause of WA, could it?

Do you have any absolutely crazy, mad, silly, loco examples I culd use as an additional test?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

Well, does your program handle these cases, when the number overflows int type:

Code: Select all

F0000000 16 10
F00000000 16 10
If that's not the problem, post your code, I'll try to help you.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

In both cases the program returns ERROR and that should be ok.

Here's the code:

Code: Select all

#include <stdio.h>           /* scanf, printf, ... */
#include <string.h>          /* strlen, memmove */
#include <ctype.h>           /* isspace */
#include <math.h>            /* pow */

/*******************************
 * ACM Contest - Problem 389   *
 * Basically Speaking          *
 * WA after umph submissions   *
 *******************************/

#ifdef ONLINE_JUDGE
#define LONG long long int
#else
#define LONG __int64
#endif

#define LIMIT 268435456

#define MAXLINE 1000
char LINE[MAXLINE];
int readline(char []);

#define strmove(d,s) memmove(d,s,strlen(s)+1)
char *rmlead(char *);
char *rmtrail(char *);

char SYM[16] = {'0','1','2','3','4','5','6','7',
                '8','9','A','B','C','D','E','F'};

void reverse(char []);
void print(char []);
short base10(int, char [], LONG *);

int main(void)
{
  int rv;
  int i, oldbase, newbase;
  char number[MAXLINE], stout[MAXLINE];
  LONG x, xn;
  long rem;
  short neg;
  rv = readline(LINE);
  while (rv >= 0){
    if (rv > 0){
      sscanf(LINE,"%s %d %d",number,&oldbase,&newbase);
/* don't know whether there are negative */
/* values, but just in case ... */
      neg = (number[0] == '-');
/* if bases are identical, no need to call base10 */
      if (oldbase == newbase){
        if (strlen(number) < 8){
          print(number);
        }
        else{
          printf("  ERROR\n");
        }
      }
      else{ /* oldbase != newbase */
/*      if (strlen(number) > 7) number[7] = '\0'; wrong!!! */
        if (neg) number[0] = ' ';
        if (!base10(oldbase,number,&x)){
          printf("  ERROR\n");
        }
        else if (abs(x) < 1){
          printf("      0\n",number);
        }
        else{
          if (newbase == 10){
            sprintf(stout,"%7ld",x);
            printf("%s\n",stout);
          }
          else{
            i = 0;
            while (x >= 1){
              xn = x/newbase;
              rem = x - newbase*xn;
              x = xn;
              stout[i++] = SYM[rem];
              stout[i] = '\0';
            }
            if (neg){
              stout[i++] = '-';
              stout[i] = '\0';
            }
            if (strlen(stout) > 7)
              printf("  ERROR\n");
            else{
              reverse(stout);
              print(stout);
            }
          }
        }
      }
    }
    rv = readline(LINE);
  }
  return 0;
}

int readline(char s[])
/* read input character after character */
{
  int i = 0;
  char ch;
  if (feof(stdin)) return (-1);
  if (fscanf(stdin,"%c",&ch) != 1) return 0;
  while (ch != '\n'){
    if (ch != '\r') s[i++] = ch;
    if (i >= MAXLINE) return (-2);
    if (fscanf(stdin,"%c",&ch) != 1) break;
  }
  s[i] = '\0';
  rmlead(LINE);
  rmtrail(LINE);
  return strlen(s);
}

char *rmlead(char *str)
/* remove leading blanks */
{
  char *obuf;
  if (str){
    for (obuf=str; *obuf && isspace(*obuf);++obuf);
    if (str != obuf)
      strmove(str,obuf);
  }
  return str;
}

char *rmtrail(char *str)
/* remove trailing blanks */
{
  int i;
  if (str && 0 != (i = strlen(str))){
    while (--i >= 0){
      if (!isspace(str[i]))
        break;
    }
    str[++i] = '\0';
  }
  return str;
}

void reverse(char s[])
/* reverse string */
{
  char t[10];
  int i, l;
  l = strlen(s);
  for (i=0;i<l;i++)
    t[i] = s[l-i-1];
  t[l] = '\0';
  strcpy(s,t);
}

void print(char s[])
/* print result, replace leading zeroes with spaces */
/* truncate to seven characters */
{
  int i, l, z;
  l = strlen(s);
  if (l > 7) l = 7;
  if (l < 7)
    for (i=0;i<7-l;i++)
      printf(" ");
  z = i = 0;
  while ((i < l) && (z == 0)){
    if ((s[i] != '0') || (i == l-1))
      z = 1;
    if (z == 0)
      s[i] = ' ';
    i++;
  }
  for (i=0;i<l;i++)
    printf("%c",s[i]);
  printf("\n");
}

short base10(int ob, char st[], LONG *x)
/* convert string to a base 10 number if within range */
{
  int i, k, l;
  LONG xx = 0;
  double dummy;
  l = strlen(st);
  for (i=0;i<l;i++){
    if ((st[i] >= SYM[0]) && (st[i] <= SYM[15])){
      k = st[i] - '0';
      if (k > 9)
        k -= 7;
      dummy = k*pow(ob,l-i-1);
      if (dummy > LIMIT)
        return 0;

      xx += dummy;

    }
  }
  *x = xx;
  return 1;
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

I've found several test cases where your program goes wrong:

Code: Select all

000000000000000000000000000000000001 10 10
F000000 16 10
The correct output must be:

Code: Select all

      1
  ERROR
BTW, you can completely avoid math.h's function, long long, and tweaked I/O. To take input you can use simply: while (scanf(" %[0-9A-F] %d %d", ...) == 3) { ... }

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

Thanks a lot, mf!

Using your hints made program half the size.

Judge is down right now, so I'm not sure whether it's still WA or AC at last.


Added:

Just got the email - Accepted at last!

Thanks again, mf!

J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

Post by J&Jewel »

hi everybody,
:lol: my code give all the input output correctly describe above...but i always got W/A.please gige me more input/output.pleaseeeeee.....
I hate Wrong Answer!

Fadia Ismael
New poster
Posts: 22
Joined: Wed Aug 17, 2005 3:04 pm

389- Basically Speaking, WA

Post by Fadia Ismael »

Hello every one, can you tell me what is the error in this code, I tried it several times without any error, so what is the error???

Hint: I made the same as 355 "The basis are loaded"
Here is the code:

Code: Select all

#include <iostream.h>
#include <iomanip.h>

unsigned int largest(char a[]){
	int i, largest=-2,temp;
	for(i=0; a[i]!='\0'; i++){
		if(a[i]>='0' && a[i]<='9')
			temp=a[i]-48;
		else
			if(a[i]>='A' && a[i]<='F')
				temp=a[i]-55;
			else{
				largest=temp=-1;
				break;
			}
		if(temp>largest)
			largest=temp;
	}
	return largest;
}

unsigned int deciValue(char a[],unsigned int b){
	int i;
	unsigned int result=0U;
	for(i=0; a[i]!='\0'; i++){
		if(a[i]>='0' && a[i]<='9')
			result = result*b + (a[i]-48);
		else
			if(a[i]>='A' && a[i]<='F')
				result = result*b + (a[i]-55);
	}
	return result;
}

void newValue(char temp[],unsigned int n, unsigned int b, int &j){
	int i,t;
	char a[100000];
	if(n==0){
		temp[0]='0';
		temp[1]='\0';
		return;}
	for (i=0; n!=0; i++){
		t=int(n%b);
		if(t>=0 && t<=9)
			t=t+48;
		else 
			if (t>=10 && t<=15)
				t=t+55;
		a[i]=t;
		n=n/b;
	}
	i--;
	for (j=0; i>=0; i--,j++)
		temp[j]=a[i];
	temp[j]='\0';

}	


void main(){
	unsigned int b1, b2, lar;
	int j;
	char number[100000];
	char result[100000];

	while(cin>>number){
		cin>>b1>>b2;
		if(b1<2 || b1>16 || b2<2 || b2>16)
			break;
		lar=largest(number);
		if(lar>=b1){
			cout<<setw(7)<<"ERROR"<<endl;
			continue;}
		
		newValue(result,deciValue(number,b1), b2, j);
		if(j>7)
			cout<<setw(7)<<"ERROR"<<endl;
		else
			cout<<setw(7)<<result<<endl;
		
	}
}
It's lack of faith that makes people afraid of meeting challanges, and I believe in myself.

tosun_ewu
New poster
Posts: 4
Joined: Tue Aug 03, 2004 7:02 am

389 Basically Speaking

Post by tosun_ewu »

Code: Select all


GOT ACC

Last edited by tosun_ewu on Tue Jun 26, 2007 1:58 am, edited 1 time in total.

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

389 - 8 months? WA

Post by smilitude »

I just saw, I spend more than 8 months to solve this problem.
I have tried every single input output, that i could get at eboard, or i could imagine. But nothing worked. I rewrote the whole code today, still getting WA. Is there anyone, who can tell me whats wrong with my code, or whats wrong with this problem?

ACed

/*
* basically speaking
* submission 1 WA
* coded at 118pm, july 10, 2006
*
*/
THANKS TO .B.



Please help me to get out from 8 months misery!
Last edited by smilitude on Mon Jul 31, 2006 11:48 am, edited 1 time in total.
fahim
#include <smile.h>

Post Reply

Return to “Volume 3 (300-399)”