Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помогите с задачей c++

Твой Тёмочка Ученик (94), закрыт 10 месяцев назад
Условие
У вас есть n
дощечек длиной d1,d2,…,dn
. Чтобы построить лестницу, вам нужно выбрать k+2
дощечки: две из них длиной x
и k
длиной y
. Можно укорачивать дощечки, но нельзя разделять одну на две. Сможете ли вы построить лестницу?

Формат входных данных
Первая строка входного файла содержит число t
- количество тестов (t≤250000
). Затем следуют описания тестов, для каждого вводятся числа n
, k
, x
, y
(1≤n≤105
, 0≤k≤105
, 1≤x,y≤109
), а за ними n
чисел d1,…,dn
(1≤di≤109
). Сумма n
по всем тестам не превосходит 1500000
.

Формат выходных данных
Для каждого теста выведите одну строку - ответ на вопрос задачи, т.е. “YES”, если возможно построить лестницу, и “NO”, если нет.


входные данные
2
8 3 5 2
1 1 1 2 3 4 5 6
8 3 6 2
1 1 1 2 3 4 5 6

выходные данные
YES
NO
Лучший ответ
Папа Высший разум (121710) 11 месяцев назад
Да легко, что тут писать вообще?
 #include 
#include

using namespace std;

int main() {
const char MSG[][4] = { "NO", "YES" };
size_t t;
cin >> t;
while (t--) {
size_t n, k, x, y;
cin >> n >> k >> x >> y;
size_t *d = new size_t[n];
for (size_t i = 0; i < n; i++)
cin >> d[i];
sort(d, d + n, greater());
cout << MSG[n > k + 1 && d[1] >= x && d[k + 1] >= y] << endl;
delete d;
}

return 0;
}
Исходим из того, что x > y, речь же о лестнице (два бруса или доски - вдоль, и много - поперёк).
Сортируем массив по убыванию. Тогда второй элемент (с индексом 1) должен быть не меньше x, а k+2-й - не меньше y, чтобы получить достаточную длину для всех элементов лестницы (если эти условия выполнены, то предшествующие элементы будут и подавно не меньше).

Но если у нас лестница от ChatGPT и его полудурков-ботов, то у неё ступеньки могут быть длиннее направляющих. Ходить по такой вряд ли получится, но кого из них это когда заботило? Тогда можно немного усложнить условие: 2-й элемент сравниваем с максимумом из x, y, а k+2-й - с минимумом:
 #include 
#include

using namespace std;

int main() {
const char MSG[][4] = { "NO", "YES" };
size_t t;
cin >> t;
while (t--) {
size_t n, k, x, y;
cin >> n >> k >> x >> y;
size_t *d = new size_t[n];
for (size_t i = 0; i < n; i++)
cin >> d[i];
sort(d, d + n, greater());
cout << MSG[n > k + 1 && d[1] >= max(x, y) && d[k + 1] >= min(x, y)] << endl;
delete d;
}

return 0;
}
Всё работает только с целыми неотрицательными числами. Если нужны вещественные, то x, y, d переделай на double.
Твой ТёмочкаУченик (94) 11 месяцев назад
не правильно
Папа Высший разум (121710) Твой Тёмочка, на твоих входных данных у меня выдаёт правильный результат. Что у тебя там "неправильно", с этим - к гадалкам. Сюда пиши полное описание ошибки.
Даниил ПолянскийУченик (142) 11 месяцев назад
Ага)
Даниил Полянский, хах
Остальные ответы
Сергей Гений (56227) 11 месяцев назад
 #include 
#include
using namespace std;
int main()
{
size_t num, n, k, x, y;
cin >> num;
vector results(num);
for (size_t i=0;i {
cin >> n >> k >> x >> y;
size_t leng_x{}, leng_y{}, tmp;
while (n--)
{
cin >> tmp;
if (tmp >= x) ++leng_x;
if (tmp >= y) ++leng_y;
}
if (x > y) k -= 2;
results[i] = (leng_x >= 2 && leng_y >= k);

}
for (size_t i = 0; i < num; i++)
cout << (results[i]? "YES\n" : "NO\n");
}
 UPD::не работает с лестницами в стиле GPT, может сейчас поправлю.
UPD::поправил )
ПапаВысший разум (121710) 11 месяцев назад
Линейная сложность в каждом тест кейсе, неплохо.
Но с GPT-лестницами какой-то мудрёж...
Нам и для обычных, и для GPT надо искать одинаковое количество досок: k + 2.
Сергей Гений (56227) Папа, я сразу написал leng_y >= k-2 полагая что если x>y то в общее количество брусков подходящих для k находится и два бруска длиной x. и тест провалился для лестницы с двумя брусями 2 метра и одной перекладиной 5 метров. После этого ввел проверку x>y. А больше там менять нечего ибо x должно быть >=2 в любом случае )
Даниил ПолянскийУченик (142) 11 месяцев назад
а как по итогу решить?
Сергей Гений (56227) Ну так программа написана. Фидбека только нет.
Похожие вопросы