Short Questions Programming: 2002-2003#8
awesomeface259Nov 2, 20191. C2. E11. Ccode: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();}}
colinzhao777Nov 4, 20191. C2. E11. 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 1000000000void 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;}
chris13888Nov 11, 2019ceca, 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)
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;
}
1)c 2)e 11)c
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)