Lista de probleme 663

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#687 liste

Numim listă un sir de numere naturale. Avem la dispoziţie mai multe liste aşezate, în ordine, una sub alta. Spunem că două liste L1 şi L2 sunt vecine dacă L1 este imediat deasupra lui L2, sau dacă L2 este imediat deasupra lui L1. Oricare două liste vecine L1 şi L2 pot fi unificate dacă ele au cel puţin un element comun. Prin unificare, noua listă va avea ca elemente toate elementele din L1 la care se adaugă toate elementele din L2. Listele L1 şi L2 vor dispărea şi în locul lor va apărea noua listă.

Determinaţi numărul minim de liste care rezultă după aplicarea unui număr suficient de unificări astfel încât să nu mai existe două liste vecine care să poată fi unificate.

Lot Juniori, Sibiu 2011

#686 grad

Se consideră o propoziţie formată din litere mici ale alfabetului englez şi eventual spaţii. Cuvintele sunt formate numai din litere şi sunt separate între ele prin unul sau mai multe spaţii.

Definim numărul asociat unui cuvânt c1c2...ck ca fiind un număr natural nc, obţinut ca produsul puterilor de forma pi, unde p este poziţia în alfabet a literei ci. Astfel cuvântului badab i se asociază numărul nc=21∙12∙43∙14∙25, adică nc=4096.

Definim gradul unui cuvânt c1c2...ck ca fiind numărul nr modulo k, unde nr este numărul de divizori al lui nc. Gradul cuvântului badab este 3, pentru că nr=13 (cei 13 divizori ai lui 4096 sunt: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 şi 4096), k=5 (cuvântul conţine 5 litere) şi 13 modulo 5=3.

Definim gradul unei propoziţii ca fiind suma gradelor cuvintelor existente în ea.

Să se scrie un program care pentru o propoziţie dată determină gradul ei.

Lot Juniori, Sibiu 2011

Dorești să mergi în vacanță și ai hotărât deja destinația. Formal, te afli în punctul (0,0) al unui sistem cartezian de axe și trebuie să ajungi în punctul de coordonate (X,X). Țara în care te afli are drumuri paralele cu axele de coordonate la fiecare abscisă și la fiecare ordonată număr natural. În fiecare moment, dacă eşti în punctul de coordonate (a,b), ai 2 variante de deplasare: în punctul (a,b+1) sau în punctul (a+1,b). La fiecare astfel de pas consumi un litru de carburant. Prin unele puncte de forma (a,a) nu poți trece, iar în celelalte puncte care au abscisa egală cu ordonata poți trece și în plus, acolo se află câte o stație de benzină unde poți să „faci plinul”. Prin toate punctele care nu au abscisa egală cu ordonata poți trece dar acolo nu se află stații de benzină. Rezervorul mașinii tale are o capacitate de K litri.

Determinați numărul de trasee distincte prin care poți ajunge la destinație. Două trasee sunt distincte dacă diferă prin cel puţin un punct.

Lot Juniori, Vaslui, 2014

#678 mts

Alex a accesat fonduri europene și a pus bazele unei afaceri profitabile, constând în creșterea viermilor de mătase. Viermii de mătase se hrănesc cu frunze de dud, iar Alex are mulți duzi în grădină. El a observat că dacă așează un vierme de mătase pe o frunză de dud, acesta va mânca toată frunza într-un timp care depinde doar de mărimea suprafeței frunzei.

Alex a decis să le aplice viermilor săi de mătase un test de inteligență. În acest scop, a pus în practică următorul experiment științific: pe o bară îngustă, liniară, a așezat de la stânga la dreapta n frunze de dud având suprafețele s[1], s[2], … s[n], la distanțe x[1], x[2],…, x[n] milimetri față de capătul din stânga. Alex a așezat un vierme de mătase pe frunza cu numărul de ordine k. Pentru oricare frunză i, viermele de mătase va mânca frunza în s[i] secunde, unde s[i] este mărimea suprafeței frunzei. După ce mănâncă în întregime o frunză, viermele pornește imediat cu viteza de 1 milimetru/ secundă spre următoarea frunză, care poate fi la stânga sau la dreapta sa. Altfel spus, el își poate schimba dacă e cazul, sensul de deplasare după ce mănâncă o frunză.

