Архив

Архив раздела ‘Программирование’

17 января 2005 2 комментария

Убил пол часа на олимпиаду и готово =)

Congratulations on qualifying for the SILVER division of the USA
Computing Olympiad. Your competition record is marked as ‘SILVER
Qualifier’ and will continue to stay that way until your performance
improves or falls dramatically.

If you receive this invitation during a contest, your timer has
been reset and you can enter the SILVER division. Note, however,
that your BRONZE results will not be shown on the final contest
scoring if you submit a SILVER division task.

BrainFuck (Мозгоебка)

23 ноября 2004 14 комментариев

Сегодня написал свою первую рабочую программу на этом языке. Кто догадается что она делает может взять с полки пирожок. =)

>,————————————————
>,————————————————
>,————————————————
+
[>+>+<<-]>>[<<+>>-]<<
>
[-[-[-[-[-[-[-[-[-[<[-]<+>>-]]]]]]]]]]
<<
[>>+>+<<<-]>>>[<<<+>>>-]<<<
>>
[-[-[-[-[-[-[-[-[-[<<[-]<+>>>-]]]]]]]]]]
<<<
[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<<<
>>>
[-[-[-[-[-[-[-[-[-[<<<[-]<+>>>>-]]]]]]]]]]
<<<
++++++++++++++++++++++++++++++++++++++++++++++++.
>
++++++++++++++++++++++++++++++++++++++++++++++++.
>
++++++++++++++++++++++++++++++++++++++++++++++++.

Ещё алгоритмическая хрень

10 ноября 2004 2 комментария

Сегодня было выяснено:

1) Не делайте так: scanf(«%d», &t);
Вот так быстрее scanf(«%s», tmp); t = atoi(tmp);

2) Не делайте так:
for (i = 0; i < 10; i++)
scanf(«%s», tmp[i]);

Вот так быстрее:
scanf(«%s %s %s %s %s %s %s %s %s %s», tmp ….);

3) Если известно что число положительное и меньше 11 знаков (то бишь 10^9) то atoi(tmp) медленнее чем
int atoi2(const char *t)
{
int sum = 0;
int i = 0;
for (; i < 11; i++)
{
sum += (t[i]-‘0’);
if (t[i+1] == 0)
break;
sum = sum + sum + (sum << 3);
}
return sum;
}

А вообще вот задача: http://spoj.sphere.pl/problems/INTEST/
Мы там с Максом пока на первых местах, если решать в лоб без оптимизации приведенной выше то получается около 8 секунд. Удалось улучшить почти в 2 раза! Если есть ещё идеи то в комменты. =)

Всякая алгоритмическая хрень

9 ноября 2004 4 комментария

Сегодня большая часть дня была посвящена изучению свойств умножения.
Было выяснено следующее, существует 3 наиболее распрастраненных алгоритма:

1) Стандартное школьное умножение (O(N^2))
2) Aлгоритм Каратсубы базирующийся на рекурсии (O(N^1.585))
3) Быстрый Алгоритм Фурье (Fast Fourie Transform) (O(N*log(N)))

Чем больше числа, тем более эффективнее нижние алгоритмы. Реализовал второй, но все равно задачка не решается. =) Тратится 15 секунд, а нужно за 3 … В данный момент въезжаю в третий алгоритм.

7 октября 2004 Нет комментариев

Ура! Я сделал это! 300 решенных задач на acm.uva:
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:46169
15 место по России
372 по Миру

Поиски открытых программерских олимпиад в Москве результатов не принесли. Только для школьников и студентов …

22 сентября 2004 2 комментария

Вот задачка из серии легко сформулировать, но не совсем понятно как решать:

Дан треугольник (задан своими сторонами a, b , c). Надо найти площадь максимального квадрата который в него поместится целиком.

Можно формулу, можно алгоритм….

21 сентября 2004 3 комментария

Только что закончилос on-line программерское соревнование. Решил 2 задачи из 9 что вообщем не плохо. Я где то на 70-м месте из 500…. Первые места заняли сборные команды.
Третью задачу решал почти 2 часа и придумал как мне казалось иделаьный бстрый алгоритм, но ни хрена … не укладываюсь в отведенные 2 секунды.
Так и не решенная задача

Задача 4

13 сентября 2004 2 комментария

Специально для
Дан набор валют и их курсы по отношению друг к другу, необходимо выделить последовательность обменов валют друг на друга которая даст в итоге прибыль.
Например 1 доллар может купить 0.7 Британских Фунтов 1 Фунт может купить 9.5 французских франков и 1 Франк покупает 0.16 долларов США, тогда:
1×0.7×9.5×0.16 = 1.064 долларов, что дает 6,4 процента прибыли.

Формат входных данных: Дано число n — размер таблицы 2 <= n <= 20. Первая строка представляет собой курсы обмена валют между первой и n-1 другими странами.

