Messages posted by: MOI

Perez wrote:Како е можно ова ?

Баш и не пробав да ја прочитам задачата од почеток, ама мислам дека имаш проблеми со читатењето на влезните податоци.
1. text[n] е подобро да е text[n+1], поради http://mendo.mk/Lecture.do?id=21 (види "Низи од знаци")
2. Мислам дека кога читаме со cin >> str, читањето се врши до првото празно место или нов ред и слично.

Можеби нешто вака би било подобро:

Perez wrote:Може помош ? Како пресмета дека треба 6 пати?
да може 6 пати ако си 103+++; али тројката е во тоа "скршено" копче
исто и за 109- - - ;

Во задачата пишува "На почеток, Трпе се наоѓа на страница 100 и сака да стигне до страницата P. ". Значи, ако веќе сме на страница 100, треба само 6 пати да притиснеме на "+".

BATIR wrote:Zdravo, imam problem okolu zadacata Stolici link:
http://mendo.mk/Task.do?id=189
Moze da mi ja najdete greskata?

Хм, треба само да видиш во која секунда од денот има најмногу луѓе. Некако вака (сменет е само последниот дел од твојот код)...

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
  
using namespace std;
  
  
/*
20
18:00:00 23:59:00
19:00:00 23:59:00
20:00:00 23:59:00
20:00:00 20:00:00
19:59:00 19:59:00
10:00:00 15:59:00
11:00:00 15:59:00
12:00:00 15:59:00
12:00:00 12:00:00
11:59:00 11:59:00
10:00:00 23:59:01
10:00:00 23:58:59
00:00:01 00:00:02
00:00:02 00:00:03
00:00:03 00:00:04
00:00:04 00:00:04
00:00:04 00:00:05
08:10:00 08:11:00
08:10:00 08:12:00
08:10:00 23:59:58
*/
  
struct vv {
  
long long vkupno, vkupno1;
};
int main()
{
int n;
cin >> n;
string *pocetoci = new std::string[n];
string *kraevi = new std::string[n];
for (int i = 0; i<n; i++)
{
cin >> pocetoci[i] >> kraevi[i];
  
}
  
int MAX = 0;
int curr = 0;
vector<vv> v;
for (int i = 0; i<n; i++)
{
curr = 0;
std::string time = pocetoci[i];
int hrs = atoi(time.substr(0, 2).c_str());
int mins = atoi(time.substr(3, 2).c_str());
int secs = atoi(time.substr(6, 2).c_str());
  
std::string time1 = kraevi[i];
int hrs1 = atoi(time1.substr(0, 2).c_str());
int mins1 = atoi(time1.substr(3, 2).c_str());
int secs1 = atoi(time1.substr(6, 2).c_str());
long long vkupno = hrs * 60 * 60 + mins * 60 + secs;
long long vkupno1 = hrs1 * 60 * 60 + mins1 * 60 + secs1;
  
vv tmp;
tmp.vkupno = vkupno;
tmp.vkupno1 = vkupno1;
v.push_back(tmp);
}
  
vector<int> inside(24 * 3600);
  
for (int i = 0; i < n; i++)
{
     for(int j=v[i].vkupno; j <= v[i].vkupno1; j++){
          inside[j]++;
     }
}
  
for (int i = 0; i < inside.size(); i++)
{
     if (MAX < inside[i])
          MAX = inside[i];
}
  
cout << MAX << endl;
return 0;
}

Perez wrote:После читање толку матријали за ова ДП , па некако слабо сфаќам.
Може ли некој да ми го објасни во кратки црти , односно да ме насочи како да размислувам за ДП.

Јас би почнал од тука, доста е добро објаснето.
https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/

Како прв чекор (да сфатиш што воопшто се обидуваме да решиме со динамичко програмирање)
https://www.quora.com/How-should-I-explain-dynamic-programming-to-a-4-year-old/answer/Jonathan-Paulson
https://www.hackerearth.com/practice/notes/dynamic-programming-i-1/

жучко wrote:Ako nekoj mozi da mi pomogni da go potsredam kodov . Mi vadi 13/22 . Site so se gresni se Runtime Error (излезен код различен од 0)
link : http://mendo.mk/Task.do?id=618

N е голем број, па матрицата што ја правиш (connected) зафаќа многу меморија. Слично, не е ефикасно да правиш count(...) на вектор (kosta, kiril), бидејќи тогаш се изминуваат сите елементи од векторот за да се пресмета бараниот број. Можеш да користиш set (каде барањето дали постои некој елемент или не се изведува во логаритамско време). Некако вака можеш да го подобриш кодот:

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
   
using namespace std;
   
int main()
{
    int n,B1,B2,P;
    cin>>n>>B1>>B2>>P;
    vector <int> kosta(B1);///gradovi na kosta
    vector <int> kiril(B2);///gradovi na kiril
  
    set<int> kirilSet;
    set<int> kostaSet;
  
    for(int i=0;i<B1;i++){
        cin>>kosta[i];
        kostaSet.insert(kosta[i]);
    }
    for(int i=0;i<B2;i++){
        cin>>kiril[i];
        kirilSet.insert(kiril[i]);
    }
    int m;///broj na parovi
    cin>>m;
    vector<int> connected[n];
     
    for(int i=0;i<m;i++){
        int xi,yi;
        cin>>xi>>yi;
 
        connected[xi-1].push_back(yi-1);
        connected[yi-1].push_back(xi-1);
    }
 
    for(int i=0; i<n; i++){
        if (connected[i].size() > 1){
            sort(connected[i].begin(), connected[i].end());
        }
    }
 
    int rez=0;
    for(int i=0;i<kosta.size();i++)
    {
        if(P==0){
            break;
        }
        for(int j : connected[kosta[i]-1]){
            if(kirilSet.count(j+1) == 0 && kostaSet.count(j+1) == 0){
                P--;
                kosta.push_back(j+1);
                kostaSet.insert(j+1);
                rez++;
            }
        }
    }
    cout<<rez;
}

