npsc2012: 2013

2013年12月21日星期六

ProblemD-跑者的修煉 => 總結

如果沒有導出公式
1 1000000000 就會Timeout了
種樹問題
oo1oo1oo
每兩棵蘋果樹間要種一棵橘子樹
要種n顆蘋果樹的話，一共種了幾棵樹?

function的使用
數列的推導

ProblemD-跑者的修煉 (Timeout)

#include <iostream>
using namespace std;
long long f( long long m,long long x){
 return x+(x-1)/m;
}
 
long long g( long long m,long long x){
 long long s=0;
 for (long long i=1;i<=x;i++)
  s+=f(m,i);
 return s;
}
 
int main(){
 int T;
 long long m,n;
 cin >> T;
 while(T>0){
  cin >>m>> n;
  cout << g(m,n) << endl;
  T--;
 }
 
 return 0;
}

2013年12月20日星期五

ProblemD-跑者的修煉

#include <iostream>
using namespace std;
int f( int m,int x){
 return x+(x-1)/m;
}
 
int g( int m,int x){
 int s=0;
 for (int i=1;i<=x;i++)
  s+=f(m,i);
 return s;
}
 
int main(){
 int m,n;
 cin >>m>> n;
 cout << g(m,n) << endl;
 system("pause");
 return 0;
}

ProblemD-跑者的修煉

#include <iostream>
using namespace std;
int f(int x){
 return x+(x-1)/5;
}
 
int g(int x){
 int s=0;
 for (int i=1;i<=x;i++)
  s+=f(i);
 return s;
}
 
int main(){
 int n;
 cin >> n;
 cout << g(n) << endl;
 system("pause");
 return 0;
}

2013年12月14日星期六

求三個數中最大 ==> 求六個數中最大值 ==> 求六個數中第三大的

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
 int cases;
 int a[6];
 cin >> cases;
 while(cases--){
 for (int i=0;i<6;i++) cin >> a[i];
 cout << *max_element(a,a+6) << endl;
 }
}

2013年11月18日星期一

分子量計算(2)

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main ()
{
 map <char,int> pt;
 int n,m;
 char ch,pch;
 cin >>n;
 char e;
 int qe;
 for (int i=0;i<n;i++){
  cin >> e >> qe;
  pt[e]=qe;
 }
 
 //'x'
 cin >>m;
 for (int i=0;i<m;i++){
  int q=0;
  while(cin>>ch && ch!='x'){
   if (ch >='2' && ch<='9'){
    q+=pt[pch]*(ch-'0'-1);
   }
   else{
    q+= pt[ch];
    pch=ch;
   }   
  }
  cout << q;
 }
 system("pause");
 return 0;
}

平方取中法

輸入: 3 位數
利用平方取中法產生亂數
規則: 取萬位數到十位數
輸出: 產生到第幾個數的時候開始出現重複?

範例
輸入:123
輸出: 14
計算過程

1	512
2	214
3	579
4	524
5	457
6	884
7	145
8	102
9	40
10	160
11	560
12	360
13	960
14	160
15	560
16	360
17	960
18	160
19	560

平方取中法=>到第幾個數開始出現重複?

#include <iostream>
#include <map>
#include <vector>
#include <iomanip>
using namespace std;
int main(){
 int x;
 map<int,bool> m;
 cin >> x;
 while( (x=((x*x)/10)%1000) && !m[x]){  
  m[x]=true;
 } 
 cout << m.size()+1;
 system("pause");
}
/*
 123 => 14
 172 => 17


輸入: 3 位數

利用平方取中法產生亂數

規則: 取萬位數到十位數

輸出: 產生到第幾個數的時候開始出現重複?




範例

輸入:123

輸出: 14

計算過程

1 512
2 214
3 579
4 524
5 457
6 884
7 145
8 102
9 40
10 160
11 560
12 360
13 960
14 160
15 560
16 360
17 960
18 160
19 560


*/

