Pădurea magică din Povestea lui Negrimon este situată pe un teren dreptunghiular care poate fi privit ca o matrice cu N linii, numerotate de la 1 la N şi M coloane, numerotate de la 1 la M. Putem spune că terenul este împărţit în N * M
parcele pătrate de latură 1. În pădure trăieşte şarpele Snake care, iniţial, este lung cât K parcele şi lat cât una singură. La începutul poveştii şarpele se află pe prima linie, pe parcelele de la 1 la K, capul fiind pe poziţia K şi orientat spre est.
Snake se deplasează cu o parcelă pe secundă. Astfel, după prima secundă, şarpele se va afla tot pe linia 1, deplasat cu o poziţie spre dreapta, mai exact capul va fi în parcela K + 1. Deplasarea se face simultan cu întreg corpul.
În pădure au loc E evenimente ce pot fi de tipurile următoare:
- Apariţia unui măr la secunda
stpe liniaxşi coloanay, care va dispărea la secundaen, dacă nu este mâncat până atunci de şarpe. Snake înghite mărul când capul său ajunge în parcela care îl conţine. Mărul dispare, desigur, iar corpul şarpelui creşte instantaneu cu o unitate care îi va fi adăugată la coadă şi va ocupa aceeaşi parcelă pe care s-a aflat coada (ultima porţiune din corp) la secunda anterioară înghiţirii mărului.
- Apariţia unui schimbător la secunda
stpe liniaxşi coloanay, care va dispărea la secundaenşi care are valoareav. Când capul şarpelui ajunge în parcela schimbătorului, direcţia ulterioară de deplasare va fi dată de valoareav ∈ {1, 2, 3, 4}cu semnificaţia:1Nord (sus);2Est (dreapta);3Sud (jos);4Vest (stânga).
Schimbătorul funcţionează astfel: de exemplu, dacă Snake se deplasează spre Est şi la o anumită secundă capul acestuia ajunge într-o parcelă unde se află un schimbător cu valoarea 1, la următoarea secundă capul se va afla în parcela situată deasupra schimbătorului şi în parcela schimbătorului se află prima porţiune din corpul şarpelui.
Schimbătorul dispare exact în secunda en iar până atunci rămâne în matrice indiferent de câte ori Snake trece prin parcela acestuia. Schimbătorul va acţiona doar când capul lui Snake ajunge în parcela lui şi nu va exista nicio situaţie în care să se schimbe direcţia în sens opus celei din care vine. De exemplu, dacă direcţia lui Snake este spre Est, nu va întâlni un schimbător cu valoarea 4, care l-ar întoarce spre Vest.
În fiecare secundă s, evenimentele se petrec în acestă ordine: dispar obiectele programate să dispară în secunda s, apar obiectele ce trebuie să apară în secunda s, Snake se deplasează cu o parcelă. Dacă printr-o combinaţie nefericită de mişcări, Snake se loveşte de propriul corp, el se blochează şi aşteptă serviciul de asistenţă a pădurii.
Deoarece Snake se află într-o pădure magică, deplasarea lui respectă reguli speciale: când capul este pe ultima coloană din matrice şi se mişcă spre Est, el reapare pe aceeaşi linie, dar pe prima coloană, trăgând corpul simultan. Analog şi pentru prima coloană, când se deplasează spre Vest, capul reapare pe aceeaşi linie dar pe ultima coloană. Dacă şarpele se află pe prima linie şi se deplasează spre Nord, mişcarea va continua pe ultima linie şi aceeaşi coloană din matrice. Analog pentru ultima linie, când Snake se deplasează spre Sud, capul reapare pe prima linie şi aceeaşi
coloană. Aceste mişcări au loc doar dacă Snake nu se blochează în propriul corp.
Povestea se termină în secunda în care apare oricare dintre situaţiile: Snake se loveşte de propriul corp, caz în care el rămâne BLOCAT; toate cele E evenimente s-au produs şi nu mai există niciun obiect în matrice pentru că toate au
dispărut, caz în care rămâne un şarpe LIBER.
Cerința
În funcţie de finalul poveştii, afişaţi starea lui Snake şi harta pădurii în secunda respectivă. Pe hartă trebuie să fie marcate parcelele ocupate de corpul lui Snake, inclusiv capul.
Date de intrare
Fișierul de intrare culegere.in conține pe prima linie valorile: N – numărul de linii, M – numărul de coloane în care este împărţită pădurea, K- lungimea şarpelui şi E – numărul de evenimente din pădure, separate prin câte un spaţiu.
Următoarele E linii respectă unul dintre formatele:
1 x y st en– Apare un măr la secundast, pe liniax, coloanayşi dispare la secundaen2 x y st en v– Apare un schimbător la secundast, pe liniax, coloanay, dispare la secundaenşi are valoareav. Evenimentele sunt sortate crescător în funcţie dest.
Date de ieșire
Fișierul de ieșire culegere.out va conține pe prima linie cuvântul BLOCAT sau LIBER, în funcţie de starea lui Snake la sfârşitul poveştii. Pe fiecare dintre următoarele N linii, se vor afla M caractere din mulţimea {'.', 'O', '#'}, cu
următoarea semnificaţie : '.' – parcelă liberă, majuscula 'O' – parcelă în care se află o porţiune din corpul şarpelui, '#' – parcela în care se află capul lui Snake. Caracterul '#' va apărea o singură dată în matrice.
Restricții și precizări
2 ≤ N, M ≤ 2000; 2 ≤ K < M; 1 ≤ E ≤ 500.000;1 ≤ x ≤ N; 1 ≤ y ≤ M; 1 ≤ st < en ≤ 500.000; v ∈ {1,2,3,4}- Obiectele apar doar în parcele libere.
- Povestea începe la secunda
0.
Exemplul 1
culegere.in
4 5 3 4 1 1 5 1 5 2 1 1 2 6 3 2 2 1 2 5 2 2 4 4 3 5 4
culegere.out
LIBER O.... OO#.. ..... .....
Explicație
Secunda 0:
OO#.. ..... ..... .....
Secunda 1: apare 1 măr, deplasare spre Est
.OO#M ..... ..... .....
Secunda 2: apar 2 schimbătoare, deplasare spre Est, înghite măr, creşte coada
3OOO# 2.... ..... .....
Secunda 3: apare un schimbător pe (4, 4), deplasare spre Est şi capul apare pe prima coloană peste schimbătorul 3 din poziţia (1, 1)
#.OOO 2.... ..... ....4
Secunda 4: Nu apar şi nu dispar obiecte, deplasare spre Sud, corpul urmează acelaşi traseu ca şi capul care a fost influenţat la secunda 3 de schimbătorul cu valoarea 3; capul ajunge peste schimbătorul 2 de la poziţia (2,1)
O..OO #.... ..... ....4
Secunda 5: dispare schimbătorul de la (4, 4), deplasare spre Est deoarece capul a fost influenţat de schimbătorul cu valoarea 2 la secunda 4; dacă mărul nu ar fi fost mâncat, acum ar fi dispărut
O...O O#... ..... .....
Secunda 6: dispare primul schimbător chiar dacă acesta a fost acoperit de corpul lui
Snake, deplasare spre Est
O.... OO#.. ..... .....
Aceasta este configuraţia finală deoarece acum a dispărut şi ultimul obiect. Snake nu s-a blocat în propriul corp, deci este LIBER.
Exemplul 2
culegere.in
2 6 5 3 2 1 6 1 20 3 2 2 6 2 20 4 2 2 5 1 20 1
culegere.out
BLOCAT ...OOO ....#O
Explicație
Snake s-a blocat în propriul corp înainte să dispară ultimul obiect.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Culegere:
#include <algorithm>
#include <bitset>
#include <list>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
int GetSpaces(char *str) {
int lg, i, ans = 0;
lg = strlen(str);
for (i = 0; i < lg; ++i) {
ans += (str[i] == ' ');
}
return ans;
}
bool HasEnter(char *str) {
int lg = strlen(str);
return (str[lg - 1] == '\n');
}
bool OnlyNumeric(char *str) {
int lg = strlen(str), i;
for (i = 0; i < lg; ++i) {
if (str[i] != ' ' && str[i] != '\n') {
if (!isdigit(str[i])) {
return false;
}
}
}
return true;
}
struct Event {
int x, y, code;
Event() {
x = y = code = 0;
}
Event(int xx, int yy, int cc) {
x = xx;
y = yy;
code = cc;
}
};
#define BUFFERSIZE 500
#define MAX_TIME 500000
int N, M, K, E;
char buffer[BUFFERSIZE];
vector <Event> events;
vector <vector <int> > mymat, workmat;
vector <pair <int, int> > starttimes, endtimes;
vector <pair <int, int> > directions = {{0, 0}, {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
pair <int, int> operator+(pair <int, int> a, pair <int, int> b) {
pair <int, int> ans;
ans.first = a.first + b.first;
ans.second = a.second + b.second;
return ans;
}
void Normalize(pair <int, int> &a) {
if (a.first == 0) a.first = N;
if (a.first == N + 1) a.first = 1;
if (a.second == 0) a.second = M;
if (a.second == M + 1) a.second = 1;
}
void WriteMat() {
cout << string(5, '\n');
int i, j;
for (i = 1; i <= 2; ++i) {
for (j = 1; j <= M; ++j) {
if (mymat[i][j] == 0) {
if (workmat[i][j] != 0) {
putchar('0' + workmat[i][j]);
}
else {
putchar('.');
}
}
else {
putchar('O');
}
}
putchar('\n');
}
}
int main() {
freopen("culegere.in", "r", stdin);
freopen("culegere.out", "w", stdout);
int i;
scanf("%d %d %d %d", &N, &M, &K, &E);
assert(K < M);
events.resize(E);
starttimes.resize(E);
endtimes.resize(E);
mymat.resize(1 + N, vector <int> (1 + M));
workmat.resize(1 + N, vector <int> (1 + M));
for (i = 0; i < E; ++i) {
char t;
cin >> t;
assert(t == '1' || t == '2');
if (t == '1') {
int x, y, st, en;
scanf("%d %d %d %d", &x, &y, &st, &en);
events[i] = Event(x, y, 5);
starttimes[i] = make_pair(st, i);
endtimes[i] = make_pair(en, i);
assert(en <= MAX_TIME);
}
else {
int x, y, st, en, code;
scanf("%d %d %d %d %d", &x, &y, &st, &en, &code);
events[i] = Event(x, y, code);
starttimes[i] = make_pair(st, i);
endtimes[i] = make_pair(en, i);
assert(en <= MAX_TIME);
}
}
sort(starttimes.begin(), starttimes.end());
sort(endtimes.begin(), endtimes.end());
for (i = 1; i <= K; ++i) {
mymat[1][i] = 2;
}
pair <int, int> tail, head;
int steptail, stephead, timenow = 0, cnt = 0;
bool apple, blocked = false;
tail = make_pair(1, 1);
head = make_pair(1, K);
steptail = 2;
stephead = 2;
int sti, eni;
sti = eni = 0;
while ((sti < E || eni < E) && cnt < E) {
++timenow;
apple = false;
while(eni < E && endtimes[eni].first == timenow) {
int pos = endtimes[eni].second;
cnt += workmat[events[pos].x][events[pos].y] != 0;
workmat[events[pos].x][events[pos].y] = 0;
++eni;
}
while(sti < E && starttimes[sti].first == timenow) {
int pos = starttimes[sti].second;
assert(workmat[events[pos].x][events[pos].y] == 0);
assert(mymat[events[pos].x][events[pos].y] == 0);
workmat[events[pos].x][events[pos].y] = events[pos].code;
++sti;
}
head = head + directions[stephead];
Normalize(head);
if (mymat[head.first][head.second] != 0 && head != tail) {
blocked = true;
break;
}
if (workmat[head.first][head.second] != 0) {
int code;
code = workmat[head.first][head.second];
if (code == 5) {
apple = true;
workmat[head.first][head.second] = 0;
++cnt;
}
else {
assert(abs(stephead - code) != 2);
stephead = code;
}
}
mymat[head.first][head.second] = stephead;
if (!apple) {
if (tail != head) {
mymat[tail.first][tail.second] = 0;
}
tail = tail + directions[steptail];
Normalize(tail);
}
steptail = mymat[tail.first][tail.second];
}
if (blocked) {
printf("BLOCAT\n");
}
else {
printf("LIBER\n");
}
pair <int, int> lastpos = tail;
while (mymat[tail.first][tail.second] < 5 && mymat[tail.first][tail.second] > 0) {
steptail = mymat[tail.first][tail.second];
mymat[tail.first][tail.second] = 'O';
lastpos = tail;
tail = tail + directions[steptail];
Normalize(tail);
}
mymat[lastpos.first][lastpos.second] = '#';
int j;
for (i = 1; i <= N; ++i) {
for (j = 1; j <= M; ++j) {
if (mymat[i][j] == 0) {
mymat[i][j] = '.';
}
putchar(mymat[i][j]);
}
putchar('\n');
}
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1642 Culegere
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1642 Culegere de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!