[APS][JAVA] code exercises (posto code e preoptovaren)

=======================1=======================
Палиндром Problem 1 (0 / 0)
Дадена е двојно поврзана листа со N јазли каде секој јазел содржи по еден карактер (буква).
Да се провери дали двојно поврзаната листа е палиндром:
 односно ако ја изминете од почеток до крај и од крај до почеток, дали ќе добиете ист збор.
Во првиот ред од влезот даден е бројот на јазли во листата N, а во вториот ред се дадени броевите.
На излез треба да се испечати 1 ако листата е палиндром, -1 ако не е.

Име на класата: PalindromeDLL

import java.util.Scanner;

class DLLNode<E> {
	protected E element;
	protected DLLNode<E> pred, succ;

	public DLLNode(E elem, DLLNode<E> pred, DLLNode<E> succ) {
		this.element = elem;
		this.pred = pred;
		this.succ = succ;
	}

	@Override
	public String toString() {
		return "<-" + element.toString() + "->";
	}
}

class DLL<E> {
	private DLLNode<E> first, last;

	public DLL() {
		// Construct an empty SLL
		this.first = null;
		this.last = null;
	}

	public void deleteList() {
		first = null;
		last = null;
	}

	public int length() {
		int ret;
		if (first != null) {
			DLLNode<E> tmp = first;
			ret = 1;
			while (tmp.succ != null) {
				tmp = tmp.succ;
				ret++;
			}
			return ret;
		} else
			return 0;

	}

	public void insertFirst(E o) {
		DLLNode<E> ins = new DLLNode<E>(o, null, first);
		if (first == null)
			last = ins;
		else
			first.pred = ins;
		first = ins;
	}

	public void insertLast(E o) {
		if (first == null)
			insertFirst(o);
		else {
			DLLNode<E> ins = new DLLNode<E>(o, last, null);
			last.succ = ins;
			last = ins;
		}
	}

	public void insertAfter(E o, DLLNode<E> after) {
		if (after == last) {
			insertLast(o);
			return;
		}
		DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
		after.succ.pred = ins;
		after.succ = ins;
	}

	public void insertBefore(E o, DLLNode<E> before) {
		if (before == first) {
			insertFirst(o);
			return;
		}
		DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
		before.pred.succ = ins;
		before.pred = ins;
	}

	public E deleteFirst() {
		if (first != null) {
			DLLNode<E> tmp = first;
			first = first.succ;
			if (first != null) first.pred = null;
			if (first == null)
				last = null;
			return tmp.element;
		} else
			return null;
	}

	public E deleteLast() {
		if (first != null) {
			if (first.succ == null)
				return deleteFirst();
			else {
				DLLNode<E> tmp = last;
				last = last.pred;
				last.succ = null;
				return tmp.element;
			}
		}
		// else throw Exception
		return null;
	}

	@Override
	public String toString() {
		String ret = new String();
		if (first != null) {
			DLLNode<E> tmp = first;
			ret += tmp + "<->";
			while (tmp.succ != null) {
				tmp = tmp.succ;
				ret += tmp + "<->";
			}
		} else
			ret = "Prazna lista!!!";
		return ret;
	}

	public DLLNode<E> getFirst() {
		return first;
	}

	public DLLNode<E> getLast() {

		return last;
	}

}

public class PalindromeDLL {

	public static int isItPalindrome(DLL<Integer> list){
		//Vashiot kod tuka...
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		DLL<Integer> list = new DLL<Integer>();
		for (int i = 0; i < n; i++) {
			list.insertLast(in.nextInt());
		}
		in.close();
		System.out.println(isItPalindrome(list));
	}

}

sample input:
5
1 2 3 1 2
sample output:
-1
========================1=====================


========================2=====================
Војска Problem 2 (0 / 1)
Пред командантот на војската наредени се сите војници и во двојно поврзана листа дадени се нивните ID-a.
На командантот не му се допаѓа како се наредени војниците и решава да одбере два под-интервали од војници и да им ги замени местата,
односно војниците што се наоѓаат во едниот под-интервал ќе ги смести во другиот, и обратно.

