infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Airinei Adrian din Aprilie 05, 2009, 11:25:28



Titlul: 836 Palindrom
Scris de: Airinei Adrian din Aprilie 05, 2009, 11:25:28
Aici puteti discuta despre problema Palindrom (http://infoarena.ro/problema/palindrom).


Titlul: Răspuns: 836 Palindrom
Scris de: Florin Marius Popescu din Aprilie 05, 2009, 12:17:37
salut! vreau si eu sa stiu care ar fii solutia optima la aceasta problema multumesc


Titlul: Răspuns: 836 Palindrom
Scris de: gaboru corupt din Aprilie 05, 2009, 12:22:47
O(N^2) cel mai nefavorabil caz. Mai poti optimiza totusi.

PS: Vor aparea solutiile oficiale?


Titlul: Răspuns: 836 Palindrom
Scris de: Florin Marius Popescu din Aprilie 05, 2009, 12:28:07
imi deasheshte cu 0.5 secunde... iau decat 5 puncte plus ca la al 2 lea test imi apare ' incorect' , in rest depasheste tipul ......oare ce oi fii scapat din vedere....???
 PS: cum ajung la arhiva de probleme de bac ?


Titlul: Răspuns: 836 Palindrom
Scris de: Andrei Misarca din Aprilie 05, 2009, 12:32:54
La Palindrom2 (http://infoarena.ro/problema/palindrom2) intra O(N2).
Aici ai nevoie de o solutie in O(N)


Titlul: Răspuns: 836 Palindrom
Scris de: gaboru corupt din Aprilie 05, 2009, 12:43:40
Ah da scuze. Si totusi solutia in O(n)? Un hint ceva... :)


Titlul: Răspuns: 836 Palindrom
Scris de: Andrei Misarca din Aprilie 05, 2009, 12:50:27
Pai eu am aflat lungimea celui mai lung palindrom care contine ultimu caracter din sirul dat, iar apoi am adaugat la spate primele (N - acea lungime) caractere din sir


Titlul: Răspuns: 836 Palindrom
Scris de: Florin Marius Popescu din Aprilie 05, 2009, 12:55:40
la fel am facut si eu si totushi nu se incadreaza in timp .. depasheste cu 0.05..... am facut programu in pascal . o fii de la pascal???


Titlul: Răspuns: 836 Palindrom
Scris de: Sima Cotizo din Aprilie 05, 2009, 13:08:36
depasheste cu 0.05.....
S-a mai discutat asta: programul vostru este oprit cu 0.05s dupa ce ati depasit limita. Daca ar fi fost lasat sa ruleze pana isi termina treaba, e posibil sa fi sarit cu mai mult de limita. Ganditi-va ce ar fi daca ar fi lasat sa ruleze pana la capat un program care intra in ciclu infinit ;)


Titlul: Răspuns: 836 Palindrom
Scris de: chisinau gheorghita din Aprilie 06, 2009, 11:53:06
De ce s-a scos problema din arhiva?


Titlul: Răspuns: 836 Palindrom
Scris de: razyelx din Aprilie 07, 2009, 00:07:31
cand apar solutiile oficiale? sau macar spuneti-mi se poate folosi kmp la problema asta a.i. sa scot 100?


Titlul: Răspuns: 836 Palindrom
Scris de: Sima Cotizo din Aprilie 07, 2009, 06:24:11
http://infoarena.ro/grigore-moisil-2009/solutii#palindrom


Titlul: Răspuns: 836 Palindrom
Scris de: razyelx din Aprilie 07, 2009, 13:43:44
iau 55 pct cu incorect pe restul.
Cod:
if(q == n-i){
if(q > l){l = q; unu = 0; doua = 1;}
q = pi[q];
}
if(q == n-i+1){
if(q > l){l = q; unu = 1; doua = 0;}
q = pi[q];
}
in KMP pun doar acele doua conditii, si ma folosesc de varibila l pentru a afisa palindromul. variabilele unu si doua reprezinte nr de varfuri. Pe exemplele mele merge, mai sunt conditii?


