|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
|
|
zadatak: Vikendica
|
Dragančetu je dosadilo da živi u gradu pa je rešio da sagradi sebi vikendicu, u kojoj će
u miru i tišini moći da sprovodi svoje programerske ideje. Kako je Draganče veoma vredan,
rešio je da sam napravi nacrte njegove kuće iz snova. No, na početku je trebalo da odredi
mesto na kome će se graditi. Kako Draganče nije baš bogat (matematika i programiranje
nije bilo isplativo kako je on mislio), odredio je maksimalni budžet koji može da potroši
za kupovinu placeva. Naravno, želi da vikendica bude što lepša, pa je odredio i donju
granicu budžeta. Sad je u nedoumici gde da je sagradi. Pomozite Dragančetu da odredi broj
mogućih mesta za gradnju vikendice.
Mesta na kojima Draganče može da gradi vikendicu data su u obliku pravougane matrice,
gde polja predstavljaju placeve. Za svaki plac je data njegova cena. Vikendica je u obliku
pravougaonika. Na pravougaoniku se može sagraditi vikendica ukoliko suma njenih parcela
upada u granice budžeta.
Ulaz:
(Ulazni podaci se nalaze u datoteci vikendica.in) U prvom redu se nalaze četiri
broja: n, m, A i B, koji predstavljaju broj vrsta i kolona matrice, donju granicu i gornju
granicu budžeta. U narednih n redova nalazi se po m nenegativnih celih brojeva koji predstavljaju cene placeva.
Izlaz:
(Izlazne podatke upisati u datoteku vikendica.out) U prvom i jedinom redu štampati
broj mogućih pozicija vikendice.
Ograničenja:
- 1 ≤ n, m ≤ 150
- 0 ≤ A ≤ B ≤ 109
- cene placeva su u opsegu [0, 104]
- broj rešenja ne prelazi 230
- ukupna suma cena svih placeva je manja od 230
- vremensko ograničenje za izvršavanje programa je 1 s.
Primer 1:
vikendica.in
|
|
vikendica.out
|
3 3 2 3
1 0 0
0 1 0
0 0 1
|
|
7
|
Objašnjenje:
Moguće pozicije za vikendicu (predstavljene sa 'o') su sledeće:
oox ooo oox xxx xoo xxx ooo
oox ooo oox xoo xoo ooo ooo
xxx xxx oox xoo xoo ooo ooo
Suma elemenata u označenim pravougaonicima je u opsegu [2,3].
Primer 2:
vikendica.in
|
|
vikendica.out
|
3 4 7 10
1 3 4 2
3 4 5 2
1 3 4 1
|
|
16
|
|
|
fajl: vikendica.cpp
|
/*
DRZAVNO TAKMICENJE 2007
ZADATAK: vikendica
AUTOR: Andreja Ilic, Nis
Svaki pristup zadatku vodi do problema kako da se izracuna zbir cena u
odredjenom pravougaoniku. Zato cemo umesto samih cena placeva u matrici d pamtiti
sume odredjenih pravougaonika, tacnije element d [i][j] ce nam predstavljati
sumu cena u pravougaoniku sa temenima: (1,1), (i,1), (j,1), (i,j). Ovu sumu
mozemo racunati preko formule
d [i][j] = d [i - 1][j] + d [i][j - 1] - d [i - 1][j - 1] + cena [i][j];
Sada mozemo linearno racunati cenu bilo kog pravougaonika. U kodu, funkcija
Sum (x1, y1, x2, y2) nam vraca zbir cune u pravougaoniku cije je gornje levo polje
(x1, y1) a donje desno (x2, y2).
Vratimo se glavnom problemu. Njemu pristupamo na sledeci nacin: za svako polje
(i, j) racunamo koliko pravougaonika postoje koji zadovoljavaju trazeni uslov,
tako da je polje (i, j) bas donje desno polje. Naravno isporbacemo sve moguce sirine
pravougaonika ali za njenu duzinu necemo isporabavati sve mogucnosti. Naime, kada trazimo
broj resenja sa sirinu k mi znamo da je njena duzina sigurno manja od duzine za
sirinu k - 1 (jer su cene nenegativne, pa je samim tim i suma rastuca) tako da cemo
samo te mogucnosti isprobavati.
Dakle, napravimo funkciju koja ce nam vracati broj prvougaonika koji imaju cenu
manju ili jednaku od date vrednosti. Kao rezultat vratimo razliku tih funkvija za
vrednosti B i A - 1.
Vremenska slozenost algoritma je O (n^2 + n^3), dok je memorijska slozenost O (n^2).
*/
#include <stdio.h>
#define MaxN 205
int n, m, A, B, d [MaxN][MaxN];
FILE *in, *out;
int Sum (int x1, int y1, int x2, int y2)
{
return (d [x2][y2] - d [x1 - 1][y2] - d [x2][y1 - 1] + d [x1 - 1][y1 - 1]);
}
int Count (int Max)
{
int sol = 0, i, j, k, l;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
k = 1;
for (l = i; l >= 1; l--)
{
while ((k <= j) && (Sum (l, k, i, j) > Max))
k++;
if (k > j) break;
sol = sol + (j - k + 1);
}
}
return sol;
}
int main ()
{
int x, i, j;
in = fopen ("vikendica.in", "r");
out = fopen ("vikendica.out", "w");
fscanf (in, "%d %d %d %d", &n, &m, &A, &B);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
fscanf (in, "%d", &x);
d [i][j] = d [i - 1][j] + d [i][j - 1] - d [i - 1][j - 1] + x;
}
fprintf (out, "%d\n", Count (B) - Count (A - 1));
return 0;
}
|
|
|