Tốc độ chạy cùa bài COINS

Code:

#include<iostream>
using namespace std ;
long arr[50000000];
long long num , sum ;
long long solve( long num ) {
        if ( num <= 50000000 ) return arr[num] ;
            return ( solve(num/2) + solve(num/3)+solve(num/4));
}

int main(){
        int i ;
        for( i=1;i<12;i++ ) arr[i] = i ;
            for( i=12;i<=50000000;i++ ) arr[i] = arr[i/2]+arr[i/3]+arr[i/4];
                while( cin >> num ){
                        if ( num > 50000000 ) sum = solve( num ) ;
                            else sum = arr[num] ;
                            cout << sum << endl ;
                }
                    return 0 ;
      }

code này của acc hcmut chạy khoảng 1.97s

Code:

#include <iostream>
using namespace std;
long table[50000000];
long long n,sum,i;
long long dollar(long n)
{
    if (n<50000000)
        return table[n];
    return dollar(n/2)+dollar(n/3)+dollar(n/4);
}
int main()
{
   
    table[0] = 0;table[5] = 5;
    table[1] = 1;table[6] = 6;
    table[2] = 2;table[7] = 7;
    table[3] = 3;table[8] = 8;
    table[4] = 4;table[9] = 9;
    table[10] = 10;
    table[11] = 11;
    for (i=12;i<50000000;++i)
    {
        table[i] = table[i/2] + table[i/3] + table[i/4];
    }
    while (cin>>n)
    {
        if (n<50000000)    sum=table[n];
        else sum=dollar(n);                   
        cout<<sum<<endl;
    }
    return 0;
}

code này của em chạy nhanh nhất là ... 7.00s
Em thấy 2 đoạn code này không khác nhau nhiều, nếu không nói là giống 90%, sao chênh lệch thời gian kinh khủng vậy:-/

theo lý thuyết code đầu truy cập phần tử 50000000 --> tràn mảng sai.
Chưa biết tại sao kết quả thế này

Bài này mình đã nâng cấp lên 0.05s rồi, hic thấy tụi nó làm 0.00s mà tức định làm thêm nhưng thiết nghĩ vậy tạm được rồi
https://www.spoj.pl/status/COINS,hcmut/

https://www.spoj.pl/status/COINS,anhdung/
--> 0.00s nè, làm từ hồi năm 2005, nên đương nhiên là Pascal

- Cũng làm gần như thế
- dùng hash table để giảm mảng lại, đồng thời đánh dấu những số đã xử ký --> nên nó nhanh

- Cho hỏi ở đâu ra cái này??

for (i=12;i<50000000;++i)
{
table[i] = table[i/2] + table[i/3] + table[i/4];
}
bài của tớ ko có cái phần nhận xét đó, mà vẫn 0.00s, giờ thêm phần này vô thì sao nhỉ

wait some minutes, converting from Pascal to C++... (spam )

Tui có thể đưa xuống 0.01s nhưng 0.00s thì pó, ông Dũng cách hay đưa lên ae tham khảo.
https://www.spoj.pl/status/thanh_hung/
Còn vấn đề Duy hỏi đúng là pó tay, hai cái này gần giống nhau vậy mà thời gian thì ....lạ thật.

figure it out! mọi người nhìn code sau và so sánh

đã tinh chỉnh lại. chú ý khai báo biến i

như sau chạy 2s:

Code:

#include<iostream>
using namespace std;

long arr[50000000];
long long num, sum;
long i;
long long solve(long num) {
   if (num <= 50000000)
      return arr[num];
   return (solve(num / 2) + solve(num / 3) + solve(num / 4));
}

int main() {
   for (i = 1; i < 12; i++)
      arr[i] = i;
   for (i = 12; i <= 50000000; i++)
      arr[i] = arr[i / 2] + arr[i / 3] + arr[i / 4];
   while (cin >> num) {
      if (num > 50000000)
         sum = solve(num);
      else
         sum = arr[num];
      cout << sum << endl;
   }
   return 0;
}

như sau chạy 7s:

Code:

#include<iostream>
using namespace std;

long arr[50000000];
long long num, sum,i;
long long solve(long num) {
   if (num <= 50000000)
      return arr[num];
   return (solve(num / 2) + solve(num / 3) + solve(num / 4));
}

int main() {
   for (i = 1; i < 12; i++)
      arr[i] = i;
   for (i = 12; i <= 50000000; i++)
      arr[i] = arr[i / 2] + arr[i / 3] + arr[i / 4];
   while (cin >> num) {
      if (num > 50000000)
         sum = solve(num);
      else
         sum = arr[num];
      cout << sum << endl;
   }
   return 0;
}

