Lista de probleme 89

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#1729 Dorel

Îl cunoașteți pe Dorel cel ”priceput” la toate. Acesta și-a propus să ”strice” armonia unui șir S format din N caractere litere mică ale alfabetului englez, S=(S[1],S[2],…,S[N]).

El alege la întâmplare un caracter din șir, caracter aflat pe poziția k (1≤k≤N) și caută în stânga lui k primul caracter mai mare sau egal cu S[k], fie acesta aflat pe poziția i, S[k]≤S[i]. Dacă acesta nu există, i=1. Această alegere nu este suficientă. Dorel caută în dreapta lui k primul caracter mai mic sau egal cu S[k], fie acesta pe poziția j, S[j]≤S[k]. Dacă acesta nu există, j=N. Extrage din șirul S subșirul astfel delimitat. Ca urmare a alegerii făcute, Dorel obține două subșiruri:

  • X=(S[1],S[2],…,S[i-1],S[j+1],S[j+2],…,S[N])
  • Y=(S[i],S[i+1],…,S[j])

Cunoscând șirul S, ajutați-l pe Dorel să răspundă la Q întrebări de forma:

  • Pentru o poziție k din șirul S să se determine lungimea maximă a unei subsecvențe palindromice comune șirurilor X și Y.

În Regatul din Sud nu e niciodată prea devreme să te pregăteşti de război. De aceea, în fiecare an Regele organizează un concurs în care premiaţi sunt cei mai buni strategi. Mai întâi, Strategul Şef alege configuraţia ideală de razboi, în care armata va fi dispusă. O trupă într-o configurație e reprezentată de o literă mica din mulțimea {'a'..'z'}. De exemplu, configuraţia “ffscaam" descrie o armată formată din doi fermieri, un soldat, un cavaler, doi arcaşi şi un mag. Bineînţeles, în timpul unei lupte, trupele nu îşi vor menţine neapărat poziiţile inţiale. Cu toate acestea, orice tip de trupă poate schimba poziţia cu maxim un alt tip de trupă, ştiut de dinainte de toţi locuitorii regatului. De asemenea se ştie că arcaşii nu schimbă poziţii decât între ei. Pentru exemplul anterior, dacă un fermier sau un soldat nu schimbă poziţii decât cu un alt fermier sau soldat, configuraţii echivalente cu “ffscaam" sunt “fsfcaam" şi “sffcaam".

Fiecare strateg concurent alege o configuraţie, iar câştigătorii sunt cei care aleg configuraţii echivalente cu cea a Strategului Şef.

Călin a primit de la învățătorul lui un exerciţiu pentru a-i testa atenția și rapiditatea. Având un șir de caractere, litere ale alfabetului englez și un cuvânt, Călin trebuie să afle care este prima anagramă (un cuvânt c1 este anagramă pentru alt cuvânt c2 dacă schimbând ordinea literelor lui c1 se obține c2) a cuvântului în șir și câte anagrame sunt. Călin, fiind pasionat de informatică dorește să rezolve această problemă printr-un program.

Cunoscând șirul de caractere și cuvântul se cere:

a) să se afișeze prima anagramă a cuvântului în șir;
b) câte anagrame ale cuvântului sunt.

Grigore Moisil, 2014

#625 vraji

Harry se află într-un duel de vrăjitori și vrea să folosească cea mai puternică vrajă pe care și-o amintește în acest moment. Deoarece mai devreme a fost lovit de o vrajă a uitării, are nevoie de ajutorul vostru pentru a calcula rapid cea mai puternică vrajă dintr-un set de vrăji. Vrăjile sunt șiruri de caractere, litere mici ale alfabetului englez, fară spații între ele.
Exemple: stupefy, accio, expelliarmus, depulso, levicorpus, reductuu, coooptuus etc.

Puterea unei vrăji se calculează în funcție de numărul de vocale și de consoane pe care le are vraja, după formula: [(nrv*V+nrc*C)/nrd]+1, unde:

  • V – puterea unei vocale;
  • C – puterea unei consoane;
  • nrv – numărul de vocale din vrajă;
  • nrc – numărul de consoane din vrajă;
  • nrd – numărul de litere distincte din vrajă;
  • [a] – reprezintă partea întreagă a numărului a.

