Lista de probleme 36

Filtrare

Dificultate

Operații intrare/ieșire

Etichete

Zoli joacă cu un labirint de dimensiune N x N, format din camere de dimensiune 1 x 1, inițial toate inaccesibile. Auzind că Zoli este mare informatician, Dănutz și D’Umbră au decis să îl pună la încercare, după cum urmează:

1 x y: Dănutz transformă camera inaccesibilă (x, y) într-una accesibilă.
2 x1 y1 x2 y2: D’Umbră îl întreabă pe Zoli care este numărul minim de camere ce trebuie traversate pentru a ajunge din camera accesibilă (x1, y1) în camera accesibilă (x2, y2).

#2493 recc

Ana Mia are o recurență liniară de forma P[N] = A[1]*P[N-1] + A[2]*P[N-2] + A[3]*P[N-3] + A[4]*P[N-4], N ≥ 5. Studiind-o, îi vine o idee MAXIMĂ de problemă: “Pentru câte cvadriplete (P[1], P[2], P[3], P[4]) din mulțimea numerelor naturale [1, B] valoarea P[N] modulo K are valoarea X?”

Se consideră un șir T de segmente în plan, ale căror extremități au coordonate numere întregi. Considerând subșirul SS al segmentelor care nu conțin alte puncte coliniare de coordonate numere întregi, în afară de extremități, să se determine lungimea subșirului maximal crescător al șirului SS, unde relația de ordine crescător(Si, Sj) se traduce prin Lungimea(SSi)<=Lungimea(SSj).

#2018 rogvaiv

Vecinul meu, Dorel, tocmai s-a mutat la casă şi vrea să-şi vopsească gardul. Fiind îndrăgostit de frumos, a cumpărat 7 cutii de vopsea: roşu, orange, galben, verde, albastru, indigo şi violet. Acum însă, are o dilemă: în câte moduri poate vopsi cele n uluci ale gardului, ştiind că fiecare ulucă poate fi vopsită cu oricare dintre culorile cumpărate?

Se dă un mesaj care conţine cel mult 100.000 de caractere, litere mari ale alfabetului englez.
Să se determine cea mai lungă subsecvenţă palindrom din cadrul mesajului.

OLI 2016, judetul CLUJ

#2627 h1

Se dau două șiruri de numere naturale a[1], a[2], …, a[n] și b[1], b[2], …, b[m]. Să se determine câte numere distincte au în comun cele două șiruri. De exemplu, șirurile a=(2,5,1,4,5,1) și b=(1,1,1,3,7,5) au în comun două numere distincte: 1 și 5.

#2338 skipass

La un parc de sporturi de iarnă au venit G grupuri de schiori numerotate de la 1 la G. Aceștia coboară pe
una dintre cele 2 pârtii disponibile dar urcă cu același teleschi. Teleschiul folosește T-bar-uri, o modalitate eficientă de a urca schiorii pe vârful pârtiei.

Un T-bar poate trage maxim 2 schiori odată. Deoarece sunt 2 pârtii, se formează 2 rânduri de oameni de-o parte și de alta a punctului de urcare în teleschi. Se știe că 2 schiori nu vor folosi același T-bar decât dacă fac parte din același grup. De asemenea, niciun schior nu se baga în fața altuia (toți sunt foarte corecți și răbdători). Atunci când un T-bar sosește, primul om de la una dintre cozi se urcă în el și pleacă sau așteaptă să se
urce încă cineva (din același grup cu el). Acest al doilea schior trebuie sa fie totuși primul de la coada lui (nimeni nu se bagă în față).

Care este numărul minim de T-bar-uri ce trebuie folosite astfel încât toți schiorii de la ambele rânduri să ajungă în vârful pârtiei?

#2629 h3

Tocmai ai primit cadou de ziua ta un șir de numere naturale a[1], a[2], …, a[n]. Ca să te simți împlinit, trebuie să determini lungimea maximă a unei secvențe cu proprietatea că oricare două valori din secvență sunt distincte. Determină lungimea maximă cerută și anul viitor vei mai primi un șir!

#1692 Calafat

Se dă un șir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvență cuprinsă între 2 indici st si dr considerăm distanța dintre indicii primei și ultimei apariții ale acesteia în cadrul subsecvenței. Dându-se M subsecvențe de forma [st,dr], se cere să se calculeze suma distanțelor corespunzătoare tuturor valorilor distincte din subsecvență.

O matrice pătratică de dimensiuni N x N cu liniile și coloanele indexate de la 1 la N se numește matrice șmecheră de Calafat dacă pe fiecare linie și fiecare coloană există exact două valori de 1, restul elementelor fiind 0.

Având două matrice șmechere de Calafat notate cu A și B, se cere ca prin interschimbări de linii și coloane să se transforme matricea B în matricea A.

ONI 2016, clasele XI-XII