Олимпиада по информатике

← →
Footballer © (2007-01-14 19:42) [40]

Вот програмка, вычисляющая первое простое число содержащее млн. знаков :)))
var i:integer; f:TextFile; s:string; begin Randomize; s:= "1"; //чтобы не вызвать подозрений :) for i:= 1 to 99999 do s:= s + inttostr(trunc(random(10000000000))); AssignFile(f, "C:/q.txt"); Rewrite(f); Write(f, s); CloseFile(f);

Получился файлик ровно 900 KB, остаётся только отдать его Microsoft и забрать честно заработанные бабки :-D

← →
Footballer © (2007-01-14 19:58) [41]

Кстати, насчёт олимпиады, распределения баллов по-моему тупое:

2-ая задача (15 баллов) самая лёгкая, ну вообще делать нечего;
3-ья задача (20 баллов) тоже очень лёгкая, если не обламаться как я :)
1-ая задача (10 баллов) вроде как не очень сложная, но там очень много писать;
4-ая задача (25 баллов) самая сложная, её даже взрослые преподаватели не смогли решить
5-ая задача (30 баллов) Вроде не очень сложная, просто надо знать числа Фибоначчи (кстати что это такое?), а без этого тут делать нечего...

← →
ferr © (2007-01-14 20:02) [42]

> 5-ая задача (30 баллов) Вроде не очень сложная, просто надо
> знать числа Фибоначчи (кстати что это такое?), а без этого
> тут делать нечего...

Ты явно не читал Дэна Брауна. =) И не читай. =) Это самое попсовое реккурентное соотношения. F(n) = F(n - 1) + F(n - 2). 1 1 2 3 5 8 13 ... Появляется во многих задачах.

← →
Footballer © (2007-01-14 20:06) [43]

То есть каждое новое число образуется суммой 2-х предыдущих?

← →
PHPdeveloper (2007-01-14 20:06) [44]

> числа Фибоначчи (кстати что это такое?

http://g6prog.narod.ru/books.html

Такс.. Посмотерел 4. Она действительно сложнее 5-ой.
Какое могу предложить решение : Выделяем все циклы в графе. Это можно сделать одним проходом dfs за O(V^2). Имеем цикл и надо сделать сумму весов рёбер как можно меньшей (по модулю). Для этого складываем все веса рёбер цикла и делим на количество рёбер. Получившееся число вычитаем из весов всех рёбер цикла.

Проблемы могут возникнуть если один цикл содержит другой, но вроде не должны..

Для первого теста, матрица смежности выглядит так

1 2 100 2 3 50 3 1 75 1 2 3 1 - 100 -75 2 -100 - 50 3 75 -50 -

vidiv © (14.01.07 16:11) [28]
а докажем как?
допустим так:
Тест на основе малой теоремы Ферма. если n простое, то выполняется условие:
При всех а из {2, 3,…n-1} имеет место сравнение a^(n-1)=1 mod n

vidiv © (14.01.07 16:47) [32]

есть такая теорема:

Теорема (Диемитко): Пусть n = qR+1 > 1,
где q - простое, R - четное и R<4(q+1).
Если существует целое а такое, что
а^(n-1) = 1 mod n
a^((n-1)/q) <> 1 mod n
то n - простое.

вперёд.

Олимпиада по информатике Найти похожие ветки