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

4
  • Publicat de Coss
  • în Fără categorie
  • — 24 oct., 2009 at 3:14 pm

Mircea este pasionat de programare. El a inceput sa rezolve probleme din ce in ce mai grele. Astfel a ajuns la o problema, care are ca date de intrare un tablou patratic cu n linii si n coloane, componente tabloului fiind toate numerele naturale distincte de la 1 la n2. green-box-number-puzzle

Pentru a verifica programul pe care l-a scris ii trebuie un fisier care sa contina tabloul respectiv. Dupa ce a creat acest fisier, fratele sau, pus pe sotii ii umbla in fisier si ii schimba cateva numere consecutive, cu numarul 0. Cand se intoarce Mircea de la joaca constata cu stupoare ca nu ii merge programul pentru testul respectiv. Dupa cateva ore de depanare isi da seama ca programul lui este corect si ca fisierul de intrare are probleme.

Cerinta

Scrieti un program care sa-l ajute pe Mircea, gasindu-i cel mai mic si cel mai mare dintre numerele consecutive schimbate de fratele sau.

Date de intrare

In fisierul de intrare numere.in se da pe prima linie valoarea n, iar pe urmatoarele n linii elementele tabloului, cate n elemente pe o linie, separate intre ele prin cate un spatiu, dupa modificarile facute de fratele lui Mircea.

Date de iesire

In fisierul de iesire numere.out se va scrie pe un singur rand cu un singur spatiu intre ele numerele cerute (primul fiind cel mai mic).

Restrictii

  • 0<n<=500
  • Fratele lui Mircea schimba cel putin un numar in fisier.
  • Numerele schimbate de fratele lui Mircea sunt mai mici sau cel mult egale cu 60000.

Solutie

Contrar asteptarilor, nu vom retine numerele intr-o matrice, le vom citi cu ajutorul variabilelor. Putem rezolva aceasta problema calculand suma numerelor „prezente” si numarul de numere „absente” (cele care lipsesc si au fost inlocuite cu 0). Vom calcula si suma totala a numerelor de la 1 la n*n, apoi ne vom baza pe niste observatii.

Notam:

suma  =  suma numerelor de la 1 la n*n

sumb = suma numerelor prezente

a = suma – sumb

b = numarul de numere absente

Si vom aveam urmatoarea relatie: x=(a-(b*b+b)/2)/b

Vom afisa x+1 ” ” si x+b .

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

#define max 500001

int main()
{
ifstream f("numere.in");
ofstream g("numere.out");
long long i,N,aux,auxi,suma=0,sumb=0,a,b=0,x;
f>>N;
aux=N*N;
if (aux>max) aux=max;
for(i=1;i<=aux;i++)
{
       suma+=i;
       f>>auxi;
       if (auxi) sumb+=auxi;
           else  b++;
}
a=suma-sumb;
x=(a-(b*b+b)/2)/b;
g<<<" "<
f.close();
g.close();
return 0;
}

Etichete: algoritmicaC++OJIOlimpiada InformaticaProbleme algoritmicăprobleme informatica

— Albulescu Cosmina a scris 223 articole

Nu există o descriere a autorului.

  • Articolul anterior Google Wave , o inovatie dar va fi folositor?
  • Articolul următor Review Metin2

4 Comentarii

  1. Andrei Misarca spune:
    octombrie 24, 2009 la 10:44 pm

    RaÈ›ionamentul gasit de tine este bun, insa apar cateva hibe. Avand in vedere ca problema a fost gandita pentru borland (unde nu exista long long, iar cel mai mare numar care poate fi reÈ›inut este 2^32 = 2 miliarde si un pic), este foarte posibil ca suma ta sa nu se incadreze in limite. Și in al doilea rand evita sa folosesti constante/variabile cu numele min sau max, pentru ca in clasa algorithm sunt deja definite, si daca se „intersecteaza” iese urat 😀

  2. miculprogramator spune:
    octombrie 24, 2009 la 10:47 pm

    Legat de min si max o sa le pun de-acum Min si Max, ca sa nu existe probleme.

    Ce urat e Borland-ul. 😐

  3. Avadanei Andrei spune:
    octombrie 24, 2009 la 11:32 pm

    Vezi ca nu se observa headerele incluse de tine. Foloeste pentru tagurile <> &lt; respectiv &gt;

  4. miculprogramator spune:
    octombrie 24, 2009 la 11:38 pm

    Done. 😉


  • 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
  • iunie 2022
    L Ma Mi J V S D
     12345
    6789101112
    13141516171819
    20212223242526
    27282930  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Problema Numere
  • 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