infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Bogdan-Cristian Tataroiu din Ianuarie 11, 2009, 13:51:28


Titlul: 785 Colier
Scris de: Bogdan-Cristian Tataroiu din Ianuarie 11, 2009, 13:51:28
Aici puteti discuta despre problema Colier (http://infoarena.ro/problema/colier).

Titlul: Răspuns: 785 Colier
Scris de: Popescu Marius din Ianuarie 11, 2009, 14:09:06
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 .

Titlul: Răspuns: 785 Colier
Scris de: Bogdan-Cristian Tataroiu din Ianuarie 11, 2009, 14:24:09
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 :-?

Titlul: Răspuns: 785 Colier
Scris de: Popescu Marius din Ianuarie 11, 2009, 16:34:54
N-am stiut .. Am trimis sursa si n-am asteptat sa o complieze . Asta e ... Am crezut ca rezultatul compilarii este ascuns .

Titlul: Răspuns: 785 Colier
Scris de: alexandru din Ianuarie 11, 2009, 17:12:50
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?

Titlul: Răspuns: 785 Colier
Scris de: Andrei Grigorean din Ianuarie 11, 2009, 17:16:40
Pentru n = 4 si colierul: 1101 tu spui ca nu este solutie.

Titlul: Răspuns: 785 Colier
Scris de: alexandru din Ianuarie 11, 2009, 17:22:26
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?

Titlul: Răspuns: 785 Colier
Scris de: razyelx din Ianuarie 11, 2009, 18:53:35
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.

Titlul: Răspuns: 785 Colier
Scris de: alexandru din Ianuarie 11, 2009, 19:40:23
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

Titlul: Răspuns: 785 Colier
Scris de: Andrei Misarca din Ianuarie 11, 2009, 19:46:45
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.

Titlul: Răspuns: 785 Colier
Scris de: alexandru din Ianuarie 11, 2009, 20:58:40
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;
}

Titlul: Răspuns: 785 Colier
Scris de: Andrei Misarca din Ianuarie 11, 2009, 21:04:44
Pai tu tot primul 1 il alegi?

Titlul: Răspuns: 785 Colier
Scris de: Andrei Grigorean din Ianuarie 12, 2009, 09:26:44
Cod:
1
4 0111

Aici afisezi NU.

Titlul: Răspuns: 785 Colier
Scris de: Dragos Oprica din Ianuarie 13, 2009, 19:30:09
Citat din mesajul lui: Andrei Grigorean din Ianuarie 12, 2009, 09:26:44
Cod:
1
4 0111

Aici afisezi NU.

aici de ce raspunsul este nu?

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

Titlul: Răspuns: 785 Colier
Scris de: Andrei Misarca din Ianuarie 13, 2009, 20:48:34
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

Titlul: Răspuns: 785 Colier
Scris de: Ionescu Victor Cristian din Aprilie 30, 2009, 14:23:51
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 :-?

Titlul: Răspuns: 785 Colier
Scris de: Andrei Misarca din Aprilie 30, 2009, 18:13:22
Eu luam 90 pentru ca nu tratam cazu in care nu e niciun 1 si totusi numaru de 0 e impar :)

Titlul: Răspuns: 785 Colier
Scris de: Ionescu Victor Cristian din Aprilie 30, 2009, 21:58:14
Mersi mult:) . Chiar nu m-am prins ca asta era :D . :aha:


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines