Soluciones de las Tareas

T1-basura.java

import java.util.Scanner;

class basura{

  public static class Bolsa{
    private int Volumen;
    Bolsa(int V){
      Volumen = V;
    }
    public void setVol(int V){
      Volumen = V;
    }
    public int getVol(){
      return Volumen;
    }
    
  }

  public static class Basurero{
    private int Volumen;
    private Bolsa[] Capacidad;
    Basurero(int N,int V){
      Volumen = V;
      Capacidad = new Bolsa[N];
      Scanner input2 = new Scanner(System.in);
      for(int i=0;i<N;i++){
        int valor = input2.nextInt();
        Capacidad[i] = new Bolsa(valor);
      }
    }
    public void output(int N){
      int Usado = 0;
      int Exceso = 0;
      for(int i=0;i<N;i++){
        if (Capacidad[i].getVol()+Usado <= Volumen){
          Usado = Usado + Capacidad[i].getVol();
        }
        else{
          Exceso = Exceso + Capacidad[i].getVol();
        }
      }
      System.out.print(Usado);
      System.out.print(',');
      System.out.print(Exceso);
      System.out.print(',');
      System.out.print(Volumen-Usado);
    }
  }
  
  public static void main(String[] args){
    Scanner input = new Scanner(System.in);
    int N = input.nextInt();
    int V = input.nextInt();
    Basurero B = new Basurero(N,V);
    B.output(N);
  }
}

T1-binario.java

import java.util.Scanner;

class binario{

  public static void B1NAR10(int N,int i,String S){
    if (N == i){
      System.out.println(S);
    }
    else if (i > 0 && S.charAt(i-1) == '1'){
      B1NAR10(N, i+1, S+'0');
    }
    else{
      B1NAR10(N, i+1, S+'0');
      B1NAR10(N, i+1, S+'1');
    }
  }
  
  public static void main(String[] args){
    Scanner input = new Scanner(System.in);
    int N = input.nextInt();
    B1NAR10(N,0,"");
  }
}

T1-palindromo.java

import java.util.Scanner;

class palidromo {

  public static boolean isPali(int i){
    String num = String.valueOf(i);
    int inicio = 0;
    int termino = num.length()-1;
    while (inicio < termino){
      if (num.charAt(inicio) != num.charAt(termino)){
        return false;
      }
      else{
        inicio = inicio + 1;
        termino = termino - 1;
      }
    }
    return true;
  }

  public static void DivPali(int N){
    for(int i=1;i<=N;i++){
      if (N%i==0 && isPali(i)){
        if (i!=1){
          System.out.print(',');
        }
        System.out.print(i);
      }
    }
  }

  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int N = input.nextInt();
    DivPali(N);
  }
}

T3-differencia-simetrica.java

class Node {
   private int value;
   private Node next;

   public Node(int value, Node next) {
     this.value = value;
     this.next = next;
   }

   public Node(int value) {
     this.value = value;
     this.next = null;
   }

  public int getValue() { return (this.value); }
  public void setValue(int value) { this.value = value; }

  public Node getNext() { return (this.next); }
  public void setNext(Node next) { this.next = next; }
}


class List {
  private Node head;

  public List() {
    this.head = null;
  }

  public void insert(int value){
    Node n_node = new Node(value);
    if (this.head == null) {
      this.head = n_node;
      return;
    }
    if (this.head.getValue() > n_node.getValue()){
      n_node.setNext(this.head);
      this.head = n_node;
      return;
    }

    Node tmp;
    for(tmp = this.head; tmp.getNext() != null; tmp = tmp.getNext()){
      if(tmp.getNext().getValue() > n_node.getValue()) {
        n_node.setNext(tmp.getNext());
        tmp.setNext(n_node);
        return;
      }
    }
    tmp.setNext(n_node);
  }

  public void pop() {
    if (this.head != null) {
      this.head = this.head.getNext();
    }
  }

  public void print(){
    Node tmp;
    int i;
    for(tmp = this.head, i = 0; tmp != null; tmp = tmp.getNext(), i++) {
        if (i == 0) System.out.print(tmp.getValue());
        else System.out.print(" " + tmp.getValue());
    }
    System.out.print("\n");
  }

  public boolean empty(){
    if (this.head == null) return true;
    else return false;
  }

