Messages posted by: ThePopivanov

longhi wrote:

ThePopivanov wrote:Вчера на натпреварот кога ја решавав оваа падна на скоро сите тест примери освен на 3.
Денеска изменив нешто ситно сега на 23 поминува а само на 7 паѓа.

Ова е greedy решение и е доста логично, па ќе добие дел од поените (инаку, како што излезе, сите ќе имаа 0 на таа задача).
Но, оваа задача е најдобро да се решава со помош на динамичко програмирање.

Идејата е доста едноставна, ќе користиме матрица dp[c][n] која ќе ни памети во колку најмногу градови може да се направи митинг ако веќе сме разгледале [c] градови и имаме уште [n] средства на располагање.
Сега, ќе ги поминуваме градовите еден по еден и ќе ја пополнуваме матрицава (како и други слични задачи кои се решаваат на ваков начин) и истата ќе содржи некаков резултат.
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x]. За се друго ќе се погрижи динамичкото програмирање. И тоа е решението.

(Постојат и други решенија за добивање на делумни поени, dfs, битмаски, итн)

Ама не разбирам оти не работи моето решение

Вчера на натпреварот кога ја решавав оваа падна на скоро сите тест примери освен на 3.
Денеска изменив нешто сега на 23 поминува а само на 7 паѓа.

MOI wrote:

ThePopivanov wrote:Средив имав некои мали грешки но ми надминува временски лимит :/

Многу BFS-а се тоа.
Ако ја прочиташ задачата уште еднаш, ќе видиш дека K <= 100, и всушност можеш да почнеш со BFS од тие позиции. Тоа е многу помал број од M*N.

Ја пишував од ново со BFS од цвеќињата ама па нејќе неможам да си ја најдам грешката :/

#include <bits/stdc++.h>
using namespace std;
int N, M, W, BC = 0;
string G[1000][1000];
int poseteno[1000][1000] = {0};
int matrix[1000][1000] = {0};
queue<pair<int, int> > red;
queue<int> far;

bool valid_move(pair<int, int> next)
{
    return (next.first >= 0 && next.first < N && next.second >= 0 && next.second < M && G[next.first][next.second][0] != '#' && G[next.first][next.second][0] != 'C');
}

vector<pair<int, int> >possible_moves(pair<int, int> node)
{
    vector<pair<int, int> > moves;
    moves.push_back(make_pair(node.first, node.second+1));
    moves.push_back(make_pair(node.first, node.second-1));
    moves.push_back(make_pair(node.first+1, node.second));
    moves.push_back(make_pair(node.first-1, node.second));
    return moves;
}

void BFS()
{
    while(!red.empty())
    {
        int mom = far.front();
        far.pop();
        pair<int, int> node = red.front();
        red.pop();
        vector<pair<int, int> > moves = possible_moves(node);
        for(pair<int, int> next : moves)
        {
            if(valid_move(next))
            {
                if(mom+1 >= W) break;
                if(poseteno[next.first][next.second] == 0)
                {
                    poseteno[next.first][next.second] = poseteno[next.first][next.second]+1;
                    red.push(next);
                    far.push(mom+1);
                }
                matrix[next.first][next.second] = matrix[node.first][node.second]+1;
            }
        }
    }
}

main()
{
    cin >> N >> M;
    cin >> W;
    string GR[N];
    for(int i = 0; i < N; i++) cin >> GR[i];
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            G[i][j] = GR[i][j];
            if(G[i][j][0] == 'C')
            {
                red.push(make_pair(i, j));
                far.push(0);
                BC++;
            }
        }
    }
    BFS();
    int NG = 0;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            NG = max(NG, matrix[i][j]);
        }
    }
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(matrix[i][j] == NG)
            {
                cout << i+1 << " " << j+1;
                return 0;
            }
        }
    }
    return 0;
}

Средив имав некои мали грешки но ми надминува временски лимит :/

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

int M, N, W;
string G[1000][1000];
int poseteno[1000][1000] = {0};

bool valid_move(pair<int, int> next)
{
    return (next.first >= 0 && next.first < M && next.second >= 0 && next.second < N && G[next.first][next.second][0] != '#');
}

vector<pair<int, int> > possible_moves(pair<int, int> next)
{
    vector<pair<int, int> > moves;
    moves.push_back(make_pair(next.first, next.second+1));
    moves.push_back(make_pair(next.first, next.second-1));
    moves.push_back(make_pair(next.first+1, next.second));
    moves.push_back(make_pair(next.first-1, next.second));
    return moves;
}

int BFS(pair<int, int> sys)
{
    int N = 0;
    memset(poseteno, 0, sizeof(poseteno));
    queue<pair<int, int> > red;
    queue<int> far;
    far.push(0);
    red.push(sys);
    while(!red.empty())
    {
        pair<int, int> node = red.front();
        int mom = far.front();
        red.pop();
        far.pop();
        vector<pair<int, int> > moves = possible_moves(node);
        for(auto next : moves)
        {
            if(valid_move(next))
            {
                if(poseteno[next.first][next.second] == 0)
                {
                    poseteno[next.first][next.second] = 1;
                    red.push(next);
                    far.push(mom+1);
                    if(mom+1 <= W)
                    {
                        if(G[next.first][next.second][0] == 'C') N++;
                    }
                    else
                    {
                        return N;
                    }
                }
            }
        }
    }
    return N;
}

