2011 или все-таки 2010?

0

Наткнувшись на эту запись: Осторожно: Ваш iPhone тоже празднует, довольно ухмыльнулся, как счастливый пользователь Android. Но не тут-то было – как оказалось, не только продукция Apple обладает таким интересным свойством. К счастью, Android не был подвержен этой «фиче» (или я этого не заметил), однако, например, невнимательное использование Zend_Date вело к тому, что 1 и 2 января 2011 года отображались как 1 и 2 января 2010. Все дело в использовании конструкции типа $date->toString(‘YYYY…’), что кажется вполне безопасным. Однако из документации можно узнать, что заглавная Y означает номер года в стандарте ISO, который, в свою очередь, начинается с недели, в которую попадает первый четверг нового года по григорианскому календарю. Первый четверг 2011 года это 6 января, значит по ISO новый год начинется 3-го января, а 1 и 2-е относятся к 2010.

Разбор задач 3-го этапа Республиканской олимпиады школьников

4

Олимпиада прошла давно, но немного времени для разбора нашлось только сейчас. Архив олимпиады (задачи, тесты и решения) можно найти где обычно.

Задача А. Мухи

Задача является вариацией довольно известной математической задачи. Главное – понять, что каждая муха всегда будет двигаться строго к соседке. В этом случае скорости мух всегда будут направлены друг к другу под одним углом, а рассматривая движение с точки зрения какой-то из мух, можно заметить, что на расстояние между ней и соседкой влияет ее скорость и проекция скорости соседки на прямую, содержащую скорость этой мухи. В результате получим, что время, через которое мухи встретятся равно T = D / (V + V cos(? – 2 ? / N)). Ну а расстояние, которое пройдет каждая из мух, легко вычисляется по магической формуле: S = VT = D / (1 + cos(? – 2 ? / N)).

Задача B. Числа

Из-за небольших ограничений задачу можно было решать множеством разных способов. Один из них – воспользоваться довольно стандартным приемом в таких задачах. Сначала немного преобразуем задачу: посчитаем, сколько раз будет выписана каждая цифра от 1 до 9, а затем посчитаем сумму. Заметим, что F(A, B, Y) = F(1, B, Y) – F(1, A – 1, Y), где A, B – границы интервала, а Y – цифра, количество которой считается. Теперь научимся считать F(1, X, Y). Для этого сначала предподсчитаем D[N] = F(1, 10^N – 1, 1). Это несложно делается по рекуррентному соотношению D[N] = D[N - 1] * 10 + 10 ^ (N – 1). Далее нужно разложить X на цифры и считать количество чисел с заданным префиксом, который нужно перебирать. Здесь проще привести код:

i64 count(i64 x, int y) {
	i64 result = 0;
	int a[20];
	int n = 0;
	if (x == 0) return 0;
	do {
		a[n++] = x % 10;
		x /= 10;
	} while (x > 0);
	int t = 0;
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < a[i]; ++j) {
			if (j == y) {
				++t;
			}
			result += D[i] + t * B[i];
			if (j == y) {
				--t;
			}
		}
		if (a[i] == y) {
			++t;
		}
	}
	result += t;
	return result;
}

(далее…)

Qwit 0.8 – it's finally here!

QwitСегодня собрал и залил очередную версию Qwit. Этот релиз – первый, с тех пор как у проекта появилась команда: в течение последнего месяца мне предложили помощь несколько человек. Главная особенность релиза – наконец-то появились Direct Messages и поиск, спасибо Валентину. Также имеется конфигурируемый ReTweet, за что спасибо kiracatgirl. Ну и перевод на турецкий язык от U?ur ?etin. А также несколько бакфиксов и возможность использовать twitter-compatible сервисы (типа identi.ca) от меня.

Скачать собранные пакеты для Linux и Windows можно как всегда на http://code.google.com/p/qwit/.

Автоматическое переключение прокси

4

OperaВ прошлый раз я писал о том, как можно настроить прокси сразу во всех браузерах. Там была такая фраза: «Процедура смены прокси: приходим домой – раскоментируем первую строку, на работу – комментируем. Да и скриптик для это несложно написать.» Ну вот собственно я и написал:

#!/bin/bash
 
if /sbin/iwconfig 2>/dev/null | grep "wlan0.*home"
then
cp /home/arti/proxy.pac.home /home/arti/proxy.pac
elif /sbin/iwconfig 2>/dev/null | grep "wlan0.*work"
then
cp /home/arti/proxy.pac.work /home/arti/proxy.pac
else
cp /home/arti/proxy.pac.home /home/arti/proxy.pac
fi

home – название сети дома, work – на работе.

Ну а для полного счастья вызов скрипта добавляется в cron с периодичностью в 1 минуту:

* * * * * /home/arti/bin/setupProxy.sh

Настройка прокси во всех браузерах одновременно

6

InternetМне по долгу службы часто приходится менять настройки прокси на своем ноутбуке: дома прокси нет, на работе один прокси, в универе – другой. Ну а то, что я пользуюсь несколькими браузерами, и централизованное место установки прокси в KDE у них не уважается только усугубляет положение. Постоянно залазить в одни и те же настройки, менять исключения и т.п. – надоедает довольно быстро. Решил я от этого избавиться и нашел довольно симпатичный способ – может кому-то тоже пригодится.

Наверное многие замечали в настройках прокси почти любой программы поле «Автоматическая конфигурация прокси» куда просили ввести адрес скрипта конфигурации. Как оказалось, этот скрипт – PAC-файл (proxy auto-config) просто функция на JavaScript, что позволяет довольно просто и удобно вводить гибкие правила и исключения для прокси.

Вот пример простой настройки:

