Senior2019-Set 2 - Recursive Functions and CNS 2

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();

}

}

1. C

2. E

11. C

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define ii pair<int, int>

#define vi vector<int>

#define vii vector<ii>

#define vs vector<string>

#define ll long long

#define ull usigned ll

#define INF 1000000000

void insert(char a, vector<char> &tree, int pos) {

if (tree[pos] == '~') {

tree[pos] = a;

} else {

if (a <= tree[pos]) {

insert(a, tree, 2 * pos);

} else {

insert(a, tree, 2 * pos + 1);

}

}

}

bool check(vector<char> a, vector<char> b, int start) {

queue<ii> q;

int thing = 1;

ii temp = ii(thing, start);

q.push(temp);

vector<bool> visited(a.size() + 1, false); visited[1] = true;

while (!q.empty()) {

ii u = q.front(); q.pop();

if (u.first * 2 < (int)a.size() && a[u.first * 2] != '~') {

if (u.second * 2 < (int)b.size() && b[u.second * 2] != '~') {

if (!visited[u.first * 2]) {

q.push(ii(u.first * 2, u.second * 2));

visited[u.first * 2] = true;

}

} else {

return false;

}

}

if (u.first * 2 + 1 < (int)a.size() && a[u.first * 2 + 1] != '~') {

if (u.second * 2 + 1 < (int)b.size() && b[u.second * 2 + 1] != '~') {

if (!visited[u.first * 2 + 1]) {

q.push(ii(u.first * 2 + 1, u.second * 2 + 1));

visited[u.first * 2 + 1] = true;

}

} else {

return false;

}

}

}

return true;

}

int main() {

string a, b;

cin >> a >> b;

a = a.substr(0, a.length() - 1);

vector<char> smallTree(4000, '~'), bigTree(4000, '~');

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

insert(a[i], smallTree, 1);

}

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

insert(b[i], bigTree, 1);

}

vector<char> ans;

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

if (bigTree[i] != '~' && check(smallTree, bigTree, i)) ans.pb(bigTree[i]);

}

for (auto it : ans) {

cout << it << ", ";

}

if (ans.size() == 0) cout << "NONE";

cout << endl;

}

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)