• 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 Carti

1
  • Publicat de Coss
  • în Probleme algoritmică
  • — 3 sept., 2009 at 10:27 pm

Vasile se joaca un joc foarte interesant. El are un pachet de N carti de joc (numerotate distinct de la 1 la N). Cartile din pachet sunt amestecate.
Vasile se uita la fiecare carte din pachet incepand cu prima, pana ajunge la cartea cu numarul 1, pe care o scoate din pachet. Apoi cauta cartea cu numarul 2, cartea cu numarul 3, s.a.m.d. De fiecare data incepe cautarea de unde a ramas (de la cartea care urmeaza dupa ultima carte scoasa din pachet). De fiecare data cand ajunge la sfarsitul pachetului, Vasile bate din palme si continua cautarea de la inceputul pachetului. Cand ultima carte din pachet este eliminata, jocul se termina.

Cerinta

Scrieti un program care sa determine de cate ori bate din palme Vasile in timpul unui joc.

Date de intrare

Prima linie a fisierului de intrare carti1.in contine un numar natural N, reprezentand numarul de carti din pachet. Urmatoarele N linii contin numerele cartilor de joc, in ordinea in care acestea se afla in pachet.

Date de iesire

Fisierul de iesire carti1.out contine o singura linie pe care se afla numarul cerut.

Restrictii

  • 1<=N <= 100000

Exemplu

carti1.in
3
2
1
3

carti1.out
2

carti1.in
7
3
6
7
1
5
4
2

carti1.out
3

Descrierea solutiei

Problema se poate rezolva in cel mai defavorabil caz in complexitatea O(n^2), ceea ce nu ne convine. O rezolvare pe baza acestei idiei s-ar referi la memorarea numerelor de la 1 la n intr-un vector si imitarea jocului lui Vasile.

O idee care ne-ar duce la o solutie optima este aceea de a tine un vector poz, pozitia initiala a fiecarei carti. Totul se reduce la numarul elemente care indeplinesc conditia poz[i]>poz[i+1].

Solutia problemei:

#include <iostream>
#include <fstream>
using namespace std;

#define MAX 20000

int n,i,palme,poz[MAX],x;
int main()
{
 ifstream f("carti1.in");
 ofstream g("carti1.out");
 f>>n;
 for (i=0;i<n;++i)
 {
 f>>x;
 poz[x-1]=i;
 }
 f.close();
 for (i=0;i<n-1;++i)
 if (poz[i]>poz[i+1]) palme++;
 g<<palme<<"\n";
 g.close();
 return 0;
}

P.S: Zilele urmatoare voi fi plecata, asa ca nu voi fi prea activa.

Etichete: C++joc de cartiprobleme informaticasolutie problema

— Albulescu Cosmina a scris 223 articole

Nu există o descriere a autorului.

  • Articolul anterior Madonna lesina pe scena.
  • Articolul următor Interesul utilizatorilor web pentru securitatea personala

1 Comentariu

  1. Ady spune:
    august 6, 2013 la 12:04 am

    Buna, sunt in primul an de informatica la liceu si am incercat sa fac problema carti1 de pe campion.edu.ro/arhiva, dar initial gandeam prea simplu si nu am stiut sa optimizez mainul pentru a intra in timp. Am gasit aceasta sursa si dupa ce am inteles-o am incercat sa o folosesc.. dar obtin doar 50 de puncte chiar si asa… Oare cum arata mainul corect ?
    Multumesc anticipat!


  • 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++
  • Probleme algoritmică
  • Problema Carti
  • 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