  public Node top(){
    Node tmp = this.head;
    return tmp;
  }
}



import java.util.Scanner;  // Import the Scanner class


public class Main {
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);  // Create a Scanner object
    int a, b, buff;
    List A = new List();
    List B = new List();
    List C = new List();

    a = scanner.nextInt();
    b = scanner.nextInt();

    for(int i=0; i < a; i++){
      buff = scanner.nextInt();
      A.insert(buff);
    }

    for(int i=0; i < b; i++){
      buff = scanner.nextInt();
      B.insert(buff);
    }

    while(!A.empty() && !B.empty()) {
      a = A.top().getValue();
      A.pop();

      if(a > B.top().getValue()){
        while(!B.empty() && a > B.top().getValue()) {
          b = B.top().getValue();
          B.pop();
          C.insert(b);
        }
      }

      if (!B.empty() && a == B.top().getValue()) B.pop();
      else C.insert(a);
    }

    while(!A.empty()) {
      a = A.top().getValue();
      A.pop();
      C.insert(a);
    }

    while(!B.empty()) {
      b = B.top().getValue();
      B.pop();
      C.insert(b);
    }

    C.print();
  }
}

T3-stackbooks.java

class Node {
   private int value;
   private Node next;

   public Node(int value, Node next) {
     this.value = value;
     this.next = next;
   }

   public Node(int value) {
     this.value = value;
     this.next = null;
   }

  public int getValue() { return (this.value); }
  public void setValue(int value) { this.value = value; }

  public Node getNext() { return (this.next); }
  public void setNext(Node next) { this.next = next; }
}

class Queue {
  private Node head;
  private Node tail;

  public Queue() {
    this.head = this.tail = null;
  }

  public void enqueue(int value){
    Node n_node = new Node(value);
    // no elements
    if(this.head == null && this.tail == null) {
      this.head = this.tail = n_node;
    }
    else {
      // n elements
      this.tail.setNext(n_node);
      this.tail = n_node;
    }
  }

  public void dequeue() {
    // no elements
    if(this.head == null && this.tail == null) return;
    // 1 element
    if(this.head == this.tail) {
      this.head = this.tail = null;
      return;
    }
    // n elements
    this.head = this.head.getNext();
  }

  public boolean empty(){
    if (this.head == null) return true;
    else return false;
  }

  public Node top(){
    Node tmp = this.head;
    return tmp;
  }

  public void print(){
    Node tmp;
    int i;
    for(tmp = this.head, i = 0; tmp != null; tmp = tmp.getNext(), i++) {
        if (i == 0) System.out.print(tmp.getValue());
        else System.out.print(" " + tmp.getValue());
    }
    System.out.print("\n");
  }
}

class Stack {
  private Node head;

  public Stack() {
    this.head = null;
  }

  public void push(int value) {
    Node n_node = new Node(value, this.head);
    this.head = n_node;
  }

  public void pop() {
    if (this.head != null) {
      this.head = this.head.getNext();
    }
  }

  public boolean empty(){
    if (this.head == null) return true;
    else return false;
  }

  public Node top(){
    return this.head;
  }

  public void print(){
    Node tmp;
    int i;
    for(tmp = this.head, i = 0; tmp != null; tmp = tmp.getNext(), i++) {
        if (i == 0) System.out.print(tmp.getValue());
        else System.out.print(" " + tmp.getValue());
    }
    System.out.print("\n");
  }
}



import java.util.Scanner;  // Import the Scanner class


