Codeforces Round 659 (Div. 2) |
---|
Закончено |
Единственная разница между простой и сложной версиями заключается в ограничениях. В этой версии ограничения ниже. Вы можете делать взломы только если обе версии задачи сданы.
Коала Коа на пляже!
Пляж состоит из (слева направо) берега, $$$n+1$$$ метров моря, и острова в $$$n+1$$$ метрах от берега.
Она измерила глубину моря на расстоянии $$$1, 2, \dots, n$$$ метров от берега и сохранила эту информацию в массиве $$$d$$$. $$$d_i$$$ обозначает глубину моря в $$$i$$$ метрах от берега для $$$1 \le i \le n$$$.
Как и на любом пляже, на этом есть прилив, интенсивность прилива измеряется параметром $$$k$$$ и влияет на все глубины с начала в момент времени $$$t=0$$$ следующим образом:
Формально, давайте определим $$$0$$$-индексированный массив $$$p = [0, 1, 2, \ldots, k - 2, k - 1, k, k - 1, k - 2, \ldots, 2, 1]$$$ длины $$$2k$$$. В момент времени $$$t$$$ ($$$0 \le t$$$) глубина на расстоянии $$$i$$$ метров от берега равна $$$d_i + p[t \bmod 2k]$$$ ($$$t \bmod 2k$$$ обозначает остаток от деления $$$t$$$ на $$$2k$$$). Обратите внимание, что изменения происходят мгновенно каждую секунду, см. примеры для лучшего понимания.
В момент времени $$$t=0$$$ Коа стоит на берегу, и хочет добраться до острова. Пусть во время $$$t$$$ ($$$0 \le t$$$) она находится в $$$x$$$ ($$$0 \le x \le n$$$) метрах от берега:
Обратите внимание, что пока Коа плывет, прилив не влияет на нее (то есть она не может утонуть во время плавания). Обратите внимание, что Коа может оставаться на берегу, сколько ей нужно, и ни берег, ни остров не подвержены влиянию прилива (это твердая земля, и она там не утонет).
Коа хочет знать, сможет ли она добраться с берега на остров. Помогите ей!
В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Описание наборов входных данных приведено ниже.
Первая строка каждого набора входных данных содержит три целых числа: $$$n$$$, $$$k$$$ and $$$l$$$ ($$$1 \le n \le 100; 1 \le k \le 100; 1 \le l \le 100$$$) — количество метров моря и параметры $$$k$$$ и $$$l$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$ ($$$0 \le d_i \le 100$$$) — глубины каждого метра моря.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$100$$$.
Для каждого набора входных данных:
Выведите Yes, если Коа сможет добраться от берега до острова, и No в обратном случае.
Вы можете выводить каждую букву в любом регистре (верхнем или нижнем).
7 2 1 1 1 0 5 2 3 1 2 3 2 2 4 3 4 0 2 4 3 2 3 5 3 0 7 2 3 3 0 2 1 3 0 1 7 1 4 4 4 3 0 2 4 2 5 2 3 1 2 3 2 2
Yes No Yes Yes Yes No No
Ниже $$$s$$$ обозначает берег, $$$i$$$ обозначает остров, $$$x$$$ обозначает расстояние от Коа до берега, нижнее подчеркивание обозначает позицию Коа, а значения в массиве ниже обозначают текущие глубины, измененные под влиянием прилива, на расстояниях $$$1, 2, \dots, n$$$ от берега.
В наборе входных данных $$$1$$$ мы имеем $$$n = 2, k = 1, l = 1, p = [ 0, 1 ]$$$.
Коа хочет добраться с берега (c $$$x = 0$$$) на остров (c $$$x = 3$$$). Опишем возможное решение:
Можно показать, что наборе входных данных $$$2$$$ Коа не сможет доплыть до острова.
Название |
---|