Are vreun nume oficial genul asta de comprimare? Seamana multicel cu run-length encoding
Ce se intampla cu sirurile de genu "ccccccacccccca"?
Ajung "2cccccca" (len=8) sau "6c1a6c1a" (len=8)? Ambele variante sunt corecte...

@micul programator
Iata ca nu e abadonat, il cloceste Tiberiu...

@bogdan
np, am realizat ca sunt mai multe gauri decat credeam
ma aprinsesem putin... bine ca am comunicat...

Pe prima am facut-o deja.Iti trimit pm, sau o pun aici?  Eh?
Mi se par interesante, au conditii mai "dure".I keep thinking about them!

Am dorit sa ofer probleme cu altfel de restrictii inafara de cele clasice legate de timpul de executie (aveti cam 800 deja). Nu doresc un concurs cu o singura rezolva, evident!
Am scris un pharser caruia voi (critici specializati) nu i-ati gasit flaw la surse de pascal si jumate din pharserul de c++ e teoretic functional (habar n-aveam cat de vast e limbajul, e chiar inutil de vast pentru algoritmi simpli de concurs, eficienti (cred ca pascal, fortran, algol sau chiar asm sunt most suitable pentru competitii dar nu ma bag)
Am scris si probleme...
Totusi, sunteti olimpici si paraolimpici (eu nu-s) si daca doreati sa infloreasca initiativa mea probabil inaintati mai mult de "e greu de facut" si "uite ca nu e bun, ha!"

in timp ce tastam altii postau... in vara scriu aticole (sper k alea nu au flaws). Aruncati un ochi pe "www.donebyme.go.ro" stiu ca e urata engleza mea de la 15 ani, dar, daca tutorial de "build yer own script interpreter" e considerat util pe infoarena scriu si asa ceva, dar la vara

...ma depaseste sintaxa C... ce ma oftica e ca sintaxa pascal e total acoperita (99% sigur)
Daca nu va vine vreo idee eu aman treaba asta pana scap de bac si admitere...

... altfel se complica pharserul... asa poate sa obiecteze oricine ca vrea inline assembly.
interzicerea defineului e o solutie SIMPLA pe care am gasito, si daca exista alternative atunci... defapt daca vrei sa declari o constanta numerica "const int max=10" este foarte ok

[Exemplu:]

"Mie nu-mi pare usor de facut un parser pentru asa ceva" ...  suna generic
Explicatie pe larg a pharserului:
1) Se apeleaza pharserul cu parametru "numefis.pas/cpp"
2) Se citesc din "numefis.phr" (deja existent pe srv) ce cuvinte se admit de cate ori si ce caractere sunt nepermise... explic de indata
3) Se citeste sursa linie cu linie, se pun "cuvintele" intr-un vector; ca separatori se iau ' ' si '('
4) Se cauta daca cuvintele restrictionate se afla in vectorul de cuvinte al liniei curente si se incrementeaza numarul lor de aparitii; cand numarul de aparitii se depaseste se termina executia programului cu exitcode:1
Odata cu separarea cuvintelor se cauta si existenta caracterelor nepermise: ? daca avem restrictii la If si suntem in c++ sau [ daca avem restrictii legate de vectori; idem pentru operatii matematice de 1 caracter
5) pentru sursele Pascal se poate restrictiona recursivitatea daca restrictionam 'function' sau 'procedure' (problema apare la c++) Pentru C++ se cauta prima ocurenta a caracterului '(' in sursa - daca acetsa este precedat de ' main' atunci totu e ok

Exemplu: intre acolade sunt comentarii...
Daca dorim sa folosim un singur ciclu (for, while, repeat) scriem asa:
1 3 {este permisa o aparitie a oricarui dintre cele 3 urmatoare}
for
while
repeat

toate cele 3 sunt delimitate in pascal de spatii, in c++ dupa for si while se pune '('

Restrictionarea if-urilor
? {caracter nepermis}
2 1 {se admite de 2 ori cel 1 keyword de mai jos}
if

