Информатика

Дано дерево решений и вектор признаков объекта. Определите, какой класс предскажет дерево.

Правило обхода

Если x[feature_index] <= threshold, идём в left_child
Иначе идём в right_child
Когда достигли листа, возвращаем его class


Формат входных данных
Первая строка: JSON с деревом. Вторая строка: признаки объекта через пробел.

Формат выходных данных
Одно число — предсказанный класс.

Дано дерево решений и id целевого узла. Найдите путь от корня (id=0) до этого узла.

Формат входных данных
Первая строка: JSON с деревом. Вторая строка: целевой id узла.

Формат выходных данных
ID узлов от корня до целевого, через пробел.

Найдите максимальную глубину дерева решений. Глубина корня равна 0.

Формат входных данных
JSON с деревом решений.
 

Формат выходных данных
Одно целое число — глубина дерева.

Дано дерево решений в формате JSON. Подсчитайте количество внутренних узлов (type = "decision") и листьев (type = "leaf").

Формат входных данных
JSON с полем "nodes" — список узлов.


Формат выходных данных
Два числа через пробел: количество внутренних узлов и количество листьев.

После Великой паники директор понял: старая система слишком сложная и ошибается. Он собрал данные за целую неделю (не только тот понедельник):

№	Странные слова?	Избегает общения?	Пришёл до 9:00?	Оказался нечистью?
1	Да	Да	Да	✅ Да
2	Да	Да	Нет	✅ Да
3	Да	Нет	Да	❌ Нет
4	Да	Нет	Нет	❌ Нет
5	Нет	Да	Да	❌ Нет
6	Нет	Да	Нет	✅ Да
7	Нет	Нет	Да	❌ Нет
8	Нет	Нет	Нет	❌ Нет

Всего: 3 нечисти, 5 людей

---

Директор заметил: «Бледное лицо» больше не работает — зимой все бледные! Нужны новые признаки.

Ты получил задачу: Построй дерево глубины 2 и предскажи для новенького.
 

Новенький — Гриша:

• Странные слова: ДА (переехал из Германии, вставляет немецкие слова)
• Избегает общения: ДА (стесняется, ещё никого не знает)
• Пришёл до 9:00: ДА (родители привезли пораньше)

Что предскажет оптимальное дерево глубины 2?

• 1. Человек
• 2. Нечисть
• 3. 50/50 — дерево не может определить
• 4. Нужен третий уровень дерева

После карантина школа Ларево установила систему для определения зомби:

              [Бледное лицо?]
               /           \
             Да            Нет
             /               \
      [Странная походка?]   НЕ ЗОМБИ
         /          \
       Да           Нет
       /              \
[Издаёт стоны?]    НЕ ЗОМБИ
    /       \
  Да        Нет
  /           \
ЗОМБИ      НЕ ЗОМБИ

Понедельник, 8:00. Костя всю ночь писал код. Приходит в школу:

• Лицо бледное (не видел солнце 3 дня)
• Походка странная (врезался в две стены)
• Издаёт стоны («уууу....стены...кофеее....коодд»)

Система сработала и вызвала охрану! Костя хочет доказать, что он не зомби. Какой ОДИН признак ему проще всего изменить прямо сейчас, чтобы система изменила решение?

• 1. Бледное лицо — умыться холодной водой
• 2. Странная походка — выпить кофе и взбодриться
• 3. Издаёт стоны — просто замолчать
• 4. Любой из трёх сработает одинаково

Дерево отбора на олимпиаду по программированию:

              [Средний балл > 4.5?]
                /              \
              Да               Нет
              /                  \
     [Победил в прошлом году?]  НЕ ПУСТЯТ
          /           \
        Да            Нет
        /               \
    ПУСТЯТ        [Рекомендация учителя?]
                      /            \
                    Да             Нет
                    /                \
                ПУСТЯТ          НЕ ПУСТЯТ

Костя Багов: средний балл 4.2, но он трижды побеждал на олимпиадах, написал школьный сайт и учитель информатики его боготворит.

Пустят на олимпиаду?

