10469 - To Carry or not to Carry

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

Moderator: Board moderators

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10469 - To Carry or not to Carry

Post by lbv » Tue Mar 05, 2013 6:25 am

omarking05 wrote:please can anyone tell me whats wrong with this code ?
  • I think you left some "debugging" couts by accident in this code. I hope you didn't left those in your real submissions, but check that, just in case.
  • Notice how the problem statement is very emphatic about the input numbers being unsigned 32-bit numbers. Consider the range of such numbers. You may try the test cases below.
  • There is a much simpler approach. Review the basic bitwise operators. Can you find an operator that works just like this problem describes?
  • There is already a thread for this problem. Please search the forums before posting a question and use an existing thread if possible. Thanks.
Input

Code: Select all

2147483648 1
893183290 1236679790
Output

Code: Select all

2147483649
2089474388

omarking05
New poster
Posts: 3
Joined: Sat Dec 08, 2012 5:16 pm

Re: 10469 - To Carry or not to Carry

Post by omarking05 » Tue Mar 05, 2013 10:26 am

well im sorry to post new thread in this section but the reason of doing that , that posting a reply in the original thread always don't get much care .

lbv , thanks for your reply ^^
[*]the debugging couts was just to trace something in the code and yes i removed them before submitting the problem
[*]yes i think that UNSIGNED 32BIT NUMBERS is the main reason of the WA xD .. but i used

Code: Select all

unsigned long long int n1,n2,l1,l2,l3;
maybe long long is not correct but i said maybe this is the right thing to do :D .. but i dont know why its wrong although i used "unsigned" as he said in the problem
[*]i know that there is more simple way with one line of code xD but i didn't get it :( so that i chose the hard way so if there any suggestions to know what that operator ( ^ ) means in c++ in simple way i would be thankful ^_^

but i really want to know what should i do in this problem :D .

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10469 - To Carry or not to Carry

Post by lbv » Tue Mar 05, 2013 12:18 pm

omarking05 wrote:well im sorry to post new thread in this section but the reason of doing that , that posting a reply in the original thread always don't get much care .
I think most experienced users of this forum are happier and more willing to help when people follow the rules, which includes not creating new threads when it's not necessary. But that's just my opinion :).

omarking05 wrote: yes i think that UNSIGNED 32BIT NUMBERS is the main reason of the WA xD ..
After taking a second look at your code, I'd say it shows signs of some big gaps in your knowledge about bits/bytes and basic data types.

My suggestion is that you take a step back, take your time to read about data types (learn about the magnitudes of integers that 32-bit and 64-bit int variables can hold, how signed and unsigned variables differ, etc.), and about bits and bitwise operations. It's very important to have a strong understanding of the fundamentals, so don't feel pressured to skip things or move too quickly, go at your own pace.

You should eventually come to understand the errors in your approach. For example, think about the maximum number of decimal digits an "unsigned long long" variable can have, and the number of binary digits in a number like 2147483648.
omarking05 wrote:i know that there is more simple way with one line of code xD but i didn't get it :(
As I said, take your time. If you feel this problem is a little too confusing for you right now, try other problems. Come back to this one later on when you have some more experience and knowledge about bits, bytes, data types, etc.

Good luck :).

GYBTM
New poster
Posts: 2
Joined: Wed Mar 13, 2013 5:58 pm

Uva 10469 new in java

Post by GYBTM » Wed Mar 13, 2013 6:04 pm

hello guys, i am new here for using java and my previous language was C++, and i had solve this problem with C++, but when i use java i get run time error, can you guys help me what wrong with my code?

Code: Select all

import java.util.*;
import java.io.*;

public class Main
{
    public static void main(String[] args) throws Exception
    {
        FastInput in = new FastInput(System.in);
        PrintWriter out = new PrintWriter(System.out, true);

        String a, b;
        long x, y;

        while((a = in.next()) != null) {
            b = in.next();
            x = in.convtoLong(a);
            y = in.convtoLong(b);
            out.println(x ^ y);
        }
        //out.close();
    }
}

class FastInput
{
    BufferedReader br;
    StringTokenizer st;

