Олимпиадные Задачи (с acmp.ru)

[Poma][a]

Сразу начну с того что извинюсь за : 1) название темы (ничего лучше не придумал) 2) за все ошибки которые допустил или допущу

Накопилось несколько не решенных задач с acmp. Как не старалась моя светлая голова, однакож воз и ныне там...

На данный момент выложу одну, уже порядочное время, действующую мне на нервы (затем дополню список своего позора с разрешение Сержа и Stilet'а)

ЗАДАЧА №349
Простые числа
(Время: 1 сек. Память: 16 Мб Сложность: 28%)
Необходимо вывести все простые числа от M до N включительно.

Входные данные

Входной файл INPUT.TXT содержит два натуральных числа M и N, разделенных пробелом (2 <= M <= N <= 106)

Выходные данные

В выходной файл OUTPUT.TXT выведите в одной строке через пробел все простые числа от M до N в порядке возрастания. Если таковых чисел нет, то следует вывести «Absent».

Примеры

№ INPUT.TXT OUTPUT.TXT
1 2 5 2 3 5
2 4 4 Absent

Ссыль : тыц

Моё решение :

var
    p : array [1..1000000] of LongInt;
    n, m, count : Int64;
    i, j : LongInt;
    flag : Boolean;

begin

    reset (input, 'input.txt');
    rewrite (output, 'output.txt');
    Read (n, m);

    // создаем массив простых чисел
    p[1] := 2; // первое простое число = 2
    count := 2; // следующие просто число будет с индексом 2

    for i := 3 to m do begin
        j := 1;
        flag := TRUE;

        while p[j]*p[j] <= i do begin
            if i mod p[j] = 0 then begin
                flag := FALSE;
                break
            end;
            Inc (j)
        end;

        if flag then begin
            p[count] := i;
            Inc (count)
        end
   end;

   // simply вывод
   flag := FALSE;
   for i := 1 to count-1 do
        if i >= n-1 then begin
            Write (p[i], ' ');
            flag := TRUE
        end;

   if not flag then
        WriteLn ('Absent')
end.

Возможно(да чего греха таить так и есть) решение не самое лучшее (мягко сказано), просто 1 вариант программы находит подводные камни, а 2 и последующие уже более эффективны, оптимальны, красивы...

[Mad_Cat]

Pascal Accepted 0,592 1948 Кб

Решето_Аткина Удачи!!!

[Poma][a]

Не знаю как меня угораздило написать такой вывод...
Вообщем выкрал чуть-чуть времени, и

var
    p : array [1..1000000] of LongInt;
    n, m, count : Int64;
    i, j : LongInt;
    flag : Boolean;

begin
    //reset (input, 'input.txt');
    //rewrite (output, 'output.txt');
    Read (n, m);

    // создаем массив простых числе от 2 до m
    p[1] := 2; // 1 простое число
    count := 2; // индекс 2 прост числ

    for i := 3 to m do begin
        j := 1;
        flag := TRUE;

        while p[j]*p[j] <= i do begin
            if i mod p[j] = 0 then begin
                flag := FALSE;
                break
            end;
            Inc (j)
        end;

        if flag then begin
            p[count] := i;
            Inc (count)
        end
   end;

   flag := FALSE;

   // просто вывод   for i := 1 to count-1 do
   for i := 1 to count-1 do
        if p[i] >= n then begin
            Write (p[i], ' ');
            flag := TRUE

        end;

   if not flag then
        WriteLn ('Absent')
end.

MadCat, огромное спасибо! (Будет время гляну)

[Poma][a]

Всем добрый день!

Т.к. каникулы кончились, мне удалось наконец-то раздобыть олимпиадные задачи школьного тура. В данной теме (извиняюсь за некропостинг) будут выложены решения некоторых задач, надеюсь никто не будет использовать их в корыстных целях, хотя это Ваше право..

И так, наверное, что бы не путаться я выложу пока 1 задачу и свое решение, далее пойдут другие.

Надеюсь Вы укажите мне на ошибки, недочеты, etc. И предложите какую-либо оптимизацию кода, или в корне другой вариант.
И так задача :

Задача A. Проверить полноту графа.
Неориентированный граф называется полным, если любая пара его различных вершин соединена хотя бы одним ребром. Для заданного списком ребер графа проверьте, является ли он полным.

Формат входных данных

Сначала вводятся числа n ( 1≤n≤100) – количество вершин в графе и m ( 1≤m≤10000) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных

Выведите «YES», если граф является полным, и «NO» в противном случае.

Примеры

Входные данные         Выходные данные
3 3                              YES
1 2 
1 3 
2 3
                                 
3 2                               NO 
1 2 
2 3

Мое решение :

var
    a : array [1..100, 1..100] of Byte;
    flag : Boolean;
    n, m, j, i : Integer;
    t1, t2 : Integer;

begin
    ReadLn (n, m);

    // инициализация массива 0-ми
    for i := 1 to n do
        for j := 1 to n do
            a[i, j] := 0;
    // заполнение
    for i := 1 to m do begin
        ReadLn (t1, t2);
        a[t1, t2] := 1;
        a[t2, t1] := 1
    end;

    // проверка на нахождение 0 не в главной диагонали
    flag := TRUE;
    for i := 1 to n do
        for j := i+1 to n do
            if a[i, j] = 0 then
                flag := FALSE;

    if flag then
        WriteLn ('YES')
    else
        WriteLn ('NO')

end.

[_-Re@l-_]

Маленький mistake.

for i := 1 to n do
        for j := i+1 to n do
            if a[i, j] = 0 then
                flag := FALSE;

За пределы массива можно выпасть.
Надо так :

for i := 1 to n-1 do
        for j := i+1 to n do
            if a[i, j] = 0 then
                flag := FALSE;

А то получается, что вы обращаетесь к a[n,n + 1] на последней итерации. Нехорошо.

[Poma][a]

Неа Смотрите j := i + 1 to n. i станет = n. А как известно, при j := n+1 to n попросту в тело цикла нас не пустят

[referent]

Сообщение от Poma][a

ЗАДАЧА №349
Простые числа

А так? покороче...

var 
 i,j,m,n,k,index:integer;
 begin
 assign(input,'input.txt');
 reset(input);
 assign(output,'output.txt');
 rewrite(output);
   Readln(m,n);
   if (m=1) or (m=2) then Write (m,' ');
   for i:=m to n do
      for j:=2 to i-1 do
       begin
         if i mod j = 0 then
      Break else begin inc(k);inc(index) end;
           if k = i-2 then begin Write(i,' '); k:=0; end;
       end;    
       if index=0 then Writeln('Absent');
       close(input);
       close(output);
 end.

[Plague]

Сообщение от referent

А так? покороче...

Вводим 2 и 10000.
Ваша программ выводит следующие числа в списке:

391
961
1807
2911
4309
5983
8023

А они те являются простыми.