11567 - Moliu Number Generator

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

Moderator: Board moderators

Post Reply
Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

11567 - Moliu Number Generator

Post by Obaida » Sun Dec 28, 2008 9:53 am

Why it gets WA?
Some one plz help me.

Code: Select all

removed
Last edited by Obaida on Sun Dec 28, 2008 11:10 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 11567 Moliu Number Generator WA!!!

Post by Articuno » Sun Dec 28, 2008 10:51 am

Try these test cases:

Code: Select all

2000000000
2000000001
1999999999
1888888888
2111111111
1000000000
9999999
1001
2000
3333
4
5
0
The output should be:

Code: Select all

40
41
41
41
40
39
32
14
14
16
3
4
0
Hope it will help. :)
Last edited by Articuno on Sun Dec 28, 2008 10:58 am, edited 1 time in total.
May be tomorrow is a better day............ :)

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11567 Moliu Number Generator WA!!!

Post by Obaida » Sun Dec 28, 2008 10:57 am

Now i understand i was completely wrong with my solution.
Thank you.
Last edited by Obaida on Sun Dec 28, 2008 11:12 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 11567 Moliu Number Generator WA!!!

Post by Articuno » Sun Dec 28, 2008 11:11 am

I used a straight forward approach.
I am illustrating for 2000. The logic is similar to all other cases.

2000
1000
500
250
125[inc or dec?]
124
62
31[inc or dec?]
32
16
8
4
2
1
0
Now we got the number of steps. Try to find the answer where to inc and where to dec.
Hope it will help.
Last edited by Articuno on Sun Dec 28, 2008 11:14 am, edited 1 time in total.
May be tomorrow is a better day............ :)

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11567 Moliu Number Generator WA!!!

Post by Obaida » Sun Dec 28, 2008 11:13 am

Thank you so much. :)
First go top to down in every possible way and count the steps for every one and last select the best.
Am i right???
try_try_try_try_&&&_try@try.com
This may be the address of success.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 11567 Moliu Number Generator WA!!!

Post by Articuno » Sun Dec 28, 2008 11:29 am

You dont need every possible way.
One way is enough. Greedy choice.Think about this:

After decrementing 125 we get 124 and 124/2=62, 62 is divisible by 2.
But if we increment 125 we get 126 and 126/2=63, 63 is not divisible by 2.

Do you get my point why 124 comes after 125 instead of 126?
May be tomorrow is a better day............ :)

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11567 Moliu Number Generator WA!!!

Post by Obaida » Sun Dec 28, 2008 12:30 pm

I got Accepted. :) :) :)
try_try_try_try_&&&_try@try.com
This may be the address of success.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 11567 Moliu Number Generator WA!!!

Post by saiful_sust » Sun Dec 28, 2008 3:44 pm


HELP ME
where is the problem
judge give me WA
:oops: :oops: :oops: :oops:

Code: Select all

CUT after accepted
Last edited by saiful_sust on Mon Dec 29, 2008 10:30 am, edited 1 time in total.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 11567 Moliu Number Generator WA!!!

Post by Articuno » Sun Dec 28, 2008 4:52 pm

Just use long long instead of long :D
May be tomorrow is a better day............ :)

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 11567 Moliu Number Generator WA!!!

Post by saiful_sust » Mon Dec 29, 2008 10:32 am

saiful wrote:thanks for help
now i got it....
:) :) :) :) :) :) :) :)

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

Re: 11567 - Moliu Number Generator

Post by tanmoy » Fri Jan 09, 2009 9:07 pm

i'm getting TLE.what's the problem and i can't think any other idea

Code: Select all

#include<stdio.h>
int c=0, d=0;
bool f1,f2;
int find(int s){
	int f=s;
	c=0,d=0;
	f1=false,f2=false;
	s++,c++;
	while(s%2==0){
		s/=2;
		if(s==1){c++;f1=true;}
		c++;
		}
	f--,d++;
	while(f%2==0){
		f/=2;
		if(f==1){d++;f2=true;}
		d++;
	}
	if(f1==true&&f2==true){
		if(c<d)return -1;
		else return -2;
	}
	else if(c>d)return 1;
	else return 0;
}

int main(){
	int a,b,k;
	while(scanf("%d",&a)!=EOF){
		k=0;
		if(a==0){printf("%d\n",a);continue;}
		else if(a==1){printf("1\n");continue;}
		while(1){
			if(a==0)break;
			    if(a%2!=0){
				b=find(a);
               	if(f1==true&&f2==true){
					if(b==-1)k+=c;
					else k+=d;
					f1=false;
					f2=false;
					break;
				}
				else if(b==1&&f1==true){
					k+=c;
					break;
				}
				else if(b==1&&f1==false){
					a++;
					k++;
				}
				else if(b==0&&f2==true){
					k+=d;
					break;
				}
				else if(b==0&&f2==false){a--;k++;}
				}
			 else{
				     a/=2;
					 if(a==1){k++;a=0;}
					 k++;
			}
		}
		printf("%d\n",k);
		
	}
	return 0;
}


Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11567 - Moliu Number Generator

Post by Chirag Chheda » Sat Jan 10, 2009 1:44 pm

If you are checking all the possible ways then you will surely get a TLE. Just follow the method described above

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 11567 - Moliu Number Generator

Post by Sedefcho » Tue Feb 24, 2009 1:19 am

Does anybody have a proof (or reference to a proof) why this greedy
procedure actually works for this problem (proof of correctness)?

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

11567 - Moliu Number Generator

Post by sazzadcsedu » Wed Jul 29, 2009 9:18 pm

can anyone tell me why runtime error???i m new in java language.so i cant detect whats wrong!!!! :(

Code: Select all

import java.io.*;
public class Main {

     static int n,a;
     static int op;

    public static void main(String[] args) {

        String ss=null;
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
       
        while(true)
        {
             try{
                 

                ss=reader.readLine();
             }
            catch (IOException ioe){}

             if(ss==null)
                 break;
             n=Integer.parseInt(ss);
             op=0;
             while(n!=0)
             {
                 if(n==3){
                     op+=3;
                     break;
                 }

                 if(n%2==0){
                     op+=1;
                     n=n/2;
                 }
                 else
                 {
                    a=(n-1)/2;
                   if(a%2==0)
                       n=n-1;
                   else
                       n=n+1;

                   op+=1;
                 }
             }

             System.out.println(op);
            }
        }

    }
 

Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

Post Reply

Return to “Volume 115 (11500-11599)”