Задача A. Robot
Шевчук Олександр
var k,q,i,j,n,c:integer;
s,ss:set of 1..10;
a:array[0..20,0..20]of integer;
x,y:array[0..10]of integer;
procedure robot(z,cc:integer);
var l:integer;
begin
ss:=ss+[z];
if cc+a[z,0]<c then
begin
if ss=s then begin if cc+a[z,0]<c then c:=cc+a[z,0] end else
begin
for l:=1 to n do
begin
if not(l in ss) then begin robot(l,cc+a[z,l]); end;
end;
end;
end;
ss:=ss-[z];
end;
begin
read(k);
for q:=1 to k do
begin
read(x[0],y[0]);
read(n);
s:=[0];
ss:=[];
c:=1000;
for i:=1 to n do
begin
read(x[i],y[i]);
s:=s+[i];
end;
for i:=0 to n do
for j:=0 to n do
a[i,j]:=abs(x[j]-x[i])+abs(y[j]-y[i]);
robot(0,0);
writeln(c);
end;
end.
Задача B. Robot-2
Березін Дмитро
Var kilt:longint;
test:longint;
n:longint;
s:string;
l,i:longint;
rez:longint;
z:boolean;
Procedure ask;
Var j:longint;
Begin
l:=0;
for j:=1 to length(s) do l:=l*10+byte(s[j])-48;
end;
Begin
Readln(kilt);
for test:=1 to kilt do begin
Readln(n); z:=false;
rez:=0; l:=0;
for i:=1 to n do Begin
Readln(s);
if s='HALT' then z:=true;
if z=false then begin
if s='LEFT' then rez:=rez-90;
if s='RIGHT' then rez:=rez+90;
if s='TURN AROUND' then rez:=rez+180;
if pos('LEFT ',s)>0 then begin delete(s,1,pos(' ',s)); ask; rez:=rez-l; end;
if pos('RIGHT ',s)>0 then begin delete(s,1,pos(' ',s));ask; rez:=rez+l; end;
if rez<0 then rez:=rez+360;
if rez>=360 then rez:=rez-360;
end;
end;
Writeln(rez);
end;
End.
Задача C. Hacker vs Olympians
Франчук Роман
#include <iostream>
#include <vector>
#include <set>
using namespace std;
vector<vector<int> > g, g_t;
vector<bool> used;
vector<int> order, c, c_cnt, cc_res;
int cnum = 0;
void dfs1(int v)
{
used[v] = true;
for (int i = 0; i < g[v].size(); ++i)
if(!used[g[v][i]])
dfs1(g[v][i]);
order.push_back (v);
}
void dfs2(int v)
{
used[v] = true;
for (int i = 0; i < g_t[v].size(); ++i)
if(!used[g_t[v][i]])
dfs2(g_t[v][i]);
c[v] = cnum;
c_cnt[cnum]++;
}
vector<set<int> > gc;
int dfs3(int v)
{
int r = c_cnt[v];
used[v] = true;
for(set<int>::iterator i = gc[v].begin(); i != gc[v].end(); i++)
{
if(!used[*i])
r += dfs3(*i);
}
return r;
}
int main()
{
int n, m;
cin >> n >> m;
g.resize(n);
g_t.resize(n);
c.resize(n);
for(int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
a--;
b--;
g[b].push_back(a);
g_t[a].push_back(b);
}
used.resize(n);
for(int i = 0; i < n; i++)
if(!used[i])dfs1(i);
used.assign(n, false);
for(int i = 0; i < n; i++)
{
int v = order[n - i - 1];
if(!used[v])
{
c_cnt.resize(cnum + 1);
dfs2(v);
cnum++;
}
}
gc.resize(cnum);
for(int i = 0; i < n; i++)
for(int j = 0; j < g[i].size(); j++)
if(c[i] != c[g[i][j]])
gc[c[i]].insert(c[g[i][j]]);
//*******************************************
cc_res.resize(cnum, 0);
int m_val = -1;
for(int i = 0; i < cnum; i++)
{
used.assign(cnum, false);
cc_res[i] = dfs3(i) - 1;
m_val = max(m_val, cc_res[i]);
}
vector<bool> t(cnum);
for(int i = 0; i < cnum; i++)
if(cc_res[i] == m_val)t[i]=true;
bool fst = true;
for(int i = 0; i < n; i++)
if(t[c[i]])
{
if(fst)
fst = false;
else
cout << " ";
cout << i + 1;
}
cout << "\n";
return 0;
}
