|
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: Spajder Đura
|
Spajder Đura se nekako našao na Novom Beogradu. Nakon što je ponovo spasao svet od uništenja, rešio je da ruča. Spajder Đura, naravno najviše voli ćevape, i to u velikim količinama. Novi Beograd je, kao što je svima poznato, podeljen na blokove (N x N), i u svakom bloku se nalazi po jedna ćevabdžinica. Spajder Đuri su poznate cene ćevapa u svakom od blokova. Međutim, kako je Spajder Đura umoran, on može da preleti (kačeći se o zgrade, pomoću paukove mreže) najviše K blokova. Iz svakog bloka, on može da skoči (preleti) na bilo koji od osam susednih (znači može da se kreće dijagonalno).
Spajder Đura je čuo da se u Beogradu održava Mala olimpijada pa je rešio da takmičare priupita za pomoć, ne bi li pojeo najviše moguće ćevapa, to jest našao najjeftiniju ćevabdžinicu u okolini u kojoj se nalazi. Na nesreću, Spajder Đura ne zna gde se trenutno nalazi, pa takmičari moraju da za svaki blok pronađu najjeftiniju ćevabdžinicu udaljenu najviše K blokova.
Vaš zadatak je da za unetu matricu, koja predstavlja cene ćevapa u svakom od blokova, odredite matricu istih dimenzija čiji elementi predstavljaju najnižu cenu ćevapa u svim blokovima do kojih se može stići sa najviše K skokova (letenja).
Ulaz:
U tekstualnom faju spider.in se u prvom redu nalaze brojevi N i K, (1 ≤ N ≤ 2000, 1 ≤ K ≤ N). Zatim se u narednih N redova nalazi matrica veličine N x N, i to u svakom redu po N celih brojeva iz intervala [0..2000000000].
Izlaz:
U tekstualni fajl spider.out u N redova ispisati matricu dimenzija N x N (koja predstavlja rešenje goreopisanog problema), i to u svakom od N redova po N brojeva razmaknutih blanko znakom.
Primer:
spider.in
|
|
spider.out
|
4 1
1 2 3 4
6 5 4 3
2 3 4 5
8 7 6 5
|
|
1 1 2 3
1 1 2 3
2 2 3 3
2 2 3 4
|
|
|
fajl: spider.cpp
|
#include <stdio.h>
#include <vector>
#define MAX_N 2000
#define MAX_PRICE 2000000000L
using namespace std;
int Prefix[MAX_N*2], Suffix[MAX_N*2];
vector<int>& LinearMin(vector<int> &A, int k) {
vector<int> &Sol = *(new vector<int>(A.size()));
for (int i=0;i<A.size();i++)
Suffix[i] = (i%(2*k+1)==0)?A[i]:min(Suffix[i-1], A[i]);
Prefix[A.size()-1] = A[A.size()-1];
for (int i=A.size()-2;i>=0;i--)
Prefix[i] = ((i+1)%(2*k+1)==0)?A[i]:min(Prefix[i+1], A[i]);
for (int i=0;i<A.size();i++)
Sol[i] = min((i-k>=0)?Prefix[i-k]:Suffix[i],(i+k<A.size())?Suffix[i+k]:Prefix[i]);
return Sol;
}
int main() {
FILE *fin, *fout;
fin = fopen("spider.in", "r");
fout = fopen("spider.out", "w");
int n, k;
fscanf(fin, "%d %d", &n, &k);
vector<int> A(n+k), Sol[MAX_N];
for (int j=0;j<n;j++) {
for (int i=0;i<n;i++)
fscanf(fin, "%d", &A[i]);
for (int i=0;i<k;i++)
A[i+n] = MAX_PRICE;
vector<int> LineSol = LinearMin(A, k);
for (int i=0;i<n;i++)
Sol[i].push_back(LineSol[i]);
}
for (int i=0;i<n;i++) {
for (int j=0;j<k;j++)
Sol[i].push_back(MAX_PRICE);
Sol[i] = LinearMin(Sol[i], k);
}
for (int j=0;j<n;j++) {
for (int i=0;i<n;i++)
fprintf(fout, "%d ", Sol[i][j]);
fprintf(fout, "\n");
}
fclose(fin);
fclose(fout);
}
|
|
fajl: spider_rbtree.cpp
|
#include <stdio.h>
#include <vector>
#include <map>
#define MAX_N 2000
#define MAX_PRICE 2000000000L
using namespace std;
vector<int>& RBTreeMin(vector<int> &A, int k) {
vector<int> &Sol = *(new vector<int>(A.size()));
map<int, int> M;
for (int i=0;i<A.size()+k;i++) {
if (i<A.size())
M[A[i]]++;
if (i > 2*k) {
M[A[i-2*k-1]]--;
if (M[A[i-2*k-1]] == 0)
M.erase(A[i-2*k-1]);
}
if (i >= k)
Sol[i-k] = M.begin()->first;
}
return Sol;
}
int main() {
FILE *fin, *fout;
fin = fopen("spider.in", "r");
fout = fopen("spider.out", "w");
int n, k;
fscanf(fin, "%d %d", &n, &k);
vector<int> A(n), Sol[MAX_N];
for (int j=0;j<n;j++) {
for (int i=0;i<n;i++)
fscanf(fin, "%d", &A[i]);
vector<int> LineSol = RBTreeMin(A, k);
for (int i=0;i<n;i++)
Sol[i].push_back(LineSol[i]);
}
for (int i=0;i<n;i++)
Sol[i] = RBTreeMin(Sol[i], k);
for (int j=0;j<n;j++) {
for (int i=0;i<n;i++)
fprintf(fout, "%d ", Sol[i][j]);
fprintf(fout, "\n");
}
fclose(fin);
fclose(fout);
}
|
|
fajl: spider_basic.cpp
|
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#define MAX_N 2000
#define MAX_PRICE 2000000000L
using namespace std;
int Mat[MAX_N][MAX_N], SolX[MAX_N][MAX_N], SolY[MAX_N][MAX_N];
int main() {
int n, k;
scanf("%d %d", &n, &k);
for (int j=0;j<n;j++)
for (int i=0;i<n;i++)
scanf("%d", &Mat[j][i]);
for (int j=0;j<n;j++)
for (int i=0;i<n;i++) {
SolX[j][i] = Mat[j][i];
for (int l=max(0,i-k);l<min(n,i+k+1);l++)
SolX[j][i] <?= Mat[j][l];
}
for (int j=0;j<n;j++)
for (int i=0;i<n;i++) {
SolY[i][j] = SolX[i][j];
for (int l=max(0,i-k);l<min(n,i+k+1);l++)
SolY[i][j] <?= SolX[l][j];
}
for (int j=0;j<n;j++) {
for (int i=0;i<n;i++)
printf("%d ", SolY[j][i]);
printf("\n");
}
}
|
|
|