Перчатки Ограничение по времени: 0.5 секунды Ограничение по памяти: 256 мегабайт Учитель принёс в класс две коробки, в одной из которых лежат только левые перчатки, а в другой —…
Перчатки Ограничение по времени: 0.5 секунды Ограничение по памяти: 256 мегабайт Учитель принёс в класс две коробки, в одной из которых лежат только левые перчатки, а в другой — только правые. Перчатки могут быть либо белыми, либо чёрными. Каждый ученик не глядя взял по одной перчатке из каждой коробки и надел их на руки. Когда все ученики надели перчатки, оказалось, что у A ребят на обеих руках надеты белые перчатки, у B ребят на правой руке надета белая перчатка, а на левой — чёрная, у C ребят, напротив, на правой руке надета чёрная перчатка, а на левой — белая, и, наконец, у D ребят на обеих руках чёрные перчатки. Теперь учитель попросил учеников взяться за руки и выстроиться в как можно более длинную цепочку, при этом: каждый ученик должен стоять лицом к учителю; ученики могут взяться за руки, только если цвет перчаток на их руках совпадает. Определите длину максимально возможной цепочки, которую могут образовать ученики. Формат входных данных В четырёх строках вводятся четыре числа A , B , C , D (0≤A , B , C , D≤108 ), описанные в условии задачи. Формат выходных данных Выведите одно целое число — длину самой длинной цепочки, в которую могут выстроиться школьники, соблюдая условия задания учителя. Система оценки В этой задаче 20 тестов, каждый из которых проверяется и оценивается независимо в 5 баллов. Замечание В первом примере можно выстроить в цепочку всех четверых детей: Во втором примере можно соединить только троих:
Для решения задачи необходимо анализировать, как ученики могут соединяться в цепочку в зависимости от цвета перчаток.
У нас есть следующие категории учеников:
- A: ребята с белыми перчатками на обеих руках.
- B: ребята с белой перчаткой на правой и чёрной на левой руке.
- C: ребята с чёрной перчаткой на правой и белой на левой руке.
- D: ребята с чёрными перчатками на обеих руках.
Чтобы ученики могли взять друг друга за руки, цвета перчаток на руках должны совпадать. Теперь давайте посмотрим, как мы можем соединить их:
- Учащиеся A могут соединяться только с другими A (двухцветная комбинация не подходит).
- Учащиеся B могут соединяться с:
- A (белые на обеих руках)
- C (так как у C на левой руке белая перчатка).
- Учащиеся C могут соединяться с:
- A (белые на обеих руках)
- B (так как у B на левой руке чёрная перчатка).
- Учащиеся D могут соединяться только с другими D (чёрные на обеих руках).
Теперь определим максимальную длину цепочки, учитывая возможности соединений:
- Мы можем объединить всех A в одну цепочку.
- Далее, чтобы соединить максимальное количество B и C, здесь важно учитывать, что их количество будет ограничивать общий результат.
Формула для вычисления длины максимальной цепочки выглядит следующим образом: \[ \text{Максимальная длина цепочки} = A + \min(B, C) + D \]
Это объясняется тем, что мы можем добавить всех учеников A, минимальное число между B и C (поскольку они могут соединяться друг с другом) и всех учеников D, потому что они могут формировать свою отдельную группу.
Теперь подставим значения и получим ответ.
Пример: Если, например, A=2, B=3, C=1, D=4, то: \[ \text{Максимальная длина цепочки} = 2 + \min(3, 1) + 4 = 2 + 1 + 4 = 7 \]
Таким образом, длина самой длинной цепочки, которую могут образовать учащиеся, равна: \[ \text{Ответ} = A + \min(B, C) + D \]
Представьте свои значения для A, B, C и D, и вы сможете легко вычислить ответ по данной формуле!
