Messages posted by: jovank

провери случајно да не го разгледуваш "0 0" во некој посебен случај во кој забораваш да испечатиш endl...

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

Забораив input и output да ставам

Input:
25 25
A 1
A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10 A 11 A 12 A 13 A 14 A 15 A 16 A 17 A 18 A 19 A 20 A 21
A 22 A 23 A 24 A 25 B 1 B 2 B 3 B 4 B 5 B 6 B 7 B 8 B 9 B 10 B 11 B 12 B 13 B 14 B 15 B 16 B 17
B 18 B 19 B 20 B 21 B 22 B 23 B 24 B 25 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 C 10 C 11 C 12 C 13
C 14 C 15 C 16 C 17 C 18 C 19 C 20 C 21 C 22 C 23 C 24 C 25 D 1 D 2 D 3 D 4 D 5 D 6 D 7 D 8 D 9
D 10 D 11 D 12 D 13 D 14 D 15 D 16 D 17 D 18 D 19 D 20 D 21 D 22 D 23 D 24 D 25 E 1 E 2 E 3 E 4 E 5
E 6 E 7 E 8 E 9 E 10 E 11 E 12 E 13 E 14 E 15 E 16 E 17 E 18 E 19 E 20 E 21 E 22 E 23 E 24 E 25 F 1
F 2 F 3 F 4 F 5 F 6 F 7 F 8 F 9 F 10 F 11 F 12 F 13 F 14 F 15 F 16 F 17 F 18 F 19 F 20 F 21 F 22
F 23 F 24 F 25 G 1 G 2 G 3 G 4 G 5 G 6 G 7 G 8 G 9 G 10 G 11 G 12 G 13 G 14 G 15 G 16 G 17 G 18
G 19 G 20 G 21 G 22 G 23 G 24 G 25 H 1 H 2 H 3 H 4 H 5 H 6 H 7 H 8 H 9 H 10 H 11 H 12 H 13 H 14
H 15 H 16 H 17 H 18 H 19 H 20 H 21 H 22 H 23 H 24 H 25 I 1 I 2 I 3 I 4 I 5 I 6 I 7 I 8 I 9 I 10
I 11 I 12 I 13 I 14 I 15 I 16 I 17 I 18 I 19 I 20 I 21 I 22 I 23 I 24 I 25 J 1 J 2 J 3 J 4 J 5 J 6
J 7 J 8 J 9 J 10 J 11 J 12 J 13 J 14 J 15 J 16 J 17 J 18 J 19 J 20 J 21 J 22 J 23 J 24 J 25 K 1 K 2
K 3 K 4 K 5 K 6 K 7 K 8 K 9 K 10 K 11 K 12 K 13 K 14 K 15 K 16 K 17 K 18 K 19 K 20 K 21 K 22 K 23
K 24 K 25 L 1 L 2 L 3 L 4 L 5 L 6 L 7 L 8 L 9 L 10 L 11 L 12 L 13 L 14 L 15 L 16 L 17 L 18 L 19
L 20 L 21 L 22 L 23 L 24 L 25 M 1 M 2 M 3 M 4 M 5 M 6 M 7 M 8 M 9 M 10 M 11 M 12 M 13 M 14 M 15
M 16 M 17 M 18 M 19 M 20 M 21 M 22 M 23 M 24 M 25 N 1 N 2 N 3 N 4 N 5 N 6 N 7 N 8 N 9 N 10 N 11
N 12 N 13 N 14 N 15 N 16 N 17 N 18 N 19 N 20 N 21 N 22 N 23 N 24 N 25 O 1 O 2 O 3 O 4 O 5 O 6 O 7
O 8 O 9 O 10 O 11 O 12 O 13 O 14 O 15 O 16 O 17 O 18 O 19 O 20 O 21 O 22 O 23 O 24 O 25 P 1 P 2 P 3
P 4 P 5 P 6 P 7 P 8 P 9 P 10 P 11 P 12 P 13 P 14 P 15 P 16 P 17 P 18 P 19 P 20 P 21 P 22 P 23 P 24
P 25 Q 1 Q 2 Q 3 Q 4 Q 5 Q 6 Q 7 Q 8 Q 9 Q 10 Q 11 Q 12 Q 13 Q 14 Q 15 Q 16 Q 17 Q 18 Q 19 Q 20
Q 21 Q 22 Q 23 Q 24 Q 25 R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 R 11 R 12 R 13 R 14 R 15 R 16
R 17 R 18 R 19 R 20 R 21 R 22 R 23 R 24 R 25 S 1 S 2 S 3 S 4 S 5 S 6 S 7 S 8 S 9 S 10 S 11 S 12
S 13 S 14 S 15 S 16 S 17 S 18 S 19 S 20 S 21 S 22 S 23 S 24 S 25 T 1 T 2 T 3 T 4 T 5 T 6 T 7 T 8
T 9 T 10 T 11 T 12 T 13 T 14 T 15 T 16 T 17 T 18 T 19 T 20 T 21 T 22 T 23 T 24 T 25 U 1 U 2 U 3 U 4
U 5 U 6 U 7 U 8 U 9 U 10 U 11 U 12 U 13 U 14 U 15 U 16 U 17 U 18 U 19 U 20 U 21 U 22 U 23 U 24 U 25
V 1 V 2 V 3 V 4 V 5 V 6 V 7 V 8 V 9 V 10 V 11 V 12 V 13 V 14 V 15 V 16 V 17 V 18 V 19 V 20 V 21
V 22 V 23 V 24 V 25 W 1 W 2 W 3 W 4 W 5 W 6 W 7 W 8 W 9 W 10 W 11 W 12 W 13 W 14 W 15 W 16 W 17
W 18 W 19 W 20 W 21 W 22 W 23 W 24 W 25 X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 X 11 X 12 X 13
X 14 X 15 X 16 X 17 X 18 X 19 X 20 X 21 X 22 X 23 X 24 X 25 Y 1 Y 2 Y 3 Y 4 Y 5 Y 6 Y 7 Y 8 Y 9
Y 10 Y 11 Y 12 Y 13 Y 14 Y 15 Y 16 Y 17 Y 18 Y 19 Y 20 Y 21 Y 22 Y 23 Y 24 Y 25