Формат выходных данных:
Для каждой таблицы необходимо определить последовательность обменов которая дает в результате более чем 0.01 процент прибыли. Если таких последовательностей несколько то необходимо напечатать последовательность МИНИМАЛЬНОЙ ДЛИНЫ. Если последовательность не существует то необходимо напечатать: «no arbitrage sequence exists»

Задача 3

8 сентября 2004 3 комментария

(Разминочная)
Любое число можно разложить на простые множители. Например:
105 = 7*5*3

Задача заключается в подсчете числа различных простых множителей данного числа (от 2 до 1000000).
Например для 105 оно равно 3
Для 8 оно равно 1! т.к. 8 = 2*2*2

Написать функцию которая возвращает число различных множителей для заданного числа.
int myFunc(int N)

Задача 2

8 сентября 2004 10 комментариев

Дана строка сотоящая только из: () []

Строка считается корректной если:
а) если это пустая строка
б) если A и B корректны то и AB корректна
в) если A корректна то (A) и [A] корректны

Максимальная длина строки 128 символов.

Написать функцию которая принимает строку:
int myFunc(char *s);
и возвращает 1 если строчка корректна и 0 в обратном случае.

7 сентября 2004 15 комментариев

Специально для alexandr_wolf:
Дана последовательность
11212312341234512345612345671234567812345678912345678910123456789101112345678910…

Дано число i(1 <=i <=2147483647)
Найти цифру которая стоит на позиции i в этой последовательности. Код плиз мне на мыло. Желательно в виде отдельной функции. =)
int myFunc(int i);

Простенькая задачка

19 августа 2004 1 комментарий

Даны длины лестниц: x, y
И высота точки пересечения: с
Найдите длину улицы =)

16 августа 2004 4 комментария

Reminder:
28 августа суббота. С 13-00 до 18-00 по МСК
«August 2004 Monthly Contest»
Надо хотя бы разок принять участие ….

Решено ровно 100 задач из 1400, если кто умеет прогить на Си присоединяйтесь, а то в одиночку сложно в топ 20 попасть …

Навеяно предыдущим постом

13 августа 2004 1 комментарий

хм =)

13 августа 2004 7 комментариев

В пятницу 9 июля на одном из калифорнийских шоссе появился огромный рекламный щит. Таких объявлений жители Силиконовой долины еще не видели. Никаких картинок, никаких логотипов компаний. Просто текст, причем очень странный.
На щите было написана такая фраза: {Первое 10-значное простое число, найденное в последовательности разрядов e}.com.

Как можно догадаться, это задача для программистов. Чтобы ее решить, нужно составить программу на любом языке программирования, которая могла бы выводить значения константы е и проверять 10-значные последовательности на наличие делителей. Или можно взять какую-нибудь базу простых чисел и проверять совпадения со знаками в десятичной дроби «e». Найденный код, очевидно, нужно ввести в адресной строке браузера, добавив суффикс «.com».

Задачка действительно пробуждает любопытство. Очень уж необычно — нечасто математические головоломки публикуются на огромных рекламных щитах за десятки тысяч долларов. Что же скрывается за этим? Народ приступил к обсуждению и решению ребуса. Многочисленные программки на разных языках программирования были в тот же день опубликованы в интернете.

Оказалось, что правильный ответ — 7427466391, он ведет нас на сайт 7427466391.com:

«Поздравляем! Вы попали на уровень 2. Теперь идите на сайт www.linux.com, введите Bobsyouruncle в качестве логина и ответ на это вычисление в качестве пароля:

f(1)= 7182818284
f(2)= 8182845904
f(3)= 8747135266
f(4)= 7427466391
f(5)= __________»

Согласитесь, все это выглядит довольно странно. Неужели реклама «линукса»? Какой-то фантасмагорический сюжет, в котором стирается грань между реальным и виртуальным миром. Плакат на шоссе является началом виртуального квеста… такое бывает только в кино.
Впрочем, тайна раскрывается после решения второй задачи, когда на экране появляется текст: «Одна из вещей, которые мы усвоили, создавая Google: то, что ищешь, легче найти, если оно само ищет тебя. Мы ищем лучших в мире инженеров. И вот вы здесь. Нетрудно догадаться, что к нам каждый день поступает множество резюме, и мы придумали этот нехитрый процесс, чтобы улучшить отношение сигнал/шум».

Вот оно что!

Оказывается, это Google таким необычным образом ищет сотрудников. Используется оригинальная рекрутинговая техника, чтобы привлечь даже тех математиков и программистов, которые никогда не собирались работать в этой компании. Ведь до последнего момента невозможно догадаться, кто является организатором этой игры. И только в конце все так неожиданно раскрывается. Настоящий детектив от Google!

Источник: webplanet.ru