Messages posted by: stoki97

Hint za zadaca Стрелки http://mendo.mk/Task.do?id=794 koja mi nadminuva limit za 4 test slucai ...?

Zadacata Nakit od 2015 J Припреми ден 3 sto moze da se najde na ovoj link
http://mendo.mk/algoritmi/Task.do?competition=150&id=255.

Nemie jasna zosto pominuva so greedy resenie a so DP(dinamicko programiranje) resenie ne pominuva.

Ova e resenieto za koe pominuva

a ova e resenieto kade sto pagja na runtime

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

int findMin(int arr[], int n, int sum){

bool dp[n + 1][sum + 1];

for (int i = 0; i <= n; i++)
        dp[i][0] = true;

for (int i = 1; i <= sum; i++)
        dp[0][i] = false;

for (int i = 1; i <= n; i++){
        for (int j = 1; j <= sum; j++){

dp[i][j] = dp[i - 1][j];

if (arr[i - 1] <= j)
                dp[i][j] |= dp[i - 1][j - arr[i - 1]];
        }
    }

int diff = INT_MAX;
    
    for (int j = sum / 2; j >= 0; j--){
    	
        if (dp[n][j]){
            diff = sum - 2 * j;
            break;
        }
    }
    
    return diff;
}

int main() {
     
    int n, sum = 0;
     
    cin >> n;
     
    int a[n];
     
    for (int i = 0 ; i < n ; i++){
        cin >> a[i];
        sum += a[i];
    }
     
    int minVal = findMin(a, n, sum); 
	
	int large = (sum + minVal) / 2;
	int small = large - minVal;

cout << small << " " << large << endl;
     
    return 0;
}

Prasanjeto mi bese zosto zadacata e napravena samo da se resava so greedy approach a ne kako sto treba.
Ova go sogledav koga vidov deka vo zadacata pisuva da se najdi optimalnoto resenie kade sto ke ima minimalna razlika pomegju dvete grupi od nakiti no za dolniot slucaj ako odime po greedy resenieto(za koe pominuva 10/10) ke bide
14 12 10 20 22 ====> greedy (22 + 12 + 10 = 44 i 20 + 14 = 34 sto ke ispecati (34 44) no treba da bide (10 + 12 + 14 = 36 20 + 22 = 42 ) sto znaci pagja na ovoj slucaj no 10/10 pominuva na od MENDO slucaite sto ne mie jasno ....)
dodeka so DP resenieto si pecati najoptimalnoto grupiranje (36 42) no pagja na runtime za 4 slucai sto ne mie jasno zosto vaka e postavena zadacata.

Probav so matrica ama na dump pagja neznam zosto eve go kodot.

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
 
struct Node {
 
	Node(char c , bool v, int d){
		val = c;
		visited = v;
		distance = d;
	}
 
	char val;
    bool visited = false; 
    int distance = 0;
}; 
 
vector< vector<Node> > graph;
int maxR = -1, blocks = 0;
 
int n, m, startX, startY, endX, endY;
queue < pair<int, int> > q, q1;
int di[4] = {-1, 0, 0, 1}, dj[4] = {0, -1, 1, 0};
 
bool isValidPuddle (int pX, int pY){
 
    for (int x = 0; x < 4; x++){
 
            int xCor = pX + di[x] , yCor = pY + dj[x];
 
            if (xCor >= 0 && xCor < n && yCor >= 0 && yCor < m && !graph[xCor][yCor].visited && graph[xCor][yCor].val == '.'){
                return true;
        }
    }
    return false;
}
 
void bfs (int i, int j){
 
    q.push(make_pair(i, j));
    graph[i][j].visited = true;
    graph[i][j].distance = 0;
 
    while(!q.empty()){
 
        pair <int, int> curr = q.front();
        q.pop();
 
        for (int x = 0; x < 4; x++){
 
            int xCor = curr.first + di[x] , yCor = curr.second + dj[x];
 
            if (!graph[xCor][yCor].visited && xCor >= 0 && xCor < n && yCor >= 0 && yCor < m){
 
                graph[xCor][yCor].visited = true;
               	graph[xCor][yCor].distance = graph[curr.first][curr.second].distance + 1;
 
                if (graph[xCor][yCor].val == 'E'){
 
                    maxR = graph[xCor][yCor].distance;
                    return;
                }
 
                if (graph[xCor][yCor].val == '#' && isValidPuddle(xCor, yCor)){
                   	graph[xCor][yCor].visited = false;
                    blocks++;
                }
 
                if (graph[xCor][yCor].val == '.'){
                    q.push(make_pair(xCor, yCor));
                }
            }
        }
    }
    return;
}
 
