b024: 指南宮的階梯 (luke)

1. /**********************************************************************************/  
2. /*  Problem: b024 "指南宮的階梯" from 動態規劃-爬樓梯問題                                        */  
3. /*  Language: C++                                                                 */  
4. /*  Result: AC (4ms, 184KB) on ZeroJudge                                          */  
5. /*  Author: luke at 2014-08-23 15:38:35                                           */  
6. /**********************************************************************************/  
7.   
8. #include <iostream>  
9. #include <iomanip>  
10. #include <stdio.h>  
11. using namespace std;  
12. long long int a[100];  
13. long long int solve( int number){  
14.     if(a[number]!=0){  
15.         return a[number];  
16.     }  
17.     if(number==1){  
18.         a[1]=1;  
19.         return 1;  
20.     }  
21.     if(number==2){  
22.         a[2]=2;  
23.         return 2;  
24.     }  
25.     else{a[number]=solve(number-1)+solve(number-2);  
26.         return solve(number-1)+solve(number-2);}  
27. }  
28. int main () {  
29.     int m;  
30.     cin>>m;  
31.     cout<<solve(m)<<" ";  
32.     long long int k=solve(m);  
33.     int v=k%m;  
34.     cout<<solve(v);  
35.       
36.       
37.        return 0;  
38. }  

b021 "指考分發" (skipper)

1. /**********************************************************************************/  
2. /*  Problem: b021 "指考分發" from 排序-複合欄位                                             */  
3. /*  Language: C++                                                                 */  
4. /*  Result: AC (4ms, 200KB) on ZeroJudge                                          */  
5. /*  Author: skipper at 2014-08-22 10:30:20                                        */  
6. /**********************************************************************************/  
7.   
8. #include <iostream>  
9. #include <algorithm>  
10. #include <numeric>  
11. using namespace std;  
12. struct Score {  
13.     int no,subj[5],total;  
14. };  
15. bool compare (Score a,Score b) {   
16.     if (a.total>b.total) return true;      
17.     if (a.total==b.total) return a.subj[2]>=b.subj[2];  
18.     return false;   
19. }  
20.   
21. int main ()  
22. {  
23.     int N; cin >> N;  
24.     Score *s;  
25.     s= new Score[N];  
26.     for (int i=0;i<N;i++){  
27.         cin >> s[i].no; s[i].total = 0;  
28.         for (int j=0;j<5;j++) { cin >> s[i].subj[j];}  
29.         s[i].total=accumulate(s[i].subj,s[i].subj+5,0);  
30.     }  
31.       
32.     sort(s,s+N,compare);  
33.     for (int i=0;i<N;i++){  
34.         cout << s[i].no << endl;  
35.     }  
36. }  

執行時間測量(gcd)

#include <time.h>

#include <iostream>

#include <math.h>

#include <algorithm>

using namespace std;

int gcd1(int a, int b){

     for (int d = 1; d <= min(a, b); d++){

         if (a%d == 0 && b%d == 0) return d;

     }

}

int gcd2(int a, int b){

     if (a<b) swap(a, b);

     if (a%b)

         return b;

     else

         return gcd2(a - b, b);

}

// source: http://www.math.wustl.edu/~victor/mfmm/compaa/gcd.c

/* Standard C Function: Greatest Common Divisor */

int gcd(int a, int b)

{

     int c;

     while (a != 0) {

         c = a; a = b%a;  b = c;

     }

     return b;

}

/* Recursive Standard C Function: Greatest Common Divisor */

int gcdr(int a, int b)

{

     if (a == 0) return b;

     return gcdr(b%a, a);

}

void main(){

     clock_t begin = clock();

     // your CODE

     srand(clock());

     int x = rand();

     int y = rand();

     for (int i = 0; i < 100000000; i++){

         gcd1(x, y);

     }

     clock_t end = clock();  

     cout << end - begin;

     //system("pause");

}

NPSC2008國中組決賽 C.喵喵捉老鼠 (Queue 的應用)

g047

