Archive

Архів автора

Розв’язання задачі MappingABC з TopCoder

Тут я розгляну розв’язок задачі MappingABC з TopCoder. Це задача з першого дивізіону другого рівня складності, тому вона вимагає певний рівень учасника для розв’язання.

Основне спостереження, яке допомагає в розв’язанні – це те, що для того, щоб порахувати всі прийнятні рядки ми можемо розбити рядок на три підрядки: до першого A – [0, FA], між першим A і останнім C – [FA, LC] і після останнього C – [LC,t.size()-1]. Ми рахуємо лише ті рядки в яких у [FA, LC] трапляється B.

Введемо дві множини для позначення символів які трапляються лише зовні [FA, LC] і інші, відповідно \mathcal O і \mathcal I. Тоді кількість прийнятних рядків така:
\prod_{s\in \mathcal O}\mbox{bitcount}(s) + \Big( \prod_{s\in \mathcal I}\mbox{bitcount}(s) - \prod_{s\in \mathcal I}\mbox{bitcount}(s \& 5) \Big).

Дивись коментарі в сирцевому коді для подальших роз’яснень.
Читати далі…

Категорії:C++, Комбінаторика Позначки:, ,

Градієнт деформації

У результаті деформації у тривимірному випадку куб перетворюється у щось схоже на паралелепіпед. Градієнт деформації це тензор, що вимірює цю зміну форми разом із обертанням матеріалу.

Будь-який куб можна характеризувати за допомогою трьох ортогональних векторів, що утворюють його ребра. Те саме можна сказати про паралелепіпед. Градієнт деформації \mathbf F виражає ці зміни через збирання трьох ребер отриманих в результаті деформації в матрицю. У декартових координатах стовпчики цієї матриці містять вектори деформованих ребер виражені відносно векторів початкових ребер. Під відносними уважається, що всі зміни довжин виражені як множники початкових довжин, а всі напрямки виражені через напрямки початкових ребер. Тобто, визначивши підхожим чином одиницю довжини, ми можемо вважати, що початковий куб – одиничний, чиї ребра вирівняні уздовж осей координат і утворюють базис \mathbf E_1, \mathbf E_2, \mathbf E_3. Після деформації ці ребра трансформуються у \mathbf e_1, \mathbf e_2, \mathbf e_3. Якщо ви знаєте компоненти \mathbf e_k то ви маєте k-й стовпчик \mathbf F у координатах \mathbf E_1, \mathbf E_2, \mathbf E_3. Тобто,

\mathbf e_k = \mathbf F \cdot \mathbf E_k.

Деформовані вектори ребер – \mathbf e_k не обов’язково ортогональні чи одиничні. Їх називають “матеріальними векторами”, тому що вони рухаються разом із матеріалом.
Читати далі…

Категорії:Механіка Позначки:

Різний дріб’язок потрібний у роботі з github

У цьому пості я буду описувати різноманітні проблеми, з якими я неодноразово стикався у декількох своїх репозиторіях на github. Просто для того, щоб не шукати це все знов кожного наступного разу.

Локальне ім’я і поштова адреса

Іноді доводиться працювати з власним/домашнім репозиторієм з робочого компа, тоді варто встановити ім’я і поштову адресу користувача локально в репозиторії. Робиться це так:

git config --local user.email no@no.no
git config --local user.name Harmyder

Символ для коментарів

Іноді закомітивши зміни помічаєш, що забув вказати номер issue до якого цей коміт мав би бути прив’язаним. Оскільки номер десятого issue в повідомленні виглядає так #10, а за промовчанням символ коментаря теє #, то виникає конфліктна ситуація. Отже можна змінити символ для коментаря:

git config --local core.commentchar ";"

Читати далі…

Категорії:Git Позначки:

Розв’язання задачі BearEmptyCoin

Нещодавно спробував одну з задач першого дивізіону на топкодері. Задача виявилось надто складною для того, щоб я її самостійно розв’язав, навіть зрозуміти код, який вільно доступний, я не зміг. Отже, шукав допомоги в інтернеті. На запит “BearEmptyCoin” Google мені видав кілька посилань власне на topcoder.com і посилання на три блоги, китайською, корейською і японською мовами:) За допомогою Google перекладача, який досить невміло перекладає з цих мов, мені вдалось якось докопатись до істини. Тому, зараз я можу поділитись поясненням розв’язку із вами.