Output:
3264

Задача Camelot, Section 3.3
Ми паѓа на 5-от тест пример на нивниот сервер, а кај мене локално поминува:

USER: Jovan Krajevski [jovan.k1]
TASK: camelot
LANG: C++

Compiling...
Compile: OK

Executing...
Test 1: TEST OK [0.000 secs, 3028 KB]
Test 2: TEST OK [0.000 secs, 3028 KB]
Test 3: TEST OK [0.000 secs, 3044 KB]
Test 4: TEST OK [0.054 secs, 3044 KB]

> Run 5: Execution error: Your program had this runtime error: Bad
syscall #32000175 (RT_SIGPROCMASK) [email kolstad if you think
this is wrong]. The program ran for 0.027 CPU seconds before the
error. It used 11424 KB of memory.

------ Data for Run 5 ------
25 25
A 1
A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10 A 11 A 12 A 13 A 14 A 15 A 16
A 17 A 18 A 19 A 20 A 21
A 22 A 23 A 24 A 25 B 1 B 2 B 3 B 4 B 5 B 6 B 7 B 8 B 9 B 10 B 11 B 12
B 13 B 14 B 15 B 16 B 17
B 18 B 19 B 20 B 21 B 22 B 23 B 24 B 25 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C
8 C 9 C 10 C 11 C 12 C 13
C 14 C 15 C 16 C 17 C 18 C 19 C 20 C 21 C 22 C 23 C 24 C 25 D 1 D 2 D
3 D 4 D 5 D 6 D 7 D 8 D 9
D 10 D 11 D 12 D 13 D 14 D 15 D 16 D 17 D 18 D 19 D 20 D 21 D 22 D 23
D 24 D 25 E 1 E 2 E 3 E 4 E 5
E 6 E 7 E 8 E 9 E 10 E 11 E 12 E 13 E 14 E 15 E 16 E 17 E 18 E 19 E 20
E 21 E 22 E 23 E 24 E 25 F 1
F 2 F 3 F 4 F 5 F 6 F 7 F 8 F 9 F 10 F 11 F 12 F 13 F 14 F 15 F 16 F
17 F 18 F 19 F 20 F 21 F 22
F 23 F 24 F 25 G 1 G 2 G 3 G 4 G 5 G 6 G 7 G 8 G 9 G 10 G 11 G 12 G 13
G 14 G 15 G 16 G 17 G 18
G 19 G 20 G 21 G 22 G 23 G 24 G 25 H 1 H 2 H 3 H 4 H 5 H 6 H 7 H 8 H 9
H 10 H 11 H 12 H 13 H 14
H 15 H 16 H 17 H 18 H 19 H 20 H 21 H 22 H 23 H 24 H 25 I 1 I 2 I 3 I 4
I 5 I 6 I 7 I 8 I 9 I 10
I 11 I 12 I 13 I 14 I 15 I 16 I 17 I 18 I 19 I 20 I 21 I 22 I 23 I 24
I 25 J 1 J 2 J 3 J 4 J 5 J 6
J 7 J 8 J 9 J 10 J 11 J 12 J 13 J 14 J 15 J 16 J 17 J 18 J 19 J 20 J
21 J 22 J 23 J 24 J 25 K 1 K 2
K 3 K 4 K 5 K 6 K 7 K 8 K 9 K 10 K 11 K 12 K 13 K 14 K 15 K 16 K 17 K
18 K 19 K 20 K 21 K 22 K 23
K 24 K 25 L 1 L 2 L 3 L 4 L 5 L 6 L 7 L 8 L 9 L 10 L 11 L 12 L 13 L 14
L 15 L 16 L 17 L 18 L 19
L 20 L 21 L 22 L 23 L 24 L 25 M 1 M 2 M 3 M 4 M 5 M 6 M 7 M 8 M 9 M 10
M 11 M 12 M 13 M 14 M 15
M 16 M 17 M 18 M 19 M 20 M 21 M 22 M 23 M 24 M 25 N 1 N 2 N 3 N 4 N 5
N 6 N 7 N 8 N 9 N 10 N 11
N 12 N 13 N 14 N 15 N 16 N 17 N 18 N 19 N 20 N 21 N 22 N 23 N 24 N 25
O 1 O 2 O 3 O 4 O 5 O 6 O 7
O 8 O 9 O 10 O 11 O 12 O 13 O 14 O 15 O 16 O 17 O 18 O 19 O 20 O 21 O
22 O 23 O 24 O 25 P 1 P 2 P 3
P 4 P 5 P 6 P 7 P 8 P 9 P 10 P 11 P 12 P 13 P 14 P 15 P 16 P 17 P 18 P
19 P 20 P 21 P 22 P 23 P 24
P 25 Q 1 Q 2 Q 3 Q 4 Q 5 Q 6 Q 7 Q 8 Q 9 Q 10 Q 11 Q 12 Q 13 Q 14 Q 15
Q 16 Q 17 Q 18 Q 19 Q 20
Q 21 Q 22 Q 23 Q 24 Q 25 R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 R 11
R 12 R 13 R 14 R 15 R 16
R 17 R 18 R 19 R 20 R 21 R 22 R 23 R 24 R 25 S 1 S 2 S 3 S 4 S 5 S 6 S
7 S 8 S 9 S 10 S 11 S 12
S 13 S 14 S 15 S 16 S 17 S 18 S 19 S 20 S 21 S 22 S 23 S 24 S 25 T 1 T
2 T 3 T 4 T 5 T 6 T 7 T 8
T 9 T 10 T 11 T 12 T 13 T 14 T 15 T 16 T 17 T 18 T 19 T 20 T 21 T 22 T
23 T 24 T 25 U 1 U 2 U 3 U 4
U 5 U 6 U 7 U 8 U 9 U 10 U 11 U 12 U 13 U 14 U 15 U 16 U 17 U 18 U 19
U 20 U 21 U 22 U 23 U 24 U 25
V 1 V 2 V 3 V 4 V 5 V 6 V 7 V 8 V 9 V 10 V 11 V 12 V 13 V 14 V 15 V 16
V 17 V 18 V 19 V 20 V 21
V 22 V 23 V 24 V 25 W 1 W 2 W 3 W 4 W 5 W 6 W 7 W 8 W 9 W 10 W 11 W 12
W 13 W 14 W 15 W 16 W 17
W 18 W 19 W 20 W 21 W 22 W 23 W 24 W 25 X 1 X 2 X 3 X 4 X 5 X 6 X 7 X
8 X 9 X 10 X 11 X 12 X 13
X 14 X 15 X 16 X 17 X 18 X 19 X 20 X 21 X 22 X 23 X 24 X 25 Y 1 Y 2 Y
3 Y 4 Y 5 Y 6 Y 7 Y 8 Y 9
... [and more] ...
----------------------------

