28B.md (1389B)
1 Source: https://codeforces.com/problemset/problem/28/B 2 3 B. pSort 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 stdin 16 17 output 18 19 stdout 20 21 One day *n* cells of some array decided to play the following game. Initially each cell contains a number which is equal to it's ordinal number (starting from 1). Also each cell determined it's favourite number. On it's move *i*-th cell can exchange it's value with the value of some other *j*-th cell, if |*i* - *j*| = *d**i*, where *d**i* is a favourite number of *i*-th cell. Cells make moves in any order, the number of moves is unlimited. 22 23 The favourite number of each cell will be given to you. You will also be given a permutation of numbers from 1 to *n*. You are to determine whether the game could move to this state. 24 25 Input 26 27 The first line contains positive integer *n* (1 ≤ *n* ≤ 100) — the number of cells in the array. The second line contains *n* distinct integers from 1 to *n* — permutation. The last line contains *n* integers from 1 to *n* — favourite numbers of the cells. 28 29 Output 30 31 If the given state is reachable in the described game, output YES, otherwise NO. 32 33 Examples 34 35 Input 36 37 ``` 38 5 39 5 4 3 2 1 40 1 1 1 1 1 41 ``` 42 43 Output 44 45 ``` 46 YES 47 ``` 48 49 Input 50 51 ``` 52 7 53 4 3 5 1 2 7 6 54 4 6 6 1 6 6 1 55 ``` 56 57 Output 58 59 ``` 60 NO 61 ``` 62 63 Input 64 65 ``` 66 7 67 4 2 5 1 3 7 6 68 4 6 6 1 6 6 1 69 ``` 70 71 Output 72 73 ``` 74 YES 75 ```