    public FastInput(InputStream stream)
    {
        br = new BufferedReader(new InputStreamReader(stream));
        st = null;
    }

    public String next()
    {
        while(st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
        return st.nextToken();
    }

    public int nextInt()
    {
        return Integer.parseInt(next());
    }

    public double nextDouble()
    {
        return Double.parseDouble(next());
    }

    public long nextLong()
    {
        return Long.parseLong(next());
    }

    public int convtoInt(String a)
    {
        return Integer.parseInt(a);
    }

    public double convtoDouble(String a)
    {
        return Double.parseDouble(a);
    }

    public long convtoLong(String a)
    {
        return Long.parseLong(a);
    }
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Uva 10469 new in java

Post by brianfry713 » Wed Mar 13, 2013 9:49 pm

https://ideone.com/JA1g63
For the sample input, your runtime error is:
Exception in thread "main" java.lang.RuntimeException: java.lang.NullPointerException
at FastInput.next(Main.java:41)
at Main.main(Main.java:14)
Caused by: java.lang.NullPointerException
at java.util.StringTokenizer.<init>(StringTokenizer.java:199)
at java.util.StringTokenizer.<init>(StringTokenizer.java:236)
at FastInput.next(Main.java:39)
... 1 more
Check input and AC output for thousands of problems on uDebug!

GYBTM
New poster
Posts: 2
Joined: Wed Mar 13, 2013 5:58 pm

Re: Uva 10469 new in java

Post by GYBTM » Thu Mar 14, 2013 5:13 am

oh oke, thanks brian :D

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

Re: 10469 - To Carry or not to Carry

Post by bgcsaif » Fri May 01, 2015 3:05 pm

I used long long int to catch the range.
Checked maximum bits of the largest number and the sum. Decided to print normally addition value if no carry bit. if there is any, i printed the value subtracting the place value for last Digit. I got WA. Help me with critical inputs or any hints to debug my code.

Code: Select all

#include <stdio.h>
int main()
{
	long long int a, b, c, i, k;
	while (scanf("%lld %lld", &a, &b) == 2)
	{
		if(a > b)
		c = a;
		else
		c = b;	
		for (i = 1; i <= c; i = i * 2);
		c = a + b;
		for (k = 1; k <= c; k = k * 2);
		if (k <= i)
			printf("%lld\n", c);
		else
			printf("%lld\n", c - (k / 2));
	}
	return 0;
}

oja
New poster
Posts: 11
Joined: Fri Apr 24, 2015 5:34 pm

Re: 10469 - To Carry or not to Carry

Post by oja » Mon May 04, 2015 8:12 am

If you've read the early posts, you've already found out that the solution is simpler than what your code seems to do.
The problem states that
He was doing bitwise addition but his carry bit always had zero output.
Now how do you do bitwise addition?
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 carry 1
The problem states that the "carry bit always had zero output". So we can ignore the "carry 1" in the last rule.
If we rewrite the rules above:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0
In other words, if the bits are the same (0 0 or 1 1) the answer is 0. If they are different(0 1 or 1 0) the answer is 1.
This is what the c++ bitwise XOR(Exclusive OR) operator (^) does. It deals with the bits of its two operands and
perform the rules above bit by bit. So just use the (^) operator.

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

Re: 10469 - To Carry or not to Carry

Post by bgcsaif » Sun May 10, 2015 3:59 am

Oja!
Thank you.... I got AC using ^
But I fund no error in my code. It does the exact thing. My codes count the sum ignoring carry bit. I think my code has faced data type problem. I stored summatiare on in a variable. If both numbers are big enough then my summing variable will have to handle twice of it's range. That's where it might stuck. Anyway, Thanks again :-)

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

Re: 10469 - To Carry or not to Carry

Post by bgcsaif » Sun May 10, 2015 4:01 am

Oja!
Thank you.... I got AC using ^
But I fund no error in my code. It does the exact thing. My codes count the sum ignoring carry bit. I think my code has faced data type problem. I stored summation in a variable. If both numbers are big enough then my summing variable will have to handle twice of it's range. That's where it might stuck. Anyway, Thanks again :-)

Post Reply

Return to “Volume 104 (10400-10499)”