2

Есть вот такая задача:

Утром все двери в школе закрыты. Школа довольно большая: n дверей. Затем начинают приходить ученики. Кроме того, в этой школе учится ровно n детей, и они приходят один за другим. Когда эти странные дети проходят мимо некоторых дверей, они меняют свой статус (т.е. Открыто -> Закрыто, Закрыто -> Открыто). У каждого ученика есть свой номер, и каждый i-й студент изменяет статус каждой i-й двери. Например: когда первый ребенок приходит в школу, он меняет каждую первую дверь (он открывает их все). Второй меняет статус каждой второй двери (закрывает некоторые двери: 2-ю, 4-ю и так далее). Наконец, когда последний – n-й – приходит в школу, он меняет статус каждой n-й двери (правда, такая дверь всего одна). Вам нужно посчитать, сколько дверей осталось открытым после того, как все ученики пришли.

В общем я задачу решил, но при n более 1000 все падает, подскажите как я могу оптимизировать код, ну или подскажите другой способ решения. Заранее спасибо!

Вот мой код:

function doors(n){
  let obj = {};
  let s = 0;
  for (let i = 1; i <= n; i++) {
    obj[i] = 'close'
  }
  for (let j = 1; j <= n; j++) {
    for (let key in obj) {
      if (key % j == 0) {
        if (obj[key] == 'close') {
          obj[key] = 'open'
        } else {
          obj[key] = 'close'
        }
      }
    }
  }
  for (let key in obj) {
    if (obj[key] == 'open') {
      s += 1;
    }
  }
  return s;
}
2
  • Приведите пример правильно выполненной функции. Какие данные приходят, и какой результат возвращает функция
    – HaZcker
    23 мар 2022 в 17:04
  • Как пример на входе: doors(5). На выходе: s == 2. 24 мар 2022 в 4:16

1 ответ 1

3

Да, нужно использовать другой подход. Посмотрите, сколько раз меняется состояние k-й двери? Оно меняется f раз, где f - число делителей числа k.
Если число делителей чётно, то дверь останется в закрытом состоянии, а если нечётно - то будет открыта.

Известно, что число делителей нечётно у точных квадратов (у других чисел делители всегда идут парами).

Так что остаётся только найти число точных квадратов 1,4,9,16... в диапазоне 1..n (это можно сделать без цикла с помощью sqrt)

6
  • Сами придумали решение или это задача, которую вы решали ранее? 23 мар 2022 в 17:09
  • @Andrei Khotko Про чётность количества множителей - уже встречал, это нередко бывает нужно в задачах, напоминающих олимпиадные
    – MBo
    23 мар 2022 в 17:12
  • Кстати, саму задачу, наверное, тоже когда-то видел, только с лампочками, а не с дверями.
    – MBo
    23 мар 2022 в 17:15
  • @MBo, с дверями тоже была, только более математическая. А как можно найти количество квадратов в диапазоне без цикла? Разве целая часть квадратного корня показывает это количество?
    – Grundy
    23 мар 2022 в 22:13
  • @Grundy Разве целая часть квадратного корня показывает это количество? Да, именно так
    – MBo
    24 мар 2022 в 2:41

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.