Перчатки Ограничение по времени: 0.5 секунды Ограничение по памяти: 256 мегабайт Учитель принёс в класс две коробки, в одной из которых лежат только левые перчатки, а в другой —…
Перчатки Ограничение по времени: 0.5 секунды Ограничение по памяти: 256 мегабайт Учитель принёс в класс две коробки, в одной из которых лежат только левые перчатки, а в другой — только правые. Перчатки могут быть либо белыми, либо чёрными. Каждый ученик не глядя взял по одной перчатке из каждой коробки и надел их на руки. Когда все ученики надели перчатки, оказалось, что у А ребят на обеих руках надеты белые перчатки, у В ребят на правой руке надета белая перчатка, а на левой — чёрная, у С ребят, напротив, на правой руке надета чёрная перчатка, а на левой — белая, и, наконец, у D ребят на обеих руках чёрные перчатки. Теперь учитель попросил учеников взяться за руки и выстроиться в как можно более длинную цепочку, при этом • каждый ученик должен стоять лицом к учителю; • ученики могут взяться за руки, только если цвет перчаток на их руках совпадает. Определите длину максимально возможной цепочки, которую могут образовать ученики. Формат входных данных В четырёх строках вводятся четыре числа A, B, C, D (0 ≤ A, B, C, D ≤ 10*), описанные Формат выходных данных Выведите одно целое число — длину самой длинной цепочки, в которую могут выстроиться школьники, соблюдая условия задания учителя. Система оценки В этой задаче 20 тестов, каждый из которых проверяется и оценивается независимо в 5 баллов. Замечание В первом примере можно выстроить в цепочку всех четверых детей: Во втором примере можно соединить только троих: Ввод Вывод 1 1 1 1 8318 Код 1 2 3 4 3
Чтобы определить максимальную длину цепочки, которую могут образовать ученики на основе цветов перчаток, давайте сначала рассмотрим данные:
- A ребята (обе белые перчатки)
- B ребята (правая белая, левая черная)
- C ребята (правая черная, левая белая)
- D ребята (обе черные перчатки)
Теперь проанализируем, как эти группы могут соединяться по цвету перчаток:
- A (оба белые) можно соединить с B (правая белая) или с C (левая белая), но не с D (черные).
- B (правая белая) можно соединить с A (обе белые) и не может соединиться с D (так как у D обе перчатки черные).
- C (левая белая) может соединяться с A (обе белые) и не может соединяться с D.
- D (оба черные) может соединяться только с теми, у кого хотя бы одна черная перчатка, а именно с B и C.
Теперь составим возможные цепочки:
Если включить A, то можем взять B или C:
- Пусть возьмём A, B и D: A (белая, белая) соединяется с B (белая, черная) -> 2 участника
- B может с D (черные) -> ещё 1 участник, итого 3.
Далее, если не брать A, можно взять только цепочку из B и D или C и D:
- С B: B (белая, черная) соединяется с D (черные) -> 2 участника.
- С C: C (черная, белая) соединяется с D (черные) -> снова 2 участника.
Но что касается выхода:
- Цепочка A, B, D дает максимум 3.
- Цепочка A, C, D также максимум 3.
- Цепочка B и D, или C и D – максимум 2.
Таким образом, максимальная длина цепочки, которую могут образовать школьники, равна 3.
Ответ: 3.