public class Main {
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);  // Create a Scanner object

    int n, buff, cont, max;
    Node tmp;
    Stack myStack = new Stack();
    Stack auxS1 = new Stack();
    Stack auxS2 = new Stack();
    Queue auxQ = new Queue();

    n = scanner.nextInt();

    // Reading data
    for(int i=0; i<n; i++){
        buff = scanner.nextInt();
        myStack.push(buff);
    }
    // for each sub stack from substack = stack to only head
    for(int i=0; i<n; i++) {
      cont=i;
      max = Integer.MIN_VALUE;
      // flip stack in aux 1 for find the max value in sub stack
      while(!myStack.empty() && cont <= (n-1)) {
        tmp = myStack.top();
        myStack.pop();

        if(max < tmp.getValue()){
          max = tmp.getValue();
        }
        auxS1.push(tmp.getValue());
        cont++;
      }

      // Returns all the values that are before the max on the auxiliary stack to the original stack
      while(!auxS1.empty()){
        tmp = auxS1.top();
        if(tmp.getValue() == max) break;
        auxS1.pop();
        myStack.push(tmp.getValue());
      }
      // Flip remaining auxiliary stack values (including max) into a second auxiliary stack
      while(!auxS1.empty()){
        tmp = auxS1.top();
        auxS1.pop();
        auxS2.push(tmp.getValue());
      }

      // Returns the values of the second auxiliary stack to the original stack
      while(!auxS2.empty()){
        tmp = auxS2.top();
        auxS2.pop();
        myStack.push(tmp.getValue());
      }

      // enter all the data from the sub stack in an auxiliary queue, in order to flip the sub stack
      cont=i;
      while(!myStack.empty() && cont <= (n-1)) {
        tmp = myStack.top();
        myStack.pop();
        auxQ.enqueue(tmp.getValue());
        cont++;
      }
      // returns the values of the auxiliary queue to the original stack having in the bottom of the sub stack the element with the highest value
      while(!auxQ.empty()){
        tmp = auxQ.top();
        auxQ.dequeue();
        myStack.push(tmp.getValue());
      }
    }
    myStack.print();
  }
}

T4-prefix.java

import java.util.Scanner;  // Import the Scanner class


public class Main {

  static String PrefixFor2Strings(String s1, String s2) {
    String prefix = "";

    for(int i=0; i < s1.length() && i < s2.length(); i++){
      if(s1.charAt(i) == s2.charAt(i)) prefix += s1.charAt(i);
    }

    return prefix;
  }

  static String CommonPrefixDyC(String arr[], int ini, int fin) {
    if (ini == fin) {
      return arr[ini];
    }
    else if (ini < fin) {
      String left = CommonPrefixDyC(arr, ini, (ini+fin)/2);
      String right = CommonPrefixDyC(arr, ((ini+fin)/2)+1, fin);

      return PrefixFor2Strings(left, right);
    }
    else {
      return "";
    }
  }

  static String CommonPrefix(String arr[]) {
    return CommonPrefixDyC(arr, 0, arr.length-1);
  }

  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);  // Create a Scanner object

    int n_strings = scanner.nextInt();
    String[] arr = new String[n_strings];

    for(int i=0; i < n_strings; i++) {
      arr[i] = scanner.next();
    }

    String prefix = CommonPrefix(arr);

    System.out.println(prefix);
  }
}

T4-stacksort.java

import java.util.Scanner;  // Import the Scanner class


public class Main {

  static Stack StackSort(Stack myStack) {
    Stack tmpStack = new Stack();
    Node tmp;

    while(!myStack.empty()) {
      tmp = myStack.top();
      myStack.pop();

      while(!tmpStack.empty() && tmpStack.top().getValue() < tmp.getValue()) {
        myStack.push(tmpStack.top().getValue());
        tmpStack.pop();
      }

      tmpStack.push(tmp.getValue());
    }

    return tmpStack;
  }

  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);  // Create a Scanner object

    int n = scanner.nextInt();
    Stack myStack = new Stack();
    Node tmp;

    for(int i=0; i < n; i++) {
      myStack.push(scanner.nextInt());
    }

    Stack orderedStack = StackSort(myStack);

    int i = 0;
    String sep = "";
    while(!orderedStack.empty()) {
      tmp = orderedStack.top();
      orderedStack.pop();

      if (i++ > 0) {
        sep = " ";
      }
      System.out.print(sep + tmp.getValue());
    }
    System.out.print("\n");


  }
}

T5-runningmean.java

import java.util.Scanner;  // Import the Scanner class
import java.util.Comparator;

