Pomoc oko zadatka(Drzavno-2B-2013)

Pitanja i problemi
1

link zadatka: http://bubblebee.petlja.org/Media/Default/Problem/Drzavno%202013%20B2%20Drvored.pdf

Na koji nacin se radi ovaj zadatak? Nemam nikakvu ideju :thinking:

2

Sortiras niz sa drvecem i razmatraj 3 najmanja.Od ta 3 najmanje jasno bar 2 moraju biti sa iste strane ulice (Dirihleov) pa imas samo 3 mogucnosti da proveris:1. i 3. su zajedno ,2. i 3 su zajedno i 1. i 2. su zajedno.Sada odradimo za svaki slucaj stranu kojoj znamo dva drveta i.e ako je visina prvog a,drugog b (od ta 2 poznata) stavljamo da a,b,a+(b-a),a+2(b-a),ā€¦ pripadaju jednoj ulici.Ukoliko se ostalo drvece uklapa u niz za drugu ulicu gotovi smo inace imamo 2 slucaja:1. Poslednje drvo koje smo eliminisali iz prve ulice vratimo i vidimo da li se sad ostala drveca uklapaju u niz,ako ne znaci da moramo eliminisati jos poslednjih drveca bar dva !Posmatrajmo sad drveca koja su po visini izmedju ta dva drveta- oni svi moraju biti u 2. ulici pa sad imamo razliku u visini izmedju 2 drveta u drugoj ulici i lako vrsimo proveru onih ne eliminisanih drveca.

1 Like
3

Hvala, ali nije mi jasno zasto razmatramo samo najmanja 3? Ako si uradio zadatak i imas kod bilo bi lepo da ga pustis ovde

4

Ne,razmatras samo kombinaceje (3 nabrojana ) od prva 3 samo da znas razliku u visini izmedju dva drveta u jednoj ulici pa onda ostala drveca eliminises (napisano je gore).Kod ti je u prilogu,nzm da li ima jos bagova ne dobijam feedback vec pola sata,ali u najgorem slucaju radi 8/10 (toliko je bilo pre ispravljanja bagova).Nisam se trudio da ga skratim ako treba nesto - pitaj.
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int A[N],n,In[N],ok,In2[N];
void Output(){
int cnt1=0,cnt2=0;
for(int i=1;i<=n;i++){
if(In[i]==1)
cnt1++;
if(In[i]==2)
cnt2++;
}
if(cnt2==0){
cnt1ā€“;
cnt2=1;
In[n]=2;
}
if(cnt1==0){
cnt1=1;
cnt2ā€“;
In[n]=1;
}
printf("%d\n",cnt1);
for(int i=1;i<=n;i++){
if(In[i]==1)
printf("%d ā€œ,A[i]);
}
printf(ā€\n");
printf("%d\n",cnt2);
for(int i=1;i<=n;i++){
if(In[i]==2){
printf("%d ",A[i]);
}
}
}
void reset1(){
for(int i=1;i<=n;i++){
if(In[i]==2)
In[i]=0;
}
}
bool SimpleCheck(){
int fir=-1,sec=-1,x,cnt=2;
for(int i=1;i<=n;i++){
if(!In[i]){
if(fir==-1){
fir=i;
In[fir]=2;
}
else{
if(sec==-1){
sec=i;
x=A[sec]-A[fir];
In[sec]=2;
}
else{
if(A[i]!=A[fir]+cntx){
return 0;
}
else{
In[i]=2;
cnt++;
}
}
}
}
}
return 1;
}
void Solve(int fir,int sec){
In[fir]=1;
int x=A[sec]-A[fir],i=sec,cnt=1,l1=fir,l2=-1; //l1 i l2 are last in first street
while(i!=n+1){
if(A[i]==xcnt+A[fir]){
In[i]=1;
cnt++;
if(l2==-1)
l2=i;
else{
l1=l2;
l2=i;
}
}
i++;
}
if(SimpleCheck()){
ok=1;
Output();
return;
}
reset1();
In[l2]=0; //last is now in second street
if(SimpleCheck()){
ok=1;
Output();
return;
}
reset1();

int x2=A[l1+1]-A[l1],cnt2=0,f;
In[l1]=0,In[l2]=0;
for(int i=1;i<=n;i++){
    if(!In[i]){
        f=i;                // find first in second street
        break;
    }
}
for(int i=1;i<=n;i++){
    if(A[i]==A[f]+cnt2*x2){
        In2[i]=2;
        cnt2++;
    }
    else{
        if(i>=l1){           //must fill larger then l1 bc first street won't
            ok=0;
            return;
        }
    }
}
cnt=0;
for(int i=1;i<=n;i++){
    if(!In2[i]){
        if(A[i]!=A[fir]+cnt*x){
            ok=0;
            return ;
        }
        else{
            In2[i]=1;
            cnt++;
        }
    }
}
for(int i=1;i<=n;i++){
    In[i]=In2[i];
}
Output();
ok=1;

}
void reset2(){
for(int i=1;i<=n;i++){
In[i]=0;
In2[i]=0;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&A[i]);
}
sort(A+1,A+n+1);
if(n==1){
printf(ā€œ1\nā€);
printf("%d",A[0]);
return 0;
}
if(n==2){
printf(ā€œ1\nā€);
printf("%d\n",A[0]);
printf(ā€œ1\nā€);
printf("%d",A[1]);
return 0;
}
Solve(1,2);
if(ok)
return 0;
reset2();

Solve(1,3);
if(ok)
    return 0;
reset2();

Solve(2,3);
if(ok)
    return 0;
else
    printf("-1");
return 0;

}

1 Like
5

Hvala. Je lā€™ mozes samo da postavis kod ovde: https://ideone.com/ - samo nalepis kod, kliknes na run i posaljes link ovde.
Ne mogu ovako kako si poslao da ga kopiram u codeblocks

6

Evo

1 Like