logotransparent.png

Legion of Learners

www.lol-101.com

  • Home

  • Classrooms

  • Courses

  • About Us

    • Executive Team
    • Board Members
  • Resources

  • More

    Use tab to navigate through the menu items.
    To see this working, head to your live site.
    • Categories
    • All Posts
    • My Posts
    sfolax6776
    Oct 29, 2019
      ·  Edited: Oct 29, 2019

    Senior2019-Set 2 - Recursive Functions and CNS 2

    in ACSL Contest Prep

    Short Questions


    Programming: 2002-2003#8

    5 comments
    0
    awesomeface259
    Nov 02, 2019

    1. C

    2. E

    11. C



    code:


    import java.util.*;

    import java.io.*;

    public class matchingTrees {

    static String match, tree;

    static char[] matchTree;

    static char[] bigTree;

    public static void addMatch(int index, char c) {

    if (matchTree[index] == ' ') {

    matchTree[index] = c;

    } else {

    if (matchTree[index] < c) {

    addMatch(index * 2 + 1, c);

    } else {

    addMatch(index * 2, c);

    }

    }

    }

    public static void addBig(int index, char c) {

    if (bigTree[index] == ' ') {

    bigTree[index] = c;

    } else {

    if (bigTree[index] < c) {

    addBig(index * 2 + 1, c);

    } else {

    addBig(index * 2, c);

    }

    }

    }

    public static boolean fits(int indexMatch, int indexBig) {

    if (matchTree[indexMatch] == ' ') return true;

    if (bigTree[indexBig] == ' ') return false;

    return fits(indexMatch * 2, indexBig * 2) && fits(indexMatch * 2 + 1, indexBig * 2 + 1);

    }

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

    BufferedReader in = new BufferedReader(new FileReader("src/matchingTrees"));

    for (int q = 0; q < 10; q++) {

    StringTokenizer st = new StringTokenizer(in.readLine());

    String match = st.nextToken(", "), tree = st.nextToken();

    matchTree = new char[Math.min((int) (Math.pow(2, match.length() + 1)), 8000000) + 1];

    bigTree = new char[Math.min((int) (Math.pow(2, tree.length() + 1)), 8000000) + 1];

    Arrays.fill(matchTree, ' ');

    Arrays.fill(bigTree, ' ');

    for (int i = 0; i < match.length(); i++) {

    addMatch(1, match.charAt(i));

    }

    for (int i = 0; i < tree.length(); i++) {

    addBig(1, tree.charAt(i));

    }

    ArrayList<Character> a = new ArrayList<Character>();

    for (int i = 1; i < bigTree.length; i++) {

    if (bigTree[i] == ' ') continue;

    if (fits(1, i)) {

    a.add(bigTree[i]);

    }

    }

    if (a.size() == 0) {

    System.out.println("NONE");

    } else {

    for (int i = 0; i < a.size() - 1; i++) {

    System.out.print(a.get(i) + ", ");

    }

    System.out.println(a.get(a.size() - 1));

    }

    }

    in.close();

    }

    }

    0
    Steven
    Nov 06, 2019

    Screen Shot 2019-11-05 at 8.50.05 PM
    .png
    Download PNG • 2.75MB

    0
    kchen4000
    Nov 06, 2019


    0
    kchen4000
    Nov 06, 2019

    1)c 2)e 11)c

    0
    chris13888
    Nov 11, 2019

    cec

    a, b = input().split(', ')


    class Node():

    def __init__(self, value):

    self.value = value

    self.left = self.right = None

    def insert(self, value):

    if value <= self.value:

    if self.left == None:

    self.left = Node(value)

    # print(f'{value} is the left child of {self.value}')

    else:

    self.left.insert(value)

    if value > self.value:

    if self.right == None:

    self.right = Node(value)

    # print(f'{value} is the right child of {self.value}')

    else:

    self.right.insert(value)

    def match(self, other):

    if self.left == None and self.right == None:

    return True

    if other.left == None and self.left != None:

    return False

    if other.right == None and self.right != None:

    return False

    if self.left == None:

    return self.right.match(other.right)

    if self.right == None:

    return self.left.match(other.left)

    return self.left.match(other.left) and self.right.match(other.right)

    def traverse(self):

    # print(self.value, self.left, self.right)

    yield self

    if self.left != None:

    yield from self.left.traverse()

    if self.right != None:

    yield from self.right.traverse()



    A = Node(a[0])

    for c in a[1:]:

    A.insert(c)


    B = Node(b[0])

    for c in b[1:]:

    B.insert(c)


    for node in B.traverse():

    if A.match(node):

    print(node.value)


    5 comments

    Questions? Email us at legionoflearners@gmail.com or join our WeChat group!

    • lol-101dotcom

    ©2020 Legion of Learners