Messages posted by: MOI

petarsor wrote:зошто во делот за интернационални натпревари нема задачи од ЈБОИ 2017?
има од сите други години

Ги има и задачите од ЈБОИ 2017 (под име ЕЈОИ), бидејќи натпреварите ЈБОИ и ЕЈОИ се оддржаа во исто време.

Цитат од сајтот на ЗИМ лани: http://cs.org.mk/index.php/novostin/329-jboi-ejoi-2017-medali
"По урнекот на досегашните јуниорски балкански олимпијади, оваа година за прв пат се организираше и Европска јуниорска олимпијада по информатика (ЕЈОИ), која се одржа заедно со ЈБОИ 2017 во Софија, Бугарија."

Тео wrote:Пробувам да ја решам задачата спот од МОИ, ама работи само на 2/20 тестови (останатите се со погрешен резултат). Од секое поле пуштам рекурзија за да наоѓа уште можни начини.

Незнам што сакаш да направиш во функцијата rek(), таму имаш грешка. Веројатно сакаш да направиш нешто вака (види поправен код долу):

#include <bits/stdc++.h>
 
typedef long long ll;
 
#define pb push_back
#define MS(x,y) memset((x),(y),sizeof((x)))
 
using namespace std;
 
int mat[25][25];
int n,m;
bool vis[22];
 
int rek(int i, int j) {
    if (i < 0 || i >= n || j < 0 || j >= m) return 0;
    if (mat[i][j] == 0) return 0;
    if (vis[mat[i][j]]) return 0;
     
    vis[mat[i][j]] = true;
     
    int set_count = 0;
    for (int k = 1; k<=21; k++) {  
        if (vis[k]) set_count++;
    }
     
    if (set_count == 21) {
        vis[mat[i][j]] = false;
        return 1; //all set already
    }
 
    int ret = 0;
    ret += rek(i-1, j);  
    ret += rek(i+1, j);  
    ret += rek(i, j-1);  
    ret += rek(i, j+1);  
     
    vis[mat[i][j]] = false;
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin>>n>>m;
 
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<m; j++) {
            string str;
 
            cin>>str;
 
            if (str == "___") mat[i][j] = 0;
            else {
                int a = str[1] - '0';
                a *= 10;
 
                int b = str[2] - '0';
 
                mat[i][j] = a+b;
            }
        }
    }
 
    int res = 0;
 
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<m; j++) {
            if (!mat[i][j]) continue;
 
            MS(vis, 0);
 
            res += rek(i, j);
        }
    }
 
    cout<<res<<endl;
 
    return 0;
}

Сега веќе не дава "Погрешен одговор", и поминува на повеќе тест случаи. Но, постојат многу начини кои твојата рекурзија треба да ги испита.
Идеја: Што ако користиме динамичко програмирање, или со помош на битови како 0001010100..11010 (каде битот означува посетеност vis) се обидеме да не пресметуваме одредени патишта повеќе пати?

VlatkoSh wrote:Каде е грешката?

Треба да е /2, наместо /4. Види подолу (заменив /4 со /2).

Не ти е баш точно ова: Бројот на парови е: (X над 2)/2 (секој пар ќе се одбере 2 пати)
https://en.wikipedia.org/wiki/Combination

shellcode wrote:Здраво. Ако може некој да ми помогне со идеја за решение за задачава: http://codeforces.com/contest/934/problem/C. Го прочитав едиторијалот, но е многу краток и не го разбирам воопшто(http://codeforces.com/blog/entry/57763). Благодарам однапред.

Прво се мислев да земам да објаснувам, ама после ми текна дека е веројатно подобро само да те насочам, бидејќи веќе читаш објаснувања на англиски.
Имено, после секој натпревар, на Codeforces има и коментари од други натпреварувачи, па често можеш таму да најдеш и подетални објаснувања. На пример, за твојата задача:
http://codeforces.com/blog/entry/57721?#comment-414134
http://codeforces.com/blog/entry/57763?#comment-414192

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

VlatkoSh wrote:Се разбира, можеби има друго решение кое не го гледам (делов на којшто заглавив ми изгледа претежок за задача на регионален). Ако може помош???

Види тука: http://mendo.mk/jforum/posts/list/547.page

VlatkoSh wrote:

Не е сложено решението воопшто; како што кажав, само динамичко програмирање.

Динамичко програмирање не е лесно.

Главниот проблем е да се смисли решението (што беше објаснето погоре), а реализацијата е полесна. Тоа сакав да кажам.

BATIR wrote:Moze mal hint okolu popravka na mojot kod za Lotarija. Nikako ne mi pominuva:
http://mendo.mk/Task.do?id=783

Во задачата пишува "доколку некој број се повтори повеќе пати во седумте извлечени (добитни) броеви, тој треба да се повтори (најмалку) толку пати и на ливчето.".
Кога користиш set, ако додаваш дупликати, тие се додаваат само еднаш. За да ги гледаш како посебни елементи, можеш да користиш multiset.
Види ги променетите (две) линии.

