Advertisement
dzocesrce

[APS] Sum of Previous Elements

Aug 28th, 2023
484
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.82 KB | None | 0 0
  1. // slatka zadaca kako jagoda
  2. import java.util.Scanner;
  3. class DLLNode<E> {
  4.     protected E element;
  5.     protected DLLNode<E> pred, succ;
  6.  
  7.     public DLLNode(E elem, DLLNode<E> pred, DLLNode<E> succ) {
  8.         this.element = elem;
  9.         this.pred = pred;
  10.         this.succ = succ;
  11.     }
  12.  
  13.     @Override
  14.     public String toString() {
  15.         return element.toString();
  16.     }
  17. }
  18.  
  19. class DLL<E> {
  20.     private DLLNode<E> first, last;
  21.  
  22.     public DLL() {
  23.         // Construct an empty SLL
  24.         this.first = null;
  25.         this.last = null;
  26.     }
  27.  
  28.     public void deleteList() {
  29.         first = null;
  30.         last = null;
  31.     }
  32.  
  33.     public int length() {
  34.         int ret;
  35.         if (first != null) {
  36.             DLLNode<E> tmp = first;
  37.             ret = 1;
  38.             while (tmp.succ != null) {
  39.                 tmp = tmp.succ;
  40.                 ret++;
  41.             }
  42.             return ret;
  43.         } else
  44.             return 0;
  45.  
  46.     }
  47.  
  48.     public DLLNode<E> find(E o) {
  49.         if (first != null) {
  50.             DLLNode<E> tmp = first;
  51.             while (tmp.element != o && tmp.succ != null)
  52.                 tmp = tmp.succ;
  53.             if (tmp.element == o) {
  54.                 return tmp;
  55.             } else {
  56.                 System.out.println("Elementot ne postoi vo listata");
  57.             }
  58.         } else {
  59.             System.out.println("Listata e prazna");
  60.         }
  61.         return first;
  62.     }
  63.  
  64.     public void insertFirst(E o) {
  65.         DLLNode<E> ins = new DLLNode<E>(o, null, first);
  66.         if (first == null)
  67.             last = ins;
  68.         else
  69.             first.pred = ins;
  70.         first = ins;
  71.     }
  72.  
  73.     public void insertLast(E o) {
  74.         if (first == null)
  75.             insertFirst(o);
  76.         else {
  77.             DLLNode<E> ins = new DLLNode<E>(o, last, null);
  78.             last.succ = ins;
  79.             last = ins;
  80.         }
  81.     }
  82.  
  83.     public void insertAfter(E o, DLLNode<E> after) {
  84.         if(after==last){
  85.             insertLast(o);
  86.             return;
  87.         }
  88.         DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
  89.         after.succ.pred = ins;
  90.         after.succ = ins;
  91.     }
  92.  
  93.     public void insertBefore(E o, DLLNode<E> before) {
  94.         if(before == first){
  95.             insertFirst(o);
  96.             return;
  97.         }
  98.         DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
  99.         before.pred.succ = ins;
  100.         before.pred = ins;
  101.     }
  102.  
  103.     public E deleteFirst() {
  104.         if (first != null) {
  105.             DLLNode<E> tmp = first;
  106.             first = first.succ;
  107.             if (first != null) first.pred = null;
  108.             if (first == null)
  109.                 last = null;
  110.             return tmp.element;
  111.         } else
  112.             return null;
  113.     }
  114.  
  115.     public E deleteLast() {
  116.         if (first != null) {
  117.             if (first.succ == null)
  118.                 return deleteFirst();
  119.             else {
  120.                 DLLNode<E> tmp = last;
  121.                 last = last.pred;
  122.                 last.succ = null;
  123.                 return tmp.element;
  124.             }
  125.         }
  126.         // else throw Exception
  127.         return null;
  128.     }
  129.  
  130.     public E delete(DLLNode<E> node) {
  131.         if(node==first){
  132.             deleteFirst();
  133.             return node.element;
  134.         }
  135.         if(node==last){
  136.             deleteLast();
  137.             return node.element;
  138.         }
  139.         node.pred.succ = node.succ;
  140.         node.succ.pred = node.pred;
  141.         return node.element;
  142.  
  143.     }
  144.  
  145.     @Override
  146.     public String toString() {
  147.         String ret = new String();
  148.         if (first != null) {
  149.             DLLNode<E> tmp = first;
  150.             ret += tmp + "<->";
  151.             while (tmp.succ != null) {
  152.                 tmp = tmp.succ;
  153.                 if(tmp.succ==null){
  154.                     ret+=tmp;
  155.                     break;
  156.                 }
  157.                 ret += tmp + "<->";
  158.             }
  159.         } else
  160.             ret = "Prazna lista!!!";
  161.         return ret;
  162.     }
  163.  
  164.     public String toStringR() {
  165.         String ret = new String();
  166.         if (last != null) {
  167.             DLLNode<E> tmp = last;
  168.             ret += tmp + "<->";
  169.             while (tmp.pred != null) {
  170.                 tmp = tmp.pred;
  171.                 ret += tmp + "<->";
  172.             }
  173.         } else
  174.             ret = "Prazna lista!!!";
  175.         return ret;
  176.     }
  177.  
  178.     public DLLNode<E> getFirst() {
  179.         return first;
  180.     }
  181.  
  182.     public DLLNode<E> getLast() {
  183.  
  184.         return last;
  185.     }
  186.  
  187.     public void izvadiDupliIPrebroj(){
  188.  
  189.     }
  190. }
  191. public class SumOfPreviousElements {
  192.     public static void sum_and_append(DLL<Integer> list){
  193.         DLLNode<Integer> temp= list.getFirst();
  194.         int sum=0;
  195.         while(temp!=null){
  196.             int counter=temp.element;
  197.             sum=0;
  198.             while(counter>0){
  199.                 if(temp==null) break;
  200.                 sum+=temp.element;
  201.                 counter--;
  202.                 if(counter==0&&temp.succ==null){
  203.                     list.insertAfter(sum,temp);
  204.                     return;
  205.                 }
  206.                 temp=temp.succ;
  207.             }
  208.             if(temp!=null)
  209.             list.insertBefore(sum,temp);
  210.  
  211.         }
  212.     }
  213.     public static void main(String[] args) {
  214.         Scanner input= new Scanner(System.in);
  215.         int n= Integer.parseInt(input.nextLine());
  216.         String[] broevi= input.nextLine().split("\\s+");
  217.         DLL<Integer> lista= new DLL<>();
  218.         for(int i=0;i<n;i++){
  219.             lista.insertLast(Integer.parseInt(broevi[i]));
  220.         }
  221.         sum_and_append(lista);
  222.         System.out.println(lista);
  223.     }
  224. }
  225. /*
  226. 14
  227. 2 3 4 5 2 4 5 7 5 9 2 3 4 13
  228. 2<->3<->5<->4<->5<->2<->4<->15<->5<->7<->5<->9<->2<->28<->3<->4<->13<->20
  229.  
  230. 15
  231. 3 3 4 5 2 4 5 7 5 9 2 3 4 2 22
  232. 3<->3<->4<->10<->5<->2<->4<->5<->7<->23<->5<->9<->2<->3<->4<->23<->2<->22<->24
  233.  */
  234.  
  235.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement