This page (revision-2) was last changed on 20-Aug-2015 17:35 by Bojan Kostadinov

This page was created on 20-Aug-2015 17:35 by Bojan Kostadinov

Only authorized users are allowed to rename pages.

Only authorized users are allowed to delete pages.

Difference between version 2 1 and 2 1

At line 1 changed one line

Овој натпревар сеуште не е оддржан...

!!Непарен збир

Она што всушност се бараше како решение на оваа задача е да се напише програма која од стандарден влез ќе прочита два цели броја (нека ги именуваме A и B) и ќе ја отпечати сумата на сите непарни цели броеви помеѓу A и B. Наједноставното решение би било: во циклус да ги изминеме сите броеви во границите помеѓу A и B, и за секој од тие броеви да проверуваме дали се непарни, и доколку се, да ги додаваме во некоја променлива (sum). Поради малите ограничувања на влезните податоци, ова решение без никакви проблеми ќе произведе резултат во дадените временски ограничувања. Следи изворниот код на официјалното решение:

%%prettify

{{{

#include <iostream>

using namespace std;

int main()

{

int a, b, sum = 0;

cin >> a >> b;

for (int i=a; i<=b; i++)

if (i%2 == 1)

sum += i;

cout << sum << endl;

return 0;

}

}}}

/%

Решението дадено погоре има линеарна сложеност O(n). Да напомене дека постои и решение со комплексност O(1). Некои натпреварувачи испратија и вакви решенија.

!!Делители

Во оваа задача се бараше да напишеме програма која ќе го пронајде бројот со најмногу делители (од даден опсег, кој се внесува на почетокот на програмата). Веројатно наједноставното решение би било да напишеме една потпрограма која ќе ни враќа резултат колку делители има даден број (кој и се проследува на потпрограмата како аргумент). Следи изворниот код на оваа потпрограма:

%%prettify

{{{

int count_divs(int k)

{

int counter = 0;

for (int j=1; j<=k; j++)

if (k%j == 0)

counter++;

return counter;

}

}}}

/%

Потоа, решението на задачата се сведува на поминување на сите броеви од опсегот и чување на бројот на делители и вредноста на оној број кој досега води (има најголем број на делители). Следи изворниот код на програмата:

%%prettify

{{{

int main()

{

int p, k, n = 0, divisors = 0;

cin >> p >> k;

for (int i=p; i<=k; i++)

{

int divisors_of_i = count_divs(i);

if (divisors_of_i > divisors)

{

n = i;

divisors = divisors_of_i;

}

}

cout << n << " " << divisors << endl;

return 0; //exit code should be zero

}

}}}

/%

Ова решение има квадратна сложеност, односно комплексноста е О(n%%sup 2/%). Решението може да се унапреди доколку забележиме дека потпрограмата која брои колку делители има даден број може да се промени така што во for-циклусот ќе се движиме само до квадратниот корен на аргументот (во ова решение треба да внимаваме на броевите кои се совршени квадрати).

!!Тест случаи

Тест случаите можете да ги симнете како .zip архива [тука|Тест електронски натпревар 1/testovi_test_elektronski_2010.zip]. \\

Текстот и решенијата дадени погоре можете слободно да ги коментирате на форумот.