public class Main {
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);  // Create a Scanner object

    Heap<Long> maxHeap = new Heap<Long>((a ,b) -> {return (int)(a - b);});
    Heap<Long> minHeap = new Heap<Long>((a ,b) -> {return (int)(b - a);});

    int n = scanner.nextInt();
    long n_value;
    long median = 0;


    for(int i=0; i < n; i++) {
        n_value = scanner.nextLong();
        if (median > n_value) {
          maxHeap.insert(n_value);
        } else {
          minHeap.insert(n_value);
        }

        if(Math.abs(maxHeap.size() - minHeap.size()) > 1) {
          if(maxHeap.size() > minHeap.size()) {
            minHeap.insert(maxHeap.delMax());
          } else {
            maxHeap.insert(minHeap.delMax());
          }
        }

        if(minHeap.size() > maxHeap.size()) {
          median = minHeap.top();
          System.out.println(median);
        } else if (maxHeap.size() > minHeap.size()){
          median = maxHeap.top();
          System.out.println(median);
        } else {
          median = (maxHeap.top() + minHeap.top()) / 2;
          System.out.println(maxHeap.top() + "," + minHeap.top());
        }
    }
  }
}

T5-waitingtime.java

import java.util.Scanner;  // Import the Scanner class

public class Main {

  public static class Pair<K, V> {
    private K first;
    private V second;

    public Pair(K first, V second) {
      this.first = first;
      this.second = second;
    }

    public K first() {return first;}
    public V second() {return second;}
  }

  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);  // Create a Scanner object

    Heap<Pair<Long, Long>> minFirstHeap = new Heap<>((a ,b) -> {return (int)(b.first() - a.first());});
    Heap<Pair<Long, Long>> minSecondHeap = new Heap<>((a ,b) -> {return (int)(b.second() - a.second());});

    Pair<Long, Long> tmp;
    int n = scanner.nextInt();
    long a_time, w_time;
    long current_time, waiting_time;
    current_time = waiting_time = 0;

    for(int i=0; i < n; i++) {
      a_time = scanner.nextLong();
      w_time = scanner.nextLong();

      minFirstHeap.insert(new Pair(a_time, w_time));
    }



    while (!minFirstHeap.empty() || !minSecondHeap.empty()) {
      while(!minFirstHeap.empty() && minFirstHeap.top().first() <= current_time) {
        minSecondHeap.insert(minFirstHeap.delMax());
      }
      if (!minSecondHeap.empty()) {
        tmp = minSecondHeap.delMax();
        current_time += tmp.second();
        waiting_time += current_time - tmp.first();
      } else {
        // only first case
        tmp = minFirstHeap.delMax();
        minSecondHeap.insert(tmp);
        current_time += tmp.first();
      }
    }

    System.out.println(waiting_time/n);
  }
}

T6-minimalexpression.java

class Node<T>{
  private T value;
  Node<T> left;
  Node<T> right;


  public Node(T value){
    this.value = value;
    this.left = null;
    this.right = null;
  }

  public Node(T value, Node<T> left, Node<T> right){
    this.value = value;
    this.left = left;
    this.right = right;
  }

  public T getValue() {return this.value;}
  public Node<T> getLeft() {return this.left;}
  public Node<T> getRight() {return this.right;}

  public void setValue(T value) {this.value = value;}
  public void setLeft(Node<T> left) {this.left = left;}
  public void setRight(Node<T> right) {this.right = right;}
}

public class Symbol{
  private String symbol;
  private String type;

  public Symbol(String symbol, String type) {
    this.symbol = symbol;
    this.type = type;
  }

  public String getSymbol() {return this.symbol;}
  public String getType() {return this.type;}
}

import java.util.Vector;
import java.util.Queue;

public class ExpressionTree {
  private Node<Symbol> root;

  public ExpressionTree(Queue<String> expression) {
    this.root = this.getExpressionTree(expression);
    this.root = this.reduceExpression(this.root);

  }

  private Node<Symbol> getExpressionTree(Queue<String> expression){
    String tmp = expression.remove();

    if(tmp.equals("(")) {

      Node<Symbol> left = this.getExpressionTree(expression);
      Node<Symbol> root = new Node<Symbol>(new Symbol(expression.remove(), "operation"));
      Node<Symbol> right = this.getExpressionTree(expression);

      // deleting ")"
      expression.remove();

      root.setLeft(left);
      root.setRight(right);
      return root;
    } else if(isNumber(tmp)) {
      // is numeric
      Symbol n_symbol = new Symbol(tmp, "numeric");
      expression.remove(0);

      return new Node<Symbol>(n_symbol);
    } else {
      // is variable
      Symbol n_symbol = new Symbol(tmp, "variable");
      expression.remove(0);

      return new Node<Symbol>(n_symbol);
    }
  }

