381 Відповідь від ur_naz

  • ur_naz
  • ur_naz
  • Користувач
  • Поза форумом
  • Дата реєстрації: 19.06.2016
  • Повідомлень: 1 755
    • Репутація: 496

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

неаргументовано.  :-X є як мінімум 1 рішення, яке не програє ані по часу, ані по пам'яті. до того ж коротше

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

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

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

Реально? Без уточнення формату, в якому задаються числа, і спроможностей обчислювальної системи? В будь-якому разі виграє, навіть якщо числа представлені десятковими рядками?

koala вебсайт

383 Відповідь від ur_naz

  • ur_naz
  • ur_naz
  • Користувач
  • Поза форумом
  • Дата реєстрації: 19.06.2016
  • Повідомлень: 1 755
    • Репутація: 496

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

справа не в форматі

384 Відповідь від leofun01

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

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

Якщо (&) :

  • процесор не вміє ділити числа

  • число ціле (зі знаком або без) і вміщається в 32 біти

  • треба число ділити на 100

то операцію діленя можна замінити на множеня+зміщеня :

int div_by_100(int value) {
    return (int)(((uint64_t)value * 0x028F5C29) >> 32);
}

Чому ?:

     1 / 100 == 42949673 / (2^32 + 4)
(2^32) / 100 ~= 42949673
              = 0x028F5C29 (hex)
Подякували: koala, P.Y.2

leofun01 вебсайт

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

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

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

Підніму тему.

Цікава задача на CodeWars. Щоб побачити повністю, треба там реєструватися, тому ось умова: є система кодування чисел, що використовує десяткові цифри 0-9, але якось не так, як ми звикли.

▼Приклади

    #       number   expected
    ('Small numbers', [
        (      '0',      0),
        (      '1',      1),
        (      '3',      3),
        (      '7',     15),
        (     '10',      2),
        (     '12',      4),
        (     '16',     16),
        (     '30',      6),
        (    '101',      5),
        (    '103',     11),
        (    '121',      9),
    ]),
    ('Somewhat familiar numbers', [
        (   '1010',     10),
        (  '10101',     21),
        ( '101010',     42),
        ('1010101',     85),
    ]),
    ('Large numbers', [
        (   '9876', 254192),
        (  '12345',   1223),
        (  '39908', 262080),
    ]),
    ('Curious numbers', [
        (    '128',    128),
        (   '3087',   3087),
    ]),
]

Задача - написати декодер, що перетворює число у загадковому форматі (в прикладах - у лапках) на звичайне число (після нього через кому). В принципі, там є ГПВЧ у тестах, тому можна ще кілька прикладів чисел глянути, але цих має бути достатньо.

▼Ще один приклад

Ну добре, мене осяяло після ('38', 96)

Подякували: P.Y., leofun012

koala вебсайт

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

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

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

Підказка: запишіть декодовані числа в двійковій системі.

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

koala вебсайт

387 Відповідь від leofun01

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

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

koala написав:

Цікава задача на CodeWars.

На задачі менші ніж "1 kyu" тепер навіть не дивлю. Ото вибрав собі задачу про regex'и, і тепер коли появляється вільна година, то роблю крок вперед на шляху до її розвязку, про це буде окремий topic, але не скоро, бо вільна година - не часте явище.

leofun01 вебсайт

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

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

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

leofun01 написав:
koala написав:

Цікава задача на CodeWars.

На задачі менші ніж "1 kyu" тепер навіть не дивлю. Ото вибрав собі задачу про regex'и, і тепер коли появляється вільна година, то роблю крок вперед на шляху до її розвязку, про це буде окремий topic, але не скоро, бо вільна година - не часте явище.

Ну я навпаки, як кажуть ДнДшники, "стільки білочок нарубав, що читати навчився".

koala вебсайт

389 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 609
    • Репутація: 4961

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

leofun01 написав:

Ото вибрав собі задачу про regex'и, і тепер коли появляється вільна година, то роблю крок вперед на шляху до її розвязку, про це буде окремий topic, але не скоро, бо вільна година - не часте явище.

Там, де перевірка подільності двійкового числа на 5? Приблизно уявляю, як це зробити на sed серією замін (з циклічним повторенням), але задача вимагає ввіпхнути всю логіку в єдиний регекс?..

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