fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6. import java.math.*;
  7. import java.util.*;
  8.  
  9. /* Name of the class has to be "Main" only if the class is public. */
  10. class Ideone
  11. {
  12. 	private static Map<String, Integer> m = new HashMap<String, Integer>();
  13.     static{
  14.     m.put("1",0);
  15.     m.put("2",1);
  16.     }
  17.     public static int answer(String n) { 
  18.         // Your code goes here.
  19.         int p=0;
  20.         BigInteger z = new BigInteger(n);
  21.         BigInteger o = new BigInteger("1");
  22.         BigInteger t = new BigInteger("2");
  23.         BigInteger ze = new BigInteger("0");
  24.         BigInteger pe = new BigInteger(n);
  25.         if(z.compareTo(ze)==0) return 1;
  26.         if(z.compareTo(o)==0) return p;
  27.         BigInteger k=z.remainder(t);
  28.         int re=k.compareTo(ze);
  29.         if(re==0){
  30.             z=z.divide(t);
  31.             if(m.containsKey(z.toString())) {return 1+m.get(z.toString());}
  32.             else m.put(pe.toString(),1+answer(z.toString()));
  33.             return m.get(pe.toString());
  34.         }else{
  35.             int a,b;
  36.             z=z.subtract(o);
  37.             if(m.containsKey(z.toString())) {
  38.                 a=1+m.get(z.toString());
  39.             }
  40.             else{
  41.                 a=1+answer(z.toString());
  42.                 m.put(z.toString(),a-1);
  43.             }
  44.             z=z.add(t);
  45.             if(m.containsKey(z.toString())) b=m.get(z.toString());
  46.             else {
  47.                 b=1+answer(z.toString());
  48.                 m.put(z.toString(),b-1);
  49.             }
  50.             z=z.subtract(o);
  51.             if(a>b){
  52.                 m.put(pe.toString(),b);
  53.                 return b;
  54.             }
  55.             else {
  56.                 m.put(pe.toString(),a);
  57.                 return a;
  58.             }
  59.         }
  60.     } 
  61. 	public static void main (String[] args) throws java.lang.Exception
  62. 	{
  63. 		// your code goes here
  64. 		System.out.print(answer("0"));
  65. 	}
  66. }
Success #stdin #stdout 0.05s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/zeKlHs
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!