Да, long long користи 8 бајти (64 бита) за претставување на броеви (позитивни и негативни), па со него може да се претстават броеви со големина до 9223372036854775807 (=2^63 - 1, бидејќи треба место за 0 и за негативните броеви). Кај оваа задача може да се добијат и поголеми броеви, па можеше да се користи низа или string за собирање на броевите. Нешто вака...

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

string add(string a, string b){
    int digits = max(a.size(), b.size());
    string result(digits, '0'); //result = "00000...0"

int carry = 0;
    int posA = a.size() - 1;  //koga sobirame, pochnuvame od poslednata cifra
    int posB = b.size() - 1;  //koga sobirame, pochnuvame od poslednata cifra
    int posResult = max(a.size(), b.size()) - 1;    //kade kje zapishuvame vo rezultatot

while(posA >= 0 || posB >= 0)
    {
        int digitA = (posA >= 0) ? (a[posA] - '0') : 0;     //ako edniot broj ima povekje cifri od drugiot, zemame deka ima 0
        int digitB = (posB >= 0) ? (b[posB] - '0') : 0;     //ako edniot broj ima povekje cifri od drugiot, zemame deka ima 0

int sum = (digitA + digitB + carry);

//ako dobieme suma 17, ja zapishuvame sedmicata vo rezultatot, i pametime 1
        result[posResult] = (char)((sum % 10) + '0');
        carry = (sum / 10);

posA--; //odi na slednata cifra
        posB--; //odi na slednata cifra
        posResult--;
    }

if(carry > 0){
        result = "1" + result;
    }

return result;
}

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

string result = "0";
    string power = "1";
    for(int i=1; i <= N; i++){

power = add(power, power); //sledniot stepen na 2 e 2*power = (power+power)
        result = add(result, power);
    }

cout << result << endl;
    return 0;
}

BATIR wrote:Еве ми го кодот , три од дваесет тест случаи ми се точни. Помош

ne ti e tochno reshenieto, na primer za sledniov sluchaj kje otpechati 4, no odgovorot e 3.
5
10 10
10 10
10 10
13 13
13 13

Jas vaka bi ja reshaval...

Tose Todorov wrote:За програмирање почнав посериозно да се интересирам пред 3-4 месеци и некои работи уште не ми се јасни па ако може некој да ми објасни нешто

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

Хм, системот не вика дека имаш надминат временски лимит, туку дека се појавува грешка при извршувањето на твојата програма.

Доколку те интересира што е грешката, прочитај го првиот дел од ова предавање: http://mendo.mk/Lecture.do?id=21
Накратко, ако имаш низа array[12], тогаш таа има големина од 12 елементи, и можеш да запишуваш на позициите: array[0], array[1], ... array[11], но не и array[12]. Слично и со матрици.

boolTrue wrote:Ако дојде до ваков ист случај на натпревар, дали ќе ми се важи задачата за решена ако се проверуват рачно?

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

Не го сфатив делот за "ако се проверуваат рачно". Комисијата која ги организира натпреварите не троши многу време да ги проверува решенијата рачно (освен ако системот не пријави дека имало препишување - т.е. повеќе решенија се слични, итн). Ако мислиш на пишување код (решение) од натпреварувач, кое ќе има if(...) за разни тест случаи, тоа тешко може да освои многу поени, бидејќи тест случаите се сокриени и не се познати додека не заврши натпреварот.

Kiko206 wrote:aj aako mozi pomos za zadaca Линеарна равенка http://mendo.mk/Task.do?id=229

Математика. http://www.e-matematika.mk/linearni-ravenki-i-neravenki (види дел 2).

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

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

mitkonikov wrote:Ja resavam zadachata so BFS od sekoe cveke.... 100 BFS najlos sluchaj ke bide CxNxM 100x(1000x1000) t.e. na cela zadaca => 100 000 000
Za site primeri raboti, samo na cetvrtiot ne.....

Во текстот на задачата пишува:
"Цревата на системот не може да поминат преку полињата со бетонски плочи, но слободно може да поминуваат преку сите други полиња."

Во твојата функција valid(), проверуваш дали (c[a][b] == '.'), а мислам дека треба да биде (c[a][b] == '.' || c[a][b] == 'C').
Го пратив тоа решение, и поминува на сите примери.

BATIR wrote:http://mendo.mk/Task.do?id=286
Ајде помош околу задачава. Имам идеја но не знам како да ги спојам броевиве.
Дали е можно ја решам задачава вака?
Со еден макс кој почнува од нула да ги проверувам сие можни споени броеви , т.е. ако тој број е поголем од најголемиот досегашен МАКС. И на крај само о печатам тој број?

Прашуваше некој за истава задача пред некој ден. Решение има тука: http://mendo.mk/jforum/posts/list/452.page

Не можев баш да разберам што мислиш под "сите можни споени броеви". Ако мислиш баш сите можни споени броеви, такви може да има многу (N! [факториел], што може да е до 1000!, што е огромен број со мноооогу нули), така да тоа не може.

Tose Todorov wrote:Ако може помош за задачава, ми вади 13/20 неможам да сфатам каде ми е грешката

Не чини овој дел, бидејќи, покрај овој стринг, ќе го прескокнеш и наредниот:

Смени го во нешто како:

Набрзина ги нацртав, ама вака би требало да изгледаат.

Инаку, решението е едноставно и поврзано со Питагорова теорема (да ги провериш сите можни тројки).