Zabavno dejstvo iz sveta matematike
1/998001 nam da urejeno zaporedje od 000 do 999. 1/998001 = 0.000001002003004...

Zabavno dejstvo iz sveta računalništva
Leta 1936 so Rusi naredili računalnik na vodo. (Vir: http://gizmodo.com/5879106/the-russian-computer-that-ran-on-water)

Drevesa

Moderatorji: hinkopihpih, Matic Conradi

lukazlatecan
Site Admin
Prispevkov: 23
Pridružen: Po Apr 24, 2017 5:29 pm
Kraj: Celje

Drevesa

OdgovorNapisal/-a lukazlatecan » Če Maj 18, 2017 12:18 pm

Pri svojem raziskovalnem delu se Janez ukvarja z dvojiškimi drevesi. Da bi sodelavcu dokazal svojo superiornost, je skonstruiral dvojiško drevo, ki je protiprimer za sodelavčevo domnevo. Žal pa je protiprimer zapisal na list, ki se je izgubil med stotinami podobnih listov na njegovi pisalni mizi (kot pri večini raziskovalcev, urejenost ni ravno Janezova močna točka). Da bi bilo vse skupaj še hujše, si Janez ni zapisal vseh podatkov o drevesu, ampak je za vsako vozlišče zgolj zabeležil, katero je njegovo nadrejeno vozlišče. Spomni pa se, da je bilo skonstruirano drevo levo poravnano.

Ker je vseh dreves na listih na njegovi pisalni mizi občutno preveč, da bi v nekaj dnevih uspel poiskati pravega, te je prosil za pomoč. Zelo bi mu pomagal že s tem, če bi iz množice podatkov o drevesih izbral le takšne, ki bi lahko predstavljali levo poravnano dvojiško drevo.

Poduk: Levo poravnano dvojiško drevo je polno drevo, ki mu morda manjkajo nekateri listi na desni strani v spodnjem nivoju (glej sliko).

Slika

Vhodni podatki
Prva vrstica vhodne datoteke vsebuje eno samo število n, tj. število testnih primerov. V prvi vrstici vsakega primera je število vozlišč dvojiškega drevesa m, nato pa sledi za vsako vozlišče po ena vrstica, ki vsebuje dve števili: [math] in [math]. Število [math] predstavlja enolično oznako vozlišča, število [math] pa oznako njegovega starša. Če je vozlišče [math] koren drevesa, je [math] enak −1. Podatki zagotovo predstavljajo neko dvojiško drevo.

Omejitve vhodnih podatkov
  • n ≤ 100
  • m ≤ 100000
  • 0 ≤ [math] ≤ 100000
  • −1 ≤ b ≤ 100000

Izhodni podatki
Za vsak testni primer izpiši po eno številko (vsako v svoji vrstici):

1, če podatki lahko predstavljajo levo poravnano dvojiško drevo in 0 sicer.

Primer vhoda

Koda: Izberi vse

3
3
5 3
3 -1
7 3
3
1 -1
3 1
7 3
9
1 -1
2 1
3 1
4 2
5 2
6 3
7 3
8 4
9 7

Pripadajoč izhod

Koda: Izberi vse

1
0
0
Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate. - Leonhard Euler

hinkopihpih
Prispevkov: 11
Pridružen: Ne Apr 30, 2017 2:11 pm

Re: Drevesa

OdgovorNapisal/-a hinkopihpih » Ne Jun 18, 2017 8:31 pm

Koda: Izberi vse

import java.util.*;

class Node
{
   private int key;
   private int index;
   private Node left;
   private Node right;

   public Node(int key, int index, Node left, Node right)
   {
      this.key = key;
      this.index = index;
      this.left = left;
      this.right = right;
   }
   public void setKey(int key)
   {
      this.key = key;
   }
   public int getKey()
   {
      return this.key;
   }
   public void setIndex(int index)
   {
      this.index = index;
   }
   public int getIndex()
   {
      return this.index;
   }
   public void setLeft(Node left)
   {
      this.left = left;
   }
   public Node getLeft()
   {
      return this.left;
   }
   public void setRight(Node right)
   {
      this.right = right;
   }
   public Node getRight()
   {
      return this.right;
   }
}

public class Drevesa
{
   public static void main(String[]args)
   {
      Scanner skan = new Scanner(System.in);
      int n = skan.nextInt();

      for(int i = 0; i < n; i++)
      {
         Node root = new Node(0,1,null,null);
         int m = skan.nextInt();
         List<int[]> connections = new ArrayList<int[]>();

         for(int j = 0; j < m; j++)
         {
            int[] connection = new int[2];
            connection[0] = skan.nextInt();
            connection[1] = skan.nextInt();

            if(connection[1] == -1)
            {
               root.setKey(connection[0]);
               continue;
            }   

            connections.add(connection);
         }   

         create(root,connections);

         if(check(root,1,m))
         {
            System.out.println(1);
         }   
         else
         {
            System.out.println(0);
         }   
      }   
   }
   public static void create(Node root, List<int[]> connections)
   {
      if(connections.size() == 0 || root == null)
      {
         return;
      }   

      for(int i = 0; i < connections.size(); i++)
      {
         if(connections.get(i)[1] == root.getKey())
         {
            if(root.getLeft() == null)
            {
               root.setLeft(new Node(connections.get(i)[0], 2 * root.getIndex(), null, null));
               connections.remove(i);
               i--;
            }
            else
            {
               root.setRight(new Node(connections.get(i)[0], 2 * root.getIndex() + 1, null, null));   
               connections.remove(i);
               i--;
               break;
            }   
         }   
      }

      create(root.getLeft(),connections);
      create(root.getRight(),connections);   
   }
   public static boolean check(Node root, int index, int n)
   {
      if(root == null)
      {
         return true;
      }

      root.setIndex(index);

      if(root.getIndex() > n)
      {
         return false;
      }   

      boolean check1 = check(root.getLeft(),2 * root.getIndex(),n);
      boolean check2 = check(root.getRight(),2 * root.getIndex() + 1,n);
      swap(root);
      boolean check3 = check(root.getLeft(),2 * root.getIndex(),n);
      boolean check4 = check(root.getRight(),2 * root.getIndex() + 1,n);
      swap(root);

      return check1 && check2 || check3 && check4;
   }   
   public static void swap(Node root)
   {
      Node temp = root.getLeft();
      root.setLeft(root.getRight());
      root.setRight(temp);
   }
}


Vrni se na “Poskusno kolo”

Kdo je na strani

Po forumu brska: 0 registriranih uporabnikov in 1 gost