[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Телепатија, училишен 2016  XML
Forum Index » Задачи од национални натпревари
Author Message
Danail



Joined: 12/11/2012 22:04:42
Messages: 7
Offline

Идеа за задачава?

http://mendo.mk/Task.do?id=610
addictus


[Avatar]

Joined: 08/10/2010 11:22:51
Messages: 23
Location: Куманово
Offline

Прво пробај да откриеш во кои случаи треба да се печати -1. Кога го откриеш тоа можеш да елиминираш голем дел од просторот за пребарување и да ја намалиш сложеноста на задачата.

Хинт: преостанатиот простор за пребарување го претставуваш како граф.

Решенија на задачи - aandevski.wordpress.com
[WWW]
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;
}
Danail



Joined: 12/11/2012 22:04:42
Messages: 7
Offline

Сфатиш*
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;
}
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team