Messages posted by: VlatkoSh

despotovski01 wrote:
Нека N се парите што ги имаме, и нека имаме 2 градови опишани со вредностите P1 R1 и P2 R2 и нека важи дека R1 > R2. Да претпоставиме дека ...

Fala za objasnuvanjeto, nema podobro od dokaz!

#include <bits/stdc++.h>
using namespace std;

inline long long pow10(int p) {
    long long res = 1;
    while (p > 0) {
        res *= 10;
        --p;
    }
    return res;
}

int main() {

long long _n;
    int k;
    cin >> _n >> k;

// zabelezi deka brojot od inputot go zgolemuvame za 1
    // ova olesnuva mnogu raboti bidejki se bara najmaliot <pogolem> broj
    string n = to_string(_n + 1);

// polesno se raboti ako n e reverse-nat
    reverse(n.begin(), n.end());

// gi broime sedumkite
    int num7 = 0;
    for (char ch : n) {
        if (ch == '7') {
            ++num7;
        }
    }

// zabelezi deka n e reverse-nat (najmalata cifra e za
    // edinici, slednata za desetki, i taka natamu)
    int i = 0;

while (num7 < k && i < n.length()) {
        //cout << "n: " << n << " ; num7: " << num7 << '\n';
        if (n[i] < '7') {
            n[i] = '7';
            ++num7;
            for (int j = 0; j < i; ++j) {
                if (n[j] != '7') {
                    if (num7 < k) {
                        n[j] = '7'; // bidejki treba da dodademe uste sedumki
                        ++num7;
                    } else {
                        n[j] = '0'; // bidejki go barame najmaliot pogolem broj
                    }
                }
            }
            ++i;
        } else if (n[i] > '7') {
            reverse(n.begin(), n.end());
            // stoll pretvoruva string vo long long
            // vsusnost sledniov red ja zgolemuva cifrata na i-tata pozicija za 1
            // go pravam vaka vo slucaj n[i] da e 9, pa neli treba i slednite
            // cifri da se smenat i slicno... vaka e polesno
            _n = stoll(n) + pow10(i);
            n = to_string(_n);
            reverse(n.begin(), n.end());
            // sega bidejki se smenija tolku raboti, pocnuvame od novo
            num7 = 0;
            for (char ch : n) {
                if (ch == '7') {
                    ++num7;
                }
            }
            i = 0;
        } else {
            ++i;
        }
    }

while (num7 < k) {
        // sme stignale do krajot na n
        n += '7';
        ++num7;
    }

reverse(n.begin(), n.end());

cout << n << '\n';

}

Vo dobra nasoka si so toa sto probuvas da go konstruiras brojot na "greedy nacin". Moeto resenie na povrsinata izgleda dosta slicno so tvoeto, ama tvoeto resenie ima nekakvi propusti vo toa kako go konstruiruva brojot. Ti preporacuvam da pocnes od novo, odnosno probaj da go napises toa sto go imas vo glava na drug nacin, bidejki si vo dobra nasoka.

longhi wrote:
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x].

Ne razbiram zosto gi sortiruvas po R[x] a ne po P[x]?

Gresna ti e postapkata... tvojot kod bi napravil 2^n operacii, a n <= 36. 2^36 e ogromen broj.

Razgledaj za Meet In The Middle.

Mislam deka treba da se znae sto se bitmaski i osnovni bitni manipulacii za da mozes da ja resis zadacava. Eve ti link ako ne znaes sto se.

Koga ke znaes sto se tie, zadacata e relativno lesna.

Zapisi gi prvite nekolku "srekni" broevi:

Seka napisi gi prvite nekolku broevi i nivnite binarni reprezentacii:

Probaj da gi povrzes nekako.

Ja resiv posle 4 meseci

Treba BFS i da se najde nacin voopsto da ne se razgledaat polinjata sto znaeme deka sme gi dodale vekje.