main()
{
    cin >> M >> N;
    cin >> W;

string GR[M];
    for(int i = 0; i < M; i++)
    {
        cin >> GR[i];
    }
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
            G[i][j] = GR[i][j];
        }
    }
    int L = 0, P, I, J;
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(G[i][j][0] == '.')
            {
                P = BFS(make_pair(i, j));
                if(P > L)
                {
                    L = P;
                    I = i;
                    J = j;
                }
            }
        }
    }
    cout << I+1 << " " << J+1;
    return 0;
}

Ова ми е кодот не ми е јасно зошто не дава точна локација.
За првито тест пример ми дава 4, 4 а треба 1, 3.
Видов на 4, 4 (т.е 3, 3) наводнува 3 цвеќиња и на 1, 3 (т.е 0, 2) наводнува 3 цвеќиња. А направено ми е само ако најде нешто повеќе цвеќиња да смене локација бидејќи пишува ако има повеќе решенија да се испечати она најлево. Help

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

int M, N, W;
string G[1000][1000];
int poseteno[1000][1000] = {0};

bool valid_move(pair<int, int> next)
{
    return (next.first >= 0 && next.first < M && next.second >= 0 && next.second < N && G[next.first][next.second][0] != '#');
}

vector<pair<int, int> > possible_moves(pair<int, int> next)
{
    vector<pair<int, int> > moves;
    moves.push_back(make_pair(next.first, next.second+1));
    moves.push_back(make_pair(next.first, next.second-1));
    moves.push_back(make_pair(next.first+1, next.second));
    moves.push_back(make_pair(next.first-1, next.second));
    return moves;
}

int BFS(pair<int, int> sys)
{
    int N = 0;
    memset(poseteno, 0, sizeof(poseteno));
    queue<pair<int, int> > red;
    queue<int> far;
    far.push(0);
    red.push(sys);
    while(!red.empty())
    {
        pair<int, int> node = red.front();
        int mom = far.front();
        red.pop();
        vector<pair<int, int> > moves = possible_moves(node);
        for(auto next : moves)
        {
            if(valid_move(next))
            {
                if(poseteno[next.first][next.second] == 0)
                {
                    poseteno[next.first][next.second] = 1;
                    red.push(next);
                    far.push(mom+1);
                    if(mom+1 <= W)
                    {
                        if(G[next.first][next.second][0] == 'C') N++;
                    }
                    else
                    {
                        return N;
                    }
                }
            }
        }
    }
    return N;
}

main()
{
    cin >> M >> N;
    cin >> W;

string GR[M];
    for(int i = 0; i < M; i++)
    {
        cin >> GR[i];
    }
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
            G[i][j] = GR[i][j];
        }
    }
    int L = 0, P, I, J;
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(G[i][j][0] == '.')
            {
                P = BFS(make_pair(i, j));
                if(P > L)
                {
                    I = i;
                    J = j;
                }
            }
        }
    }
    cout << I+1 << " " << J+1;
    return 0;
}

И твојата надминува временски лимит, ја средив со овој код работи без проблем имав проблем со иницијализацијата

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

main()
{
int N;
cin >> N;
int A[N], zbir = 0;
for(int i = 0; i < N; i++)
{
cin >> A[i];
zbir += A[i];
}
int lz = 0, dz = 0, tr = 0;
for(int i = 0; i < N; i++)
{
if(i-1 >= 0) lz += A[i-1];
dz = zbir - A[i] - lz;

if(dz == lz)
{
tr = i+1;
break;
}
}
if(tr == 0) tr = -1;
cout << tr;
return 0;
}

Со мали измени сеа работи.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

main()
{
int N;
cin >> N;
int A[N], zbir = 0;
for(int i = 0; i < N; i++)
{
cin >> A[i];
zbir += A[i];
}
int lz = 0, dz = 0, tr = 0;
for(int i = 0; i < N; i++)
{
if(i-1 >= 0) lz += A[i-1];
dz = zbir - A[i] - lz;

if(dz == lz)
{
tr = i+1;
break;
}
}
if(tr == 0) tr = -1;
cout << tr;
return 0;
}

И јас иам таков код пишано ама не дозволува врменскиот лимит. Мојот код би требало да работи незнам оти прави проблем.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

main()
{
int N;
cin >> N;
int A[N], zbir = 0;
for(int i = 0; i < N; i++)
{
cin >> A[i];
zbir += A[i];
}
int lz = 0, dz = 0, tr;
for(int i = 0; i < N; i++)
{
lz += A[i-1];
dz = zbir - A[i] - lz;

if(dz == lz)
{
tr = i+1;
break;
}
}
if(tr == 0) tr = -1;
cout << tr;
return 0;
}

Ми дава точни резултати симнав еден тест случај што го покажува како грешка на мендо и проверив дава точен резултат.

Сигурни сте дека не ви е ставено погрешна дата за регионалниот натпревар? Пишува на 11 март а 11 март е недела, обично сабота беше O.o

Може некој пример

Здраво може некој да ми помогне околу овој вид на задачи? Барам на интернет но неможам да најдам :/
Еве задачи од овој вид.

http://mendo.mk/Task.do?id=704
http://mendo.mk/Task.do?id=629

И исто така задачата од регионалниот натпревар минатата година на која сеуште не го знам одговорот. http://mendo.mk/Task.do?id=614

Ова е мојот код. И го ставив на мендо.мк да проверам дали е точно. И на пример 7 се внесува 1 и нормално треба да се отпечати 0 оти тоа 1 ден ке се одработи во тек на тие 18 недели. И нели кажав кога го симнав инпут е 1 а излез 16.. која логика O.o

Problemot e vo toa sto kaj mene na DevC++ se kompajlira uspesno bez greska a na Mendo.mk kompajlerot go vagja ovoj eror:

Eve i kodot:

Што е грешка? Наместо да ја печати најблиската ја печати првата..