  private String solveOperation(String s1, String s2, String op) {
    if(op.equals("+")) {
      return Integer.toString(Integer.parseInt(s1) + Integer.parseInt(s2));
    } else if (op.equals("-")) {
      return Integer.toString(Integer.parseInt(s1) - Integer.parseInt(s2));
    } else if (op.equals("*")) {
      return Integer.toString(Integer.parseInt(s1) * Integer.parseInt(s2));
    } else if (op.equals("/")) {
      return Integer.toString(Integer.parseInt(s1) / Integer.parseInt(s2));
    } else {
      return null;
    }
  }

  private Node<Symbol> reduceExpression(Node<Symbol> root) {
    if(root == null) return null;
    if(root.getValue().getType() == "operation") {
      Node<Symbol> left = this.reduceExpression(root.getLeft());
      Node<Symbol> right = this.reduceExpression(root.getRight());

      if(left.getValue().getType() == "numeric" && right.getValue().getType() == "numeric") {
        return new Node<Symbol>(new Symbol(solveOperation(left.getValue().getSymbol(), right.getValue().getSymbol(), root.getValue().getSymbol()) , "numeric"));
      }
      else {
        root.setLeft(left);
        root.setRight(right);

        return root;
      }
    } else if(root.getValue().getType() == "numeric" || root.getValue().getType() == "variable") {
      return root;
    } else {
      return null;
    }
  }


  public Vector<String> inOrder() {
    Vector<String> inOrderVector = new Vector<String>();
    this.getInOrder(this.root, inOrderVector);
    return inOrderVector;
  }
  private void getInOrder(Node<Symbol> root, Vector<String> inOrderVector) {
    if(root == null) return;
    if(root.getLeft() == null && root.getRight() == null) {
      inOrderVector.add(root.getValue().getSymbol());
      return;
    }

    inOrderVector.add("(");
    this.getInOrder(root.getLeft(), inOrderVector);
    inOrderVector.add(root.getValue().getSymbol());
    this.getInOrder(root.getRight(), inOrderVector);
    inOrderVector.add(")");
  }

  public Vector<String> preOrder() {
    Vector<String> preOrderVector = new Vector<String>();
    this.getPreOrder(this.root, preOrderVector);
    return preOrderVector;
  }
  private void getPreOrder(Node<Symbol> root, Vector<String> preOrderVector) {
    if(root == null) return;
    if(root.getLeft() == null && root.getRight() == null) {
      preOrderVector.add(root.getValue().getSymbol());
      return;
    }

    preOrderVector.add("(");
    preOrderVector.add(root.getValue().getSymbol());
    this.getPreOrder(root.getLeft(), preOrderVector);
    this.getPreOrder(root.getRight(), preOrderVector);
    preOrderVector.add(")");
  }

  private boolean isNumber(String str) {return str.matches("[-+]?[0-9]*\\.?[0-9]+");}
  private boolean isOperation(String str) { return (str == "+" || str == "-" || str == "*" || str == "/"); }

}

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Vector;

public class Main {
  public static void main(String[] args){
    String expression;
    String[] expression_splited;

    Scanner scanner = new Scanner(System.in);  // Create a Scanner object
    expression = scanner.nextLine();
    expression_splited = expression.split("\\s+");

    Queue<String> expression_q =  new LinkedList<String>();

    for (int i = 0; i < expression_splited.length ;  i++) {
      expression_q.add(expression_splited[i]);
    }


    ExpressionTree eTree = new ExpressionTree(expression_q);
    Vector<String> vec = eTree.preOrder();

    for(int i=0;i<vec.size();i++){
      System.out.print(vec.get(i) + " ");
    } System.out.print("\n");
  }
}

T6-pathfinder.java

class Node<T>{
  private T value;
  Node<T> left;
  Node<T> right;


  public Node(T value){
    this.value = value;
    this.left = null;
    this.right = null;
  }

  public Node(T value, Node<T> left, Node<T> right){
    this.value = value;
    this.left = left;
    this.right = right;
  }

  public T getValue() {return this.value;}
  public Node<T> getLeft() {return this.left;}
  public Node<T> getRight() {return this.right;}