• 1. Пустят — он же гений!
• 2. Не пустят
• 3. Пустят вне конкурса
• 4. Создаст свою олимпиаду

Нейросеть школы Ларево предсказывает, проспит ли Тимоха урок:

        [Урок до 10:00?]
         /           \
       Да            Нет
       /               \
   ПРОСПИТ         НЕ ПРОСПИТ

Сейчас урок информатики, начало в 8:30. Что предскажет модель?

• 1. Проспит
• 2. Не проспит
• 3. Зависит от предмета
• 4. Нужно проверить, выпил ли он кофе

Добро пожаловать в школу Ларево — место, где ученики строят ML-модели, чтобы предсказать, кого вызовут к доске, а учителя используют нейросети для распознавания тех, кто не сделал домашку.

---

🌟 ГЕРОИ ШКОЛЫ ЛАРЕВО:

• Тимофей «Тимоха» Лапшин — засыпает на любом уроке за 3 минуты
• Алиса Кактусова — рисует мемы в тетради вместо конспектов
• Данил «Данон» Йогуртов — всегда голодный, ест на уроках
• Вика Вайфайная — не может жить без телефона больше 5 минут
• Костя Багов — гений программирования, но забывает надеть разные носки
• Маша Мемасова — знает все тренды, но не знает, кто такой Пушкин

Готовы к викторине?
1. Да
2. Нет



---
Все имена и события выдуманы. Любые совпадения случайны (честно)
За ответ на этот вопрос тоже дают балл :)

ИИ-система школы Ларево научилась распознавать котов на фото (для важных научных целей):

            [Есть усы?]
            /         \
          Да          Нет
          /             \
    [Говорит «мяу»?]   НЕ КОТ
       /        \
     Да         Нет
     /            \
   КОТ        [Ловит мышей?]
                /        \
              Да         Нет
              /            \
            КОТ        НЕ КОТ

Ситуация: На перемене Вика нарисовала Тимохе усы маркером пока он спал. Тимоха проснулся, увидел себя в камере телефона и от неожиданности издал звук «мяяяу?!». В этот момент школьная система распознавания сфоткала его для пропуска.

Что выдаст система?

• 1. Кот 🐱
• 2. Не кот 👦
• 3. Ошибка распознавания
• 4. Тимофей Лапшин, 10-Б класс

Данные о том, выйдет ли человек на пробежку:

№	Дождь?	Температура	Выходной?	Бегал?
1	Нет	Тепло	Да	✅
2	Нет	Тепло	Нет	✅
3	Нет	Холодно	Да	✅
4	Нет	Холодно	Нет	❌
5	Да	Тепло	Да	❌
6	Да	Тепло	Нет	❌
7	Да	Холодно	Да	❌
8	Да	Холодно	Нет	❌

Новый человек — Саша: Дождь=Нет, Температура=Холодно, Выходной=Нет.

Что предскажет дерево с оптимальным корнем?
 

1. Побежит (100% уверенность)
2. Не побежит (100% уверенность)
3. Побежит (но есть неопределённость)
4. Не побежит (но есть неопределённость)

Данные: кто пойдёт на школьную дискотеку?

№	Есть пара?	Друзья идут?	Домашка сделана?	Пошёл?
1	Да	Да	Да	✅
2	Да	Да	Нет	✅
3	Да	Нет	Да	✅
4	Да	Нет	Нет	✅
5	Нет	Да	Да	✅
6	Нет	Да	Нет	✅
7	Нет	Нет	Да	❌
8	Нет	Нет	Нет	❌

Какой признак лучше поставить в корень?

• 1. Есть пара
• 2. Друзья идут
• 3. Домашка сделана
• 4. Все одинаково хороши

В школе Ларево пятничная мафия — священная традиция. Дерево предсказывает участие:

              [Пятница?]
              /        \
            Да          Нет
            /             \
     [Домашки много?]   НЕ ПРИДЁТ
        /        \
      Да         Нет
      /            \
[Мафия или домашка?] ПРИДЁТ
    /        \
 Мафия     Домашка
   /          \
ПРИДЁТ    НЕ ПРИДЁТ

Пять учеников в пятницу:

