Архивы за Январь, 2009

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

3 лет назад

Автор: arti в Lifehack

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

3 лет назад

Автор: arti в Qwit

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

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

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

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

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

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

3 лет назад

Автор: arti в Олимпиады

На прошлой неделе буквально одновременно с 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))
```

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

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

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

3 лет назад

Автор: arti в Алгоритмы

Как-то, ради интереса, я решил поискать в Сети материалы о нахождении всех простых чисел в диапазоне от 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;
}

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

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