Messages posted by: MOI

Ако сакаме да ги подредиме броевите по редоследот по кој треба да се спојуваат, кога разгледуваш два броја (на пример, A и B), и сакаш да знаеш дали е подобро првиот да оди пред вториот или обратно, можеш само да споредиш дали е подобро спојувањето A па B, или пак B па A. Со други зборови, ако имаш броеви 159 и 75, можеш да ги споредиш 15975 и 75159. За самото спојување, можеш да користиш string, бидејќи таму лесно можеш да споиш два броја со операторот +. Нешто вака:

divio wrote:Moze pomos okolu zadaca Patuvanje?
Blagodaram!

Во задачата се бара "низ колку најмалку патишта треба да се помине ...". Тој проблем, стандардно, се решава со BFS, нешто слично како наоѓање пат во лавиринт.

Во однос на тоа дека постојат тројки од населени места кои не треба да се посетат по ред, замисли дека имаш матрица d[x][y], која ќе ти чува колку најмалку патишта треба да се поминат за да се стигне до y, а последниот додаден пат е оној од x до y. Сега, кога разгледуваш можни движења од "y" па натаму, знаеш дека не смееш да се придвижиш до населено место z, доколку постои забранета тројка (x, y, z).

divio wrote:Moze pomos okolu ovaa zadaca?
Blagodaram odnapred,

Ако добро ја сфатив задачата, постојат само K (до 15) важни градови кои ни се од интерес да ги посетиме. На почеток, можеме да го искористиме алгоритамот за пронаоѓање на најкраток пат во граф од Dijkstra, и од секој од овие K градови, да го најдеме растојанието до сите останати K важни градови. Сега, добиваме нов граф кој што има само 15 темиња, бидејќи воопшто не не интересира кои други градови ги посетуваме кога патуваме, само не интересира растојанието, а тоа веќе го имаме пресметано за секој од важните градови (до секој друг).

Остатокот од решението е со динамичко програмирање.

mitkonikov wrote:Eve video koe go napraviv za ovaa zadaca!
https://www.youtube.com/watch?v=6zcFB1nIoq8

Многу интересно. Good job!

Tose Todorov wrote:http://mendo.mk/Task.do?id=10 точно ми е а ми покажува погрешен резултат за тест случај 5

Тешко вака да се каже на кое решение мислиш, без да ни го дадеш кодот. Ако погодив да го разгледувам точното, треба да смениш

во

Причината е дека подолу во кодот пристапуваш до a[i+1], што не е дефинирано (за последното i е надвор од границите на векторот).
Повеќе можеш да најдеш тука http://mendo.mk/Lecture.do?id=21 .

Искористи map-а и тоа што сите книги имаат различен број на страни, за да не ги бараш цело време позициите на книгите. Вака:

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int main()
{
    map<int, int> lokacija;
    int raspored[500001];
    int rasporedPodredeni[500001];

int N, K;
    cin >> N >> K;

for(int i=0; i<N; i++) {

int strani;
        cin >> strani;

raspored[i] = strani;
        lokacija[strani] = i;

//za sortiranje, posle
        rasporedPodredeni[i] = strani;
    }

sort(rasporedPodredeni, rasporedPodredeni + N);

for(int i=0; i<K; i++) {
        //i-tata najmala so i-tata najgolema
        int straniNaItataNajmala = rasporedPodredeni[i];
        int straniNaItataNajgolema = rasporedPodredeni[N - i - 1];

//konecnite lokacii vekje gi imame vo lokacija[], taka da samo
        //gi vrakjame nazad

int lokacijaNaItataNajmala = lokacija[straniNaItataNajmala];
        int lokacijaNaItataNajgolema = lokacija[straniNaItataNajgolema];

//swap
        int temp = raspored[lokacijaNaItataNajmala];
        raspored[lokacijaNaItataNajmala] = raspored[lokacijaNaItataNajgolema];
        raspored[lokacijaNaItataNajgolema] = temp;
    }

for(int i=0; i<N; i++) {
        cout << raspored[i] << " ";
    }

return 0;
}

lekov wrote:Ми вади погрешно на 6ти и 8ми тест случај. На 6ти тест случај кај мене печати 52. Помош?

Искрено, малку ти е покомплициран кодот од што треба за оваа задача. Може да побараш во други теми на форумов, има полесни решенија. Сепак, малку ми беше чудно што бараш најмала разлика (и тоа го тргнав), бидејќи само се бара да се отпечати максималниот број на задачи, и решението поминува точно. Еве...

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int suma_posledovatelni(int[], int, int);

int main() {
    int n, k;

scanf("%d %d", &n, &k);

int zadaci[k];
    int suma_clen[n];
    int brojaci[n];
    int rezultat = 30000000;
    int i;

for(i = 0; i < n; i++)
        suma_clen[i] = 0;

for(i = 0; i < n - 1; i++)
        brojaci[i] = 1;

brojaci[n - 1] = k - (n - 1);

for(i = 0; i < k; i++)
        scanf("%d", &zadaci[i]);

while(1) {
        int suma_zadaci[n]; // [n]
        int pocetok = 0, kraj = brojaci[0];

for(i = 0; i < n; i++) {
            suma_zadaci[i] = suma_posledovatelni(zadaci, pocetok, kraj);

pocetok += brojaci[i];
            kraj += brojaci[i + 1];
        }

int najgolema_suma = 0;
            for(i = 0; i < n; i++)
                if(suma_zadaci[i] > najgolema_suma)
                    najgolema_suma = suma_zadaci[i];

if(najgolema_suma < rezultat){
				rezultat = najgolema_suma;
			}

if(brojaci[0] == k - (n - 1))
            break;

for(i = n - 1; i > 1; i--) {
            int izlez = 0;

if(brojaci[n - 1] == 1) {
                int j;
                for(j = n - 2; j > 0; j--) {
                    if(brojaci[j] != 1 && brojaci[j + 1] == 1) {
                        brojaci[j - 1]++;
                        brojaci[j] = 1;

int l, vkupno = 0;
                        for(l = 0; l < n - 1; l++)
                            vkupno += brojaci[l];

brojaci[n - 1] = k - vkupno;

izlez = 1;
                        break;
                    }
                }

if(izlez)
                    break;
            } else {
                brojaci[n - 1]--;
                brojaci[n - 2]++;
                break;
            }
        }
    }

printf("%d\n", rezultat);
    return 0;
}