Daca se doreste restricionarea arrayurilor... se pomeneste '[' ca fiind caracter nepermis, simplu
"dar in pascal trebuiesc restrictionate si fUnction si FUnction si toate variantele" - raspuns: se trec pe downcase (ca la C)
Cat despre acele defineuri dubioase... se restrictioneaza '#define' si gata

"simplu ca placinta"!

Chiar ma bucur pentru entuziasmul vostru.

@miculprogramator
Solutiile tale pot fi trimise spre evaluare tot pe infoarena DACA mai lucrez putin de tot la pharser si DACA sunt deacord cei de sus cu acest tip de concurs. Ai putintica rabadare sa vedem ce iese...

Problema 3: Un IF e un IF, nu 10; e corecta indicatia data de gaboru, numai ca if-ul acela nu trebuie irosit la verificarea paritatii... nu este permit nici un fel de for,while,repeat, dar sunt permise subprograme (acolo intervine si if-ul)

Catre Dl. Pripoae
De implementat verificatorul inainte de compilare... din cate cunosc procesu sta asa: serverul sitului apeleaza un script of some sort care suna la evaluatorul meu cu parametru "numele fisierului" si asteapta exitcode-ul ... daca acesta este 0 paseaaza sursa la compilator si mai departe la evaluatorul infoarena.
Nu ating scopul acestui site? Probabil (mie mi se par "puzzleuri programatoricesti"); Nu cred ca strica daca se adauga si ele, amaratele. Am incercat sa imbogatesc infoarena. Eu unul, nu ma antrenez pentru olimpiade, si tot urmaresc situl, e printre putinele forumuri programatoricesti romanesti.

Poti coda in C++ fara probleme... (specificasem ca sursa evaluatorului este scrisa in pascal)
Unde poti verifica rezultatele? Eu am scris evaluatorul, am postat si aceste probleme... astept decizia echipei infoarena - daca doresc/e posibila sau nu introducerea noului tip de probleme.
Apreciez interesul. Am postat aceste probleme ca un fel de preview...

Iata probleme despre care discutam mai devreme.
Martinel s-a angajat mai nou la o companie de electronice. Acesta are de programat fel de   electronice care nu sunt prea avansate. Unele au microprocesoare care nu inteleg operatii matematice, altele nu isi permit sa ruleze mai mult de 1 ciclu, altele nu stiu operatii conditionale. Ajutati-l pe Martinel sa rezolve urmatoarele probleme:

1) Sa se verifice daca un numar este palindrom fara sa se utilizeze notiunea de vector.
2) Sa se calculeze partea intreaga a lui Log2(N) (logaritm in baza doi din N) fara a folosi functia predefinita de limbaj (log, ln...)
3) Sa se creeze o "matrice tabla de sah" (01) NxN fara foruri, whileuri, repeaturi. Se permite un singur If.
Ex: pentru N = 5
01010
10101
01010
10101
01010

4) Sa se creeze o "matrice spirala" NxM cu un singur ciclu (for, while, repeat) si un singur if (se va porni din exterior spre interior din coltul stanga-sus in sensul invers acelor de ceasornic)
Ex: pentru N = 5, M = 4
1|14|13|12
2|15|20|11
3|16|19|10
4|17|18| 9
5| 6| 7| 8

5) Sa se calculeze Radical(N) fara a se folosi Sqrt(), Pow() (Se cere o precizie de 2 zecimale, neaproximat)
6) Sa se genereze primiele N patrate perfecte fara a se folosi Sqr, Pow, operatorul * (sau alta instructiune ASM echivalenta: MUL)
7) Sa se sorteze un vector fara a folosi operatii de comparare (vezi sortarea prin numarare de care pomenea Martinel)
Sa se calculeze Sin(N) fara a se folosi vreo functie trigonometrica existanta in limbaj (Se cere o precizie de 2 zecimale, neaproximat)
9) Se cere sa se calculeze CMMDC a doua numere fara a se folosi / % mod div
10) Sa se transforme un numar N din baza 10 in baza 2 fara a se folosi operatorii %, mod, /, div (adunarea ar trebui sa fie singura operatie necesara)
11) Sa se calculeze al N-lea numar alcatuit din cifrele 1 si 0 fara sa se foloseasca vreo functie (procedura), sau vreun vector
12) Sa se calculeze cate numere in baza N (3<=N<=16) mai mici decat M dat (in baza 10) au cifrele distincte 2 cate 2. Nu se vor folosi functii (sau proceduri).

