# Codey and Money

## Question

Codey is planning a trip to Penang, and it needs to gather exactly `n` ringgits for its exciting journey. However, it only has access to a limited number of ringgit bills, each of which is a power of $$10$$. The ringgit bills that Codey has been defined by an array `a` with a length of `k`, where represents the number of $$10^{i-1}$$ ringgit bills that Codey possesses.

For example, when $$k = 3, a = \[3, 2, 1]$$, Codey has three $$1$$ ringgit bills, two $$10$$ ringgit bills, and one $$100$$ ringgit bill.

Codey would like you to determine if it's possible to obtain **precisely** `n` **ringgits** for its trip using the ringgit bills it has.

### Input Format

The first line contains an integer `t`, which represents the number of test cases.

The following provides the description of each test case:

* The first line contains an integer `k`, which represents the length of array `a`.
* The second line contains an integer `n`, which represents the final amount Codey needs.
* The third line contains `k` integers $$a\_1, a\_2, ..., a\_k$$, each representing the number of $$10^{i-1}$$ ringgit bills.

### Constraints

$$
1 \le t \le 500
$$

$$
1 \le k \le 10^5
$$

$$
1 \le n \le 10^k
$$

$$
0 \le a\_i \le 10^5
$$

* It is guaranteed that the sum of `k` over all test cases does not exceed `5 * 10^5`.

### Output Format

Outputs `YES` for test case if it's possible to obtain `n` ringgits, otherwise output `NO`.

### Sample Inputs:

{% tabs %}
{% tab title="Input 0" %}

#### Input

```
1
4
357
7 6 4 11
```

#### Output

```
YES
```

#### Explanation

The final amount `n` can be formed using `7` bills of `1` ringgit, `5` bills of `10` ringgit and `3` bills of `100` ringgit.
{% endtab %}

{% tab title="Input 1" %}

#### Input

```
2
2
11
2 3
2
1
0 1
```

#### Output

```
YES
NO
```

#### Explanation

In second test case, even though you have a `10` ringgit bill, you cannot split the bill to form exactly `1` ringgit.
{% endtab %}
{% endtabs %}

***

<details>

<summary>Solution - So many constraints QAQ</summary>

I had tried a lot of method to solve this question, but only this one work and passed all the test cases.

Basically, there are 3 things need to consider:

* The larger money can't split into smaller money
* The smaller money can merge into larger money
* Given largest currency amount is < 10, If the required money digit length is bigger than the largest currency, that is 100% no.

My personal logic would be:

1. Split the required amount of money into arrays and reverse it.
2. Check if the money\[i] is smaller than the required money digits\[i], if yes, that is instant NO.
3. Otherwise, subtract that, and divide the current money\[i] by 10, then add onto the next money\[i], and so on.

In illustrate, it would look like this:

```
Requires: 351
Money: 11 7 6 4

Step 1: Split and Reverse the required money
Requires: [1, 5, 3]
Money: [11, 7, 6, 4]

Step 2: Compare Requires[0] < Money[0]
Requires: [5, 3]
Money: [10, 7, 6, 4]

Step 3: Money[0] // 10, then add onto Money[1]
Requires: [5, 3]
Money: [8, 6, 4]

...

Step 6:
Requires: []
Money: [3, 4]

Since the Requires is empty, the answer is YES.
```

Here's the full code for the implementation:

{% code overflow="wrap" lineNumbers="true" %}

```python
def compare_array_and_digits(array, digits):
    digits.reverse()

    for i in range(len(digits)):
        if array[i] < digits[i]:
            return "NO"
        else:
            array[i] -= digits[i]
            try:
                array[i+1] += array[i] // 10
            except:
                pass
    return "YES"

t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    req = [int(digit) for digit in str(input())]
    have = list(map(int, input().strip().split()))
    
    print(compare_array_and_digits(have, req))
```

{% endcode %}

Note that I used `try, except, pass` to override the index out of range error. This technic is useful when it comes to competitive programming, when you simply don't want to handle the array leakage.

</details>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://eaglepb2.gitbook.io/cpw/codenection/2023/preliminary-round/codey-and-money.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.