Привіт всім, багато здало задачу "1247 - Число Pi", думаю всі знають яким саме способом.
Можна було поставити обмеження у 10000 (10к) символів, але від того розв'язки учасників кардинально б не змінились.
Відповідно потрібно було ставити таке обмеження, яке вже б не помістилось, тобто більше ніж ~64000 (64к). Але так виходить, що при таких обмеженням розв'язки, всі відомі мені, працюють занадто довго. Може, якщо хтось запропонує швидкий розв'язок, то я буду радий подивитись на нього.
Але ця задача була дана у навчальних цілях.
Хто має бажання, то може спробувати розв'язати її більш коректно (саме для цього і були вибрані такі смішні обмеження, щоб не потрібно було бавитись із обмеженням на час).
Ех... До мене тільки сьогодні вранці доперло, як то робиться. Спробую написати чесно, коли буде час. А то я сидів і думав "хех... ну і ну... там така непроста писанина, а всі з першого разу здають без проблем... і по часу, і по пам'яті, і по всьому решта".
Цікаво, як її такими "навчальними цілями" на якомусь контесті писати? Витягнути з кишені голку і робити Монте-Карло, чи коло вписувати/описувати? Хіба напам'ять вивчити... Але я знаю тільки перші 25 цифр, а якщо дати обмеження 1000, то це буде довго...
З приводу 64000 знаків - тоді можна ТЛ збільшити. Дати, скажімо, 20 секунд... А для 20 секунд це вже набагато простіше. Якщо є якісь класні алго для пошуку конкретної цифри в записі в системі числення з основою, не кратною 2, то може якось і робиться швидше, але якщо тупо будувати число... На Сфері можна подивитись на топ тої челендж-задачі, найкращий результат це 720000 знаків за 25 секунд.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 15-03-2010 13:22
YaroslavPugach написав:
Я знаходив статті про те як обчислити певну десятичну цифру для числа пі, але не до кінця розібрався (є кілька незрозумілих моментів).
повністю ще не читав статтю але побачив таке:
100,000 - 185.1 sec
є алгоритми, що за такий час дають не тільки одну цифру а всі до даної.
Коли прочитаю, то щось напишу.
Я по принципу не здаю задачу таким нерозумним способом, на реальному контесті немає доступу до інтернету для copy-paste. Тому хочу використати наступний метод: http://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm
але для цього алгоритму потрібно писати довгу арифметику з квадратним коренем.
Birthday(s):
Витягнути з кишені голку і робити Монте-Карло, чи коло вписувати/описувати? 
