fork(5) download
copy 
  1.  
  2. import java.util.Arrays;
  3. import java.util.HashSet;
  4. import java.util.Iterator;
  5. import java.util.Set;
  6.  
  7.  
  8. abstract class ImmutableLongList implements Iterable<Long> {
  9.  
  10.     public abstract boolean isEmpty();
  11.  
  12.     public abstract ImmutableLongList getTail();
  13.  
  14.     public abstract long getHead();
  15.     private static final ImmutableLongList empty = new ImmutableLongList() {
  16.         @Override
  17.         public boolean isEmpty() {
  18.             return true;
  19.         }
  20.  
  21.         @Override
  22.         public ImmutableLongList getTail() {
  23.             throw new UnsupportedOperationException("Not supported on empty list.");
  24.         }
  25.  
  26.         @Override
  27.         public long getHead() {
  28.             throw new UnsupportedOperationException("Not supported on empty list.");
  29.         }
  30.     };
  31.  
  32.     private class ImmutableLongListIterator implements Iterator<Long> {
  33.         private ImmutableLongList currentList;
  34.  
  35.         public ImmutableLongListIterator(ImmutableLongList currentList) {
  36.             this.currentList = currentList;
  37.         }
  38.  
  39.         @Override
  40.         public boolean hasNext() {
  41.             return !currentList.isEmpty();
  42.         }
  43.  
  44.         @Override
  45.         public Long next() {
  46.             final Long result = currentList.getHead();
  47.             currentList = currentList.getTail();
  48.             return result;
  49.         }
  50.  
  51.         @Override
  52.         public void remove() {
  53.             throw new UnsupportedOperationException("Not supported yet.");
  54.         }
  55.     }
  56.  
  57.     @Override
  58.     public Iterator<Long> iterator() {
  59.         return new ImmutableLongListIterator(this);
  60.     }
  61.  
  62.     public static ImmutableLongList getEmpty() {
  63.         return empty;
  64.     }
  65.  
  66.     private static final class NonEmptyList extends ImmutableLongList {
  67.  
  68.         private final long head;
  69.         private final ImmutableLongList tail;
  70.  
  71.         private NonEmptyList(final long head, final ImmutableLongList tail) {
  72.             this.head = head;
  73.             this.tail = tail;
  74.         }
  75.  
  76.         @Override
  77.         public boolean isEmpty() {
  78.             return false;
  79.         }
  80.  
  81.         @Override
  82.         public long getHead() {
  83.             return head;
  84.         }
  85.  
  86.         @Override
  87.         public ImmutableLongList getTail() {
  88.             return tail;
  89.         }
  90.     }
  91.  
  92.     public static ImmutableLongList makeList(final int head, final ImmutableLongList tail) {
  93.         return new NonEmptyList(head, tail);
  94.     }
  95. }
  96.  
  97. /**
  98.  * @author User
  99.  */
  100. public class Main {
  101.  
  102.     final int kwota = 29;
  103.     final int[] nominały = new int[]{12, 5, 7, 4, 1};
  104.     final ImmutableLongList[] L = new ImmutableLongList[kwota + 1];
  105.     final long[] W = new long[kwota + 1];
  106.     final long pseudoInfinity = Long.MAX_VALUE;
  107.  
  108.     void run() throws Exception {
  109.         Arrays.fill(L, ImmutableLongList.getEmpty());
  110.         Arrays.fill(W, pseudoInfinity);
  111.         W[0] = 0;
  112.         for (final int nominał : nominały) {
  113.             for (int i = nominał; i < W.length; i++) {
  114.                 if (W[i - nominał] != pseudoInfinity) {
  115.                     if (W[i - nominał] + 1 < W[i]) {
  116.                         W[i] = W[i - nominał] + 1;
  117.                         L[i] = ImmutableLongList.makeList(nominał, L[i - nominał]);
  118.                     }
  119.                 }
  120.             }
  121.             for (int i = 0; i < W.length; i++) {
  122.                 final long v = W[i];
  123.                 if (v == pseudoInfinity) {
  124.                     System.out.print(" --, ");
  125.                 } else {
  126.                     System.out.format("%3d, ", W[i]);
  127.                 }
  128.             }
  129.             System.out.println("objects count: " + objectsCount(L));
  130.         }
  131.         System.out.print("Change: ");
  132.         for (final long nominał : L[kwota]) {
  133.             System.out.println(nominał + ", ");
  134.         }
  135.         System.out.println();
  136.  
  137.     }
  138.  
  139.     long objectsCount(final ImmutableLongList[] lists) {
  140.         final Set<ImmutableLongList> objects = new HashSet<ImmutableLongList>();
  141.         long wynik = lists.length == 0 ? 0 : 1; // empty lists by default
  142.         for (final ImmutableLongList list : lists) {
  143.             ImmutableLongList currentHead = list;
  144.             while (currentHead != ImmutableLongList.getEmpty()) {
  145.                 wynik += objects.add(currentHead) ? 1 : 0;
  146.                 currentHead = currentHead.getTail();
  147.             }
  148.         }
  149.         return wynik;
  150.     }
  151.  
  152.     public static void main(final String[] args) throws Exception {
  153.         new Main().run();
  154.     }
  155. }
  156.  
Success #stdin #stdout 0.04s 245760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
  0,  --,  --,  --,  --,  --,  --,  --,  --,  --,  --,  --,   1,  --,  --,  --,  --,  --,  --,  --,  --,  --,  --,  --,   2,  --,  --,  --,  --,  --, objects count: 3
  0,  --,  --,  --,  --,   1,  --,  --,  --,  --,   2,  --,   1,  --,  --,   3,  --,   2,  --,  --,   4,  --,   3,  --,   2,   5,  --,   4,  --,   3, objects count: 12
  0,  --,  --,  --,  --,   1,  --,   1,  --,  --,   2,  --,   1,  --,   2,   3,  --,   2,  --,   2,   4,   3,   3,  --,   2,   5,   3,   4,   4,   3, objects count: 18
  0,  --,  --,  --,   1,   1,  --,   1,   2,   2,   2,   2,   1,   3,   2,   3,   2,   2,   3,   2,   3,   3,   3,   3,   2,   4,   3,   4,   3,   3, objects count: 26
  0,   1,   2,   3,   1,   1,   2,   1,   2,   2,   2,   2,   1,   2,   2,   3,   2,   2,   3,   2,   3,   3,   3,   3,   2,   3,   3,   4,   3,   3, objects count: 30
Change: 5, 
12, 
12,
https://ideone.com/d6suB
language:
Java (HotSpot 12)
created:
13 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!