TAKMIČENJA IZ PROGRAMIRANJA


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.

robot.cpp    2,610 b      izvorni kod rešenja
robot.tests.7z    810,044 b      test primeri

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);
    
    
    
}