  public void setValue(T value) {this.value = value;}
  public void setLeft(Node<T> left) {this.left = left;}
  public void setRight(Node<T> right) {this.right = right;}
}

import java.util.Vector;

class Btree<T> {
    private Node<T> root;

    public Btree() {
      this.root = null;
    }

    public Btree(Node<T> root) {
      this.root = root;
    }

    public Node<T> getRoot() { return this.root;}
    public void setRoot(Node<T> root) {this.root = root;}


    public boolean search(T value) {
      return this.getSearch(value, this.root);
    }

    public Vector<T> inOrder() {
      Vector<T> inOrderVector = new Vector<T>();
      this.getInOrder(this.root, inOrderVector);
      return inOrderVector;
    }

    public Vector<T> preOrder() {
      Vector<T> preOrderVector = new Vector<T>();
      this.getPreOrder(this.root, preOrderVector);
      return preOrderVector;
    }

    public Vector<T> postOrder() {
      Vector<T> postOrderVector = new Vector<T>();
      this.getPostOrder(this.root, postOrderVector);
      return postOrderVector;
    }

    private boolean getSearch(T value, Node<T> root) {
      if(root == null) return false;
      if(root.getValue() == value) return true;
      return (this.getSearch(value, root.getLeft()) || this.getSearch(value, root.getRight()));
    }

    private void getInOrder(Node<T> root, Vector<T> inOrderVector) {
      if(root == null) return;

      this.getInOrder(root.getLeft(), inOrderVector);
      inOrderVector.add(root.getValue());
      this.getInOrder(root.getRight(), inOrderVector);
    }

    private void getPreOrder(Node<T> root, Vector<T> preOrderVector) {
      if(root == null) return;

      preOrderVector.add(root.getValue());
      this.getPreOrder(root.getLeft(), preOrderVector);
      this.getPreOrder(root.getRight(), preOrderVector);
    }

    private void getPostOrder(Node<T> root, Vector<T> postOrderVector) {
      if(root == null) return;

      this.getPostOrder(root.getLeft(), postOrderVector);
      this.getPostOrder(root.getRight(), postOrderVector);
      postOrderVector.add(root.getValue());
    }
}



import java.util.Scanner;
import java.util.Vector;

public class Main {
  public static <T> Node<T> create_tree(Vector<T> inOrder, Vector<T> postOrder, int startIn, int endIn, int startPost, int endPost) {
    if(startIn > endIn) return null;
    if(startPost > endPost) return null;
    if(endIn - startIn != endPost - startPost) return null;

    Node<T> root = new Node<T>(postOrder.get(endPost));
    int inIndex = inOrder.indexOf(postOrder.get(endPost));
    root.setLeft(create_tree(inOrder, postOrder, startIn, inIndex - 1, startPost, startPost+(inIndex - startIn)-1));
    root.setRight(create_tree(inOrder, postOrder, inIndex + 1, endIn, startPost+(inIndex - startIn), endPost-1));

    return root;
  }

  public static <T extends Comparable<T>> boolean findPath(Node<T> root, Vector<T> path, T value) {
    if(root == null) return false;


    if(root.getValue().compareTo(value) == 0) {
      path.add(value);
      return true;
    }

    path.add(root.getValue());
    if (findPath(root.getLeft(), path, value) == true || findPath(root.getRight(), path, value) == true ) {
      return true;
    } else {
      path.remove(path.size()-1);
      return false;
    }
  }

  public static void main(String[] args){
    int n, buff;
    Vector<Integer> inOrder = new Vector<Integer>();
    Vector<Integer> postOrder = new Vector<Integer>();
    Btree<Integer> tree;

    Scanner scanner = new Scanner(System.in);  // Create a Scanner object
    n = scanner.nextInt();

    for(int i=0;i<n;i++){
      buff = scanner.nextInt();
      inOrder.add(buff);
    }

    for(int i=0;i<n;i++){
      buff = scanner.nextInt();
      postOrder.add(buff);
    }

    tree = new Btree<Integer>(create_tree(inOrder, postOrder, 0, inOrder.size()-1, 0, postOrder.size()-1));

    Vector<Integer> preOrderVector = tree.preOrder();
    String sep = "";
    for (int i = 0; i < preOrderVector.size() ; i++ ) {
      System.out.print(sep + preOrderVector.get(i));
      if(i == 0) {
        sep = " ";
      }
    }System.out.print("\n");

    buff = scanner.nextInt();

    Vector<Integer> path = new Vector<Integer>();
    findPath(tree.getRoot(), path, buff);
    sep = "";
    for (int i = 0; i < path.size() ; i++ ) {
      System.out.print(sep + path.get(i));
      if(i == 0) {
        sep = "-";
      }
    }System.out.print("\n");
  }
}