Cảm ơn anh Thuận.
Cái biến i be bé vậy mà kinh thật.
https://www.spoj.pl/status/COINS,bt25/ ->1.94s
Mấy anh có cách làm 0.01, 0.00s submit vô acc hcmut đi, cho đàn em mở rộng tầm nhìn:D

bản chất sau lưng nó là việc ép kiểu Long Long --> Long

Từ nay mỗi lần for hãy khai báo biến cho chắc ăn . Đúng là kinh nghiệm "xương máu" thật.

#include <iostream>
using namespace std;

//typedef struct link *Plink;

struct link{
int so;
long long value;
link *next;
};

int n;
link *hash[10000];

long long DaXet(int so) {
link *p;
p = hash[so%99�73];

while (p != NULL) {
if (p->so==so) return p->value;
p = p->next;
}
return -1; //chua co
}

int add(int so, long long value) {
link *p;
int i = so�%9973;

p = new link;
p->so = so;
p->value = value;
p->next = NULL; //null
hash[i] = p;
}

long long pt(int so) {
long long v;
if (so <= 10) return so;

v = DaXet(so);
if (v==-1) { //chua xet
v = pt(so/2) + pt(so/3) + pt(so/4);
if (v < so) v = so; //neu doi ra ma nho hon thi ko doi
add(so, v);
}
return v;
}

int main() {
memset(hash, 0, sizeof(hash));
while (cin>>n) {
cout<<pt(n)<<endl;
}
//system("PAUSE");
}

nói chung hướng là như thế, nhưng nỗ lực convert bất thành, ở dưới máy mình chạy ngon lành, submit lên đó thì nó báo lỗi tá lả, cụ thể như sau. Ai rành con trỏ coi sửa lại xem nó bị cái j

/sources/tested.cpp:13: error: expected constructor, destructor, or type conversion before '*' token
/sources/tested.cpp: In function 'long long int DaXet(int)':
/sources/tested.cpp:16: error: 'p' was not declared in this scope
/sources/tested.cpp:17: error: 'hash' was not declared in this scope
/sources/tested.cpp: In function 'int add(int, long long int)':
/sources/tested.cpp:27: error: 'p' was not declared in this scope
/sources/tested.cpp:30: error: expected type-specifier before 'link'
/sources/tested.cpp:30: error: expected `;' before 'link'
/sources/tested.cpp:34: error: 'hash' was not declared in this scope
/sources/tested.cpp: In function 'int main()':
/sources/tested.cpp:51: error: 'hash' was not declared in this scope

code của Thanh Hùng 0.00s rồi đó
https://www.spoj.pl/status/COINS,hcmut/
để xem code Dũng thử

nguyên bản pascal đây

Type Plink = ^Link;
link = record
so: longint;
value: int64;
next: Plink;
End;
var n: longint;
Hash: array [1..10000] of Plink;

Function DaXet(so: longint): int64;
Var p: Plink;
Begin
p := Hash[so mod 9973];
DaXet := -1;
While p <> nil do
Begin
If p^.so = so then
Begin
DaXet := p^.value; exit
End;
p := p^.next
End;
End;

Procedure Add(so: longint; value: int64);
Var p: Plink;
i: longint;
Begin
i := so mod 9973;
New(p);
p^.so := so; p^.value := value;
p^.next := Hash[i]; {nil}
Hash[i] := p;
End;

Function Pt(so: longint): int64;
Var v: int64;
Begin
If so <= 10 then
Begin
Pt := so; exit
End;
v := DaXet(so);
If v = -1 then {chua xet}
Begin
v := Pt(so div 2) + Pt(so div 3) + Pt(so div 4);
If v < so then v := so; {neu doi ra ma nho hon thi ko doi}
Add(so, v);
End;
Pt := v;
End;

Procedure main;
Begin
Fillchar(Hash, SizeOf(Hash), 0);
While not eof do
Begin
readln(N);
Writeln( Pt(N) );
End;
End;

BEGIN main END.

f(n) = 3*f(n/+f(n/9)+5*f(n/12)+2*f(n/16)+2*f(n/18)+2*f(n/24);

chứng minh giùm chút đi

Code:
1 //return (fun(n/2)+fun(n/3)+fun(n/4));
2 //return 2*fun(n/6)+3*fun(n/+fun(n/9)+3*fun(n/12)+2*fun(n/16);
3 return 3*fun(n/+fun(n/9)+5*fun(n/12)+2*fun(n/16)+2*fun(n/18)+2*fun(n/24);

Theo thứ tự đó chính là cách tối ưu dần
Từ 1 ta phân tích tiếp, với đ/k n/2>= 12 ta có 2 fun(n/2) = fun(n/2/2)+fun(n/2/3)+fun(n/2/4) rồi cộng dồn
Tương tự từ 2 phân tích rồi cộng dồn fun(n/6)