Формулювання

Маємо чесну монету, чисту з обох боків. Цією монетою ми гратимемо в гру. На початку рахунок 0, гра триватиме K раундів. Кожен раунд такий:
1. Вкидаємо монету.
2. Якщо верхній бік порожній, то записуємо на нього число, яке забажаємо.
3. Додаємо до рахунку число записане на верхньому боку монетки.
Для перемоги потрібно, щоб кінцевий рахунок був S.

На вході ми маємо K, S. Нехай P – ймовірність виграшу у разі слідування найоптимальнішій стратегії. Можна показати, що P помножена на 2^K є цілим числом. Повернути це число.
Читати далі…

Відмінності між одинарними ([ ]) і подвійними ([[ ]]) скобами у bash

[ і [[ використовуються для обчислення виразів. [[ працює лише в Bash, Zsh і Korn оболонках, і вона більш потужна; [ доступна в усіх POSIX оболонках.

Одинарна скоба [ насправді це те саме, що команда test, тобто це не синтаксис.

Подвійні скоби [[ ]] – це синтаксис. Вони дозволяють C-подібний синтаксис із >, <, >=, <=, !=, ==, &&, || операторами.

Усередині одинарних скоб, вам потрібно використовувати подвійні лапки навколо змінних, як і в більшості інших місць, оскільки це запобігає тлумаченню всіх спеціальних символів усередині рядка в лапках окрім $, `, \. Усередині подвійних скоб, вам не потрібні подвійні лапки, оскільки оболонка не виконує розбиття на слова чи глобування (globbing): вона розбирає умовний вираз, а не команду.

Хоча є виняток – [[ $var1 == "$var2" ]] де необхідно використати лапки, якщо ви бажаєте виконати побайтове порівняння рядків, інакше, $var2 був би шаблоном для порівняння з $var1.

Читати далі…

Категорії:Uncategorized Позначки:

Як створити документ з україномовним індексом на LaTeX

Сирцевий tex-файл:

\documentclass{book}
\usepackage[T1, T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english, ukrainian]{babel}
\usepackage[xindy]{imakeidx}
\makeindex[program=truexindy]

\makeatletter
\newcommand{\ukindex}[2][\imki@jobname]{%
  \index[#1]{\detokenize{#2}}%
}
\makeatother

\begin{document}

\chapter{Оптимізація}

\ukindex{notepad}
\ukindex{apple}
\ukindex{лінійне програмування|(}
\ukindex{симплекс-метод}
\ukindex{метод еліпсоїдів}
\pagebreak
\ukindex{метод внутрішньої точки}
\ukindex{лінійне програмування|)}

Якийсь текст. 
\printindex

\end{document}

Читати далі…

Категорії:LaTeX Позначки:

Встановлюємо Apache, PHP та MySQL на Windows 8

Apache

Apache не надає двійкові файли для Windows, однак з їхньої сторінку є посилання на декілька інших сайтів які надають вже готові двійкові файли, наприклад Apache Lounge.

Обирайте ту версію, бітність якої збігається з бітністю вашої Windows.

Після завантаження, просто розпакуйте теку Apache24 в корінь вашого диску, так щоб у вас був шлях на кшталт C:\Apache24\bin.

Відчиніть вікно командного рядку (Windows+R і наберіть cmd, потім Enter), змініть теку на C:\Apache24\bin і запустіть httpd.exe, зазвичай ви не повинні отримати ніяких помилок.

Якщо ж ви побачили щось подібне на (номер порту може бути іншим)

(OS 10048)Only one usage of each socket address (protocol/network address/port) is normally permitted. : make_sock: could not bind to address 0.0.0.0:80 no listening sockets available, shutting down Unable to open logs

тоді вам треба з’ясувати хто саме використовує цей порт і вбити той процес за допомогою Task Manager. Допоможе виявити “злодія” приладдя netstat -ano, щоб було швидше можна так netstat -ano | findstr 0.0:80.
Читати далі…

Категорії:Адміністрування Позначки:, ,