361 Відповідь від bebyk

  • bebyk
  • bebyk
  • не сере, а SRE
  • Поза форумом
  • Дата реєстрації: 29.10.2018
  • Повідомлень: 1 460
    • Репутація: 918

Re: Цікаві задачі

Довго промучився, пробуючи рекурсію як за каноном у Scala, проте на «складних програмах» воно сипалося. І ніяк не придумав, де втулити хвостову рекурсію з теґом @tailrec.

▼Прихований текст
object SimpleAssembler {
  def interpret(program: List[String]): Map[String, Int] = {
    val result = new HashMap[String, Int]

    def loop(list: List[String]): Unit = breakable {
      for (command <- list) {
        val args = command.split(' ')
        args(0) match {
          case "mov" => 
            result.put(args(1), result.get(args(2)).getOrElse(args(2).toInt))
          case "inc" => 
            result.put(args(1), result.get(args(1)).get + 1)
          case "dec" => 
            result.put(args(1), result.get(args(1)).get - 1)
          case "jnz" =>
            val switcher = 
                result.get(args(2)).getOrElse(args(2).toInt)
            if (result.get(args(1)).getOrElse(args(1).toInt) != 0) {
              val startPosition = program.indexOf(command) + switcher
              loop(program.slice(startPosition, program.length))
              break()
            }
        }
      }
    }
    loop(program)
    result.toMap
  }
}

Зрештою закинув до готових цей процедурний стандарт як у koala:

▼Прихований текст
object SimpleAssembler {
  def interpret(program: List[String]): Map[String, Int] = {
    val result = new HashMap[String, Int]
    var iter = 0
    

    while (iter < program.length) {
      breakable {
        val args = program(iter).split(' ')
        args(0) match {
          case "mov" => 
            result.put(args(1), result.get(args(2)).getOrElse(args(2).toInt))
          case "inc" => 
            result.put(args(1), result.get(args(1)).get + 1)
          case "dec" => 
            result.put(args(1), result.get(args(1)).get - 1)
          case "jnz" =>
            val switcher = 
                result.get(args(2)).getOrElse(args(2).toInt)
            if (result.get(args(1)).getOrElse(args(1).toInt) != 0) {
              iter = iter + switcher
              break()
            }
        }
        iter = iter + 1
      }
    }
    result.toMap
  }
}

Відтак мені відкрилися рішення інших людей, котрі знають Скалу і ФП ліпше за мене і хвостову ресурсію звісно ж реалізували — є чого повчитися.

bebyk вебсайт

362 Відповідь від bebyk

  • bebyk
  • bebyk
  • не сере, а SRE
  • Поза форумом
  • Дата реєстрації: 29.10.2018
  • Повідомлень: 1 460
    • Репутація: 918

Re: Цікаві задачі

Що ж, рекурсію мені таки втулити вдалося, навіть @tailrec не знадобився.

▼Прихований текст
object SimpleAssembler {
  def interpret(program: List[String]): Map[String, Int] = {
    val getNumericValue = (
      hashMap: HashMap[String, Int], 
      value: String
    ) => 
      hashMap.get(value).getOrElse(value.toInt)
    
    def loop(list: List[String], currentIndex: Int, result: HashMap[String, Int]): Map[String, Int] = {
      if (currentIndex >= list.length) result.toMap
      else {
        val args = list(currentIndex).split(' ')
        val switcher: Int = args(0) match {
          case "mov" =>
            result.put(args(1), getNumericValue(result, args(2)))
            1
          case "inc" =>
            result.put(args(1), result.get(args(1)).get + 1)
            1
          case "dec" =>
            result.put(args(1), result.get(args(1)).get - 1)
            1
          case "jnz" =>
            if (getNumericValue(result, args(1)) != 0) {
              getNumericValue(result, args(2))
            } else {
              1
            }
        }
        loop(program, currentIndex + switcher, result)
      }
    }
    loop(program, 0, new HashMap[String, Int])
  }
}

bebyk вебсайт

363 Відповідь від bebyk

  • bebyk
  • bebyk
  • не сере, а SRE
  • Поза форумом
  • Дата реєстрації: 29.10.2018
  • Повідомлень: 1 460
    • Репутація: 918

Re: Цікаві задачі

Ок, можна ще так, щоб зовсім без зайвини. І на цьому мої ідеї сьодні вичерпались.

▼Прихований текст
object SimpleAssembler {
  def interpret(program: List[String], 
                currentIndex: Int = 0, 
                result: HashMap[String, Int] = new HashMap[String, Int]
                ): Map[String, Int] = {
    if (currentIndex >= program.length) result.toMap
    else {
      lazy val getNumericValue = (
        hashMap: HashMap[String, Int], 
        value: String
      ) => 
        hashMap.get(value).getOrElse(value.toInt)
      val args = program(currentIndex).split(' ')
      val switcher: Int = args(0) match {
        case "mov" =>
          result.put(args(1), getNumericValue(result, args(2)))
          1
        case "inc" =>
          result.put(args(1), result.get(args(1)).get + 1)
          1
        case "dec" =>
          result.put(args(1), result.get(args(1)).get - 1)
          1
        case "jnz" =>
          if (getNumericValue(result, args(1)) != 0) {
            getNumericValue(result, args(2))
          } else {
            1
          }
      }
      interpret(program, currentIndex + switcher, result)
    }
  }
}
Подякували: koala1