BATIR wrote:Moze psevdokod. Otptilika ja razbiram idejata, ama ako moze pokonkretno objanuvanje.
Fala odnapred

Не е сложено решението воопшто; како што кажав, само динамичко програмирање. Вака нешто (пробав да ставам и неколку коментари).

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

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

vector<string> O;
    O.resize(L+1);

for (int i=1; i<=L; i++) {
        cin >> O[i];
    }

int options[L+1];
    options[0] = 1;

for (int i=1; i<=L; i++) {
        options[i] = 0;

for (int sz=1; sz<=i; sz++) {

//dali mozhe tuka da zavrshuva grupa od "sz" lica?
            //mozhe, ako poslednite "sz" elementi se ili ednakvi na "N" ili na "sz"

bool good = true;
            int from = i-sz+1, to = i; //poslednite "sz" elementi se od "from" do "to"
            for (int j=from; j<=to; j++) {
                if (O[j] != "N" && stoi(O[j]) != sz) {
                    good = false;      //broj razlichen od "sz"
                    break;
                }
            }

if (good) {
                options[i] = options[i] + options[i - sz];

if (options[i] > 1) {    //ne ni treba tochniot rezultat
                    options[i] = 2;      //samo ne interesira dali ima 1 ili povekje (2+) opcii
                                         //(za sluchajno da ne ni se pojavi overflow, iako nema vo test primerite)
                }
            }
        }
    }

if (options[L] == 1) {
        cout << "DA" << endl;
    } else {
        cout << "NE" << endl;
    }
    return 0;
}

BATIR wrote:Moze idea za zadaca moj termin?
http://mendo.mk/Task.do?id=807
Fala odnapred
Probav nesto vaka ama pominuva na 12/20

Наједноставното решение е со динамичко програмирање, каде што имаме некоја низа options[X], која што ќе означува на колку начини (ако ни се разгледани првите X лица) може да се заменат непознатите вредности (N). Тогаш, ако важи options[L] == 1, решението е "DA" бидејќи постои само еден начин да се направат замените (да се поделат лицата на групи), инаку е "NE".

SmokiB wrote:Но, значи дека правилото важи?

Па, да, чим го пишува во листата со поканети ученици.
Само го разбрав твоето прашање како "бидејки јас немам решено, не сум поканет", па затоа пишав дека има уште доста време до рокот.

Не е многу променето, али само информација дека е всушност 230 задачи. Според сајтот на ЗИМ: http://cs.org.mk/index.php/natprevari/srednoobrazovanie/makedonskaolimpijada-informatika

SmokiB wrote:Правилото: (право на учество ќе добијат само оние што ќе имаат решено 240 задачи на МЕНДО заклучно со 20.04.2018год).
Дали ова правило важи за сите? Значи јас, штом немам над 240 задачи решено ќе неможам да се натпреварувам на олимпијадата, иако ме има на листата на поканети учесници???

Па, можеш да решаваш до 20.04.2018 (околу 25 дена има до тогаш). Веројатно поради тоа е и правилото - бидејќи има доста време до Олимпијада.
Али ова 240 делува некако многу (има доста луѓе кои имаат решено толку), али незнам од каде дошло, треба да прокоментира некој друг. (инаку можно е, бидејќи има доста задачи и во делот почетници, и во делот национални итн)

BRabbit wrote:Може помош? Поминува на 6/10 тест примери а на другите дава погрешен резултат.
http://mendo.mk/Task.do?id=17

Еве еден пример каде што твојата програма ќе отпечати погрешен одговор: N=5, K=6.
Тука твојата програма нема да направи една група од 5 (кои можат да пишуваат дури по 9 задачи во еден ден). Има и други се разбира.

Пробај да го користиш K во пресметките на почеток, наместо само на крајот.
Инаку, јас би ја решавал задачава со испробување на сите можни опции (колку групи од 3 и 5). Нешто вака (слободно користи го да најдеш за кои податоци програмата ти дава различен одговор):

BATIR wrote:Може идеја за задачава?
http://mendo.mk/Task.do?id=291

Интересна задача е ова. Ако знаеш што е сегментно дрво (segment tree) или нешто како binary indexed tree, тогаш ете ти идеја - користи некоја од тие структури. (Има предавање и во делот "Алгоритми" на МЕНДО)
Инаку, поприлично сум сигурен дека темава (задачава) се појавувала порано на форумов, па можеш да побараш. Еве едно (мада е добро прво да размислиш и сам/а): http://mendo.mk/jforum/posts/list/263.page

BATIR wrote:Dali mozat ucenici od osnovnoto obrazovanie da ucestvuvaat??

Да, ако се меѓу најдобрите

.
Исто, тие што се основно образование се натпреваруваат на други изборни натпревари за учество на ЕЈОИ и слично ( http://cs.org.mk/index.php/natprevari/srednoobrazovanie/megunarodni-natprevari-po-informatika ).