Se vor considera vocale: a, e, i, o, u, q, w, y.

Se numeşte grup o secvenţă de cel puţin două litere identice. Un grup se numeşte maximal, dacă este delimitat de litere diferite de conţinutul său, respectiv de începutul sau sfârşitul vrăjii.
Spre exemplu: în vraja coooptuus, ooo și uu sunt grupuri maximale, însă oo nu este grup maximal.

Deoarece Harry este un vrăjitor special, acesta are abilitatea de a calcula puterea fiecărui grup maximal dintr-o vrajă, și apoi să o adune la puterea acesteia. Puterea unui grup se obține înmulțind puterea literei respective cu ea însăși de același număr de ori câte litere identice are grupul.
Exemple: pentru V=5 și C=2, stupefy are puterea [(3*5+4*2)/7)]+1=3+1=4;
accio are puterea [(3*5+2*2)/4]+1+2*2=4+1+4=9;
reductuu are puterea [(4*5+4*2)/6]+1+5*5=4+1+25=30.

După lovitura primită, Harry mai știe doar N vrăji.
Se numește vrajă specială o vrajă pe care Harry își poate folosi abilitatea specială.
Exemple: accio și reductuu sunt vrăji speciale, deoarece au fiecare cel puțin un grup maximal de două litere identice;
stupefy nu este o vrajă specială deoarece nu are are niciun grup de litere identice.

Cerința

Cunoscând N, V, C și vrăjile pe care le mai știe Harry, se cere:

a)numărul total de vrăji speciale;
b)prima vrajă de putere maximă pe care Harry şi-o aminteşte, și câte astfel de vrăji poate folosi eroul nostru.

Cercetări recente au scos la iveală un vechi document scris într-un dialect ciudat denumit masaretu. Textul conţinut de acest document este format din cuvinte iar între două cuvinte există cel puţin un spaţiu.

Despre acest dialect se cunosc câteva caracteristici:

  • scrierile din acest dialect folosesc literele mici ale alfabetului englez;
  • toate cuvintele dialectului au exact opt litere;
  • cuvintele dialectului sunt formate din silabe. Fiecare silabă are două litere dintre care una este o vocală (adică una dintre literele a e i o u) iar cealaltă o consoană. Rezultă că fiecare cuvânt are patru silabe.

Din păcate documentul descoperit este deteriorat: din unele cuvinte au dispărut una sau mai multe litere. Astfel în document apar grupuri formate din mai puţin de opt litere care nu mai reprezintă cuvinte ale vocabularului dialectului masaretu.

Să se scrie un program care determină:

1) câte cuvinte corecte sunt în documentul recent descoperit.
2) silabele care apar cel mai des în cuvintele corecte din document.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1493 Masca

Se consideră alfabetul compus din literele mici, de la a la z, fără diacritice. Se numeşte cuvânt un şir finit, eventual vid, de litere din alfabet. Se numeşte mască un şir de caractere din alfabet având eventual în plus caracterele ? şi * cu următoarea semnificaţie: caracterul ? înlocuieşte oricare din literele de la a la z (o singură literă) iar caracterul * înlocuieşte un cuvânt oarecare, eventual vid, format cu litere de la a la z.

Spre exemplu avem masca a?b*c. Dacă avem 3 cuvinte şi anume abbc, acbaac şi abac atunci primele 2 se potrivesc cu masca.

Considerându-se o listă de cuvinte, să se determine:

a) Numărul de cuvinte distincte.
b) Numărul de cuvinte distincte ce se potrivesc cu o mască dată, adică se pot obţine prin înlocuirea caracterelor ? şi * din mască.

Olimpiada locală de Informatică, Prahova, 2016

Corina are un text format din mai multe cuvinte separate între ele printr-un spațiu, pentru care trebuie să utilizeze cuvintele aflate pe poziţii consecutive. Se știe că pentru două cuvinte pe care le vom numi x și y:

  • cuvântul x=x[0]x[1]...x[n-1] este prefix al cuvântului y=y[0]y[1]...y[m-1], dacă x[0]=y[0], x[1]= y[1],…, x[n-1]=y[n-1]
  • cuvântul x=x[0]x[1]...x[n-1] este sufix al cuvântului y=y[0]y[1]...y[m-1], dacă există un indice i, (0≤ i≤ m-1), astfel încât x[0]=y[i], x[1]= y[i+1],…, x[n-1]= y[m-1].