Alex ar dori să știe care este numărul maxim de frunze de dud pe ar putea să le mănânce în întregime cel mai inteligent vierme de mătase pe care îl are, având la dispoziție timpul de maxim t secunde.

Cunoscând n, k, t, distanțele x[1], x[2], .., x[n] și suprafețele s[1], s[2], …, s[n] cu semnificațiile descrise mai sus, să se determine numărul maxim de frunze pe care un vierme de mătase poate să le mănânce în întregime, într-un timp cel mult egal cu t, dacă este plasat inițial pe frunza k.

Lot Juniori, Vaslui, 2014

#629 Zet

Fie \(z \in R, z \neq 0\) astfel încât \(z + \frac{1}{z} = k, k \in N\).

Dându-se k și un număr natural n, se cere:

a) să calculați \(z^2 + \frac{1}{z^2}\) ;
b) să se determine \(z^n + \frac{1}{z^n}\) .

#628 Cub1

Lui Andrei îi plac foarte mult jocurile de tip puzzle. De curând, el a descoperit un joc nou: un cub de dimensiune n format din n•n•n cuburi unitate sub forma unor cămăruţe. Cubul poate fi văzut ca o matrice tridimensionala ale cărei elemente sunt cămăruţele. Două cămăruţe se numesc adiacente dacă au o faţă comună. Astfel, o cămăruţă poate fi adiacentă cu maxim 6 cămăruţe. Scopul jocului este acela de a duce o bilă din cămăruţa de coordonate (1,1,1) în cămăruţa de coordonate (n,n,n). Bila poate trece dintr-o cămăruţă în alta doar dacă acestea sunt adiacente, iar noua cămăruţă este accesibilă din cămăruţa curentă.

Cunoscând n, dimensiunea cubului şi valorile asociate fiecărei cămăruţe, determinaţi:

a) cămăruța cu un număr maxim de cămăruțe ce pot fi accesate din ea;
b) un drum de lungime minimă de la cămăruţa (1,1,1) la cămăruţa (n,n,n).

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.

Se dau N puncte în spațiul 3D prin coordonatele lor. Dorim să amplasăm două cuburi cu laturile paralele cu axele de coordonate, astfel încât fiecare punct să se afle pe una dintre feţele sau în interiorul a cel puțin unuia dintre cuburi. În plus, latura cubului de latură maximă dintre cele două trebuie să fie minimă.

Scrieţi un program care să determine latura cubului de latură maximă pentru două cuburi care realizează acoperirea mulțimii de puncte în condiţiile de mai sus.

Urmasii lui Moisil, 2014, Clasa a X-a

În premieră în acest an, pentru a putea ridica marele trofeu “Urmașul lui Moisil” vor fi necesare o serie de ștampile ce se obțin de la Primărie.

La Primăria din Iași sunt N camere numerotate de la 1 la N. În fiecare cameră există câte o ștampilă pe care apare o literă mică a alfabetului englez a-z. Pot exista camere cu același caracter pe ștampilă.

În instituţie sunt două categorii de camere, în funcţie de modul în care acordă ștampilele:

  • camere simple – se aplică ștampila camerei imediat, fără a fi necesare ştampilele din alte camere.
  • camere complicate – Mecanismul birocratic intră în acţiune! Funcţionarul unei astfel de camere i aplică ştampila pe cerere apoi solicită obţinerea în ordine a ştampilelor camerelor c[i1], c[i2] ... c[iLg], toate aceste camere având numere mai mari strict decât i. După fiecare ștampilă obținută în camerele specificate, aplică și el, încă o dată, ştampila camerei sale. Spunem că această cameră complicată este dependentă de fiecare dintre camerele din lista asociată, care pot fi la rândul lor simple sau complicate.

Pentru ca festivitatea de premiere să nu înceapă prea târziu , câștigătorul trofeului trebuie să raspundă repede la M întrebări de tipul (q,k): care este litera de pe poziția k a șirului de ștampile obținut de la camera q?

Urmasii lui Moisil, 2014, Clasa a X-a