Your program printed data to stderr. Here is the data:
-------------------
terminate_called_after_throwing_an_instance_of_'std::bad_alloc'
__what():__std::bad_alloc
-------------------

Test 5: SIGNAL 50 (0.027 secs, 11424 KB)

Кога ја тестирам задачата кај мене локално, ми дава резултат 3264, и не покажува никаков run-time error. Знае некој до што може да биде ова? Фала однапред

Еве го и кодот:

РЕШЕНО!
Идеата ми била погрешна, одново ја искуцав задачата, и сеуште незнам зошто се појави SIGNAL 50 на USACO

Благодариме

@bedzo: LOL

ако знаеш да најдеш нзд на 2 броја, тогаш нзс на тие броеви е количникот при делење на нивниот производ со нивниот нзд, или поедноставно кажано: нзс(a,b)=a*b/нзд(a,b)

пробав прво со бфс, али и тоа ми падна на време... :/

мал bug има форумов со знаците < и >

Сега ми паѓа на време...

има некој идеа како да го убрзам решениево?

Executing...
   Test 1: TEST OK [0.216 secs, 7404 KB]
   Test 2: TEST OK [0.243 secs, 7404 KB]
   Test 3: TEST OK [0.243 secs, 7404 KB]
   Test 4: TEST OK [0.189 secs, 7404 KB]
   Test 5: TEST OK [0.513 secs, 7404 KB]
   Test 6: TEST OK [0.810 secs, 7404 KB]

