• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Problema kperms, Campion 2009

3
  • Publicat de Andrei Avădănei
  • în C/C++ · Probleme algoritmică · Tehnic
  • — 29 ian., 2010 at 8:00 am

De curand Gigel a devenit atras de permutari, in special de acele permutari cu N elemente ce contin exact K secvente descrescatoare maximale.

Cerinta

Scrieti un program care sa determine cate permutari de N elemente cu exact K secvente descrescatoare maximale exista?

Date de intrare

Fisierul de intrare kperms.in va contine o singura linie pe care se afla numerele naturale N si K separate printr-un spatiu.

Date de iesire

Fisierul de iesire kperms.out va contine o singura linie pe care va fi scris numarul de permutari de N elemente cu exact K secvente descrescatoare maximale modulo 666013.

Restrictii

  • 2 ≤ N ≤ 1000
  • 1 ≤ K ≤ N
  • Prin secventa se intelege o succesiune de de elemente situate pe pozitii consecutive. O secventa descrescatoare este considerata maximala daca nu mai poate fi adaugat in secventa un element (evident, la unul dintre capetele secventei) astfel incat secventa sa ramana descrescatoare.

Exemple

kperms.in kperms.out Explicatie
4 2 11 Cele 11 permutari sunt:

1 4 3 2
2 1 4 3
2 4 3 1

3 1 4 2
3 2 1 4
3 2 4 1
3 4 2 1
4 1 3 2
4 2 1 3

4 2 3 1
4 3 1 2

Solutie

Aceasta problema are nevoie de o tehnica ce se bazeaza pe programare dinamica. Vom considera
Vom considera :
d[i][j] = cate permutari de i elemente cu j secvente descrescatoare maximale

Presupunem ca avem o permutare cu i-1 elemente si cu j secvente descrescatoare maximale. Observam ca putem insera elementul i intre i pozitii (la inceput, la sfarsit, sau intre oricare 2 elemente consecutive).
Daca introducem pe i inaintea uneia dintre cele j secvente numarul de secvente descrescatoare va ramane la fel
iar daca inseram in celelalte i – j + 1 pozitii numarul de secvente descrescatoare creste cu 1.

Recurenta va ajunge astfel:

d[1][1] =1 
d[i][j] = (i – j + 1) * d[i – 1] [j – 1]  + j * d[i – 1][ j ]  

Rezolvarile mele difera putin, eu am folosit doua abordari mai „ciudate”, ca de obicei. In ambele situatii m-am folosit de faptul ca datorita recurentei dezvoltate mai sus, vom avea nevoie de doar de ultimile doua linii din matrice.

In primul caz am folosit doi pointeri cu care am jonglat pentru a schimba intre ele liniile, prima devenind ultima si invers.Solutia o puteti descarca de aici.
Cea de-a doua situatie se bazeaza pe acelasi lucru, doar ca am folosit doar un singur vector si doua variabile care schimba pozitiile indicilor si muta locatiile la inceputul vectorului sau la pozitia n+ceva .Solutia a doua o puteti descarca aici.

Etichete: .campionalgoritmicainformaticakpermsOJIONIProbleme algoritmică

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior Cea mai populara parola este…
  • Articolul următor Sa lucram cu fisiere .htaccess

3 Comentarii

  1. Andrei Dumbrava spune:
    ianuarie 29, 2010 la 2:09 pm

    Pff… mi-e dor de campion… cate nopÈ›i nedormite si cate petreceri neonorate din cauza campionului (imi placea mai mult sa stau cu „echipa” de matefizinformaticieni decat sa-i fi vazut pe alÈ›ii cum dau la raÈ›e si la colÈ›u blocului)

  2. Avadanei Andrei spune:
    ianuarie 30, 2010 la 9:34 pm

    Da e frumos. De ce nu mai lucrezi? Cine te opreste?Nu e neaparat nevoie sa intri la finala ci doar sa te „incalzesti”.Mai este algoritmiada pe infoarena care este si pentru studenti. 🙂

  3. Tweets that mention Problema kperms, Campion 2009 | WorldIT -- Topsy.com spune:
    ianuarie 31, 2010 la 6:38 am

    […] This post was mentioned on Twitter by Avadanei Andrei and Avadanei Andrei, Andrei Avadanei. Andrei Avadanei said: Problema kperms, Campion 2009 http://bit.ly/dvtg5G #WorldIT […]


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • mai 2022
    L Ma Mi J V S D
     1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Problema kperms, Campion 2009
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons