Lista de probleme 551

Se dau N numere reale considerate ca fiind razele a N discuri. Considerăm că așezăm un disc în sistemul xOy dacă îl plasăm la o coordonată x pozitivă suficient de mare, tangent cu axa Ox și deasupra ei, apoi îl împingem spre Oy până când devine tangent cu Oy sau cu primul disc așezat anterior întâlnit. În figura rezultată după așezarea tuturor discurilor în ordinea dată unele dintre ele pot fi considerate dispensabile, pentru că prin eliminarea lor nu se modifică lățimea totală a figurii, adică nici un disc nu se mai poate deplasa spre stânga. Identificați toate discurile dispensabile din figură.

Refolosirea cuvintelor care au fost scrise pe bannere publicitare mai vechi este deviza angajaților firmei publicitare “Catchy”. În magazia firmei sunt depozitate K bannere vechi. Cuvintele de pe acestea pot fi decupate integral şi reasamblate pentru a forma textul noilor bannere comandate. Caracterele speciale care separă cuvintele nu vor fi refolosite. Si-au propus să realizeze un singur banner pentru care textul este format numai din cuvinte care se află deja scrise pe bannerele depozitate în magazie. Dacă există mai multe astfel de bannere, vor alege un banner pentru care numărul de exemplare identice care pot fi realizate este maxim. Dacă şi în acest caz există mai multe bannere, se va realiza bannerul cu numărul de ordine cel mai mic.
Cunoscând textele scrise pe cele K bannere depozitate în magazia firmei, precum și textele care trebuie să fie scrise pe cele N bannere nou comandate, scrieţi un program care să determine bannerul care urmează să fie realizat, în condiţiile descrise în enunţul problemei.

Să se scrie o funcție C++ care inserează într-o listă simplu înlănțuită cu elementele ordonate crescător un nou nod care memorează valoarea x astfel încât informațiile din lista să fie în continuare ordonate crescător.

Numim număr k-binar un număr natural care în scrierea sa în baza 2 are exact k cifre de 1. De exemplu numărul 23 este 4-binar pentru că el se scrie în baza 2 sub forma 10111 și conține exact patru biți de 1. Pentru valorile date ale lui N și k, să se calculeze suma tuturor numerelor k-binare strict mai mici decât N. Deoarece sumele sunt foarte mari, acestea vor fi calculate modulo 1234567.

Să se determine o partiționare a unui șir în subșiruri zebră.

Se dau n perechi de numere naturale, m şi k. Pentru fiecare pereche să se afle câte numere naturale de m cifre, formate cu cifrele 1,2,...,k există, astfel încât prin permutarea cifrelor să devine palindroame.

În Piatra Neamț sunt N+2 locații numerotate de la 0 la N+1, de la stânga la dreapta. Distanța dintre două locații i si j este egală cu |i – j|. La început, în locațiile 0 și N+1, sunt construite benzinării, și în celelalte locații sunt case. Compania BuildNT a decis sa construiască N benzinării, una în fața fiecărei case.

Înainte să construiască o benzinărie, constructorii calculează valoarea S egală cu suma distanțelor de la fiecare casă la cea mai apropiată benzinărie, si adaugă această sumă la suma totală T. După, ei aleg o casă, la cea mai mare distanță de orice benzinărie, în fața căreia construiesc o nouă benzinărie. Casele sunt alese în așa fel încât, după construirea benzinăriilor, valoarea S recalculată sa fie minimă. Dacă sunt mai multe case ce respectă această regulă, se alege prima din stânga.
Desigur, după ce toate benzinăriile au fost construite, suma S va deveni 0 și suma totală T nu se va mai schimba.

Calculați T pentru o valoare dată N.

Turnurile din Hanoi este un joc matematic sau, dacă vreți, un puzzle. Este format din trei tije A, B și C și un număr variabil de discuri, de diferite diametre. Inițial discurile sunt așezate în ordine descrescătoare a diametrelor pe tija A, de la vârf către bază, astfel încât să formeze un turn.
Scopul jocului este acela de a muta toate discurile de pe tija A pe tija C folosind ca tijă intermediară tija B, respectând următoarele reguli:

• doar un singur disc poate fi mutat, la un moment dat
• fiecare mutare constă în luarea celui mai de sus disc de pe o tija și mutarea acestuia pe o altă tijă
• un disc cu diametrul mai mare nu poate fi poziționat deasupra unui disc cu diametrul mai mic.

Cerința

Dacă se cunoaște numărul n de discuri aflate pe tija A, să se determine șirul mutărilor necesare pentru ca toate discurile să fie mutate pe tija C.

Se dau numerele naturale nenule a, b, c, n, urmate de o secvența de n numere naturale distincte ordonate crescător, notată cu s. Scrieți în limbajul C++ definiția completă a subprogramului diofantic care returnează numărul de perechi (x,y) care verifică ecuația: a•x2 + b•y2 = c , unde x și y aparțin secvenței s.

Se consideră numerele naturale nenule X, N, K, unde N este o putere a lui 2. Pentru o permutare p = (p1,p2,…,pN) a mulțimii {1,2,...,N} se determină maximul după modelul din exemplu. Să se determine numărul permutărilor mulțimii {1,2,...,N} în care valoarea X va fi prezentă pe nivelul K, nu și pe nivelul K-1. Pentru că acest număr poate fi foarte mare, se va determina modulo 1234577.