T7-huffman.java

class Node{
  private int freq;
  private char key;
  private Node left;
  private Node right;

  public Node(char key, int freq) {
    this.freq = freq;
    this.key = key;
    this.left = null;
    this.right = null;
  }

  public Node(Node left, Node right) {
    this.left = left;
    this.right = right;
    this.freq = left.getFreq() + right.getFreq();
    this.key = Character.MIN_VALUE;
  }

  public int getFreq() { return this.freq; }
  public char getKey() { return this.key; }
  public Node getLeft() { return this.left; }
  public Node getRight() { return this.right; }
}

class Pair<K, V> {
  private K first;
  private V second;

  public Pair(K first, V second) {
    this.first = first;
    this.second = second;
  }

  public K first() {return first;}
  public V second() {return second;}

  public void setfirst(K first) {this.first = first;}
  public void setSecond(V second) {this.second = second;}
}

import java.util.Map;
import java.util.PriorityQueue;
import java.util.HashMap;
import java.util.Vector;

class HuffmanTree {
  private Node root;


  public HuffmanTree(Vector<Pair<Character, Integer>> freq_vec) {
    Node left, right, tmp = null;
    // Heap<Node> huffmanHeap = new Heap<Node>((a ,b) -> {return (int)(b.getFreq() - a.getFreq());});
    PriorityQueue<Node> huffmanHeap = new PriorityQueue<Node>(10, (a ,b) -> {return (int)(a.getFreq() - b.getFreq());});


    for(Pair<Character, Integer> p:freq_vec) {
      tmp = new Node(p.first(), p.second());
      huffmanHeap.add(tmp);
    }

    while(huffmanHeap.size() > 1) {
      left = huffmanHeap.poll();
      right = huffmanHeap.poll();

      tmp = new Node(left, right);
      huffmanHeap.add(tmp);
    }

    this.root = huffmanHeap.poll();
  }

  public Map<Character, String> getCodification() {
    Map<Character, String> cod_map = new HashMap<Character, String>();
    String cod = "";
    this.getCodification(this.root, cod, cod_map);
    return cod_map;
  }

  private void getCodification(Node root, String cod, Map<Character, String> cod_map) {
    if(root == null) return;
    if(root.getKey() != Character.MIN_VALUE) {
      cod_map.put(root.getKey(), cod);
    } else {
      this.getCodification(root.getLeft(), cod+"0", cod_map);
      this.getCodification(root.getRight(), cod+"1", cod_map);
    }
  }
}



import java.util.Scanner;  // Import the Scanner class
import java.util.Map;
import java.util.Vector;

public class Main {
  public static int searchKey(Vector<Pair<Character, Integer>> freq_vec, char key) {
    for(int i=0; i<freq_vec.size(); i++) {
      if(freq_vec.get(i).first() == key) return i;
    }
    return -1;
  }

  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);  // Create a Scanner object
    int i, j;
    String line;
    Vector<Pair<Character, Integer>> freq_vec = new Vector<Pair<Character, Integer>>();
    HuffmanTree tree;

    line = scanner.nextLine();
    for(j=0; j < line.length(); j++){
       i = searchKey(freq_vec, line.charAt(j));
       if(i == -1) {
         freq_vec.add(new Pair<Character, Integer>(line.charAt(j), 1));
       } else {
         freq_vec.get(i).setSecond(freq_vec.get(i).second() + 1);
       }
    }

    tree = new HuffmanTree(freq_vec);
    Map<Character, String> cod_map = tree.getCodification();
    
    String sep = "";
    for(j=0; j < line.length(); j++){
      System.out.print(sep + cod_map.get(line.charAt(j)));
      if(j == 0) sep = " ";
    }
    System.out.print("\n");

  }
}

