import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[] dx = {0, 1, 0, -1};
static int[] dy = {-1, 0, 1, 0};
static long MOD = (long) (1e9 + 7);
static boolean isAnswerFound = false;
public static void main(String[] args) {
FastReader in = new FastReader();
while (true) {
int N = in.nextInt();
int[] nums = new int[N];
for (int i = 0; i < N; i++) {
nums[i] = in.nextInt();
}
int M = in.nextInt();
if (N == 0 && M == 0) {
break;
}
String s = in.nextLine();
isAnswerFound = false;
System.out.println(solve(nums, M, s) ? "YES" : "NO");
}
}
public static boolean solve(int[] nums, int M, String s) {
int[] newnums = new int[nums.length];
rec(nums, newnums, 0, s, M);
return isAnswerFound;
}
public static void rec(int[] nums, int[] newnums, int index, String s, int M) {
if (isAnswerFound) {
return;
}
if (index == nums.length) {
if (isValid(newnums, s, M)) {
isAnswerFound = true;
}
} else {
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= 0) {
int tmp = nums[i];
nums[i] = -1;
newnums[index] = tmp;
rec(nums, newnums, index + 1, s, M);
nums[i] = tmp;
}
}
}
}
public static boolean isValid(int[] nums, String s, int M) {
// printNumArray(nums);
HashMap<Character, Long> unknownMap = new HashMap<>();
Stack<CustomClass> stack = new Stack<CustomClass>();
// 1 => number, 2 => op, 3 => parenthesis
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// No number in string, so just look at character by character
if (c == '(') {
CustomClass cc = new CustomClass(3);
stack.add(cc);
} else if (c == ')') {
CustomClass keep = stack.pop();
CustomClass tmp = stack.pop();
// If it's an opening parenthesis, just replace it with the result of the expression
if (tmp.type == 3) {
stack.add(keep);
}
// It was an op
else if (tmp.type == 2) {
keep.n = exp(stack.pop().n, keep.n, tmp.op);
// Remove the starting parenthesis
stack.pop();
stack.add(keep);
} else {
// Should not reach here
out("This is unexpected");
}
} else if (c == '+' || c == '-' || c == '*') {
CustomClass cc = new CustomClass(2);
cc.op = c;
stack.add(cc);
} else {
long n = -1;
if (unknownMap.containsKey(c)) {
n = unknownMap.get(c);
} else {
n = nums[unknownMap.size()];
unknownMap.put(c, n);
}
// If we can compute the result, compute the result
if (stack.size() > 0 && stack.peek().type == 2) {
CustomClass op = stack.pop();
n = exp(stack.pop().n, n, op.op);
// Add the result of expression back to the result
CustomClass cc = new CustomClass(1);
cc.n = n;
stack.add(cc);
} else {
CustomClass cc = new CustomClass(1);
cc.n = n;
stack.add(cc);
}
}
}
return stack.pop().n == M;
}
public static long exp(long a, long b, char op) {
if (op == '+') {
return a + b;
} else if (op == '-') {
return a - b;
} else if (op == '*') {
return a * b;
} else {
out("Unknown operation");
return a;
}
}
public static int maxSideLength(int[][] mat, int threshold) {
if (mat == null || mat.length == 0 || mat[0].length == 0) {
return 0;
}
int M = mat.length;
int N = mat[0].length;
// Precompute the sum
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
mat[i][j] = getAt(mat, i, j) + getAt(mat, i - 1, j) + getAt(mat, i, j - 1) - getAt(mat, i - 1, j - 1);
}
}
int ans = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
for (int k = 1; i + k < M && j + k < N; k++) {
int area = getAt(mat, i + k, j + k) - getAt(mat, i + k, j - 1) - getAt(mat, i - 1, j + k) + getAt(mat, i - 1, j - 1);
if (area <= threshold) {
ans = Math.max(ans, k + 1);
}
}
}
}
return ans;
}
public static int getAt(int[][] mat, int i, int j) {
if (i < 0 || j < 0) return 0;
return mat[i][j];
}
public static List<Integer> findAnagrams(String s, String p) {
List<Integer> ans = new ArrayList<Integer>();
int[] pfreq = new int[26];
for (int i = 0; i < p.length(); i++) {
pfreq[p.charAt(i) - 'a']++;
}
int[] sfreq = new int[26];
for (int i = 0; i < p.length() && i < s.length(); i++) {
sfreq[s.charAt(i) - 'a']++;
}
// key is in the format character###,
String pkey = "";
String skey = "";
for (int i = 0; i < 26; i++) {
pkey += String.format("%c%d,", i + 'a', pfreq[i]);
skey += String.format("%c%d,", i + 'a', sfreq[i]);
}
for (int i = p.length(); i < s.length(); i++) {
char removed = s.charAt(i - p.length());
char added = s.charAt(i);
}
return ans;
}
public static int count(String[] arr, Map<String, Map<Character, TreeSet<Integer>>> map, String s) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
if (subsequence(s, map.get(arr[i]))) {
count++;
}
}
return count;
}
public static boolean subsequence(String s, Map<Character, TreeSet<Integer>> map) {
char f = s.charAt(0);
char m = s.charAt(1);
char e = s.charAt(2);
if (!map.containsKey(f) || !map.containsKey(m) || !map.containsKey(e)) {
return false;
}
Iterator<Integer> it = map.get(m).iterator();
while (it.hasNext()) {
int index = it.next();
if (map.get(f).lower(index) != null && map.get(e).higher(index) != null) {
return true;
}
}
return false;
}
public static String str(int i, int j, int k) {
return String.format("%c%c%c", c(i), c(j), c(k));
}
public static char c(int i) {
if (i < 26) {
return (char) ('A' + i);
} else {
i -= 26;
return (char) ('a' + i);
}
}
public static int sol(int N, int k) {
if (N == 1 && k == 1) return 1;
int parent = sol(N - 1, (k + 1) / 2);
if (k % 2 == 0) {
return (parent + 1) % 2;
} else {
return parent;
}
}
public static double calculate(double base, double n) {
return Math.pow(Math.E, Math.log(base)/n);
}
public static int partition(int[] nums, int low, int high) { // [1,2], 0, 1
// Pick the first element as pivot
// int pivot = nums[low]; // 1
//
// int left = low + 1; // 2
// int right = high; // 1
//
//
// while (left <= right) { // This equal to is important to move right
// cursor left cursor correct position
// if (nums[left] <= pivot) {
// left++;
// continue;
// }
// if (pivot <= nums[right]) {
// right--;
// continue;
// }
// int tmp = nums[left];
// nums[left] = nums[right];
// nums[right] = tmp;
// }
// int tmp = nums[low];
// nums[low] = nums[right];
// nums[right] = tmp;
//
// return right;
// Pick the last element as pivot
int pivot = nums[high];
int left = low;
int right = high - 1;
while (left <= right) {
if (nums[left] <= pivot) {
left++;
continue;
}
if (pivot <= nums[right]) {
right--;
continue;
}
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
int tmp = nums[high];
nums[high] = nums[left];
nums[left] = tmp;
return left;
}
// Pivot is the first element
public static int partitionFront(int[] nums, int low, int high) {
int pivot = nums[low];
int left = low + 1;
while (left <= high) {
// Increment left until it reaches the element greater than pivot
while (left <= high && nums[left] <= pivot)
left++;
while (left <= high && nums[high] >= pivot)
high--;
if (left < high) {
int tmp = nums[left];
nums[left] = nums[high];
nums[high] = tmp;
}
}
int tmp = nums[low];
nums[low] = nums[high];
nums[high] = tmp;
return high;
}
// Pivot is the last element
public static int partitionBack(int[] nums, int low, int high) {
int pivot = nums[high];
int right = high - 1;
while (low <= right) {
// Increment low until it is greater than pivot
while (low <= right && nums[low] <= pivot)
low++;
// Decrement right until it is less than pivot
while (low <= right && nums[right] >= pivot)
right--;
if (low < right) {
int tmp = nums[low];
nums[low] = nums[right];
nums[right] = tmp;
}
}
int tmp = nums[low];
nums[low] = nums[high];
nums[high] = tmp;
return low;
}
public static void out(Object o) {
System.out.println(o);
}
public static void print(Object o) {
System.out.print(o);
}
public static void printNumArray(int[] nums) {
System.out.printf("[");
for (int i = 0; i < nums.length; i++) {
System.out.printf("%d%s", nums[i], i != nums.length - 1 ? ", " : "");
}
System.out.println("]");
}
public static void printNumArray(long[] nums) {
System.out.printf("[");
for (int i = 0; i < nums.length; i++) {
System.out.printf("%d%s", nums[i], i != nums.length - 1 ? ", " : "");
}
System.out.println("]");
}
public static void printDoubleArray(double[] nums) {
System.out.printf("[");
for (int i = 0; i < nums.length; i++) {
System.out.printf("%f%s", nums[i], i != nums.length - 1 ? ", " : "");
}
System.out.println("]");
}
public static void printDoubleList(List<List<Integer>> nums) {
for (int i = 0; i < nums.size(); i++) {
printNumList(nums.get(i));
}
}
public static void printNumList(List<Integer> nums) {
System.out.printf("[");
for (int i = 0; i < nums.size(); i++) {
System.out.printf("%d%s", nums.get(i), i != nums.size() - 1 ? ", " : "");
}
System.out.println("]");
}
public static void printStringList(List<String> list) {
System.out.printf("[");
for (int i = 0; i < list.size(); i++) {
System.out.printf("%s%s", list.get(i), i != list.size() - 1 ? ", " : "");
}
System.out.println("]");
}
public static void printStringArray(String[] arr) {
print("[");
for (int i = 0; i < arr.length; i++) {
print(String.format("%s%s", arr[i], i != arr.length - 1 ? ", " : ""));
}
out("]");
}
public static void printStringListOfStringList(List<List<String>> list) {
for (int i = 0; i < list.size(); i++) {
printStringList(list.get(i));
}
}
public static void printNumListOfNumList(List<List<Integer>> num) {
for (int i = 0; i < num.size(); i++) {
printNumList(num.get(i));
}
}
public static void printNumListOfNumArray(List<int[]> list) {
for (int i = 0; i < list.size(); i++) {
printNumArray(list.get(i));
}
}
public static void printNum2DArray(int[][] map) {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
System.out.printf("%2d ", map[i][j]);
}
System.out.println();
}
}
public static void printNum2DArray(long[][] map) {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
System.out.printf("%2d ", map[i][j]);
}
System.out.println();
}
}
public static void printCharArray(char[] arr) {
print("[");
for (int i = 0; i < arr.length; i++) {
System.out.printf("%c%s", arr[i], i == arr.length - 1 ? "" : ", ");
}
out("]");
}
public static void printChar2DArray(char[][] map) {
for (char[] arr : map) {
for (char c : arr) {
print(String.format("%c ", c));
}
out("");
}
}
public static void printBoolean2DArray(boolean[][] map) {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
print(map[i][j] ? "T " : "F ");
}
out("");
}
}
public static void printListNode(ListNode node) {
boolean first = true;
while (node != null) {
if (!first) {
print("->");
}
print(node.val);
node = node.next;
first = false;
}
}
public static void printStringSet(Set<String> set) {
for (String s : set) {
out(s);
}
}
/**
* Receives an integer and print in numBits from the right
*
* @param n
* @param numBits
*/
public static void printBinary(int n, int numBitsFromRight) {
String s = "";
for (int i = numBitsFromRight - 1; i >= 0; i--) {
s += (n & (1 << i)) > 0 ? "1" : "0";
}
out(s);
}
// Taken from
// https://www.geeksforgeeks.org/c-program-find-gcd-hcf-two-numbers/
public static long gcd(long a, long b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
public static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
public static long lcm(long a, long b) {
return a * b / gcd(a, b);
}
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class CustomClass {
int type; // 1 => number, 2 => op, 3 => parenthesis
// parenthesis will be stored in op
char op;
long n;
public CustomClass(int type) {
this.type = type;
}
}
class TreeDrawer {
public static String treeNodeToString(TreeNode root) {
if (root == null) {
return "[]";
}
String output = "";
Queue<TreeNode> nodeQueue = new LinkedList<>();
nodeQueue.add(root);
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();
if (node == null) {
output += "null, ";
continue;
}
output += String.valueOf(node.val) + ", ";
nodeQueue.add(node.left);
nodeQueue.add(node.right);
}
return "[" + output.substring(0, output.length() - 2) + "]";
}
public static TreeNode stringToTreeNode(String input) {
input = input.trim();
input = input.substring(1, input.length() - 1);
if (input.length() == 0) {
return null;
}
String[] parts = input.split(",");
String item = parts[0];
TreeNode root = new TreeNode(Integer.parseInt(item));
Queue<TreeNode> nodeQueue = new LinkedList<>();
nodeQueue.add(root);
int index = 1;
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();
if (index == parts.length) {
break;
}
item = parts[index++];
item = item.trim();
if (!item.equals("null")) {
int leftNumber = Integer.parseInt(item);
node.left = new TreeNode(leftNumber);
nodeQueue.add(node.left);
}
if (index == parts.length) {
break;
}
item = parts[index++];
item = item.trim();
if (!item.equals("null")) {
int rightNumber = Integer.parseInt(item);
node.right = new TreeNode(rightNumber);
nodeQueue.add(node.right);
}
}
return root;
}
public static void prettyPrintTree(TreeNode node, String prefix, boolean isLeft) {
if (node == null) {
System.out.println("Empty tree");
return;
}
if (node.right != null) {
prettyPrintTree(node.right, prefix + (isLeft ? "│ " : " "), false);
}
System.out.println(prefix + (isLeft ? "└── " : "┌── ") + node.val);
if (node.left != null) {
prettyPrintTree(node.left, prefix + (isLeft ? " " : "│ "), true);
}
}
public static void draw(TreeNode node) {
prettyPrintTree(node, "", true);
}
}
class Interval {
int start;
int end;
Interval() {
start = 0;
end = 0;
}
Interval(int s, int e) {
start = s;
end = e;
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
long nextLong()
{
return Long.parseLong(next());
}
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try
{
str = br.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
}
Harigami
タイトルなし
タイトルなし
UVa 12392 - Guess the Numbers