> Run 7: Execution error: Your program (`msquare') used more than
        the allotted runtime of 1 seconds (it ended or was stopped at
        1.269 seconds) when presented with test case 7. It used 13232 KB
        of memory.

------ Data for Run 7 ------
        3 4 2 1 5 6 7 8 
        ----------------------------

Test 7: RUNTIME 1.269>1 (13232 KB)

/*
ID: jovan.k1
PROG: msquare
LANG: C++
*/
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <fstream>
using namespace std;

struct komb
{
    vector<int> niza;
    string a;
    bool pos;
};

bool operator < (vector<int> a, vector<int> b)
{
    int k;
    for (k=0;k<8;k++) if (a[k]!=b[k]) return a[k]<b[k];
}

bool operator >< (komb a, komb b)
{
    if (a.a.length()!=b.a.length()) return a.a.length()>b.a.length();
    else
    {
        return a.a>b.a;
    }
}

vector<komb> kom;

void init(vector<int> niza, bool pos[10])
{
    if (niza.size()==8)
    {
        komb a;
        a.niza=niza;
        a.a="DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD";
        a.pos=0;
        kom.push_back(a);
    }
    else
    {
        int k;
        niza.push_back(0);
        for (k=1;k<=8;k++)
        {
            if (pos[k]==0)
            {
                niza[niza.size()-1]=k;
                pos[k]=1;
                init(niza,pos);
                pos[k]=0;
            }
        }
    }
}

komb potegA(komb a)
{
    komb b;
    b.niza=a.niza;
    b.niza[0]=a.niza[7];b.niza[1]=a.niza[6];b.niza[2]=a.niza[5];b.niza[3]=a.niza[4];
    b.niza[4]=a.niza[3];b.niza[5]=a.niza[2];b.niza[6]=a.niza[1];b.niza[7]=a.niza[0];
    return b;
}

komb potegB(komb a)
{
    komb b;
    b.niza=a.niza;
    b.niza[0]=a.niza[3];b.niza[1]=a.niza[0];b.niza[2]=a.niza[1];b.niza[3]=a.niza[2];
    b.niza[4]=a.niza[5];b.niza[5]=a.niza[6];b.niza[6]=a.niza[7];b.niza[7]=a.niza[4];
    return b;
}

komb potegC(komb a)
{
    komb b;
    b.niza=a.niza;
    b.niza[1]=a.niza[6];b.niza[2]=a.niza[1];
    b.niza[5]=a.niza[2];b.niza[6]=a.niza[5];
    return b;
}

int bin(komb a)  //binary search
{
    int l,d,m;
    l=0;
    d=kom.size();
    while(l<d)
    {
        if (a.niza==kom[l].niza) return l;
        if (a.niza==kom[d].niza) return d;
        m=(l+d)/2;
        if (a.niza==kom[m].niza) return m;
        if (a.niza><kom[m].niza) d=m;
        else l=m;
    }
    return -1;
}

int tar;

void dikstra()
{
    priority_queue><komb> q;
    //bool pos[40350];
    int k,i,j,br;
    for (k=1;k<kom.size();k++) q.push(kom[k]);
    //for (k=0;k<40345;k++) pos[k]=0;
    komb a;
    a=kom[0];
    a.a="";
    kom[0].pos=1;
    kom[0].a="";
    br=1;
    k=bin(potegA(a));
    i=bin(potegB(a));
    j=bin(potegC(a));
    kom[k].a="A";
    q.push(kom[k]);
    kom[i].a="B";
    q.push(kom[i]);
    kom[j].a="C";
    q.push(kom[j]);
    while (br><kom.size() && kom[tar].pos==0)
    {
        //cout><<br<<endl;
        //cout><<q.size();
        a.pos=1;
        while (a.pos==1)
        {
            a=q.top();
            q.pop();
        }
        //cout<<a.a><<endl;
        //cout<<a.a><<endl;
        //a.pos=1;
        kom[bin(a)].pos=1;
        br++;
        k=bin(potegA(a));
        if (a.a.length()+1<kom[k].a.length() || (a.a.length()+1==kom[k].a.length() && a.a+'A'><kom[k].a) && kom[k].pos==0)
        {
            kom[k].a=a.a+'A';
            q.push(kom[k]);
            //cout><<1;
        }
        i=bin(potegB(a));
        if (a.a.length()+1<kom[i].a.length() || (a.a.length()+1==kom[i].a.length() && a.a+'B'><kom[i].a) && kom[i].pos==0)
        {
            kom[i].a=a.a+'B';
            q.push(kom[i]);
            //cout><<1;
        }
        j=bin(potegC(a));
        if (a.a.length()+1<kom[j].a.length() || (a.a.length()+1==kom[j].a.length() && a.a+'C'><kom[j].a) && kom[j].pos==0)
        {
            kom[j].a=a.a+'C';
            q.push(kom[j]);
            //cout><<1;
        }
    }
}

int main()
{
    ifstream fin("msquare.in");
    ofstream fout("msquare.out");
    vector<int> a;
    /*string z,x;
    z="AAAA";
    x="B";
    cout<<(z<x)><<endl;*/
    bool niz[10];
    int k,i;
    komb c,d;
    for (k=0;k<10;k++) niz[k]=0;
    init(a,niz);
    for (k=0;k<8;k++)
    {
        cin>>i;
        a.push_back(i);
    }
    c.niza=a;
    tar=bin(c);
    /*cout<<bin(c)><<endl;
    d=potegA(c);
    for (k=0;k<8;k++) cout<<d.niza[k]><<" ";
    cout<<endl><<bin(d)<<endl;
    d=potegB(c);
    for (k=0;k<8;k++) cout><<d.niza[k]<<" ";
    cout<<endl><<bin(d)<<endl;
    d=potegC(c);
    for (k=0;k<8;k++) cout><<d.niza[k]<<" ";
    cout<<endl><<bin(d)<<endl;*/
    dikstra();
    cout><<kom[bin(c)].a.length()<<endl;
    cout><<kom[bin(c)].a<<endl;
    return 0;
}

>

ејј фала многу, вториов хинт е тој што стварно ми разјасни некои ствари (после првиот, за момент помислив на brute force

)

Малку помош ако може

http://olympiads.win.tue.nl/ioi/ioi96/contest/ioi96m.html

На линков има една задача, Magic Squares... Идеата ми е да направам граф од табелата (темиња се сите полиња, врска помеѓу две полиња постои ако може со некоја од трансформациите A, B и C да се сменат тие две полиња), и после некако да ги најдам најкратките патишта помеѓу полињата кои треба да дојдат до своето место (најверојатно со алгоритамот на Floyd-Warshall)... Но бидејќи со секоја трансформација се менуваат група на полиња со група на полиња, не знам како би го направил тоа... Ако знае некој да ми помогне, или пак ако има некоја друга идеа би било супер

Првиот ден на овогодинешните припреми, имаше една задача во која се бараше да се најдат секвенците на битови што најчесто се повторуваат... еве го текстот на задачата за подетално објаснување: http://olympiads.win.tue.nl/ioi/ioi98/contest/day1/contact/contact.pdf
На интернет има само решенија во форма на код, па затоа ако може некој да ми даде идеа за тоа како би се решила задачава

на предавањата баш не ја пратев оваа задача

Не е забрането crt, но нема потреба да се користи...

сега сфаќаш што сакавме да ти кажеме?

кои 5 цифри ќе ги извадиш од 666435324321 за да добиеш 6665443?