powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Каким алгоритмом можно заполнить все озёра рельефа водой?
11 сообщений из 261, страница 11 из 11
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36118895
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вот примерчик из ФАКа одного китайского контестера:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Here is an example for "long long": 

#include <stdio.h>

int main(void)
{
	long long a = 1LL <<  48 ;
	printf("%lld\n", a);
	return  0 ;
}
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36118918
vino
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
VadimPanovТак, не понял... Отчего

Код: plaintext
printf("%lld",  128 * 256 * 256 * 256 )

выводит мне

Код: plaintext
- 2147483648 

???????(?)компилятор работает только со знаковым 32-битным целым, попробуй явно привести к беззнаковому или 64-битному
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36118937
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
это тоже не помогает
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36118960
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
сейчас глянул на их форуме: http://www.spoj.pl/forum/viewtopic.php?f=3&t=5789

Это же надо было не полениться стругануть фибоначчиеву кучу для этой хрени (shortest path), ыхыхыхых

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
# include <iostream>
# include <vector>
# define MAX  15 
using namespace std;

vector <pair<int, int> > v[ 10000 ]; //Adjacency list
vector <pair <int,int> >::iterator it;
int cost[ 10000 ]; //Cost of each vertex

//Compare function
bool cmp(int a, int b)
{
    return cost[a]<cost;
}

//Class Node
class Node{
    public:
        int key; //Value
        int size; //Size of the child list
        int degree; //Degree
        Node *child; //Reference to the first element of the child list
        Node *left; //Left element
        Node *right; //Right element
        //Constructor
        Node(int value)
        {
            this->size= [b]0 ;
            this->key=value;
            this->degree= 0 ;
            this->child=NULL;
            this->left=this;
            this->right=this;
        }
        //Destructor
        ~Node(){}
        //Methods
        void insert(Node *n);
        //Print the child list
        void printNode() {
            int i, t=this->size;
            printf("%d (", this->key);
            Node *n=this->child;
            for (i= 0 ;i<t;i++) {
                n->printNode();
                n=n->right;
            }
            printf(") ");
        }
};

//Fibonacci Heap class
class FibonacciHeap
{
    public:
        int size; //Number of elements in the root list
        Node *minimum; //Reference to the element with the smallest value
        Node *first; //Reference to the first element of the root list
        //Constructor
        FibonacciHeap() {
            this->size= 0 ;
            this->minimum=NULL;
            this->first=NULL;
        }
        //Destructor
        ~FibonacciHeap(){};
        //Methods
        bool empty();
        void insert(Node *n);
        void merge(FibonacciHeap *fh);
        int minKey();
        void consolidate();
        //Print the Heap elements
        void printHeap()
        {
            int i;
            Node *x=this->first;
            for (i= 0 ;i<this->size;i++) {
                x->printNode();
                putchar(' ');
                x=x->right;
            }
            putchar('\n');
        }
};

//Function that inserts a child into the child list. O( 1 )
void Node::insert(Node *n)
{
    if (this->size== 0 ) {
        this->child=n;
        this->child->right=n;
        this->child->left=n;
    }
    else {
        n->right=this->child;
        n->left=this->child->left;
        this->child->left->right=n;
        this->child->left=n;
    }
    this->size++;
    this->degree++;
}

/*Function that returns true if the heap is empty, otherwise, returns false.
O(1)*/
bool FibonacciHeap::empty()
{
    return this->size== 0 ;
}

/* Function that inserts a node into the root list. O(1)*/
void FibonacciHeap::insert(Node *n)
{
    if (this->size== 0 ) {
        this->first=n;
        this->first->right=this->first;
        this->first->left=this->first;
        this->minimum=this->first;
    }
    else {
        n->right=this->first;
        n->left=this->first->left;
        this->first->left->right=n;
        this->first->left=n;
        if (cmp(n->key, this->minimum->key)) {
            this->minimum=n;
        }
    }
    this->size++;
}