int suma_posledovatelni(int zadaci[], int n, int m) {
    int i, suma = 0;

for(i = n; i < m; i++)
        suma += zadaci[i];

return suma;
}

BATIR wrote:Mozes da obasnis kodo vo najbrzo vreme
?

Па, незнам што конкретно да дообјаснам. Ќе пробам на кратко.
Значи, ова е најобично решение со BFS (https://en.wikipedia.org/wiki/Breadth-first_search), каде што користиме ред (queue) за чување кои следни полиња треба да ги разгледаме. Отприлика оди вака: почнуваме од тие објекти кои се иницијално во барок стил (и нив ги ставаме во queue-то). Околу нив, ги наоѓаме објектите кои не се барок (тие се оние кои ќе станат барок следниот месец), и како што ги наоѓаме ги ставаме и нив во queue-то. Постапката продолжува додека не дојдеме до бараниот број објекти N.

Има само една финта во решението што може да не е јасно за некој што прв пат го гледа, тоа се низите dr[] и dc[]. Тие служат само за да не се повторуваме и да го пишуваме истиот код за "лево", "десно", "горе", "доле", туку само гледаме од овие низи кои се можните потези.

На добар пат си. Вака некако.

Што ако повеќе книги треба да се однесат на иста локација? Еве поправено решение.

Незнам во која смисла полесен со BFS, бидејќи во другата тема има решение на задачата баш со BFS.
Сепак, еве уште еден код кој што е малку пократок од другите.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int main()
{
    int L, W;
    cin >> L >> W;

int N;
    cin >> N;

queue<pair<int, int> > q;
    int city[L][W];
    memset(city, 0, sizeof(city));

int B;
    cin >> B;

for(int i=0; i<B; i++){
        int Ri, Ci;
        cin >> Ri >> Ci;

N--;
        city[Ri-1][Ci-1] = 1;

q.push(make_pair(Ri-1, Ci-1));
    }

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

while(N > 0){
        months++;

while(!q.empty()){
            int r = q.front().first;
            int c = q.front().second;

q.pop();

for(int i=0; i<4; i++){
                int nr = r + dr[i];
                int nc = c + dc[i];

if(nr >= 0 && nr < L && nc >= 0 && nc < W && city[nr][nc] == 0){
                    N--;
                    city[nr][nc] = months + 1;
                }
            }
        }

//create a new queue
        for(int i=0; i<L; i++)
            for(int j=0; j<W; j++)
                if(city[i][j] == months + 1) {
                    q.push(make_pair(i, j));
                }
    }

cout << months << endl;
    return 0;
}

Веќе има повеќе дискусии за таа задача. Еве една: http://mendo.mk/jforum/posts/list/347.page

MladenP wrote:Hi, sorry for using English, I'm from Serbia and I'm not quite fluent in Macedonian. I've been doing past JBOI problems on this site and yesterday I tried doing problem P2 2010 (Competition) and on my computer when I try a test case that gets a runtime error on this site, I get a correct answer and no error whatsoever. I don't know why that is the case, is it possible that it's a bug in the system, or that it's because of using different systems?

Could be anything, but my guess is that either 1) you're using more memory than you're allowed to (the memory limit for each problem is written in the task description), or 2) you don't initialize some variables or array. If you can't fix the problem by yourself, copy/paste your source code here, and maybe someone else will be able to find and fix it.

Koki wrote:Во ред, но ако ги земаме тековните позиции на (X,Y) секој чекор, одговорот е 19. Најпрвин ја подместуваме за (X-6), вредноста на X станува 136. Потоа, немаме друг избор да ја движиме освен повторно со ( X - 1 - ( (2*X) mod 31 ) па подместуваме за (X-25). Сега позицијата на палачинката е 111, а треба да дојде до 128. Мора да ја движиме со (X+1) начинот и тоа 17 пати. Се добива 19 од 2та чекори со ( X - 1 - ( (2*X) mod 31 ) и 17те со (X+1).

Може вака?

Koki wrote:Во случајов палачинката можеме да ја движиме за (X-6), (Y+6) или (X+1), (Y-1). Ако гледаме само за X оската (бидејќи исто се движи и на Y оската), позицијата на палачинката треба од 142 да дојде до 128. Во најмалку чекори (секунди) тоа се прави кога во 3 пати (3 чекори) ќе ја подместиме за (X-6), и тогаш палачинката ќе е на позиција 124. Сега мораме да одиме со другиот начин на движење, односно (X+1), и тоа 4 пати. Вкупно добиваме резултат 3+4=7 чекори (секунди).

Не го отворив примерот, ама мислам дека знам каде ја правиш грешката. Викаш "палачинката можеме да ја движиме за (X-6), (Y+6) или (X+1), (Y-1)", и тоа го земаш дека важи цело време. Во реалноста, за толку можеме да ја придвижиме палачинката во првиот потег. Понатаму, повторно треба да ги пресметаш можните потези ( X - 1 - ( (2*X) mod 31 ) , Y + 1 + ( (2*X) mod 31 )) или ( X+1, Y-1 ), од тековната позиција (X, Y), итн.