Влез: Во првиот ред даден е бројот на војници. Во вториот ред дадени се ID-то на секој од војниците.
 Во третиот ред дадени се два броеви, ID на првиот војник и ID на последниот војник од првиот интервал.
 Во четвртиот ред дадени се два броеви, ID на првиот војник и ID на последниот војник од вториот интервал.

Излез: Да се испечати новиот редослед на војниците (т.е. на нивните ID-a)

Забелешка 1: Интервалите никогаш нема да се преклопуваат и ќе содржат барем еден војник.
Целата низа ќе содржи најмалку два војника. Забелешка 2: Обратете посебно внимание кога интервалите
се еден до друг и кога некој од интервалите почнува од првиот војник или завршува со последниот војник.

Име на класата: DLLVojska


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class DLLNode<E> {
	protected E element;
	protected DLLNode<E> pred, succ;

	public DLLNode(E elem, DLLNode<E> pred, DLLNode<E> succ) {
		this.element = elem;
		this.pred = pred;
		this.succ = succ;
	}

	@Override
	public String toString() {
		return "<-"+element.toString()+"->";
	}
}


class DLL<E> {
	private DLLNode<E> first, last;

	public DLL() {
		// Construct an empty SLL
		this.first = null;
		this.last = null;
	}

	public void deleteList() {
		first = null;
		last = null;
	}

	public int length() {
		int ret;
		if (first != null) {
			DLLNode<E> tmp = first;
			ret = 1;
			while (tmp.succ != null) {
				tmp = tmp.succ;
				ret++;
			}
			return ret;
		} else
			return 0;

	}

	public void insertFirst(E o) {
		DLLNode<E> ins = new DLLNode<E>(o, null, first);
		if (first == null)
			last = ins;
		else
			first.pred = ins;
		first = ins;
	}

	public void insertLast(E o) {
		if (first == null)
			insertFirst(o);
		else {
			DLLNode<E> ins = new DLLNode<E>(o, last, null);
			last.succ = ins;
			last = ins;
		}
	}

	public void insertAfter(E o, DLLNode<E> after) {
		if(after==last){
			insertLast(o);
			return;
		}
		DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
		after.succ.pred = ins;
		after.succ = ins;
	}

	public void insertBefore(E o, DLLNode<E> before) {
		if(before == first){
			insertFirst(o);
			return;
		}
		DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
		before.pred.succ = ins;
		before.pred = ins;
	}

	public E deleteFirst() {
		if (first != null) {
			DLLNode<E> tmp = first;
			first = first.succ;
			if (first != null) first.pred = null;
			if (first == null)
				last = null;
			return tmp.element;
		} else
			return null;
	}

	public E deleteLast() {
		if (first != null) {
			if (first.succ == null)
				return deleteFirst();
			else {
				DLLNode<E> tmp = last;
				last = last.pred;
				last.succ = null;
				return tmp.element;
			}
		}
		// else throw Exception
		return null;
	}


	@Override
	public String toString() {
		String ret = new String();
		if (first != null) {
			DLLNode<E> tmp = first;
			ret += tmp + "<->";
			while (tmp.succ != null) {
				tmp = tmp.succ;
				ret += tmp + "<->";
			}
		} else
			ret = "Prazna lista!!!";
		return ret;
	}

	public DLLNode<E> getFirst() {
		return first;
	}

	public DLLNode<E> getLast() {

		return last;
	}

}

public class DLLVojska {