Ne mozam da razberam sto sakas da napravis, ni vo tekstot ni vo kodot. Ako uspees da go resis na tvojot nacin, super, ama ne znam zosto nekoj bi se macel da ti bara popravka vo kodot?

Jas go resiv vaka (vo slucajot deka ne moze direktno da se stigne od Sase do Elena):

0) Pustas BFS od Sase, a potoa BFS od Elena. Dvete se na istata dist matrica. Isto taka sakame da znaeme dali nekoe pole e na "stranata na Sase" ili na "stranata na Elena". Ova moze da go napravis ako koristis nekoja druga matrica i stavas na primer sign[r][c] = 'S' ili sign[r][c] = 'E' za vreme na BFSto.

1) Odi kaj sekoe pole sto e baricka. Neka koordinatite se r i c. Sakame da vidime dali ako go izbriseme ova pole ke moze da se stigne od Sase do Elena. Ako moze, sakame da go najdeme najdolgiot pat za toa. Ovoj broj e odgovorot za zadacata. Neka se vika ovoj broj ans. Na pocetok ans = 0.

2) Probaj gi site mozni parovi na sosedni polinja (na pr. (r-1, c) i (r+1, c) za toa nad i pod, ili pak (r-1, c) i (r, c+1) za toa nad i toa desno, i slicno). Na primer neka gi probuvame (r1, c1) = (r-1, c) i (r2, c2) = (r+1, c). Togas ako ovie koordinati ne se baricka, i ako ednoto bilo stignato od Sase, a drugoto od Elena, pravime ans = max(ans, dist[r1][c1] + 1 + dist[r2][c2]). (edinicata vo sredina e deka go pominuvame samoto pole (r, c))

Da, najverojatno toa e. Dali ima nekoj drug nacin da se implementira dinamicko? (deka toa go rece MOI) Ili dali moze da se resi na drug nacin? Nemam ideja vekje.

Probav dinamicko ama dobiva Runtime Error na povekje testovi (izgleda bara premnogu memorija?): https://pastebin.com/S4TG5782
Isto taka probav Meet In The Middle, sto e pobrzo ama dobiva Runtime Error na istite testovi: https://pastebin.com/34V0q9GH
Moze da mi pomogne nekoj?

Eve ti go relevantniot del od kodot:

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

int R, C;
char grid[1002][1002];
int dist[1002][1002];
vector<pi> guards;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

inline bool in(int r, int c) {
  return r >= 1 && r <= R && c >= 1 && c <= C;
}

void bfs1() {
  memset(dist, -1, sizeof(dist));
  queue<pi> q;
  for (pi& p : guards) {
    dist[p.first][p.second] = 0;
    q.push(p);
  }
  while (!q.empty()) {
    pi top = q.front(); q.pop();
    int r = top.first, c = top.second;
    for (int d = 0; d < 4; ++d) {
      int r1 = r + dr[d], c1 = c + dc[d];
      if (in(r1, c1) && grid[r1][c1] != '*' && dist[r1][c1] == -1) {
        dist[r1][c1] = dist[r][c] + 1;
        q.emplace(r1, c1);
      }
    }
  }
}

int main() {
  cin >> R >> C;
  for (int r = 1; r <= R; ++r) {
    for (int c = 1; c <= C; ++c) {
      cin >> grid[r][c];
      if (grid[r][c] == 'R') {
        //...
      } else if (grid[r][c] == 'Z') {
        //...
      } else if (grid[r][c] == 'G') {
        guards.emplace_back(r, c);
      }
    }
  }
  bfs1();
  //...
}

Pretpostavuvam deka ne mora nesto kako BigInt da se koristi?

Dodeka ja procesiras matricata, dodaj gi koordinatite na sekoj zatvorenik vo queue. Potoa pravis normalno bfs, ama namestno od eden izvor (pocetna pozicija), od poveke izvori istovremeno. Nesto vaka:

Taka ke bide isto brzo kako da bi bilo od eden izvor, (kako sto ti planirase da pravis za sekoj zatvorenik). Inaku na dobar pat si.