分子量計算

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main ()
{
  map <char,int> pt;
  char ch,pch;
  pt['H']=1;
  pt['O']=16;
  pt['C']=12;
  //'x'
  int q=0;
  while(cin>>ch && ch!='x'){
   if (ch >='2' && ch<='9'){
  q+=pt[pch]*(ch-'0'-1);
   }
   else{
  q+= pt[ch];
  pch=ch;
   }   
  }
  cout << q;
  system("pause");
return 0;
}
/*

以x標示分子式的結束
CH3COOHx  =>60
CH3CH2COOHx => 74

題目二

輸入資料:

3 <= 構成原子數量

H 1

O 16

C 12

2 <= 分子式數量

CH3COOHx
CH3CH2COOHx
輸出
60
74
*/

平方取中

#include <iostream>
#include <map>
#include <vector>
#include <iomanip>
using namespace std;
int main(){
 int samplesToProduce,x;
 int newseed;
 vector<int> storage;
 cin >> x;
 cin >> samplesToProduce;
 x=x*x; 
 for (int i = 0; i < samplesToProduce; ++i)
 {
        //select the middle six digits for the next seed
  cout << setw(6);
  cout << x << "\t";
        newseed = (x / 10) % 1000;
  cout << setw(3);
  cout << newseed << endl;
  storage.push_back(newseed);        
        x = newseed * newseed;
 }
 system("pause");
}
/*
123 10
512
214
579
524
457
884
145
102
40
160
 
455 100
172 100
*/

5 的 100次方 mod 7 (更精簡版)

#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main(){
 map<int,bool> m; //記錄已經出現的餘數
 vector<int> v;  //依序記錄餘數
 int a,b,c,d;  //a被除數, b除數, c次方, d餘數
 cin >> a >> b >> c;
 d = a%b;  //處理 a<b 的情形
 while(!m[d]){  
  m[d]=true;
  v.push_back(d);
  d=(d*a)%b; 
 } 
 c = c%m.size(); 
 cout<<v[c-1];
 system("pause");
 return 0;
}
/*
 5 7 1 => 5 //(5^1)%7, 5%7
 5 7 100 => 2 //(5^100)%7
*/

2013年11月11日星期一

#include <iostream>
#include <map>
using namespace std;
int main(){
map<int,bool> m; //記錄已經出現的餘數
int a,b,c,d;
cin >> a >> b>>c;
d = a;
while(!m[d]){
m[d]=true;
d=(d*a)%b;
}
//cout << m.size();
c = c%m.size();
d = a;
for(int i=0;i<c-1;i++){
d=(d*a)%b;
}
cout<<d;

system("pause");
return 0;
}/*
5 7 1 => 5
5 7 100 => 2
*/

循環節的長度

#include <iostream>
#include <map>
using namespace std;int main(){
map<int,bool> m;
int a,b;
cin >> a >> b;
a=a%b;
while(!m[a]){
m[a]=true;
a=(a*10)%b;
}
cout << m.size();
system("pause");
return 0;
}