bebyk вебсайт

364 Відповідь від leofun01 Востаннє редагувалося leofun01 (19.02.2023 23:58:07)

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 2 461
    • Репутація: 2350

Re: Цікаві задачі

Завершилося змаганя в Алґотестер, а я все ще не маю рішеня, яке би проходило всі тести для задачі E (pdf).

Дано: n, a[k] (k=1..n)
, де a[k] - кількість інверсій префікса довжиною k.
Знайти: p[k] - перестановку, для якої всі префікси мають задану кількість інверсій (a[k]).

▼Приклад даних
stdin написав:

5
0 1 2 4 7

stdout написав:

5 1 4 3 2

Всі мої ідеї виявились до сраки. Може ви знаєте як рішати подібні задачі ?

leofun01 вебсайт

365 Відповідь від lucas-kane

  • lucas-kane
  • Користувач
  • Поза форумом
  • Дата реєстрації: 13.01.2021
  • Повідомлень: 215
    • Репутація: 126

Re: Цікаві задачі

leofun01 написав:
▼Прихований текст

Завершилося змаганя в Алґотестер, а я все ще не маю рішеня, яке би проходило всі тести для задачі E (pdf).

Дано: n, a[k] (k=1..n)
, де a[k] - кількість інверсій префікса довжиною k.
Знайти: p[k] - перестановку, для якої всі префікси мають задану кількість інверсій (a[k]).

▼Приклад даних
stdin написав:

5
0 1 2 4 7

stdout написав:

5 1 4 3 2

Всі мої ідеї виявились до сраки. Може ви знаєте як рішати подібні задачі ?

Цей алгоритм?

Подякували: leofun011

366 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 14 738
    • Репутація: 12514

Re: Цікаві задачі

lucas-kane, узагалі не те

Ніби все нескладно, але у мене температура під 38, можу сильно переплутати.

Ідемо з кінця. Знаходимо різницю між a[k] і a[k-1] - це кількість інверсій для числа p[k], тобто кількість чисел, більших за p[k], що йдуть перед ним. Оскільки в кінці вже кілька чисел зайнято, то треба перевірити, які з них більші і відповідно зменшити значення. Таким чином визначаємо p[k] і переходимо на наступний крок. Загальна складність - O(n^2).

Подякували: leofun011

koala вебсайт

367 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 14 738
    • Репутація: 12514

Re: Цікаві задачі

Ні, щось не працює

koala вебсайт

368 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 14 738
    • Репутація: 12514

Re: Цікаві задачі

Спитав CharGPT

Одним з можливих алгоритмів для відновлення перестановки з масиву кількості інверсій на префіксі можна використати алгоритм "merge sort", який за O(n log n) відсортує вхідний масив і одночасно підрахує кількість інверсій у ньому.

Оскільки ми знаємо кількість інверсій на префіксі кожної довжини, то ми можемо побудувати масив пар (індекс, кількість інверсій) для кожного елемента вхідного масиву. Після того, як ми відсортуємо цей масив, ми можемо відновити вихідну перестановку, пройшовши по відсортованому масиву і додаючи до вихідного масиву індекси у порядку зростання кількості інверсій.

Отже, код може виглядати наступним чином:

n = int(input())
a = list(map(int, input().split()))

# Побудова масиву пар (індекс, кількість інверсій)
pairs = [(i, a[i-1]) for i in range(1, n+1)]

# Сортування масиву пар за зростанням кількості інверсій
sorted_pairs = sorted(pairs, key=lambda x: x[1])

# Відновлення вихідної перестановки
p = [0] * n
current_index = 1
for pair in sorted_pairs:
    p[pair[0]-1] = current_index
    current_index += 1

# Виведення відповіді
print(' '.join(map(str, p)))
Подякували: leofun011

koala вебсайт

369 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 14 738
    • Репутація: 12514

Re: Цікаві задачі

https://www.reddit.com/r/learnpython/co … utput_for/

Людина випадково(?) виявила, що 10001^10110 = 111 (побітове виключне АБО дає правильну відповідь для десяткових чисел, неправильно сприйнятих як двійкові).
Які ще є такі збіги?

Подякували: Firefox is dead, leofun012

koala вебсайт

370 Відповідь від Firefox is dead Востаннє редагувалося Firefox is dead (28.02.2023 20:28:12)

  • Дата реєстрації: 11.01.2023
  • Повідомлень: 191
    • Репутація: 83

Re: Цікаві задачі

koala написав:

https://www.reddit.com/r/learnpython/co … utput_for/

Людина випадково(?) виявила, що 10001^10110 = 111 (побітове виключне АБО дає правильну відповідь для десяткових чисел, неправильно сприйнятих як двійкові).
Які ще є такі збіги?

якщо я правильно зрозумів,
далеко йти не треба

>>> 10^1 (2 та 1)
11 (3)

>>> 111^101 (7 та 5)
10 (2)

Подякували: leofun011

371 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 14 738
    • Репутація: 12514

Re: Цікаві задачі

до 8-значних таких пар 1356. Аж по 11111110^11111111 = 1.

Подякували: leofun011

koala вебсайт