function FindProxyForURL(url, host) {
// Эта строка для домашнего интернета
//	return "DIRECT";
 
// Все остальное для рабочего
// Local
	if (shExpMatch(url,"*://localhost/*") || shExpMatch(url,"*.localhost/*") || shExpMatch(url,"*.lo/*")) {
		return "DIRECT";
	}
// Work
	if (shExpMatch(url,"*://work.kz/*")) {
		return "DIRECT";
	}
	return "PROXY 12.34.56.78:9000";
}

Скрипт помещается в любое место и в поле «Автоматическая конфигурация прокси» во всех программах вводится полный путь к нему. Например, /home/arti/proxy.pac.

Процедура смены прокси: приходим домой – раскоментируем первую строку, на работу – комментируем. Да и скриптик для это несложно написать. Точно работает в Linux и должно работать в Windows.

(далее…)

Qwit 0.7

0

А тем временем разработка клинта для твиттера Qwit понемногу продвигается. К Новому году я собрал все что было в SVN в очередную версию.

Основные изменения:

  • кэширование сообщений – теперь при очередном запуске Qwit старые сообщения берутся с диска;
  • пересмотрена структура диалога настроек – используются табы;
  • ну и как всегда пофиксены маленькие баги.

Скачать архив с исходными текстами или бинарную версию можно с со страницы на Google Code или на KDE-Apps.

Ну а в SVN уже есть 2 перевода: на турецкий и русский языки.
(далее…)

Разбор задач 2-го этапа Республиканской олимпиады школьников

12

На прошлой неделе буквально одновременно с V Международной Жаутыковской олимпиадой прошел 2-й этап Республиканской олимпиады школьников, для Алматы являющийся районным. Задачи были довольно несложные, но для полного решения требовалась некоторая сообразительность. Условия задач, тесты к ним и решения как всегда можно найти в правильном месте.

Задача A. Окружность

Во-первых, будем считать, что A1 < B1 и A2 < B2 (если это не так, то добьемся этого поменяв числа в соответствующей паре местами). Далее, нарисовав один-два случая можно заметить, что хорды будут пересекаться или касаться только в трех случаях:

  • они совпадают, то есть обе вершины общие:
    ((A1 == A2) && (B1 == B2))
  • одна вершина общая:
    ((A1 == A2) || (A1 == B2) || (A2 == B1) || (A2 == B2))
  • вершины разные, и для каждой хорды выполняется следующее условие: если окружность разрезать по этой хорде, то вершины другой хорды должны быть в разных частях окружности:
    ((A1 < A2) && (A2 < B1) != (A1 < B2) && (B2 < B1))

Все решение заключается в проверке этих трех условий.

Читать разбор остальных задач

Об одном алгоритме поиска простых чисел

4

ЭратосфенКак-то, ради интереса, я решил поискать в Сети материалы о нахождении всех простых чисел в диапазоне от 1 до N за линейное время. Нашлись некоторые статьи на английском, но описанные алгоритмы были несколько сложны для реализации. К сожалению, поиски на русском не увенчались успехом – были какие-то оптимизации, пытающиеся уменьшить объем памяти, константу в оценке времени, но ничего за O(N), так что я решил восполнить данный пробел.

Определение проблемы

Для начала, вспомним, что существует так называемое решето Эратосфена, позволяющее решать нашу задачу за O(N ln ln N):

bool notPrime[MAXN + 1];
int primes[MAXN];
 
int sieve(int n) {
	int primesCount = 0;
	int sqrt_n = (int)sqrt((double)n);
	for (int i = 2; i < = n; ++i) {
		if (!notPrime[i]) {
			primes[primesCount++] = i;
			if (i <= sqrt_n) {
				for (int j = i * i; j <= n; j += i) {
					notPrime[j] = true;
				}
			}
		}
	}
	return primesCount;
}

Почему решето работает не за линейное время? Потому что одно число в нем может вычеркиваться несколько раз (во внутреннем цикле) . Если добиться, чтобы каждое число вычеркивалось не более одного раза, то, очевидно, алгоритм будет линейным.

Далее – описание линейного алгоритма

Screencast: TopCoder SRM 430

7

Очередной screencast – TopCoder Single Round Match 430. Не очень удачный, но демонстрирует терпение и настойчивость :)

Залито на RuTube по причине временного запрета загрузки на Kiwi.

Музыка для фона отсюда: http://www.penmachine.com/podcast/.

(далее…)

Chroot как средство усмирения пингвинов

2

Дерущиеся пингвиныМногие пользователи GNU/Linux любят устраивать holywars по поводу, какой же дистрибутив лучше: приходя в новый коллектив пытаются поставить на сервер их «единственный верный» Gentoo/Debian/Slackware вместо «убогих» RedHat/Ubuntu, им начинают противостоять злые админы и просто иноверцы и так далее. Описанный далее прием позволяет без особого ущерба нервной системе обеим сторонам работать в своем любимом окружении на одной и той же машине одновременно.

Те, кто имел опыт работы в Gentoo, знают, насколько продумана и удобна здесь система установки пакетов из исходных кодов: автоматическое установка зависимостей, управление параметрами компиляции и т.д. Но, к сожалению, не всегда на рабочем сервере удается поставить ту систему, которую мы хотим, и приходится работать с тем, что есть. Так было и в этот раз…

Сначала опишу типичный процесс компиляции на системах отличных от Gentoo, а потом расскажу, как все замечательно в ней, и как добиться этого же где угодно. Показывать буду на примере одного пакета и одной системы, но большая часть сказанного относится и к любым другим конфигурациям. В качестве систем используются: «убогий» RedHat-like дистрибутив и «единственно верная» Gentoo.

(далее…)

Вверх