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

2
  • Publicat de Coss
  • în Probleme algoritmică · Tehnic
  • — 30 nov., 2009 at 12:46 am

Piata centrala a orasului Bacau are forma circulara. De jur imprejurul pietei au fost montate n felinare numerotate de la 0 la n-1. Fiecare felinar poate avea doua stari: aprins sau stins. Seara, toate felinarele se aprind simultan. Turistul Vasile T. Popescu incepe sa se plimbe de jur imprejurul pietei, pornind de la felinarul 0 spre felinarul 1, apoi de la 1 spre 2, …, de la n-2 spre n-1, de la n-1spre 0 etc, iar atunci cand trece pe langa un felinar, el executa exact una dintre urmatoarele operatii:
– daca felinarul precedent (i-1 daca i>0 sau n-1 daca i=0) este aprins, atunci schimba starea felinarului curent (daca era aprins il stinge, daca era stins il aprinde);
– daca felinarul precedent este stins, atunci starea felinarului curent ramane neschimbata.

  • Cerinta

Determinati numarul minim de operatii pe care trebuie sa le execute turistul nostru pana cand felinarele sunt aprinse din nou toate.

  • Date de intrare

Fisierul de intrare felinare.in contine pe prima linie numarul natural n reprezentand numarul de felinare.

  • Date de iesire

Fisierul de iesire felinare.out va contine o singura linie pe care va fi scris un singur numar natural reprezentand numarul minim de operatii ce trebuie sa fie executate pentru ca toate felinarele sa fie din nou aprinse.

Restrictii si observatii

2 ≤ n ≤ 5000
n este de forma 2k sau 2k+1
Turistul stinge cel putin un felinar.

  • Exemplu

felinare.in

3

felinare.out

7

  • Solutie

Putem simula pur si simplu procesul de stringere/aprindere al felinarelor si daca vom optimiza putin ne va intra in timp.

O alta observatie interesanta este aceea ca avem cazuri pentru care n = 2 ^ k , numarul fiind egal cu n * n – 1. Sau, cand n = 2^k + 1, numarul fiind egal cu n * n – n + 1.

Revin si cu o implementare cat de curand. 🙂

Etichete: C++Olimpiada InformaticaONIproblema felinareprobleme algoritmica

— Albulescu Cosmina a scris 223 articole

Nu există o descriere a autorului.

  • Articolul anterior Launch48 – ia parte la crearea si lansarea unui business online in doar 48 de ore!
  • Articolul următor Koobface Worm intreaba de Captcha

2 Comentarii

  1. andrei spune:
    mai 10, 2011 la 3:01 pm

    Sper sa nu fie gresit… am luat cazurile pt care n= 2,3,4…iar numarul de operatii a fost mereu : (2 la n)-1

  2. andrei spune:
    mai 10, 2011 la 3:05 pm

    Deoarece inafara cazului in care toate felinarele sunt stinse( caz ce nu apare ), avem toate posibilitatile de a forma siruri din faruri stinse/pornite


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