/*
注意用不是用商判斷，用餘數判斷 14143 99999 => 5
1 7 => 7
1231234 9999999 => 7

Excel

=QUOTIENT(B2,99999)

=MOD(B2,99999)

2013年8月30日星期五

bridge and torch (not optimal solution)

#include <iostream>
#include <algorithm>
using namespace std;
void sol1();
 
void print_array(int *A, int n){
 cout << "{ ";
 for(int i=0;i<n;i++){
  cout << A[i] << ' ';
 }
 cout << '}';
}
void print_status(int *A, int n, int *B, int m, int cost){
 cout << endl;
 print_array(A,n);
 print_array(B,m);
 cout << ":" << cost;
 cout << endl;
}
void sol2(){
  int n;
 cin >> n;
 int *A= new int[n]; 
 int *B=A+n;
 int m=0;
 int cost=0;
 
 for(int i=0;i<n;i++){
  cin >> A[i];
 }
 
 if (n<=0){
  cout << "n must be larger than 0";
  system("pause");
  return ;
 }else if(n==1){
  cout << "cost:" << A[0];
  system("pause");
  return ;
 }else if(n==2){
  cout << "cost:" << max(A[0],A[1]);
  system("pause");
  return ;
 }
 
 sort(A,A+n);
 print_status(A,n,B,m,cost);
 
 while(n>0){
  //GO 
  B--;B--;
  cost+=A[n-1];
  swap(A[0],B[0]);
  n-=2;m+=2; 
  print_status(A,n,B,m,cost);
  //BACK
  if (n>0){
   cost+=B[0];//寫錯的地方
   swap(A[0],B[0]);
   B++;
   n++;m--; 
   print_status(A,n,B,m,cost);
  }
 }
 
 cout << "cost:" << cost << endl;
}
int main()
{
 //sol1();
 sol2();
 system("pause");
    
    return 0;
}
// SOURCE: http://hoyusun.blogspot.tw/2012/02/blog-post.html
void sol1(){
 int n;
 cin >> n;
 int *A= new int[n];  
 for(int i=0;i<n;i++){
  cin >> A[i];
 }
    
 int cost = 0;
    sort(A, A+n);
    for(n--; n >= 3; n -= 2){   
        int t1 = A[1] + A[0] + A[n] + A[1];  //AB->A->CD->B, 故B+A+D+B
        int t2 = A[n] + A[0] + A[n-1] + A[0];   //AD->A->AC->A, 故D+A+C+A
        cost += t1<t2?t1:t2; //取最小時間
    }
    if(n == 2)  cost += (A[2]+A[0]+A[1]);    //若三個人時, AC->A->AB故C+A+B
    else if(n == 1) cost += A[1];   //若兩個人時, AB故B
    else    cost += A[0];     //只有一個人, A故A
    cout << cost << endl;
}

2013年8月17日星期六

Array and Pointer

2D Array

http://www.youtube.com/watch?v=ud6C0VnfqI8

Array

http://digital.cs.usu.edu/~watson/cs1410/notes/ch7.ppt‎

Pointer

http://digital.cs.usu.edu/~watson/cs1410/notes/ch9.ppt‎

http://digital.cs.usu.edu/~watson/cs1410/classnotes.htm

Diamond

#include <iostream>
#include <string>
using namespace std;
void method1(){ 
 int n;
 cin >> n; 
 
 //being: init char string a
 char *a = new char[2*n]; 
 for (int i=0;i<2*n-1;i++){
  a[i]=' ';
 }
 a[2*n-1]='\0';
 //end: init char string a
 
 for (int i=0;i<=n-1;i++){    
     a[n-i-1]='A';
     a[n+i-1]='A';  
  cout << a << endl;
 }
 
 for (int i=n-1;i>=0;i--){    
     a[n-i-1]=' ';
     a[n+i-1]=' ';  
  cout << a << endl;
 }
}
 
void method2(){
 int n;
 cin >> n; 
 
 string a=string(2*n,' '); //init string a
 
 for (int i=0;i<=n-1;i++){    
     a[n-i-1]='A';
     a[n+i-1]='A';  
  cout << a << endl;
 }
 
 for (int i=n-1;i>=0;i--){    
     a[n-i-1]=' ';
     a[n+i-1]=' ';  
  cout << a << endl;
 }
}
int main(){ 
 method2();
 system("pause");
}

2013年7月31日星期三

VS 2010 & 線上解題系統

2013年6月29日星期六

Man of Steel

2013 06-29 review from Kai-Ping Hsu

計算機概論與程式設計 Introduction to Computers and Programming, 交大電機工程學系溫宏斌老師有課程影音與講義可下載使用，課本(電子書)在意見回饋裡最後的流言可以找到。

Array(陣列)的補充範例

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){ 
 
 /*

字串的使用:

 char name[] = "曹操"; // in C
 string name = "曹操"; // in C++

如果用三個變數儲存國名，後面要使用就只能用 swtich ...case

 string nation0="魏";
 string nation1="蜀";
 string nation2="吳";
 */
 string nations[3]={"魏","蜀","吳"};
 string names[3][4]=
 {
  {"曹操","曹丕","曹植","司馬懿"},
  {"劉備","關羽","張飛","諸葛亮"},
  {"孫權","周瑜","魯肅","陸遜"}
 };
 
 int ages[3][4]=
 {
  {61,40,37,39},
  {45,43,42,28},
  {27,35,38,25}
 };
 int i=0,j=0;
 cout << "names["<< i << "][" << j <<"] is "  << names[i][j] << endl;;
 cout << endl;
 
 string search_for ="魯肅";
 for (int i=0;i<3;i++){
  for (int j=0;j<4;j++){
   if (names[i][j]==search_for){
    cout << search_for << "is at names["<<i<<","<<j<<"]" << endl;
    cout << search_for << "is" << nations[i] << endl;
    /*
    cout << search_for << "is";
    switch(i){
    case 0: cout << nation0;
     break;
    case 1: cout << nation1;
     break;
    case 2: cout << nation2;
     break;
    }
     cout <<  endl;;
 
   */
      }
  }
 }
 cout << endl;
 // find oldest
 
 //cout << *max_element(ages[0],ages[0]+4);
 
 int oldests[3]= {0};
 
 for (int i=0;i<3;i++)
  oldests[i]= *max_element(ages[i],ages[i]+4);
 
 int oldest = *max_element(oldests,oldests+3);
 
 cout << "最老的人的年齡是:" << oldest << endl;
 
 
 for (int i=0;i<3;i++){
  for (int j=0;j<4;j++){
   if (ages[i][j]==oldest){
    cout << "oddest is " << names[i][j] << endl;
   }
  }
 }
 
 cout << endl;
 
 system("pause");
 return 0;
}

