fork download
copy 
  1. import java.lang.Math; // headers MUST be above the first class
  2. import java.util.*;
  3. import java.io.*;
  4. // one class needs to have a main() method
  5. class HelloWorld
  6. {
  7.   // arguments are passed using the text field below this editor
  8.   public static void clear(TreeMap<Integer, Integer> tree)
  9.   {
  10.     for(Integer e : tree.keySet())
  11.     {
  12.       tree.put(e, 0);
  13.     }
  14.   }
  15.   public static void calc(TreeMap<Integer, Integer> yes, int value, int e)
  16.   {
  17.     if(value(yes) + e*(yes.get(e)+1)<=value)
  18.     	coinAdd(yes, value, e);
  19.     while(hasKey(yes.lowerKey(e)))
  20.     {
  21.       e = yes.lowerKey(e);
  22.       if(value(yes) + e*(yes.get(e)+1)<=value)
  23.       	coinAdd(yes, value, e);
  24.     }
  25.   }
  26.   public static boolean hasKey(Integer key)
  27.   {
  28.     if(key!=null)
  29.       return true;
  30.     return false;
  31.   }
  32.   public static void coinAdd(TreeMap<Integer, Integer> yes, int value, int key)
  33.       {
  34.           yes.put(key, yes.get(key)+1);
  35.       }
  36.      public static int value(TreeMap<Integer, Integer> yes)
  37.       {
  38.         int value = 0;
  39.         for(Integer e : yes.keySet())
  40.         {
  41.           value += (yes.get(e)*e);
  42.         }
  43.         return value;
  44.       }
  45.   public static void main(String[] args) throws Exception
  46.   {
  47.    	Scanner scan = new Scanner(System.in);
  48.     int num = scan.nextInt();
  49.     TreeMap<Integer, Integer> yes = new TreeMap<Integer, Integer>();
  50.     for(int i = 0; i<num; i++)
  51.     {
  52.       yes.put(scan.nextInt(), 0);
  53.     }
  54.     int value = scan.nextInt();
  55.     int e = yes.lastKey();
  56.     HelloWorld.calc(yes, value, e);
  57.     Stack<Integer> thing = new Stack<Integer>();
  58.     for(Integer f : yes.keySet())
  59.     	thing.push(f);
  60.     while(!thing.isEmpty())
  61.     {
  62.       Integer f = thing.pop();
  63.       if(HelloWorld.value(yes)==value)
  64.       {
  65.          String what = "";
  66.         for(Integer g : yes.keySet())
  67.         {
  68.           what+=yes.get(g) + " of " + g + " coins, ";
  69.         }
  70.         System.out.println(what);
  71.         break;
  72.       }
  73.       else if(HelloWorld.value(yes)!=value&&HelloWorld.hasKey(yes.lowerKey(f)))
  74.       {
  75.         System.out.println (yes);
  76.         HelloWorld.clear(yes);
  77.         f = yes.lowerKey(f);
  78.         HelloWorld.calc(yes, value, f);
  79.       }
  80.       else if(HelloWorld.value(yes)!=value&&!HelloWorld.hasKey(yes.lowerKey(f)))
  81.       {
  82.         System.out.println("You cannot get this value");
  83.         break;
  84.       }
  85.     }
  86.   }
  87. }
  88.  
  89.  
  90.  
Success #stdin #stdout 0.07s 4386816KB
comments (?)
stdin
copy 
7 1 3 7 19 56 76 110 138
stdout
copy 
{1=1, 3=0, 7=1, 19=1, 56=0, 76=0, 110=1}
{1=1, 3=1, 7=0, 19=0, 56=1, 76=1, 110=0}
{1=1, 3=1, 7=1, 19=1, 56=1, 76=0, 110=0}
{1=1, 3=1, 7=1, 19=1, 56=0, 76=0, 110=0}
{1=1, 3=1, 7=1, 19=0, 56=0, 76=0, 110=0}
{1=1, 3=1, 7=0, 19=0, 56=0, 76=0, 110=0}
You cannot get this value
https://ideone.com/iWiqck
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!