	public static void main(String[] args) throws IOException {
		DLL<Integer> lista = new DLL<Integer>();
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		String s = stdin.readLine();
		int N = Integer.parseInt(s);
		s = stdin.readLine();
		String[] ids = s.split(" ");
		for (int i = 0; i < N; i++) {
			lista.insertLast(Integer.parseInt(ids[i]));
		}

		s = stdin.readLine();
		String interval[] = s.split(" ");
		int a = Integer.parseInt(interval[0]);
		int b = Integer.parseInt(interval[1]);

		s = stdin.readLine();
		interval = s.split(" ");
		int c = Integer.parseInt(interval[0]);
		int d = Integer.parseInt(interval[1]);


		DLL<Integer> result = vojska(lista, a, b, c, d);


		DLLNode<Integer> node = result.getFirst();
		System.out.print(node.element);
		node = node.succ;
		while(node != null){
			System.out.print(" "+node.element);
			node = node.succ;
		}

	}

	private static DLL<Integer> vojska(DLL<Integer> lista, int a, int b, int c, int d) {

        // Vasiot kod tuka

		return lista;
	}
}

Sample input
10
1 2 3 4 5 6 7 8 9 10
1 5
6 10
Sample output
6 7 8 9 10 1 2 3 4 5
=================================2===============================


=================================3===============================
Листа од листи Problem 3 (0 / 0)
Дадена е двојно поврзана листа од двојно поврзани листи.
Да се најде сума на секоја од подлистите, а потоа производ на овие суми

Влез: Број N кој кажува колку листи има Број М кој кажува колку елементи има во секоја листа
Во следните М линии се податоците 1<=A<=1000за секоја од листите

Излез: Еден број што е производот на сумите од низите. Со седум децимали.

Пример влез: 3 4 1 2 3 4 2 3 4 5 6 7 8 9

Излез: 1400


import java.util.Scanner;

class DLLNode<E> {
	protected E element;
	protected DLLNode<E> pred, succ;

	public DLLNode(E elem, DLLNode<E> pred, DLLNode<E> succ) {
		this.element = elem;
		this.pred = pred;
		this.succ = succ;
	}

	@Override
	public String toString() {
		return "<-" + element.toString() + "->";
	}
}

class DLL<E> {
	private DLLNode<E> first, last;

	public DLL() {
		// Construct an empty SLL
		this.first = null;
		this.last = null;
	}

	public void deleteList() {
		first = null;
		last = null;
	}

	public int length() {
		int ret;
		if (first != null) {
			DLLNode<E> tmp = first;
			ret = 1;
			while (tmp.succ != null) {
				tmp = tmp.succ;
				ret++;
			}
			return ret;
		} else
			return 0;

	}

	public void insertFirst(E o) {
		DLLNode<E> ins = new DLLNode<E>(o, null, first);
		if (first == null)
			last = ins;
		else
			first.pred = ins;
		first = ins;
	}

	public void insertLast(E o) {
		if (first == null)
			insertFirst(o);
		else {
			DLLNode<E> ins = new DLLNode<E>(o, last, null);
			last.succ = ins;
			last = ins;
		}
	}

	public void insertAfter(E o, DLLNode<E> after) {
		if (after == last) {
			insertLast(o);
			return;
		}
		DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
		after.succ.pred = ins;
		after.succ = ins;
	}

	public void insertBefore(E o, DLLNode<E> before) {
		if (before == first) {
			insertFirst(o);
			return;
		}
		DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
		before.pred.succ = ins;
		before.pred = ins;
	}

	public E deleteFirst() {
		if (first != null) {
			DLLNode<E> tmp = first;
			first = first.succ;
			if (first != null) first.pred = null;
			if (first == null)
				last = null;
			return tmp.element;
		} else
			return null;
	}

	public E deleteLast() {
		if (first != null) {
			if (first.succ == null)
				return deleteFirst();
			else {
				DLLNode<E> tmp = last;
				last = last.pred;
				last.succ = null;
				return tmp.element;
			}
		}
		// else throw Exception
		return null;
	}

	@Override
	public String toString() {
		String ret = new String();
		if (first != null) {
			DLLNode<E> tmp = first;
			ret += tmp + "<->";
			while (tmp.succ != null) {
				tmp = tmp.succ;
				ret += tmp + "<->";
			}
		} else
			ret = "Prazna lista!!!";
		return ret;
	}

