Блог Ромки

Итак, что мы имеем:

2 геометрические задачки
2 задачи на графы
2 на теорию чисел
1 парсер + полиномы
3 задачки с неоднозначным решением
— решалка японских кроссвордов
— нахождение цифр чила Пи
— распознование образов

Ещё 2 задачи будут добавлены в процессе, мне кажется лучшими будут:
1) Задача использующая Convex Hull
2) Задача на строки
3) Задача на динамическое программирование + рекурсия (че нить вроде задачи о рюкзаке)
их сложность будет зависеть от того насколько будут успешно решаться уже добавленные задачи.

Вчера на мой запрос ответила администрация горсети. Обеспечат бесплатным траффиком + дадут новость на главной странице. Попросили макет новости и картинку … Вчера 2 часа сочинял новость, но все равно звучит КРИВО. Надеюсь до понедельника, что нибудь удобоваримое удастся родить. Дата старта уже стопроцентно известна: 15 февраля, ура товарищи. =)

Программист — начальнику отдела:
Мы не можем справиться с предложенным проектом! Повторяю: НЕ МОЖЕМ! Это потребует полного изменения структуры дерева наследования, никто в нашем отделе в ней не разбирается. Более того, никто в компании не знает даже языка, на котором это всё было написано, так что даже если кто-то и захочет этим заняться, он просто не сможет. Если Вас интересует моё мнение, наша компания вообще не должна соглашаться работать над подобными проектами.

Начальник отдела — руководителю проекта:
Проект потребует изменения структуры системы. На текущий момент у нас нет сотрудников, имеющих опыт подобной работы. К тому же, язык нам не очень знаком, так что нам придётся организовать кое-какую переподготовку, если мы возьмёмся за этот проект. Если Вас интересует моё мнение, мы не готовы работать над проектами подобного рода.

Руководитель проекта — менеджеру среднего звена:
Этот проект подразумевает изменение структуры, а у нас маловато опыта в этой области. К тому же, у нас в компании не так много людей, которые специально обучались таким вещам. Если Вас интересует моё мнение, мы бы смогли справиться с этим проектам, но на это у нас уйдёт немного больше времени, чем обычно.

Менеджер среднего звена — менеджеру верхнего уровня:
Этот проект подразумевает пересмотр структуры. У нас есть несколько специалистов, которые работали в этой области и ещё несколько специалистов по языку реализации. Они могли бы организовать обучение персонала. Если Вас интересует моё мнение, нам стоит взяться за этот проект, но действовать нужно осторожно.

Менеджер верхнего уровня — управляющему: Этот проект даст нам возможность продемонстрировать нашу способность полного изменения структуры существующей системы. У нас есть все необходимые умения и ресурсы, чтобы успешно справиться с проектом. Некоторые сотрудники уже начали обучать других необходимым навыкам неофициальном порядке. Если Вас интересует моё мнение, мы не должны упустить этот проект ни в коем случае.

Управляющий — клиенту:
Это как раз тот тип проектов, в которых наша компания специализируется. Мы уже завершили несколько проектов подобного типа для крупных заказчиков. Поверьте, что в этой области именно мы являемся наиболее компетентными. Если Вас интересует моё мнение, мы можем выполнить этот проект успешно и в назначенные Вами сроки.

©http://www.fishki.net/index.php?page=9

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

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.

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

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

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

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 раза! Если есть ещё идеи то в комменты. =)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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