-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathB. Clockwork.py
More file actions
70 lines (57 loc) · 3.5 KB
/
B. Clockwork.py
File metadata and controls
70 lines (57 loc) · 3.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
----------------------------------------------------------------------------B. Clockwork-------------------------------------------------------------------------------
---------------------------------------------------------------------time limit per test1.5 seconds---------------------------------------------------------------------
-------------------------------------------------------------------memory limit per test512 megabytes-------------------------------------------------------------
You have a sequence of n time clocks arranged in a line, where the initial time on the i-th clock is ai. In each second, the following happens in order:
Each clock's time decreases by 1. If any clock's time reaches 0, you lose immediately.
You can choose to move to an adjacent clock or stay at the clock you are currently on.You can reset the time of the clock you are on back to its initial value ai.
Note that the above events happen in order. If the time of a clock reaches 0 in a certain second, even if you can move to this clock and reset its time during that second, you will still lose.
You can start from any clock. Determine if it is possible to continue this process indefinitely without losing.
------------------------------------------------------------------------Input-------------------------------------------------------
The first line of input contains a single integer t (1≤t≤104) — the number of test cases.
For each test case, the first line contains a single integer n (2≤n≤5⋅105) — the number of time clocks.
The second line contains n integers a1,a2,…,an (1≤ai≤109) — the initial times set on the clocks.
It is guaranteed that the sum of n over all test cases does not exceed 5⋅105.
------------------------------------------------------------------------Output------------------------------------------------------------
For each test case, print "YES" (without quotes) if it is possible to continue this process indefinitely, or "NO" (without quotes) otherwise.
You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).
Example
Input
5
2
4 10
2
2 2
3
4 10 5
3
5 3 5
5
12 13 25 17 30
Output
YES
NO
NO
YES
YES
Note
In the first test case, you can move back and forth between the two clocks, resetting them repeatedly.
In the third test case, assuming that you start from clock 1 and follow the strategy below:Initially, a=[4,10,5].
a becomes [3,9,4]. You move to clock 2 and reset its time, resulting in a=[3,10,4].
a becomes [2,9,3]. You move to clock 3 and reset its time, resulting in a=[2,9,5]
a becomes [1,8,4]. You move to clock 2 and reset its time, resulting in a=[1,10,4].
a becomes [0,9,3]. You move to clock 1, but you lose because a1 reaches 0.
------------------------------------------------------------------solution--------------------------------------------------------------
check where distence is small from left side or right side choose the max distance and check does a1 has enough time so we can go to the end timer and come back from it
--------------------------------------------------------------Code--------------------------------------------------------------------
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
possible = True
for i in range(n):
if a[i] <= 2 * max(i, n - i - 1):
print("No")
break
else:
print("Yes")
It can be proven that no other strategy allows you to continue this process indefinitely.