Diferențe pentru problema/paint1 între reviziile #6 si #9

paint1

Paint1 (Lot Juniori)

== include(page="template/taskheader" task_id="paint1") ==

Roberto are suflet de artist. El visează să ajungă într-o bună zi un pictor celebru, dar pentru moment își câștigă existența ca zugrav. Roberto a primit sarcina de a zugrăvi un zid având lungimea **n** metri și înălțimea un metru. Pentru aceasta are la dispoziție **m** zile. În fiecare zi **i**, el acoperă cu un singur strat de vopsea o porțiune compactă de înălțime un metru și de lungime **l[~i~]** metri, începând de la distanța **d[~i~]** metri față de capătul din stânga al zidului. Roberto știe din experiență că fiecare porțiune de zid trebuie acoperită cu cel puțin **K** straturi de vopsea pentru ca stratul final de vopsea să aibă consistența dorită. Din nefericire, firea lui de artist nu i-a permis să-și poată planifica munca în mod optim, astfel că la capătul celor **m** zile de efort, Roberto a constatat că zidul are porțiuni pe care le-a acoperit de mai mult de **k** ori și alte porțiuni pe care le-a acoperit de mai puțin de **k** ori.

Roberto are suflet de artist. El visează să ajungă într-o bună zi un pictor celebru, dar pentru moment își câștigă existența ca zugrav. Roberto a primit sarcina de a zugrăvi un zid având lungimea $n$ metri și înălțimea un metru. Pentru aceasta are la dispoziție $m$ zile. În fiecare zi [$i$], el acoperă cu un singur strat de vopsea o porțiune compactă de înălțime un metru și de lungime $l[~i~]$ metri, începând de la distanța $d[~i~]$ metri față de capătul din stânga al zidului. Roberto știe din experiență că fiecare porțiune de zid trebuie acoperită cu cel puțin $K$ straturi de vopsea pentru ca stratul final de vopsea să aibă consistența dorită. Din nefericire, firea lui de artist nu i-a permis să-și poată planifica munca în mod optim, astfel că la capătul celor $m$ zile de efort, Roberto a constatat că zidul are porțiuni pe care le-a acoperit de mai mult de $k$ ori și alte porțiuni pe care le-a acoperit de mai puțin de $k$ ori.

Pentru a recupera în proprii săi ochi dar mai ales în ochii șefului de echipă, el trebuie să afle mai întâi suprafața totală a tuturor porțiunilor de zid care mai trebuie zugrăvite.
h2. Cerință

Cunoscând lungimea zidului **n**, numărul de zile **m** și porțiunile compacte pe care le zugrăvește în fiecare zi, determinați suprafața totală a zidului care mai trebuie zugrăvită.

Cunoscând lungimea zidului [$n$], numărul de zile $m$ și porțiunile compacte pe care le zugrăvește în fiecare zi, determinați suprafața totală a zidului care mai trebuie zugrăvită.

h2. Date de intrare

Fișierul de intrare **paint1.in** conține pe prima linie trei numerele naturale **n**, **k** și **m** separate printr-un spațiu, unde **n** este lungimea zidului, **k** este numărul minim de straturi de vopsea pentru a se obține consistența dorită, iar **m** este numărul de zile în care Roberto pictează.

Fișierul de intrare $paint1.in$ conține pe prima linie trei numerele naturale [$n$], $k$ și $m$ separate printr-un spațiu, unde $n$ este lungimea zidului, $k$ este numărul minim de straturi de vopsea pentru a se obține consistența dorită, iar $m$ este numărul de zile în care Roberto pictează.

Pe următoarele **m** linii se află câte două valori naturale separate prin câte un spațiu. Numerele **d[~i~]** și **l[~i~]** de pe linia **i+1** reprezintă distanța față de capătul din stânga al zidului de la care începe să zugrăvească în ziua **i**, respectiv lungimea în metri a porțiunii de zid zugrăvite în ziua **i**.

Pe următoarele $m$ linii se află câte două valori naturale separate prin câte un spațiu. Numerele $d[~i~]$ și $l[~i~]$ de pe linia $i+1$ reprezintă distanța față de capătul din stânga al zidului de la care începe să zugrăvească în ziua [$i$], respectiv lungimea în metri a porțiunii de zid zugrăvite în ziua [$i$].

h2. Date de ieșire

Fișierul de ieșire **paint1.out** conține pe prima linie un număr natural **S** care reprezintă suprafața totală a zidului care nu a fost acoperită cu cel puțin **k** straturi de vopsea.

Fișierul de ieșire $paint1.out$ conține pe prima linie un număr natural $S$ care reprezintă suprafața totală a zidului care nu a fost acoperită cu cel puțin $k$ straturi de vopsea.

h2. Restricții

table(example).
|_. paint1.in |_. paint1.out |
| 5 2 3

  0 2
  1 3
  2 3

0 2
1 3
2 3

| 2
|

n = 5, k = 2, m = 3.
În prima zi Roberto vopsește 2 m din zid între pozițiile 0 și 2. În a doua zi Roberto vopsește 3 m din zid între pozițiile 1 și 4. În a treia zi Roberto vopsește 3 m din zid între pozițiile 2 și 5. Deci, începând cu capătul din stânga al zidului, se va găsi o porțiune de zid de lungime 1, acoperită cu un singur strat și începând de la distanța 4 față de capăt, se va găsi o altă porțiune de zid de lungime 1, acoperită cu un singur strat

== include(page="template/taskfooter" task_id="paint1") ==
 

== include(page="template/taskfooter" task_id="paint1") ==