Scrieţi un program care determină pentru un text dat, format din mai multe cuvinte separate între ele printr-un spațiu, două cerințe:

  • cerința 1: câte perechi de cuvinte, notate x și y, aflate pe poziții consecutive în text au proprietatea: x este sufix al lui y sau x este prefix al lui y.
  • cerința 2 : care este perechea de cuvinte, aflate pe poziții consecutive în text, care conține cele mai multe caractere.

Urmasii lui Moisil, gimnaziu, 2017

#1999 Caps

Miruna a descoperit un nou joc. Ea dispune de litere mari și mici ale alfabetului englez și construiește succesiv șiruri de litere din ce în ce mai lungi. Ea definește operația CAPS a unei litere, ca fiind transformarea literei respective din literă mare în literă mică sau invers, din litera mică în literă mare. Pentru fiecare șir S, Miruna asociază un nou șir Sc, numit șir CAPS, care se obține aplicând operația CAPS asupra tuturor literelor din șirul S. Miruna a inventat o altă operație pentru un șir de litere S, numită NEXT, prin care obține un nou șir SN care are structura SScScS (este format în ordine de la stânga la dreapta din literele lui S, apoi de două ori succesiv literele șirului Sc, iar apoi urmează din nou literele șirului S). De exemplu, șirului S="Ham" îi corespunde șirul CAPS Sc="hAM" și dacă se aplică și operația NEXT asupra șirului S, obține șirul Sn="HamhAMhAMHam". Inițial, Miruna construiește un șir S de K litere. Apoi, ea construiește un nou șir obținut prin aplicarea operației NEXT asupra șirului S. Miruna dorește să obțină succesiv șiruri de litere din ce în ce mai lungi aplicând operația NEXT asupra șirului construit în etapa precedentă.

Astfel, pentru K=3 și S="Ham", Miruna va construi șirurile "HamhAMhAMHam", "HamhAMhAMHamhAMHamHamhAMhAMHamHamhAMHamhAMhAMHam" și așa mai departe. Miruna continuă procedeul de construire până când obține un șir final suficient de lung.

Miruna vă roagă să răspundeți la Q întrebări de tipul:

„Dacă se dă un număr natural N, ce literă este în șirul final pe poziția N și de câte ori a apărut această literă în șirul final, de la începutul șirului final până la poziția N inclusiv?”.

OJI 2017, Clasa a X-a

#2107 Pomi

În livada sa, Vasile are pomi fructiferi, organizaţi în parcele în funcţie de soi. În fiecare an, scoate la vânzare doar o parte dintre pomii adulţi dintr-o singură parcelă. Ca să asigure spaţiu de dezvoltare pentru pomii rămaşi, Vasile s-a decis să fie scoşi la vînzare numai acei pomi din parcelă al căror număr de ordine este divizibil cu o cifră k, numită cifra anului.

Cunoscând valorile a şi b, reprezentând numerele de ordine ale primului, respectiv ultimului pom din parcela din care se face vânzarea, precum şi kcifra anului, se cere să se determine numărul de pomi scoşi la vânzare de Vasile în acest an.

Olimpiada Municipala Informatica Iasi 2013

#2108 Fraze

Alina este pasionată de rebus şi literatură. Recent, a citit un articol în limba engleză despre fraze denumite pangram. O frază pangram este formată din cuvinte, separate printr-un singur caracter (spaţiu sau virgulă) şi care folosește fiecare literă din alfabetul unei limbi cel puțin o dată.
O frază pangram perfectă este o frază pangram care folosește fiecare literă din alfabet doar o singură dată. Alina se decide să stabilească frazele pangram, numărul de fraze pangram şi numărul de fraze pangram perfecte dintr-un text. Fiecare frază din text începe cu o literă mare şi se încheie cu caracterul punct.

Scrieţi un program care să determine numărul de fraze pangram, numărul de fraze pangram perfecte dintr-un text dat şi să afişeze frazele pangram în ordine lexicografică.

Olimpiada Municipala Informatica Iasi 2013