O colonie de N furnici a început să exploreze sistematic teritoriul din preajma muşuroiului. Furnicile se deplasează doar la dreapta sau în jos. Această parte a teritoriului a fost împătrită în zone dispuse pe linii si coloane sub forma unei matrice cu NX linii şi NY coloane. Furnicile pornesc în explorare una câte una din celula din stânga-sus a matricei. Ele merg alternativ: prima spre dreapta, a doua în jos, a treia din nou la dreapta si tot așa. La fel procedează în fiecare celulă a matricei în care ajung, ghidându-se după feromoni lăsați de celelalte furnici. Astfel prima furnică ce ajunge într-o celulă continuă drumul spre celula din dreapta, a doua furnică care ajunge în aceeași celulă o ia în jos, a treia din nou la dreapta și tot așa. Furnicile merg în acest fel până ies din matrice.

Cerința

Ce suprafaţă a matricei a rămas neexplorată dacă din muşuroi pornesc N furnici.

Date de intrare

Fișierul de intrare explorare.in conţine pe prima linie numărul natural N. A doua linie a fişierului conţine două numere naturale reprezentând NX şi NY.

Date de ieșire

Fișierul de ieșire explorare.out va conţine un număr natural reprezentând suprafaţa din teritoriu a rămasă neexplorată.

Restricții și precizări

1 ≤ N ≤ 10⁹
1 ≤ NX, NY ≤ 10⁵

Exemplu

explorare.in

4
5 6

explorare.out

Explicație

În fişier se va scrie numărul 7, acesta fiind numărul de celule nevizitate de niciuna din cele 4 furnici. Traseele urmate de furnici sunt următoarele:

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema explorare:

#include <fstream>
#define yMax 100001
using namespace std;
ifstream in("explorare.in");
ofstream out("explorare.out");
int p,nx,ny;
int n,s[yMax];
int main()
{
    in>>n>>nx>>ny;
    s[1]=n;
    for(int j=2;j<=ny;j++){
        s[j]=s[j-1]/2+s[j-1]%2;
    }
    int valInit=1;
    long long st=0;
    if(n<nx){
        st=ny*(nx-n);
        nx=n;
    }
    for(int i=2;i<=nx;i++){
        for(int j=valInit;j<=ny;j++){
            s[j]=s[j-1]/2+s[j]/2+s[j-1]%2;
            if(s[j]==0)
                valInit++;
            if(s[j]==1 && s[j-1]==1)
                break;
        }
        st=st+valInit-1;
    }
    out<<st<<endl;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2491 explorare

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2491 explorare de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2491 explorare