	public DLLNode<E> getFirst() {
		return first;
	}

	public DLLNode<E> getLast() {

		return last;
	}

}

public class ListaOdListi {

    public static long findMagicNumber(DLL<DLL<Integer>> list) {
		//Vashiot kod tuka...
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		DLL<DLL<Integer>> list = new DLL<DLL<Integer>>();
		for (int i = 0; i < n; i++) {
			DLL<Integer> tmp = new DLL<Integer>();
			for (int j = 0; j < m; j++) {
				tmp.insertLast(in.nextInt());
			}
			list.insertLast(tmp);
		}
		in.close();
		System.out.println(findMagicNumber(list));
	}

}

Sample input
4
4
6 13 16 7
7 23 9 11
8 0 8 19
6 6 9 11

Sample output
2352000

==============================3===============================

==============================4===============================
Опсег Problem 4 (0 / 0)
Дадена е равенката: x2+s(x)+200·x=N каде што x, N се природни броеви,
а s(x) е функција која што го дава збирот на цифри на бројот x.
Даден е и бројот N и два природни броеви A и B, каде што A≤B и A, B≤1,000,000,000.
Потребно е да проверите дали постои природен број x во опсегот [A, B] така што е задоволена равенката,
и ако постои тогаш треба да се врати како резултат.
Ако таков природен број x во опсегот [A, B] што ја задоволува равенката не постои, тогаш се враќа -1.

