Author |
Message |
20/02/2016 17:40:49
|
Danail
Joined: 12/11/2012 22:04:42
Messages: 7
Offline
|
Идеа за задачава?
http://mendo.mk/Task.do?id=610
|
|
|
21/02/2016 00:43:01
|
addictus
Joined: 08/10/2010 11:22:51
Messages: 23
Location: Куманово
Offline
|
Прво пробај да откриеш во кои случаи треба да се печати -1. Кога го откриеш тоа можеш да елиминираш голем дел од просторот за пребарување и да ја намалиш сложеноста на задачата.
Хинт: преостанатиот простор за пребарување го претставуваш како граф.
|
Решенија на задачи - aandevski.wordpress.com |
|
|
14/03/2016 13:24:03
|
BATIR
Joined: 20/06/2015 16:36:50
Messages: 155
Offline
|
Прво пробај да ја сватиш задачата , а потоа види го решениево кое поминува на сите тест случаи.
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int main()
{
int teminja, kosta, kiril, parichki;
cin >> teminja >> kosta >> kiril >> parichki;
int cnt = 0;
bool vis[100001];
memset(vis, false, sizeof(vis));
queue<int> q;
for(int i=0; i<kosta; i++)
{
int a;
cin>> a;
vis[a]=true;
q.push(a);
}
for(int i=0; i<kiril; i++)
{
int a;
cin >> a;
vis[a] = true;
}
int rebra;
cin >> rebra;
vector <int> niza[100001];
for(int i=0; i<rebra; i++)
{
int a, b;
cin >> a >> b;
niza[a].push_back(b);
niza[b].push_back(a);
}
while(!q.empty())
{
int teme = q.front();
q.pop();
for(int i=0; i<niza[teme].size(); i++)
{
int novo = niza[teme][i];
if(vis[novo] == false)
{
vis[novo] = true;
q.push(novo);
cnt++;
}
}
}
if(cnt > parichki)
cnt = parichki;
cout << cnt << endl;
return 0;
}
|
|
|
23/03/2016 11:53:21
|
Danail
Joined: 12/11/2012 22:04:42
Messages: 7
Offline
|
Сфатиш*
|
|
|
24/03/2016 12:48:53
|
BATIR
Joined: 20/06/2015 16:36:50
Messages: 155
Offline
|
pardon greska jas ti prtiv dr resenie eve go pravoto
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int main()
{
int x, y;
int ex, ey;
cin >> x >> y;
cin >> ex >> ey;
if( x + y != ex + ey)
{
cout << -1 << endl;
return 0;
}
int zbir = x + y;
bool vis[200001];
memset(vis, 0, sizeof(vis));
queue <int> q, cekori;
q.push(x);
cekori.push(0);
while(!q.empty())
{
int temeX = q.front();
int cek = cekori.front();
q.pop();
cekori.pop();
if( temeX == ex )
{
cout << cek << endl;
break;
}
int temeY = zbir - temeX;
if( temeY - 1 > 0 && vis[temeX + 1] == false)
{
vis[temeX + 1] = true;
q.push(temeX + 1);
cekori.push(cek + 1);
}
if (temeX-1-((2*temeX)%31) > 0 && vis[temeX-1-((2*temeX)%31)]==false)
{
vis[temeX-1-((2*temeX)%31)] = true;
q.push(temeX-1-((2*temeX)%31));
cekori.push(cek + 1);
}
}
return 0;
}
|
|
|
|