785 Colier

[•bogdan2412]

Aici puteti discuta despre problema Colier.

[•jupanubv92]

Eu am rezolvat corect problema in concurs numai ca nu stiam ca linux-ul e case sensitive si am scris #include<Stdio.h> ...... si am luat eroare de compliare adica 0 p ( codebloks-ul meu nu dadea nici o eroare )  ....  ... ce face neatentia am pierdut 90 de p din cauza unu S .

[•bogdan2412]

Cand trimiti sursa evaluatorul iti zice daca a compilat sau nu sursa, trebuia sa te uiti la monitor doar. Ar fi trebuit sa-ti apara si mesajul de eroare cand faceai click pe job

[•jupanubv92]

N-am stiut .. Am trimis sursa si n-am asteptat sa o complieze . Asta e ... Am crezut ca rezultatul compilarii este ascuns .

[•alexandru92]

Imi  zice  si  mie  ce-i  gresit  la  urmatoarea  rezolvare:  Intr-un vector de  tip caractere memorez  configuratia  colierului. Apoi daca  n>=3   gasesc  primul  element '1'   schimb vecinii  si  sterg  '1'. Continui  asa  pana  n<=2  sau  nu  mai exista  numere de 1 in vector? Daca  n==2  verific daca  cele 2 elemte  is  egale  , afisez  NU, daca este adevart sau  DA  altfel. Daca n==1 vad daca este  1 afisez  Da  altfel  Nu. Ce-i gresit?  Codul e  urmatorul:

Cod:

#include<stdio.h>
#define InFile "colier.in"
#define OutFile "colier.out"
#define Nmax 100001
int T;
long  n;
char  s[Nmax];
FILE *fout;
int parcurge(long n,char s[])
{long i;
  for(i=0;i<n&&s[i]=='0';i++);
    if(i==n) {printf("NU\n");return 1;}
return 0;
}
int out(long n,char s[])
{long i;
if(n>2)return parcurge(n,s);
  else {if(n==1&&s[0]=='0') printf("NU\n");
	       else if(n==1) printf("DA\n");
        if(n==2&&s[0]==s[1]) printf("NU\n");
	       else if(n==2) printf("DA\n");
      }
return 1;
}
int main()
{int i;  
 long j;
	FILE *fin=freopen(InFile,"rt",stdin);
	fout=freopen(OutFile,"wt",stdout);
	scanf("%d",&T);
	for(i=1;i<=T;i++)
	{
		scanf("%ld %s",&n,&s);
		if(!out(n,s))
		  {do
		    {
                               for(j=0;j<n&&s[j]=='0';j++);
			 if(j>0) s[j-1]=s[j-1]=='0'?'1':'0';
			 if(j<n-1)  s[j+1]=s[j+1]=='0'?'1':'0';
                                for(;j<=n;j++) s[j]=s[j+1];
		        n--;
		      }while(!out(n,s));
		 }
	}
fclose(fout); fclose(fin);
return 0;
}

Nu-i bine  cum am  gandit-o?

[•wefgef]

Pentru n = 4 si colierul: 1101 tu spui ca nu este solutie.

[•alexandru92]

NU!, spune ca este  solutie
1 1 0 1
gaseste  1   si sirul devine  001
apoi  gaseste    1  si  sirul  devine   01
si  raspuns este   DA:)  ( is  doar  2  numere diferite intre ele:P)
Am  si  compilat  in  caz, ca  nu dadea dar merge
Nu  cumva  se  poate afisa  testul  1?

[•razyelx]

alaxandru tu faci brut force. Problema presupun ca se rezolva intr-o complexitate mai mica decat O(n^2).  Tu ai acolo O(n^2). Ma gandesc ca iei TLE.

[•alexandru92]

ok, fota  bruta  sau  nu.........de ce  apare  Incorect  asat  ma deranjeaza, ca nu  intra  in  timpi asa  stiam de cand  am  postat-o:P

[•Mishu91]

pai nu trebiue schimbat neaparat primul 1, iar daca pentru exemplul 1101, dupa ce ai gasit primul 1 sirul tau devine 001, inseamna ca nu ai implementat bine, pentru ca ar trebui sa devina 000,  sirul fiind circular, iar vecinii pozitii 1 sunt pozitiile 2 si N.

[•alexandru92]

Buna remarca!  am  incercat si tot  nu mere

Cod:

#include<stdio.h>
#define InFile "colier.in"
#define OutFile "colier.out"
#define Nmax 100001
int T;
long  n;
char  s[Nmax];
FILE *fout;
int parcurge(long n,char s[])
{long i;
	for(i=0;i<n&&s[i]=='0';i++);
    if(i==n) {printf("NU\n");return 1;}
return 0;
}
int out(long n,char s[])
{long i;
if(n>2)return parcurge(n,s);
  else {if(n==1&&s[0]=='0') printf("NU\n");
	       else if(n==1) printf("DA\n");
        if(n==2&&s[0]==s[1]) printf("NU\n");
	       else if(n==2) printf("DA\n");
      }
return 1;
}
int main()
{int i;  
 long j;
	FILE *fin=freopen(InFile,"rt",stdin);
	fout=freopen(OutFile,"wt",stdout);
	scanf("%d",&T);
	for(i=1;i<=T;i++)
	{
		scanf("%ld %s",&n,&s);
		if(!out(n,s))
		  {do
		    {
             for(j=0;j<n&&s[j]=='0';j++);
			 if(j>0) {s[j-1]=s[j-1]=='0'?'1':'0'; }
			 else  s[n-1]=s[n-1]=='0'?'1':'0';
			 if(j<n-1)  s[j+1]=s[j+1]=='0'?'1':'0';
			 else s[1]=s[1]=='0'?'1':'0';
                                       for(;j<=n;j++) s[j]=s[j+1];
			 n--;
			}while(!out(n,s));
		 }
	}
fclose(fout); fclose(fin);
return 0;
}

[•Mishu91]

Pai tu tot primul 1 il alegi?

[•wefgef]

Cod:

1
4 0111

Aici afisezi NU.

[•DraStiK]

Cod:

1
4 0111

Aici afisezi NU.

aici de ce raspunsul este nu?

0-1-11 devine -1-01 devine 10 care devine nul

[•Mishu91]

Pt exemplul

Cod:

1
4 0111

Raspunsul este DA, dar cred ca se referea la faptul ca programu postat mai sus da raspunsul NU pentru acest exemplu

[•vanila_CPP]

Are careva idee care e cazu ala special pentru care se ia 90? Eu in afara de faptul in care N==1 vad daca numarul de 0'uri e impar .. si am cam demonstrat chestia asta

[•Mishu91]

Eu luam 90 pentru ca nu tratam cazu in care nu e niciun 1 si totusi numaru de 0 e impar

[•vanila_CPP]

Mersi mult:) . Chiar nu m-am prins ca asta era .