#include <iostream>
#include <string>
#include <map>
#include <queue>
using namespace std;
int grid[100][100],N,M;
map<char,int> tr;
enum {WALL=-3,MOUSE,SPACE,CAT};
struct Position {int r; int c;};
Position k; 

queue<Position> q;
Position moves[4]={{0,1},{1,0},{0,-1},{-1,0}};
bool FOUND;
int steps;
int main(){
 tr['#']=WALL, tr['@']=MOUSE, tr['.']=SPACE, tr['K']=CAT;
 while(cin>>N && N>0){
  for (int i=0;i<N;i++){
   string row; cin >> row;
   M = row.length();
   for (int j=0;j<M;j++){
    grid[i][j]=tr[row[j]];
    if (row[j]=='K') {k.r=i; k.c=j;};
   }
  }
  FOUND = false;
  while(!q.empty()) q.pop();
  q.push(k);
  while(!q.empty()&&(!FOUND)){
   k=q.front();q.pop();
   steps = grid[k.r][k.c]+1;
   for (int i=0;i<4 &&(!FOUND);i++){
    Position p = {k.r+moves[i].r, k.c+moves[i].c};
    switch(grid[p.r][p.c]){
    case MOUSE:
     FOUND=true;     
     break;
    case SPACE:
     grid[p.r][p.c]=steps;
     q.push(p);
    }
   }
  }
  if(FOUND)
   cout << steps << endl;
  else
   cout << "= =\"" << endl;
 }
}

烤餅乾(51.471秒) Luke

// accessing mapped values
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <ctime>
 
using namespace std;
int main ()
{
clock_t begin = clock();
  int numofcase;
  cin>>numofcase;
  for(int z=0;z<numofcase;z++){
   int testnum;
   cin>>testnum;
   int numofans=0;
   
   for(int i=1;i<testnum;i++){
    for(int j=1;j<testnum;j++){
     for(int k=1;k<testnum;k++){
      if((i+j+k)==testnum&&i<=j&&j<=k&&i<=k){
       int m=max(i,j);
       int n=max(m,k);
       if(testnum%2==1){
        if(n<=testnum/2){
         numofans++;
        }
       }
       if(testnum%2==0){
        if(n<testnum/2){
         numofans++;
        }
       }
      }
 
       
      
      
      
     }
    }
   }
   cout<<numofans<<endl;
  }
  clock_t end = clock();
  double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
  cout << elapsed_secs;
}

蚯蚓王

// accessing mapped values
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
using namespace std;
int main ()
{
  map<int,int> m;
  queue<int> q;
  int T,N,n;
  cin >> T;
  while(T--){
   cin >> N;
   n=N;
   while(n--){
    int k;
    cin >> k;
    if (m[k]) m[k]++;
    else {
   m[k]=1;
   q.push(k);
    }
   }
   bool found=false;
   while(!q.empty() && !found){
    int k = q.front();
    if (m[k]>N/2){
     cout << k << endl;
     found = true;
    }
    q.pop();
   }
   if (!found) cout << -1 << endl;
  }
  return 0;
}

測資 a+b+c+abc=n, 第一行為筆數

pa.in

32
40
54
82
96
124
138
166
84
128
150
194
260
174
204
294
354
120
184
149
7488
81576
716808
9654
56
36
32064
426936
14064
29736
135336
13128
1388

pa.sol

6
10
18
22
30
34
42
10
18
22
30
42
18
22
34
42
8
16
54
12
80
28
138
4
0
180
88
60
80
100
136
54




Code

#include <iostream>
using namespace std;
int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
int compute(int a, int b,int c){
 return a+b+c+a*b*c;
}
int deviation(int a, int b,int c){
 return abs(a-b)+abs(b-c)+abs(c-a);
}
int solve(int n){
 for (int i=0;i<25;i++){
  for (int j=0;j<25;j++){
   for (int k=0;k<25;k++){
    if (n==compute(p[i],p[j],p[k])){
     return deviation(p[i],p[j],p[k]);
    }
   }
  }
 }
}
 
int main(){ 
 int cases;
 cin >> cases;
 for (int i=0;i<cases;i++){
  int n;
  cin >> n;
  cout << solve(n) << endl;
 }
 return 0;
}