View Attach (1) Info

Add new attachment

Only authorized users are allowed to upload new attachments.

List of attachments

Kind Attachment Name Size Version Date Modified Author Change note
zip
 testovi_prv_elektronski_2010.z... 102.9 kB 1 20-Aug-2015 17:35 Bojan Kostadinov

This page (revision-6) was last changed on 20-Aug-2015 17:35 by mariomako

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 and

At line 1 changed one line
Овој натпревар сеуште не е оддржан...
!!Фудбал
Во оваа задача се бараше да напишеме програма која од стандарден влез ќе прочита информации за резултатите на N фудбалски екипи, и на стандарден излез ќе го отпечати максималниот број на поени кои ги освоила една од N-те екипи... Решението е доста едноставно: во циклус ги изминуваме сите екипи, пресметуваме колку поени освоила секоја од нив (притоа, во секој чекор од for-циклусот го паметиме резултатот на екипата која освоила најмногу поени). Решението има линеарна сложеност, која следува од тоа што мораме да ги изминеме сите екипи пред да можеме да бидеме сигурно дека сме ја пронашле екипата со најмногу поени. Следи изворниот код на официјалното решение:
%%prettify
{{{
#include <iostream>
using namespace std;
int main()
{
int best = 0, n;
cin >> n;
for (int i=0; i<n; i++)
{
int wi, di, li;
cin >> wi >> di >> li;
int points = 3*wi + di;
if (points > best)
best = points;
}
cout << best << endl;
return 0;
}
}}}
/%
!Паскал
%%prettify
{{{
program fudbal; (* Марио Величковски *)
var n,wi,di,li,b,max,p:longint;
begin
readln(n);
readln(wi,di,li);
p:=wi*3+di*1;
max:=p;
for b:=2 to n do
begin
readln(wi,di,li);
p:=wi*3+di*1;
if p>max then max:=p;
end;
writeln(max);
readln;
end.
}}}
/%
Како што напоменавме и погоре, ова решение има линеарна сложеност O(n).
!!Факторизација
Она што всушност се бараше како решение на оваа задача е да се напише програма која ќе прочита еден цел број од стандарден влез, и на излез ќе ја отпечати факторизација на тој број (ќе го претстави бројот како производ од прости фактори). Решението на задачата се состои во следното: додека бројот е поголем од 1 (сеуште има фактори кои не сме ги пронашле), ги проверуваме сите можни основи и за нив го пресметуваме степенот на факторот (почнувајќи од најмалата основа - 2, бидејќи во текстот на задачата се бара од нас да ги печатиме факторите подредени од оној со најмала кон оној со најголема основа). Вториот проблем во задачата е печатењето на резултатите (особено поставеноста на знакот за множење), но решението и на овој проблем е доста едноставно (воведуваме само уште една променлива која ќе памети дали го печатиме првиот фактор или не). Следи изворниот код на програмата:
%%prettify
{{{
#include <iostream>
using namespace std;
int main()
{
int n, base=2, deg, first=1;
cin >> n; //read n from console
while (n >= 2)
{
deg = 0;
while (n%base == 0)
{
n /= base;
deg = deg+1;
}
if (deg > 0)
{
if (first == 1)
{
cout << "(" << base << "^" << deg << ")";
first = 0; //printed the first factor
} else
{
cout << "*" << "(" << base << "^" << deg << ")";
}
}
base = base + 1;
}
cout << endl;
return 0;
}
}}}
/%
Иако на прв поглед, решението има два вгнездени while циклуси, сепак комплексноста не е квадратна, туку ова решение има линеарна сложеност О(n). Во пракса, решението работи многу побрзо и од тоа.
!!Тест случаи
Тест случаите можете да ги симнете како .zip архива [тука|Прв електронски натпревар/testovi_prv_elektronski_2010.zip]. \\
Текстот и решенијата дадени погоре можете слободно да ги коментирате на форумот.
Version Date Modified Size Author Changes ... Change note
6 20-Aug-2015 17:35 3.72 kB mariomako to previous
5 20-Aug-2015 17:35 3.34 kB Bojan Kostadinov to previous | to last
4 20-Aug-2015 17:35 3.343 kB Bojan Kostadinov to previous | to last
3 20-Aug-2015 17:35 3.359 kB Bojan Kostadinov to previous | to last
2 20-Aug-2015 17:35 3.361 kB Bojan Kostadinov to previous | to last
1 20-Aug-2015 17:35 0.039 kB Bojan Kostadinov to last
« This page (revision-6) was last changed on 20-Aug-2015 17:35 by mariomako