|
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: Robot
|
Imamo robota kome se mogu zadati 3 različite komande:
- P - govori robotu da se pomeri za 1 metar unapred u pravcu u kome je okrenut,
- L - govori robotu da se okrene za 90° u levo u mestu (lokacija mu se ne menja),
- D - govori robotu da se okrene za 90° u desno u mestu (lokacija mu se ne menja).
Dato je K blokova od po N ovakvih komandi, blokovi se mogu izvršiti u bilo kom
redosledu, dok se komande unutar jednog bloka moraju izvršiti u redosledu u kome su date.
Svi blokovi se moraju izvršiti. Odrediti u koliko razliqitih redosleda izvršavanja
blokova komandi će se robot na kraju naći nazad u istom mestu iz koga je pošao.
Ulaz:
(Ulazni podaci se nalaze u datoteci robot.in.)
U prvom redu ulazne datoteke sa nalaze dva broja K i N
(1 ≤ K ≤ 8, 1 ≤ N ≤ 100.000). U sledećih K
redova nalazi se po N znakova od kojih je svaki P, L ili D.
Izlaz:
(Izlazne podatke upisati u datoteku robot.out)
U prvom i jedinom redu izlaza ispisuje se traženi broj redosleda izvršavanja blokova komandi.
Primer:
robot.in
|
|
robot.out
|
3 4
PPLP
PLPD
LPLD
|
|
1
|
Objašnjenje.
Ako je robot na početku okrenut ka severu, dati su svi mogući redosledi
izvršavanja blokova komandi i relativna pozicija robota na kraju u odnosu na početnu
tačku.
- 1 - 2 - 3 [PPLP—PLPD—LPLD] 0 metara na sever, 2 metara na zapad
- 1 - 3 - 2 [PPLP—LPLD—PLPD] 0 metara na sever, 0 metara na istok
- 2 - 1 - 3 [PLPD—PPLP—LPLD] 2 metara na sever, 2 metara na zapad
- 2 - 3 - 1 [PLPD—LPLD—PPLP] 0 metara na sever, 4 metara na zapad
- 3 - 1 - 2 [LPLD—PPLP—PLPD] 2 metara na jug, 2 metara na zapad
- 3 - 2 - 1 [LPLD—PLPD—PPLP] 2 metara na jug, 4 metara na zapad
Samo u drugom slučaju kada se blokovi izvršavaju u redosledu 1 - 3 - 2 se robot na kraju
nalazi u istoj tački odakle je počeo.
Napomena.
U 30% test primera biće K ≤ 6 i N ≤ 1000.
|
|
fajl: robot.cpp
|
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
const int MAX_K = 8;
const int XS[] = {0, 1, 0, -1};
const int YS[] = {1, 0, -1, 0};
int k, n;
string blok[MAX_K];
int dx[MAX_K];
int dy[MAX_K];
int ds[MAX_K];
int perm[MAX_K];
bool ubacen[MAX_K];
void izracunajPomeraje()
{
for(int i = 0; i < k; i++)
{
int x = 0;
int y = 0;
int s = 0;
for(int j = 0; j < n; j++)
if(blok[i][j] == 'P')
{
x += XS[s];
y += YS[s];
}
else if(blok[i][j] == 'L')
{
s += 3;
if(s >= 4)
s -= 4;
}
else
{
s += 1;
if(s >= 4)
s -= 4;
}
dx[i] = x;
dy[i] = y;
ds[i] = s;
}
}
bool proveri()
{
int s = 0;
int x = 0;
int y = 0;
for(int i = 0; i < k; i++)
{
int tx = dx[perm[i]];
int ty = dy[perm[i]];
for(int j = 0; j < s; j++)
{
int t = tx;
tx = ty;
ty = -1 * t;
}
x += tx;
y += ty;
s += ds[perm[i]];
if(s > 3)
s -= 4;
}
return (x == 0 && y == 0);
}
int permutacije(int t)
{
if(t == k)
if(proveri())
return 1;
else return 0;
int broj = 0;
for(int i = 0; i < k; i++)
if(!ubacen[i])
{
perm[t] = i;
ubacen[i] = true;
broj += permutacije(t + 1);
ubacen[i] = false;
}
return broj;
}
int main()
{
FILE *fin = fopen("robot.in", "r");
fscanf(fin, "%d %d", &k, &n);
for(int i = 0; i < k; i++)
{
char c = getc(fin);
while(c != 'P' && c != 'L' && c != 'D')
c = getc(fin);
blok[i] = "";
while(c == 'P' || c == 'L' || c == 'D')
{
blok[i] += c;
c = getc(fin);
}
}
fclose(fin);
izracunajPomeraje();
for(int i = 0; i < k; i++)
ubacen[i] = false;
int r = permutacije(0);
FILE *fout = fopen("robot.out", "w");
fprintf(fout, "%d\n", r);
fclose(fout);
}
|
|
|