T7-segmenttree.java

import java.math.BigInteger;

class Segment {
  private BigInteger value;
  private int start;
  private int end;

  public Segment(BigInteger value, int start, int end) {
    this.value = value;
    this.start = start;
    this.end = end;
  }

  public BigInteger getValue() {return this.value;}
  public int getStart() {return this.start;}
  public int getEnd() {return this.end;}

  public void setValue(BigInteger value) {this.value = value;}
  public void setStart(int start) {this.start = start;}
  public void setEnd(int end) {this.end = end;}
}

import java.util.Vector;
import java.math.BigInteger;

class SegmentTree{
  private Segment[] data;
  private int n;
  private int nLeafs;

  public SegmentTree(Vector<Long> data) {
    this.nLeafs = data.size();
    int log = (int)(Math.log(this.nLeafs)/Math.log(2) + 1e-10);
    this.n = (int)((1-Math.pow(2,log+1))/(1-2)) + 1;

    this.data = new Segment[this.n];

    this.initialize();

    for(int i=0; i<this.nLeafs;i++) {
      this.changeValue(i+1, BigInteger.valueOf(data.get(i)));
    }
  }

  private void initialize() {
    this.initialize(1);
  }

  private Segment initialize(int i) {
    if(2*i > this.n || (2*i)+1 > this.n) {
      // is leaf
      this.data[i] = new Segment(BigInteger.valueOf(0), i%this.nLeafs +1, i%this.nLeafs +1);
      return this.data[i];
    } else {
      // is intermediate node
      Segment left = initialize(2*i);
      Segment right = initialize((2*i) + 1);

      this.data[i] =  new Segment(BigInteger.valueOf(0), left.getStart(), right.getEnd());

      return this.data[i];
    }
  }

  public void changeValue(int i, BigInteger value) {
    i = i -1 + this.nLeafs;
    this.data[i].setValue(value);

    i/=2;
    while(i > 0) {
      this.data[i].setValue(this.data[2*i].getValue().multiply(this.data[2*i+1].getValue()));
      i/=2;
    }
  }

  public BigInteger getMultiplication(int start, int end) {
    return this.getMultiplication(1, start, end);
  }

  private BigInteger getMultiplication(int i, int start, int end) {
    if(this.data[i].getStart() == start && this.data[i].getEnd() == end) return this.data[i].getValue();

    int leftStart = this.data[i].getStart();
    int leftEnd = (this.data[i].getStart() + this.data[i].getEnd())/2;
    int rightStart = leftEnd+1;
    int rightEnd = this.data[i].getEnd();

    if(leftStart <= start && leftEnd >= end) return getMultiplication(i*2, start, end);
    else if(rightStart <= start && rightEnd >= end) return getMultiplication(i*2+1, start, end);
    else return getMultiplication(i*2, start, leftEnd).multiply(getMultiplication(i*2+1, rightStart, end));
  }


}

import java.util.Scanner;  // Import the Scanner class
import java.util.Map;
import java.util.Vector;
import java.math.BigInteger;

public class Main {
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);  // Create a Scanner object
    int n, ops, j, k;
    long buff;
    BigInteger bigBuff;
    String op;
    Vector<Long> vec;

    n = scanner.nextInt();
    ops = scanner.nextInt();
    vec = new Vector<Long>(n);

    for(int i=0; i < n; i++) {
      buff = scanner.nextLong();
      vec.add(buff);
    }
    SegmentTree tree = new SegmentTree(vec);

    for(int i=0; i<ops;i++) {
      op = scanner.next();
      if(op.compareTo("P") == 0) {
        j = scanner.nextInt();
        k = scanner.nextInt();
        bigBuff = tree.getMultiplication(j, k);
        // System.out.println(bigBuff);
        if(bigBuff.compareTo(BigInteger.valueOf(0)) > 0) System.out.println("+");
        else if(bigBuff.compareTo(BigInteger.valueOf(0)) < 0) System.out.println("-");
        else System.out.println(0);

      } else if (op.compareTo("C") == 0) {
        j = scanner.nextInt();
        bigBuff = BigInteger.valueOf(scanner.nextLong());
        tree.changeValue(j, bigBuff);
      }
    }
  }
}