Function (函數) 的補充

求寫一函數計算交錯數列之和
f(n) = 1-2+3-4+....n
維基百科

2013年6月15日星期六

過橋問題

程式練習

數學

不是雙胞胎
不定方程 a+1/b=1 b+1/c=1 c+1/a=?


高斯消去法





張貼者：



Unknown




於

清晨6:56



沒有留言:
  









以電子郵件傳送這篇文章BlogThis！分享至 X分享至 Facebook分享到 Pinterest


        

          
        
2013年6月1日 星期六

          
        






台大資工甄選入學題目





程式

2008年
2009年 


數學

99學年度 第六題 第七題






張貼者：



Unknown




於

凌晨12:22



沒有留言:
  









以電子郵件傳送這篇文章BlogThis！分享至 X分享至 Facebook分享到 Pinterest




較新的文章

首頁




訂閱：
意見 (Atom)












網頁



首頁


NPSC


台中女中解題系統


網路資源


Books










著作人


Unknown
jedi qwerty
joy00526







網誌存檔








        ► 
      



2016

(1)





        ► 
      



1月

(1)









        ► 
      



2014

(56)





        ► 
      



9月

(2)







        ► 
      



8月

(7)







        ► 
      



7月

(8)







        ► 
      



6月

(3)







        ► 
      



5月

(17)







        ► 
      



4月

(4)







        ► 
      



3月

(4)







        ► 
      



2月

(8)







        ► 
      



1月

(3)









        ▼ 
      



2013

(20)





        ▼ 
      



12月

(5)

ProblemD-跑者的修煉 => 總結
ProblemD-跑者的修煉 (Timeout)
ProblemD-跑者的修煉
ProblemD-跑者的修煉
求三個數中最大 ==> 求六個數中最大值 ==> 求六個數中第三大的








        ► 
      



11月

(8)

分子量計算(2)
平方取中法
平方取中法=>到第幾個數開始出現重複?
分子量計算
平方取中
5 的 100次方 mod 7 (更精簡版)
5 的 100次方 mod 7
循環節的長度








        ► 
      



8月

(3)

bridge and torch (not optimal solution)
Array and Pointer
Diamond








        ► 
      



7月

(1)

VS 2010 & 線上解題系統








        ► 
      



6月

(3)

Man of Steel
過橋問題
台大資工甄選入學題目



























簡單主題. 技術提供：Blogger.

1	512
2	214
3	579
4	524
5	457
6	884
7	145
8	102
9	40
10	160
11	560
12	360
13	960
14	160
15	560
16	360
17	960
18	160
19	560

1	512
2	214
3	579
4	524
5	457
6	884
7	145
8	102
9	40
10	160
11	560
12	360
13	960
14	160
15	560
16	360
17	960
18	160
19	560

1	512
2	214
3	579
4	524
5	457
6	884
7	145
8	102
9	40
10	160
11	560
12	360
13	960
14	160
15	560
16	360
17	960
18	160
19	560

1	512
2	214
3	579
4	524
5	457
6	884
7	145
8	102
9	40
10	160
11	560
12	360
13	960
14	160
15	560
16	360
17	960
18	160
19	560

2013年12月21日 星期六

2013年12月20日 星期五

2013年12月14日 星期六

2013年11月18日 星期一

2013年11月11日 星期一

2013年8月30日 星期五

2013年8月17日 星期六

2013年7月31日 星期三

2013年6月29日 星期六