Iata ce propun: un nou tip de probleme - sau mai degraba probleme usoare dar care, din pricina unor restrictii devin interesante si evident mai grele.
Spre exemplu: "sorteaza un vector fara operatii de comparatii", "calculeaza log2(N) sau sin(N) fara sa folosesti functii prestabilite de limbaj", "umple o matrice dupa o regula fara sa folosesti for-uri sau while-uri (repeaturi) sau fara if-uri"...
Problemele acestea pun in principiu accentul pe complexitate memorie, sau complexitate numar de instructiuni, si/sau obliga programatorul sa gaseasca o solutie alternativa, il obliga sa-si foloseasca inventivitatea (sortarea fara comparatii este un exemplu).
Nu v-ati minunat oare cand ati auzit pentru prima data ca 2 variabile pot fi interschimbate fara una auxiliara? Problemele de acet tip nu prea au aplicabilitate (poate decat daca programati pe arhitecturi ciudate si crippled rau), dar sunt interesante daca sunt luate ca provocari, ca puzzleuri.
O parte buna a problemelor de genu este ca sunt mai usor de conceput/propus, sunt, dupa mine, mai interesante, si nu implica notiuni grele de genu programare dinamica. Sunt probleme obisnuite la care nu se cer performante, ci solutii alternative sub niste restrictii. (solutii alternative - creative/latheral thinking)
10 probleme de genu pot scrie, si daca fiecare din echipa infoarena mai coace cate 10...

Punerea in practica:
Am realizat deja evaluatorul care verifica sursele inainte ca acestea sa fie compilate si evaluate dupa evaluatorul deja existent.
Programul este scris in Pascal (stringurile mi se par hellish in c/c++)
Primeste ca parametru numele sursei de verificat (sursa.pas sursa.cpp)
Deschide fisierul de restrictii (sursa.phr) (... il si inchide)
In caz ca sursa.pas/cpp indeplineste restrictiile dorite returneaza exitcode:0 altfel 1
De aici incolo ar trebui sa plece catre evaluatorul vostru deja existent.

Sursa o dau oricarui dev infoarena care mi-o cere.
E-mail de contact (pentru orice eventualiatate): [email protected]; YMSG: madflame991

Ideea parea foarte ok... daca intreaga problema putea fi restransa la o formula era exceptional... dar nu este, mi-am dat seama dupa mult trial and error ce si cum.
5^13 este ultima putere a lui 5 care incape intr-un integer (4 byte int)
MACAR ca aproximatie bunicica ar putea fi folosita formula... am facut teste si greseste pentru numere mari undeva cam cu 8-9%, deci de la aproximatie spre numar se poate apela la un algoritm simplu de adunari repetate (sau fie... si cautare binara)

Propun o abordare fara cautare binara
Pentru P zerouri ne trebuiesc in N! sa apara 5 de P ori.
Intalnim un 5 la fiecare 5 numere, apoi intalnim un 5 in plus la fiecare 25 de numere, inca unu in plus la fiecare 125 de numere... si asa mai departe pana la 5^13 = 1220703125.
Plecand de la aceasta idee putem spune ca
P zerouri se gasesc in primele (P - (P div 5) - (P div 25) - (P div 125) - ... - (P div 5^13))*5 numere.
Rationamentul, zic eu, este corect, dar pe alocuri nu returneaza ce ar trebui.
Mi-a placut mai mult ideea aceasta deoarece algoritmul este minim...

EX: pentru P = 2 avem P * 5 = 10
               P = 7         (P - 1) * 5 = 30

Ma poate corecta cineva?