Titlul: Răspuns: 836 Palindrom
Scris de: Marius Stroe din Iunie 11, 2009, 20:55:15
Testul 8 a fost înlocuit şi am reevaluat sursele.


Titlul: Răspuns: 836 Palindrom
Scris de: Andrei Geogescu din Martie 21, 2010, 22:01:11
Cod:
#include<iostream.h>
#include<fstream.h>
#include<string.h>
int main()
{char a[200001],b,c[200001];
long i,k=0;
ifstream f("palindrom.in");
ofstream g("palindrom.out");
f.getline(a,200000);
i=strlen(a)-1;
b=a[i-1];
while(i!=0)
{if(a[i]!=b)
i=0;
else
{k++;
i--;}
}
if(k==0)
{strcpy(c,a);
strcpy(a+strlen(a)-1,a+strlen(a));
strcat(c,strrev(a));
g<<c;}

else
{strcpy(c,a);
strcpy(c+strlen(c)-k+1,c+strlen(c));
strcpy(a+strlen(a)-k,a+strlen(a));
strcat(c,strrev(a));
g<<c;
}

return 0;}

care este problematica totusi...?
dc apare aceasta inexplicabila eroare?
va multumesc

Editat de admin: Foloseste tagul "code" cand postezi surse.


Titlul: Răspuns: 836 Palindrom
Scris de: Simoiu Robert din Martie 22, 2010, 12:16:38
Din cate stiu si din ceea ce am citit pe net functia strrev nu este in bibliotecile originale , adica doar in limbajele care au functii "optionale", cum ar fi Code::Blocs, dar in MinGW Developer Studio , adica si pe evaluatorul infoarena, nu exista. De accea iti sugerez sa implementezi functia de mana  :)
[LE] Am gasit un exemplu de reverse, o sa-l postez, sper sa te ajute :)
Cod:
#include <iostream> 
#include <cstring>
using namespace std;
 
int main()
{
  char str[] = "this is a test";
  char *start, *end;
  int len;
  char t;
 
  cout << "Original: " << str << "\n";
  
  len = strlen(str);
 
  start = str;
  end = &str[len-1];
 
  while(start < end) {
    // swap chars
    t = *start;
    *start = *end;
    *end = t;
 
    // advance pointers
    start++;
    end--;
  }
 
 
  cout << "Reversed: " << str << "\n";
  return 0;
}


Titlul: Răspuns: 836 Palindrom
Scris de: Pripoae Teodor Anton din Martie 22, 2010, 16:57:30
Citat
Din cate stiu si din ceea ce am citit pe net functia strrev nu este in bibliotecile originale , adica doar in limbajele care au functii "optionale", cum ar fi Code::Blocs, dar in MinGW Developer Studio , adica si pe evaluatorul infoarena, nu exista. De accea iti sugerez sa implementezi functia de mana 
[LE] Am gasit un exemplu de reverse, o sa-l postez, sper sa te ajute
De cand sunt Codeblocks si Mingw Studio limbaje ?


Titlul: Răspuns: 836 Palindrom
Scris de: Simoiu Robert din Martie 22, 2010, 17:02:44
Am zis limbaje si am pus "optionale", deci eu cred ca se intelege ca e IDE ...  :o