Име на класата: Range

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Range {

    static int proveri(int N, int A, int B) {
        // Vasiot kod tuka
    }

    public static void main(String[] args) throws Exception {
        int i,j,k;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Long.parseLong(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Long.parseLong(st.nextToken());
        int B = Long.parseLong(st.nextToken());

        int res = proveri(N, A, B);
        System.out.println(res);

        br.close();

    }

}

Sample input
1456
10 80
Sample output
-1
=================================4============================

=================================5============================
Автобус Problem 5 (0 / 0)
На автобуската станица во ФинТаун имало N возрасни и M деца кои што сакале да патуваат заедно за соседниот град МинТаун.
Цената на еден билет е 100 денари. Ако некој возрасен сака да патува со k деца,
треба да плати еден билет за него и k-1 билети за децата (за едно дете не мора да плаќа билет).
Исто така, возрасен може да се вози и сам, во тој случај ќе си плати еден билет за него.
Дополнително знаеме дека децата не можат да се возат без да се придружени од некој возрасен.
Во првиот ред од влезот е даден бројот N. Во вториот ред е даден бројот M.
Потребно е да пресметате колкав е минималниот и максималниот број на денари што може да ги платат патниците за билети и да ги испечатите во две линии.
Во автобусот ќе има најмалку еден возрасен.

Име на класата: Bus

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Bus {

    public static void main(String[] args) throws Exception {
        int i,j,k;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        br.close();

        // Vasiot kod tuka



    }

}

Sample input
4
10

Sample output
1000
1300
=========================5======================

=========================6======================
Најдолга опаѓачка секвенца - Java Problem 6 (0 / 0)
Најди ја најдолгата опаѓачка секвенца во една низа. Броевите во секвенцата не мора да се наоѓаат на последователни индекси во низата.

Име на класата: LDS

import java.util.Scanner;


public class LDS {


	private static int najdolgaOpagackaSekvenca(int[] a) {

        // Vasiot kod tuka

	}

	public static void main(String[] args) {
		Scanner stdin = new Scanner(System.in);

		int n = stdin.nextInt();
		int a[] = new int[n];
		for (int i = 0; i < a.length; i++) {
			a[i] = stdin.nextInt();
		}
		System.out.println(najdolgaOpagackaSekvenca(a));
	}


}


Sample input
8
1 2 3 4 5 6 7 8

Sample output
1
==========================6==============================

==========================7==============================
Букви Problem 7 (0 / 0)
Дадена е низа од големи букви, во која буквата S се појавува парен број пати.
 После секоја буква S буквата Т се појавува еднаш или повеќе пати.
Користејќи стек да се одреди дали после секоја буква S (до следната буква S), буквата Т се појавува ист број на пати.
На првиот ред од влезот се чита низа од карактери (стринг),
на излез се печати 1 доколку буквата Т се појавува ист број на пати после секоја S,
и нула доколку овој услов не е исполнет.

Име на класата: StackBukvi

import java.io.IOException;
import java.util.Scanner;

interface Stack<E> {

    // Elementi na stekot se objekti od proizvolen tip.

    // Metodi za pristap:

    public boolean isEmpty ();
    	// Vrakja true ako i samo ako stekot e prazen.

    public E peek ();
    	// Go vrakja elementot na vrvot od stekot.

    // Metodi za transformacija:

    public void clear ();
    	// Go prazni stekot.

    public void push (E x);
    	// Go dodava x na vrvot na stekot.

    public E pop ();
    	// Go otstranuva i vrakja elementot shto e na vrvot na stekot.
}

class ArrayStack<E> implements Stack<E> {
    private E[] elems;
    private int depth;

    @SuppressWarnings("unchecked")
    public ArrayStack (int maxDepth) {
        // Konstrukcija na nov, prazen stek.
        elems = (E[]) new Object[maxDepth];
        depth = 0;
    }


    public boolean isEmpty () {
        // Vrakja true ako i samo ako stekot e prazen.
        return (depth == 0);
    }


    public E peek () {
        // Go vrakja elementot na vrvot od stekot.
        if (depth == 0)
            throw new NoSuchElementException();
        return elems[depth-1];
    }


    public void clear () {
        // Go prazni stekot.
        for (int i = 0; i < depth; i++)  elems[i] = null;
        depth = 0;
    }


    public void push (E x) {
        // Go dodava x na vrvot na stekot.
        elems[depth++] = x;
    }


    public E pop () {
        // Go otstranuva i vrakja elementot shto e na vrvot na stekot.
        if (depth == 0)
            throw new NoSuchElementException();
        E topmost = elems[--depth];
        elems[depth] = null;
        return topmost;
    }
}

public class StackBukvi {
    static int proveri_t_posle_s(char [] St)
	{
	    // Vasiot kod tuka
	}

	public static void main(String[] args) throws IOException {
		char [] niza=new char[100];

		Scanner f=new Scanner(System.in);
		String st=f.next();
		niza=st.toCharArray();

	    int rez= proveri_t_posle_s(niza);
		System.out.println(rez);
	}


}

Sample input
ASGTBST

Sample output
1
=============================7=========================

=============================8=========================
Математички израз Problem 8 (0 / 0)
Да се напише алгоритам кој ќе пресметува (евалуира) математички израз составен од броеви
и операциите за собирање (+) и множење (*).

Забелешка: Операцијата множење има предност пред операцијата собирање.

Име на класата: ExpressionEvaluator

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class ExpressionEvaluator {

	public static int evaluateExpression(String expression){
		// Vasiot kod tuka

	}
	public static void main(String[] args) throws IOException {
		BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
		System.out.println(evaluateExpression(input.readLine()));
	}

}

Sample input
2+2*2*2*2*2*2+2*2

Sample output
70

===========================8=========================

===========================9=========================
Трик со карти Problem 9 (0 / 0)
Перо прави трик со карти. Тој има шпил од 51-на карта
(некој некогаш не му вратил една) од којшто ви дозволува да влечете карта.
Тој, за трикот да биде веродостоен, не ја знае картата, но знае на која позиција се наоѓа.
Мааната на Перо е тоа што тој не знае регуларно да измеша карти, туку ги зема првите седум карти,
им им го превртува редоследот (пр. од 1 2 3 4 5 6 7 ги реди во 7 6 5 4 3 2 1),
потоа зема една карта од превртените и една од врвот од шпилот и го става на крајот од шпилот,
така се додека не ги потроши сите седум карти. Со тоа остварува едно мешање на шпил.
Ваша задача е, да изработите симулцаија на ваквото мешање, такашто за дадена N-та карта т.ш. 1<=N<=51,
вие ќе му изброите колку вакви мешања треба тој да направи за на врв на шпилот да дојде извлечената карта.

Име на класата: card_trick

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


public class card_trick {
	public static int count(int N){
		// Vasiot kod tuka

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in) );
		System.out.println(count(Integer.parseInt(br.readLine())));
	}

}

