codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1948B.md (1984B)


      1 Source: https://codeforces.com/problemset/problem/1948/B
      2 
      3 B. Array Fix
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an integer array $a$ of length $n$.
     22 
     23 You can perform the following operation any number of times (possibly zero): take any element of the array $a$, which is at least $10$, delete it, and instead insert the digits that element consisted of in the same position, in order they appear in that element.
     24 
     25 For example:
     26 
     27 * if we apply this operation to the $3$-rd element of the array $[12, 3, 45, 67]$, then the array becomes $[12, 3, 4, 5, 67]$.
     28 * if we apply this operation to the $2$-nd element of the array $[2, 10]$, then the array becomes $[2, 1, 0]$.
     29 
     30 Your task is to determine whether it is possible to make $a$ sorted in non-descending order using the aforementioned operation any number of times (possibly zero). In other words, you have to determine if it is possible to transform the array $a$ in such a way that $a_1 \le a_2 \le \dots \le a_k$, where $k$ is the current length of the array $a$.
     31 
     32 Input
     33 
     34 The first line contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases.
     35 
     36 Each test case consists of two lines:
     37 
     38 * the first line contains a single integer $n$ ($2 \le n \le 50$).
     39 * the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 99$).
     40 
     41 Output
     42 
     43 For each test case, print YES if it is possible to make $a$ sorted in non-decreasing order using the aforementioned operation; otherwise, print NO.
     44 
     45 You can print each letter in any case. For example, yes, Yes, YeS will all be recognized as a positive answer.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 3
     53 
     54 4
     55 
     56 12 3 45 67
     57 
     58 3
     59 
     60 12 28 5
     61 
     62 2
     63 
     64 0 0
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 YES
     71 NO
     72 YES
     73 ```
     74 
     75 Note
     76 
     77 In the first example, you can split the first element, then the array becomes $[1, 2, 3, 45, 67]$.
     78 
     79 In the second example, there is no way to get a sorted array.
     80 
     81 In the third example, the array is already sorted.