Titlul: Răspuns: 836 Palindrom
Scris de: alexandru din Martie 22, 2010, 17:11:33
adica doar in limbajele care au functii "optionale", cum ar fi Code::Blocs, dar in MinGW Developer Studio
Code::Blocks si MinGW nu contin nici o functie optionala, asta depinde de compilatorul si versiunea( de compilator ) folosita.
strrev este depreciated, la fel ca si itoa.
Pentru strrev exista reverse (http://www.cplusplus.com/reference/algorithm/reverse/) din STL
Cod:
#include <algorithm> 
//s-sirul
n=strlen(s);
reverse( s, s+n ); //reverse actioneaza pe intervalul [ begin, last )


Titlul: Răspuns: 836 Palindrom
Scris de: Andrei Grigorean din Martie 22, 2010, 17:14:40
SpiderMan, tu chiar nu vrei sa intelegi, sau te prefaci?

E a nu stiu cata oara cand trebuie sa atrag atentia pe forum ca MinGW Developer Studio si Code::Blocks nu pot compila/rula surse.


Titlul: Răspuns: 836 Palindrom
Scris de: Simoiu Robert din Martie 22, 2010, 17:39:26
SpiderMan, tu chiar nu vrei sa intelegi, sau te prefaci?

E a nu stiu cata oara cand trebuie sa atrag atentia pe forum ca MinGW Developer Studio si Code::Blocks nu pot compila/rula surse.
Ce vrei sa zici cu asta ? Adica da, nu pot compila singure, dar au incorporate un program care face asta ....


Titlul: Răspuns: 836 Palindrom
Scris de: alexandru din Martie 22, 2010, 19:29:41
Ce vrei sa zici cu asta ? Adica da, nu pot compila singure, dar au incorporate un program care face asta ....
Vrea sa zica ca MinGW/ Code::Blocks sunt niste unelte care te ajuta sa redactezi, compilezi sau sa faci un debug intr-un mod cat mai simplu si placut. Cel care face toata munca din spatele acestor operatiuni este compilatorul , "MinGW/ Code::Blocks sunt doar interfetele"


Titlul: Răspuns: 836 Palindrom
Scris de: Dan-Constantin Spatarel din Decembrie 03, 2011, 21:05:16
Vă rog să adăugați și testul:

acdbdbacabdca

cu raspunsul corect:

acdbdbacabdcacdbacabdbdca

deoarece am observat că există o sursă (643532) care a obținut 100p, deși pică acest test.

Vă mulțumesc.


Titlul: Răspuns: 836 Palindrom
Scris de: SeFu SeFiLoR din Martie 16, 2012, 19:22:48
.... la problema asta iei 100 si daca faci numa pentru palindroame impare  :-'
trebuie modificat ori enuntul ori testele  :)


Titlul: Răspuns: 836 Palindrom
Scris de: Radu-Andrei Szasz din Ianuarie 24, 2013, 21:14:11
Daca a rezolvat cineva problema asta cu algoritmul lui Manacher, as avea nevoie de putin ajutor. Iau doar 25 de puncte cu TLE, desi teoretic ar trebui sa intru lejer in limita de timp.

LE Uitam sa updatez centrul celui mai extins palindrom  ](*,)

Problem solved thanks to Tudor Tiplea  \:D/


Titlul: Răspuns: 836 Palindrom
Scris de: Florin Gabriel Haja din Septembrie 25, 2016, 21:21:27
Puteti sa-mi dati, va rog, input-ul de la testul 7 pe care mi-l pica mie?   :eyebrow:
Sursa este #1764809. Iar eu fac un simplu KMP intre sir si inversul sau.

L.E.: Imi da corect pe testul cu input-ul "acdbdbacabdca", pentru ca verific daca bucata de sir ce nu mai trebuie afisata o data este palindrom sau nu. Dar tot 95 de puncte imi da.


Titlul: Răspuns: 836 Palindrom
Scris de: George Marcus din Octombrie 02, 2016, 15:07:46
Nu o sa iti dea nimeni testul. Compara rezultatul algoritmului tau cu rezultatul unui algoritm mai lent (dar corect) pe niste teste la intamplare.


Titlul: Răspuns: 836 Palindrom
Scris de: Feleaga Dragos-George din Ianuarie 29, 2017, 12:12:10
La problema Palindrom2 iau 100 de puncte, insa aici iau WA. Imi poate spune cineva care este diferenta(in afara de complexitate)?