Sample input
15
Sample output
1
======================9======================

=====================10======================
Компанија Problem 10 (0 / 0)
Податоците за плати на вработените во една компанија привремено се чуваат во еднострано поврзана листа.
 Во секој јазол од листата се чува единствен ID на вработениот и неговата плата.
Потребно е да се отстранат сите вработени со помали плати од даден износ,
 а остатокот да се прикажат во опаѓачки редослед во однос на ID-то.
Во првиот ред од влезот е даден бројот на вработени,
 потоа наизменично се дадени ID и плата за секој од вработените
и во последниот ред е износот во однос на кој ќе се отстрануваат вработените.
На излез се печати листа (ID, плата) во опаѓачки редослед според ID на секој од вработените.

Доколку нема вработени со плата поголема од дадената да се испечати: nema

Име на класата: SLLKompanija

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;



class SLLNode {
	protected int id;
	protected int plata;
	protected SLLNode succ;

	public SLLNode(int id,int plata, SLLNode succ) {
		this.id = id;
		this.plata=plata;
		this.succ = succ;
	}


}

class SLL {
	private SLLNode first;

	public SLL() {
		// Construct an empty SLL
		this.first = null;
	}

	public void deleteList() {
		first = null;
	}

	public int length() {
		int ret;
		if (first != null) {
			SLLNode tmp = first;
			ret = 1;
			while (tmp.succ != null) {
				tmp = tmp.succ;
				ret++;
			}
			return ret;
		} else
			return 0;

	}


	public void insertFirst(int id, int plata) {
		SLLNode ins = new SLLNode(id,plata, first);
		first = ins;
	}

	public void insertLast(int id,int plata) {
		if (first != null) {
			SLLNode tmp = first;
			while (tmp.succ != null)
				tmp = tmp.succ;
			SLLNode ins = new SLLNode(id, plata, null);
			tmp.succ = ins;
		} else {
			insertFirst(id,plata);
		}
	}

	public SLLNode getFirst() {
		return first;
	}


	public SLL brisi_pomali_od(int iznos) {
		// Vasiot kod tuka
	}

	public SLL sortiraj_opagacki() {
    	// Vasiot kod tuka

	}
    public void pecati (SLL lista)
    {
    	SLLNode p=lista.first;
    	while(p!=null)
    	{
    		System.out.println(p.id+","+p.plata);
    		p=p.succ;
    	}
    }

}
public class SLLKompanija {
	public static void main(String[] args) throws IOException {

		SLL lista1 = new SLL();
		BufferedReader stdin = new BufferedReader(new InputStreamReader(
				System.in));
		String s = stdin.readLine();
		int N = Integer.parseInt(s);

		for (int i = 0; i < N; i++) {
			s=stdin.readLine();
			String s1=stdin.readLine();
			lista1.insertLast(Integer.parseInt(s),Integer.parseInt(s1));
		}
		s = stdin.readLine();

		lista1=lista1.brisi_pomali_od(Integer.parseInt(s));
		if(lista1!=null)
        {
		    lista1=lista1.sortiraj_opagacki();
		    lista1.pecati(lista1);
        }

	}
}

Sample input
3
1111
19000
2222
22000
1155
60000
30000
Sample output
1155 60000
==========================10===========================