[APS] ISPITNA JANUARI 2014

Поништување топчиња Задача 1 (0 / 0)
Да се напише алгоритам со кој ќе се имплементира играта “Поништување топчиња”. Во оваа игра на располагање имате топчиња во три различни бои (R-црвена, G-зелена и B-сина), обележани со знакот + или -. Поништување на топчиња може да настане само доколку тие се од иста боја и со спротивен знак. На почеток се генерира една случајна листа со топчиња. Ваша задача е од тој влез, како доаѓаат топчињата да направите поништување и да кажете колку, од каков тип (+ или -) и од која боја фалат за да се поништат сите топчиња од влезот.

Влез: Листа од случајни топчиња и тоа во облик: боја, знак

Име на класата (Java): Topcinja

Делумно решение: Задачата се смета за делумно решена доколку се поминати 5 тест примери.

Забелешка: При реализација на задачите МОРА да се користат дадените структури, а не да се користат помошни структури како низи или сл.

Пример влез: R+ G- G+ G+ R+ B- B+ R- G+ R- B- B+ B+ R+

Парови кои може да се формираат од овој список се: (R+,R-); (B+, B-); (B- B+); (R+, R-); (G-, G+); (R+, R-)

Остануваат без партнер: G+, G+, B+, R+

Излез:

4

R- G- G- B+

==========================================================================================================================================

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

class Scratch {


    static interface Queue<E> {

        // Elementi na redicata se objekti od proizvolen tip.

        // Metodi za pristap:

        public boolean isEmpty ();
        // Vrakja true ako i samo ako redicata e prazena.

        public int size ();
        // Ja vrakja dolzinata na redicata.

        public E peek ();
        // Go vrakja elementot na vrvot t.e. pocetokot od redicata.

        // Metodi za transformacija:

        public void clear ();
        // Ja prazni redicata.

        public void enqueue (E x);
        // Go dodava x na kraj od redicata.

        public E dequeue ();
        // Go otstranuva i vrakja pochetniot element na redicata.

    }

    static class LinkedQueue<E> implements Queue<E> {

        // Redicata e pretstavena na sledniot nacin:
        // length go sodrzi brojot na elementi.
        // Elementite se zachuvuvaat vo jazli dod SLL
        // front i rear se linkovi do prviot i posledniot jazel soodvetno.
        SLLNode<E> front, rear;
        int length;

        // Konstruktor ...

        public LinkedQueue () {
            clear();
        }

        public boolean isEmpty () {
            // Vrakja true ako i samo ako redicata e prazena.
            return (length == 0);
        }

        public int size () {
            // Ja vrakja dolzinata na redicata.
            return length;
        }

        public E peek () {
            // Go vrakja elementot na vrvot t.e. pocetokot od redicata.
            if (front == null)
                throw new NoSuchElementException();
            return front.element;
        }

        public void clear () {
            // Ja prazni redicata.
            front = rear = null;
            length = 0;
        }

        public void enqueue (E x) {
            // Go dodava x na kraj od redicata.
            SLLNode<E> latest = new SLLNode<E>(x, null);
            if (rear != null) {
                rear.succ = latest;
                rear = latest;
            } else
                front = rear = latest;
            length++;
        }

        public E dequeue () {
            // Go otstranuva i vrakja pochetniot element na redicata.
            if (front != null) {
                E frontmost = front.element;
                front = front.succ;
                if (front == null)  rear = null;
                length--;
                return frontmost;
            } else
                throw new NoSuchElementException();
        }

    }


    static class SLLNode<E> {
        protected E element;
        protected SLLNode<E> succ;

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

        @Override
        public String toString() {
            return element.toString();
        }
    }


    static 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.
    }


    static class LinkedStack<E> implements Stack<E> {

        //Stekot e pretstaven na sledniot nacin: top e link do prviot jazol
        // na ednostrano-povrzanata lista koja sodrzi gi elementite na stekot .
        private SLLNode<E> top;

        public LinkedStack () {
            // Konstrukcija na nov, prazen stek.
            top = null;
        }

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

        public E peek () {
            // Go vrakja elementot na vrvot od stekot.
            if (top == null)
                throw new NoSuchElementException();
            return top.element;
        }

        public void clear () {
            // Go prazni stekot.
            top = null;
        }

        public void push (E x) {
            // Go dodava x na vrvot na stekot.
            top = new SLLNode<E>(x, top);
        }

        public E pop () {
            // Go otstranuva i vrakja elementot shto e na vrvot na stekot.
            if (top == null)
                throw new NoSuchElementException();
            E topElem = top.element;
            top = top.succ;
            return topElem;
        }

    }


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

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line = in.readLine();
        String pom[] = line.split(" ");


        LinkedStack<String> r = new LinkedStack<>();
        LinkedStack<String> g = new LinkedStack<>();
        LinkedStack<String> b = new LinkedStack<>();

        for(int i = 0; i < pom.length;i++){
            if(pom[i].charAt(0) == 'R'){
                r.push(pom[i]);
            }
            else if(pom[i].charAt(0) == 'G'){
                g.push(pom[i]);
            }
            else if(pom[i].charAt(0) == 'B'){
                b.push(pom[i]);
            }
        }


        //
        LinkedQueue<String> nepareni = new LinkedQueue<>();

        // r stek
        LinkedQueue<String> pomosna = new LinkedQueue<>();
        while(!r.isEmpty()){
            String el = r.pop();
            if(pomosna.isEmpty()){
                pomosna.enqueue(el);
            }else{
                // ima elementi sporedi so prviot
                String el2 = pomosna.dequeue();
                if(el2.charAt(1) == el.charAt(1)){
                    pomosna.enqueue(el);
                    pomosna.enqueue(el2);
                }
            }
        }

        // r stek
        LinkedQueue<String> pomosna2 = new LinkedQueue<>();
        while(!g.isEmpty()){
            String el = g.pop();
            if(pomosna2.isEmpty()){
                pomosna2.enqueue(el);
            }else{
                // ima elementi sporedi so prviot
                String el2 = pomosna2.dequeue();
                if(el2.charAt(1) == el.charAt(1)){
                    pomosna2.enqueue(el);
                    pomosna2.enqueue(el2);
                }
            }
        }





        // r stek
        LinkedQueue<String> pomosna3 = new LinkedQueue<>();
        while(!b.isEmpty()){
            String el = b.pop();
            if(pomosna3.isEmpty()){
                pomosna3.enqueue(el);
            }else{
                // ima elementi sporedi so prviot
                String el2 = pomosna3.dequeue();
                if(el2.charAt(1) == el.charAt(1)){
                    pomosna3.enqueue(el);
                    pomosna3.enqueue(el2);
                }
            }
        }

        while(!pomosna.isEmpty()){
            nepareni.enqueue(pomosna.dequeue());
        }


        while(!pomosna2.isEmpty()){
            nepareni.enqueue(pomosna2.dequeue());
        }


        while(!pomosna3.isEmpty()){
            nepareni.enqueue(pomosna3.dequeue());
        }

        System.out.println(nepareni.length);
        while (!nepareni.isEmpty()){
            System.out.print(nepareni.dequeue()+ " ");
        }




    }
}