void bfs2 (int i, int j){
 
     q1.push(make_pair(i, j));
     graph[i][j].visited = true;
     graph[i][j].distance = 0;
 
 
     while(!q1.empty()){
 
        pair < int, int> curr = q1.front();
        q1.pop();
 
        for (int x = 0 ; x < 4 ; x++){
 
            int xCor = curr.first + di[x] , yCor = curr.second + dj[x]; 
 
            if (!graph[xCor][yCor].visited && xCor >= 0 && xCor < n  && yCor >= 0 && yCor < m){
 
                graph[xCor][yCor].visited = true;
 
                if (graph[xCor][yCor].distance != 0){
                    blocks--;
                    maxR = max(maxR, graph[xCor][yCor].distance + 1 + graph[curr.first][curr.second].distance);
 
                    if (blocks <= 0){
                        return;
                    }
                }
 
                graph[xCor][yCor].distance = graph[curr.first][curr.second].distance + 1;
 
                if (graph[xCor][yCor].val == '.'){
                    q1.push(make_pair(xCor, yCor));
                }
 
            }
 
        }
 
     }
     return;
 
} 
 
int main() {
 
    cin >> n >> m;
 
    for (int i = 0 ; i < n; i++){
        graph.push_back(vector<Node>());
        for (int j = 0 ; j < m ; j++){
            char val;
            cin >> val;
 
            if (val == 'S'){
                startX = i, startY = j;
            }
 
            if (val == 'E'){
                endX = i, endY = j;
            }
 
            graph[i].push_back(Node(val, false, 0));
        }
    }
 
    bfs(startX, startY);
 
    if (maxR != -1){
        cout << maxR << endl;
        return 0;
    }
 
    bfs2(endX, endY);
 
    if (maxR != -1){
        cout << maxR << endl;
        return 0;
    }
 
    cout << -1;
 
    return 0;
}

Moze pokonkretno da ponudite nekoj hint za Љубов zosto napisav algoritam sto pominuva 16/20 a za ostanatite 4 test slucai pagja na limit.. Gi probav tie test slucai i tocen resultat davaat ama pagjaat na limit.

Inace toa sto pravam vo kratki crti e pustam bfs od Saso i ako najde pat do Elena toas go pecati najkratkiot pat do krajot , ako ne prebaruva bari koi mozi da se pomini niz niv i gi cuva vo mapa .

so Vtoriot BFS pocnuva od krajot odnosno od Elena i bara od tie barite koj bea zacuvani vo mapata , ako najde togas go sporeduva maximumPatot so patot do pronajdenata bara. Vo slucaj ako e pogolg patot do barata od maximumot togas go setira patot do pronajdenata bara na maximalenPat.

Mala optimizacija napraviv so toa sto gi brojam vo prviot BFS brojot na bari a potoa gi odzemam vo vtoriot i ako se potrosi brojot na bari koj bea markirani kako proodni vo prviot BFS togas prekinuva programata i pecati (-1). PAtot za (i, j) tata bara koja e pronajdena so vtoriot BFS i markirana od prviot se presmetuva taka sto patot do barata koj bese presmetan se sobira so izminatiot pat od vtoriot BFS + 1 i taka se dobiva patot od Elena do Sase preku barata.

Kodot mi fati okolu 151 red

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
  
vector< vector<char> > graph;
int maxR = -1, blocks = 0;
map  <pair<int, int>, int> visited, distances, puddles;
int n, m, startX, startY, endX, endY;
queue < pair<int, int> > q, q1;
int di[4] = {-1, 0, 0, 1}, dj[4] = {0, -1, 1, 0};
  
bool isValidPuddle (int pX, int pY){
  
    for (int x = 0; x < 4; x++){
  
            int xCor = pX + di[x] , yCor = pY + dj[x];
  
            if (xCor >= 0 && xCor < n && yCor >= 0 && yCor < m && !visited[make_pair(xCor, yCor)] && graph[xCor][yCor] == '.'){
                return true;
        }
    }
    return false;
}
  
