Matei a inventat un nou joc cu bile. Terenul de joc este o tablă dreptunghiulară aşezată vertical. Tabla este împărţită în m*n celule, aşezate în m linii şi n coloane. În unele dintre celule se află obstacole.

De sus, din celulele aflate pe prima linie, sunt lăsate să cadă bile. Bilele cad vertical până la întâlnirea unui obstacol sau până în celula cea mai de jos din coloana pe care se află. Prima bilă care loveşte un obstacol se deplasează pe orizontală în coloana alăturată din stânga, apoi îşi continuă căderea. Fiecare dintre celelalte bile care lovesc acelaşi obstacol se deplasează pe orizontală, în coloana alăturată, dar în direcţie opusă faţă de bila care a lovit acest obstacol exact înaintea lor, apoi îşi continuă căderea.

Cerința

Cunoscând numărul de bile lăsate să cadă de pe fiecare celulă a primei linii şi poziţia obstacolelor, determinaţi numărul de bile ajunse în fiecare celulă a ultimei linii. Poziţiile obstacolelor sunt indicate prin linia şi coloana lor (colţul din stânga sus corespunde liniei 1 şi coloanei 1).

Date de intrare

Fişierul bile.in conţine pe prima linie, separate prin câte un spaţiu, numerele naturale m, n şi p (numărul de linii, numărul de coloane şi numărul de obstacole). Următoarele p linii conţin câte două numere, separate de câte un spaţiu, reprezentând poziţiile celor p obstacole. Ultimele n linii conţin câte un număr natural, reprezentând numărul bilelor lansate din fiecare celulă a primei linii (începând cu prima celulă de pe linie).

Date de ieșire

Fişierul de ieşire bile.out va conţine n linii cu câte un număr, acesta reprezentând numărul de bile din fiecare celulă a ultimei linii (începând cu prima celulă de pe această linie).

Restricții și precizări

2 ≤ m,n ≤ 2000
0 ≤ p ≤ 10.000
Se lansează maximum 1000 de bile din fiecare celulă;
Pe prima şi ultima linie, respectiv prima şi ultima coloană, nu există obstacole;
Nu există două obstacole alăturate pe linie, coloană sau diagonală.

Exemplu

bile.in

bile.out

Explicație

4	6	4	5	8	3	5
4	8	–	11	–	7	5
4	8	0	11	0	7	5
8	–	10	–	5	7	5
8	0	10	0	9	–	8
8	0	10	0	9	0	8

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 Bile3:

#include <stdio.h>
#include <stdlib.h>
struct coord
{
    int x;
    int y;
} a[10002];
int fc(const void *a, const void *b)
{
    return ((struct coord *)a)->x - ((struct coord *)b)->x;
}
int main()
{
    FILE *fi, *fo;
    int m,n,i,j,p,b[5002];
    coord t;
    fi=fopen("bile.in","r");
    fscanf(fi,"%d %d %d",&m,&n,&p);
    for(i=1; i<=p; i++) fscanf(fi,"%d %d",&a[i].x,&a[i].y);
    for(i=1; i<=n; i++) fscanf(fi,"%d",&b[i]);
    fclose(fi);
    /*for(i=1;i<n;i++)
     for(j=i+1;j<=n;j++)
       if(a[i].x>a[j].x) {t=a[i]; a[i]=a[j]; a[j]=t;}*/
    qsort(a+1,p,sizeof a[0],fc);
    for(i=1; i<=p; i++)
    {
        j=a[i].y;
        b[j-1]+=b[j]/2+b[j]%2;
        b[j+1]+=b[j]/2;
        b[j]=0;
    }
    fo=fopen("bile.out","w");
    for(i=1; i<=n; i++) fprintf(fo,"%d\n",b[i]);
    fclose(fo);
    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 #1758 Bile3

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1758 Bile3 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 #1758 Bile3