Ученик	Много домашки?	Выбор
Тимоха	Да	Мафия
Алиса	Нет	—
Данон	Да	Домашка
Вика	Да	Мафия
Костя	Нет	—

Сколько придут на мафию?

• 1. 2
• 2. 3
• 3. 4
• 4. 5

Предсказываем, кто забудет сменку.

Начальная энтропия: 1.0 (половина забывает, половина нет)

Разделяем по признаку «Понедельник»:

• Понедельник (8 человек): энтропия 0.0 (все забыли!)
• Другой день (12 человек): энтропия 0.65

Чему равна информационная выгода?

• 1. 0.21
• 2. 0.39
• 3. 0.61
• 4. 1.0

Голосование за меню школьной столовой:

• 20 человек за пельмени 🥟
• 5 человек за овсянку 🥣

Формула: Gini = 1 − (p₁² + p₂²)

Чему равен Gini?

• 1. 0
• 2. 0.32
• 3. 0.5
• 4. 1

Данные: кто нарисовал усы на портрете Пушкина?

№	Был на перемене в кабинете?	Имеет маркер?	Смеялся громче всех?	Виновен?
1	Да	Да	Да	✅
2	Да	Да	Нет	✅
3	Да	Нет	Да	❌
4	Да	Нет	Нет	❌
5	Нет	Да	Да	❌
6	Нет	Да	Нет	❌
7	Нет	Нет	Да	❌
8	Нет	Нет	Нет	❌

Какой признак лучше всего разделяет виновных?

• 1. Был в кабинете
• 2. Имеет маркер
• 3. Смеялся громче всех
• 4. Нужны все три вместе

(вопрос с подвохом) 

Дерево учителя информатики:

                [Телефон на парте?]
                 /              \
               Да               Нет
               /                  \
      [Вика смотрит в него?]   НЕ КОНФИСКУЮТ
          /           \
        Да            Нет
        /               \
  КОНФИСКУЮТ     [Звук включён?]
                    /        \
                  Да         Нет
                  /            \
            КОНФИСКУЮТ    НЕ КОНФИСКУЮТ

Ситуация: телефон на парте, Вика смотрит в окно, но телефон вдруг играет «Never Gonna Give You Up».

Что случится?

• 1. Не конфискуют — она же не смотрит!
• 2. Конфискуют
• 3. Учитель посмеётся и простит
• 4. Рикролл защитит телефон

В столовой школы Ларево продают пиццу. Очередь:

День 1: Все 30 человек взяли пиццу 🍕🍕🍕

День 2: 15 взяли пиццу, 15 взяли салат 🍕🥗

В какой день энтропия выбора ВЫШЕ?

• 1. День 1 — пиццы больше
• 2. День 2 — выбор разделился
• 3. Одинаково
• 4. Энтропия не работает с пиццей

Дерево решает, будет ли Данон есть на уроке:

           [Прошло больше часа с завтрака?]
                  /                \
                Да                 Нет
                /                    \
        [Учитель строгий?]       НЕ БУДЕТ ЕСТЬ
           /          \
         Да           Нет
         /              \
    БУДЕТ ЕСТЬ      БУДЕТ ЕСТЬ
    (тихо)          (громко хрустя)

Что является ЛИСТОМ дерева?

• 1. «Прошло больше часа с завтрака?»
• 2. «Учитель строгий?»
• 3. «БУДЕТ ЕСТЬ (тихо)»
• 4. «Да» и «Нет»

У вас есть дерево для предсказания, понравится ли фильм:

                [Жанр = Ужасы?]
                /            \
              Да              Нет
              /                \
        НЕ ПОНРАВИТСЯ     [Есть супергерои?]
                            /           \
                          Да            Нет
                          /              \
                   ПОНРАВИТСЯ      [Длительность > 2ч?]
                                      /          \
                                    Да           Нет
                                    /             \
                              НЕ ПОНРАВИТСЯ   ПОНРАВИТСЯ

Маша идёт на фильм: комедия, без супергероев, длится 1.5 часа. Что предскажет дерево?

1. Понравится
2. Не понравится
3. Невозможно определить
4. Нужно больше данных