void bfs (int i, int j){
  
    q.push(make_pair(i, j));
    visited[make_pair(i, j)] = 1;
    distances[make_pair(i, j)] = 0;
  
    while(!q.empty()){
  
        pair <int, int> curr = q.front();
        q.pop();
  
        for (int x = 0; x < 4; x++){
  
            int xCor = curr.first + di[x] , yCor = curr.second + dj[x];
  
            if (!visited[make_pair(xCor, yCor)] && xCor >= 0 && xCor < n && yCor >= 0 && yCor < m){
  
                visited[make_pair(xCor, yCor)] = 1;
                distances[make_pair(xCor, yCor)] = distances[curr] + 1;
  
                if (graph[xCor][yCor] == 'E'){
  
                    maxR = distances[make_pair(xCor, yCor)];
                    return;
                }
  
                if (graph[xCor][yCor] == '#' && isValidPuddle(xCor, yCor)){
  
                    puddles[make_pair(xCor, yCor)] = distances[make_pair(xCor, yCor)];
                    visited[make_pair(xCor, yCor)] = 0;
                    blocks++;
                }
  
                if (graph[xCor][yCor] == '.'){
                    q.push(make_pair(xCor, yCor));
                }
            }
        }
    }
    return;
}
  
void bfs2 (int i, int j){
  
     q1.push(make_pair(i, j));
     visited[make_pair(i, j)] = 1;
     distances[make_pair(i, j)] = 0;
  
     while(!q1.empty()){
  
        pair < int, int> curr = q1.front();
        q1.pop();
  
        for (int x = 0 ; x < 4 ; x++){
  
            int xCor = curr.first + di[x] , yCor = curr.second + dj[x]; 
  
            if (!visited[make_pair(xCor, yCor)] && xCor >= 0 && xCor < n  && yCor >= 0 && yCor < m){
  
                visited[make_pair(xCor, yCor)] = 1;
                distances[make_pair(xCor, yCor)] = distances[curr] + 1;
  
                if (puddles[make_pair(xCor, yCor)] != 0){
                    blocks--;
                    maxR = max(maxR, puddles[make_pair(xCor, yCor)] + 1 + distances[curr]);
  
                    if (blocks <= 0){
                        return;
                    }
                }
  
                if (graph[xCor][yCor] == '.'){
                    q1.push(make_pair(xCor, yCor));
                }
  
            }
  
        }
  
     }
     return;
  
} 
  
int main() {
  
    cin >> n >> m;
  
    for (int i = 0 ; i < n; i++){
        graph.push_back(vector<char>());
        for (int j = 0 ; j < m ; j++){
            char val;
            cin >> val;
  
            if (val == 'S'){
                startX = i, startY = j;
            }
  
            if (val == 'E'){
                endX = i, endY = j;
            }
  
            graph[i].push_back(val);
        }
    }
  
    bfs(startX, startY);
  
    if (maxR != -1){
        cout << maxR << endl;
        return 0;
    }
  
    bfs2(endX, endY);
  
    if (maxR != -1){
        cout << maxR << endl;
        return 0;
    }
  
    cout << -1;
  
    return 0;
}

Evo O(1) resenie za Koalicija :

Ako pustas resenie vo Java i ako sakas da ti pomogni nekoj treba prven da go pustis resenieto tvoe tuka za da znaeme kade e problemot ...

Moze Nekoj da mi kaze do koe mesto odat na drzavniot natprevar za MENDO

Na vlez imas: den-int ;vreme-int ;2D/3D-string ; dali e student(da/ne)-string . so if else lesno se pravi za denovite i proekcijata , zaa 30 procenti popust da go pretvorime 30%vo broj treba da go podelime so 100 30%=30/100=0.3 .Cenata ja mnozime so 0.3 za da dobieme kolku popust. I posle na cenata mu se odzema popustot, a za 2.30 h toa vo sekundi e 8280 sec .

Toa znaci ke se presretne so potokot broj 3 vo brojot 204.Znaci nemozi so 1 i 9.sea ke ti kazam kako odi

3+3)=6(+6)=12(+3)" 1+2"=15(+6)=21(+3)=24+6=30+3=33+6=39+12=51+6=57+12=69+15=84+12=96+15=111+3=114+6=120+3=123+6=129+12= 141+6=147+12=159+15=174+12=186+15=201+3=204 edinstveno potok 3 se sretnuva so potok 165