/*Function that returns the key of the node with the smallest value.
O(1) + O(consolidate)*/
int FibonacciHeap::minKey()
{
    int t;
    Node *temp=this->minimum, *childs=this->minimum->child;
    if (temp!=NULL) {
        this->size--;
        if (this->size== 0 ) {
            this->first=NULL;
            this->minimum=NULL;
        }
        else {
            temp->left->right=temp->right;
            temp->right->left=temp->left;
            this->minimum=temp->right;
            if (this->first->key==temp->key) {
                this->first=this->first->right;
            }
        }
        if (childs!=NULL) {
            if (this->size== 0 ) {
                this->first=childs;
                this->minimum=childs;
            }
            else {
                childs->left->right=this->minimum;
                this->minimum->left->right=childs;
                this->minimum->left=childs->left;
                childs->left=this->minimum->left;
            }
            this->size+=temp->size;
        }
        this->consolidate();
        return temp->key;
    }
}

/*Function that consolidates the root list. O(MAX), 
where MAX=lg(n), 0<=n<=10000*/
void FibonacciHeap::consolidate()
{
    int i, d, aux=this->size;
    Node *vv[MAX], *x=this->minimum, *y, *temp, *next;
    for (i= 0 ;i<MAX;i++) {
        vv[i]=NULL;
    }
    for (i= 0 ;i<aux;i++) {
        d=x->degree;
        next=x->right;
        while (vv[d]!=NULL)  {
            y=vv[d];
            if (x->key > y->key) {
                y->insert(x);
                x=y;
            }
            else {
                x->insert(y);
            }
            vv[d]=NULL;
            d++;
        }
        vv[d]=x;
        x=next;
    }
    this->first=NULL;
    this->minimum=NULL;
    this->size= 0 ;
    for (i= 0 ;i<MAX;i++) {
        if (vv[i]!=NULL) {
            this->insert(vv[i]);
        }
    }
}

int dijkstra(int ini, int fin){
    int i,j;
    FibonacciHeap *fh=new FibonacciHeap();
    memset(cost,0x3f3f3f3f,sizeof cost);
    cost[ini]= 0 ;
    fh->insert(new Node(ini));
    while(!fh->empty()){
        i=fh->minKey();
        if (i==fin)
            break;
        for(it=v[i].begin();it!=v[i].end();it++){
            if (cost[i]+(*it).second<cost[(*it).first]){
                cost[(*it).first]=cost[i]+(*it).second;
                fh->insert(new Node((*it).first));
            }
        }
    }
    return cost[fin];
}

int read(){
    int r= 0 ;
    char c;
    while(!isdigit(c=getchar()));
    while(isdigit(c)){
        r=r* 10 +(c-'0');
        c=getchar();
    }
    return r;
}

int main(){
    char c[ 10000 ][ 11 ],ini[ 11 ],fin[ 11 ];
    int t,n,i,j,k,m;
    pair <int, int> p;
    t=read();
    while(t--){
        n=read();
        for(i= 0 ;i<n;i++){
            v[i].clear();
            scanf("%s",c[i]);
            m=read();
            for(j= 0 ;j<m;j++){
                p.first=read()- 1 ;
                p.second=read();
                v[i].push_back(p);
            }
        }
        m=read();
        for(i= 0 ;i<m;i++){
            scanf("%s%s",ini,fin);
            for(j= 0 ;j<n && strcmp(ini,c[j])!= 0 ;j++);
            for(k= 0 ;k<n && strcmp(fin,c[k])!= 0 ;k++);
            printf("%d\n",dijkstra(j,k));
        }
    }
    return  0 ;
}
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36119395
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vinoVadimPanov,
1) у тебя на одну проверку больше (условный переход обычно замедляет расчеты)

Твой алгоритм на файле с 99999 входными значениями отрабатывает меньше, чем за секунду, а мой - больше, чем за минуту! Отчего такая разница?!!!
Давай посмотрим ещё раз циклы (всё остальное, по сути - одинаковое, заполнение массива у меня занимает меньше секунды):
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
        for i := mx +  1  to j do begin
            w := i;
            a[i] := a[i- 1 ] + ( 2  * w -  1 ) + ((w * (w -  1 )) div  2 );
            if odd(i) then 
               a[i] := a[i] + (((w -  3 ) * (w -  1 )) div  4 ) 
            else
               a[i] := a[i] + (((w -  2 ) * (w -  2 )) div  4 );
        end;
В каждой итерации цикла от 4-х до N*10^6 (т.е. тот факт, что от 4-х, а не от 1 - несущественен)
происходит следующее:

1 действие: присвоение
2 действие: чтение элемента массива, 4 сложения, 2 умножения, 1 деление, запись элемента
3 действие: проверка с переходом
4 действие: чтение элемента массива, 2 сложения, 1 умножение, 1 деление, запись элемента
Итого на итерацию цикла: 1 присвоение, 2 чтения и 2 записи элемента массива, 6 сложений, 3 умножения, 2 деления

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
  for sz:= 1  to lv do begin
  
    pos:=lv-sz+ 1 ;
    if(pos> 0 )then res:=res+M[pos];
    
    pos:=lv- 2 *sz+ 1 ;
    if(pos> 0 )then res:=res+M[pos];

  end;
Для моего цикла (в самом худшем случае):
1 действие: 2 сложения, 1 присвоение
2 действие: проверка, 1 чтение элемента массива, 1 сложение
3 действие: 2 сложения, 1 умножение, 1 присвоение
2 действие: проверка, 1 чтение элемента массива, 1 сложение
Итого на итерацию цикла: 4 присвоения, 2 чтения элемента массива, 6 сложений, 1 умножение

Видно, что мои вычисления - проще. Отчего такая огромная разница - я не понимаю...

Можно, кстати, мой алгоритм и так записать (не думаю, что сильно спасёт):

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
  for sz:= 2  to lv+ 1  do begin
  
    pos:=lv-sz;
    if(pos> 0 )then res:=res+M[pos];
    
    pos:=lv- 2 *sz;
    if(pos> 0 )then res:=res+M[pos];

  end;

Будет на пару сложений меньше...

vino
2) заметил еще {$I-, Q-, R-, S-}, попробуй скомпилится с такими же флагами (это отключение кучи скрытого кода - проверки при расчетах, операциях ввода-вывода...)
Оба варианта компилировал в пятых дельфях в одинаковых условиях. Может, конечно, это как-то и влияет, но не настолько же. Скажи, что каждый параметр означает, я поставлю те же дельфозные.
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36119418
clihlt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VadimPanov,

А разница то здесь
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
   if j > mx then begin
       for i := mx +  1  to j do begin // Цикл не от нуля а  от j считанного на предыдущей итерации
            w := i;
            a[i] := a[i- 1 ] + ( 2  * w -  1 ) + ((w * (w -  1 )) div  2 );
            if odd(i) then 
               a[i] := a[i] + (((w -  3 ) * (w -  1 )) div  4 ) 
            else
               a[i] := a[i] + (((w -  2 ) * (w -  2 )) div  4 );
        end;
        mx := j;
    end;

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
   for sz:= 1  to lv do begin // цикл всегда с единицы
  
    pos:=lv-sz+ 1 ;
    if(pos> 0 )then res:=res+M[pos];
    
    pos:=lv- 2 *sz+ 1 ;
    if(pos> 0 )then res:=res+M[pos];

  end;
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36119430
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VadimPanovзаполнение массива у меня занимает меньше секунды
А МОЖЕТ ОНО У НИХ ТАМ ЗАНИМАЕТ МНОГО ВРЕМЕНИ??? Хз, чем они там компилят и на какой платформе запускают...
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36119432
clihlt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
автор
В каждой итерации цикла от 4-х до N*10^6 (т.е. тот факт, что от 4-х, а не от 1 - несущественен)

Каждая итерация не от 4-х, присмотрись внимательно.
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36119974
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
clihlt,

Да, точно, не заметил сразу...
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36119991
Фотография VadimPanov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VadimPanov
Твой код для треугольников, на паскале, прекрасно у них работает, а ОН ЖЕ, переведённый с паскаля на С, тоже даёт time limit exceeded!!! И как это понимать?
RT183.1чудеса... бум смотреть
Не разбирался с этим?
...
Рейтинг: 0 / 0
Каким алгоритмом можно заполнить все озёра рельефа водой?
    #36120367
clihlt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VadimPanov,

Таже самая проблема и в C. Ну может еще разве что с лонг лонг.
...
Рейтинг: 0 / 0
11 сообщений из 261, страница 11 из 11
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Каким алгоритмом можно заполнить все озёра рельефа водой?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]