從雞兔同籠到分子組成推估

Ex1. 雞兔同籠, 雞跟兔的數量都小於一萬

輸入範例

1 // #case

14 7 //腳　頭

輸出範例

7 0 //雞 兔

測資

5

14 7

22 7

9998 4499

556 139

59994 19998

答案

7 0 3 4 3999 500 0 139 9999 9999

Ex2. 外星版雞同籠 (題目設計)

輸入範例

2 3 // #spicies #testcase

2 1 // 物種0的 腳 頭

4 1 // 物種1的 腳 頭

14 7 // 第0籠

22 7 // 第1籠

9998 4499 // 第2籠

輸出範例

7 0

3 4

3999 500

Ex3. 堆積木，以長方堆正方, Ex 2x3 的積木可以堆出的最小正方形, #piece

輸入範例

1 // #case

2 3

輸出範例

6

測資

3 2 3 250 375 30641 25927

解答

6 6 143

Ex4 由分子量推化學式

ax+by+cz=46

x+12y+16z=46, x,y,z >=1

輸入範例

1 //#case   

46 3 //分子量 元素

1 12 16  //原子量

輸出範例

3

18 1 1

6 2 1

2 1 2

測資

3 46 3 1 12 16 60 3 1 12 16 106 3 12 16 23

解答

3 18 1 1 6 2 1 2 1 2 5 4 2 2 16 1 2 8 3 1 20 2 1 32 1 1 1 1 3 2

程式碼

#include<iostream> #include<vector> using namespace std;int main() { int numofcase; cin>>numofcase; while (numofcase--){ int amount=0; int moleculer; cin>>moleculer; int numofelement; cin>>numofelement;    int b,c,e; cin>>e>>c>>b; int bstart=moleculer/b; for(int z=bstart;z>0;z--){ int moleculer2=moleculer; moleculer2=moleculer2-(b*z); int cstart=moleculer2/c; for(int y=cstart;y>0;y--){ int moleculer3=moleculer2; moleculer3=moleculer3-(c*y); if(moleculer3%e==0){ int x=moleculer3/e; cout<<x<<" "<<y<<" "<<z<<endl; amount++; } } } cout<<amount; } system("pause"); return 0; }

Bézout's identity

3x+5y=11, x,yZ, look for (x,y) maximize (x+y)  under the condition: max(x+y)<= 100

#include<iostream>
using namespace std;
int main(){
 int a,b,c;
 cin>>a;
 cin>>b;
 cin>>c;
 int sum=0;
 for(int x=-1000;x<101;x++){

  int x1=x;
  int x2=(-1)*x;
  int y1=(c-a*x1)/b;
  int y2=(c-a*x2)/b;
  if( (y1<=100-x1) && (a*x1+b*y1==c))
  {
   cout<<x1<<" "<<y1<<endl;} 
   //cout<<x1+y1<<endl;
  if((x1+y1>sum)&&(x1+y1<101)/*&&(x1+y1==99)*/)
   {
    sum=x1+y1;
    
   }

  
  if( (y2<=100-x2) && (a*x2+b*y2==c))
  {
cout<<x2<<" "<<y2<<endl;
  //cout<<x2+y2<<endl;
  }
  if((x2+y2>sum)&&(x2+y2<101)/*&&(x2+y2==99)*/)
  {
   sum=x2+y2;
   
  }
 }

 cout<<sum;
 system("PAUSE");
}

貝祖定理(Bézout's identity)

ax+by=m, 求所有解中 x+y 最小的一組 (x,y>0)

輸入
第一行為筆數
之後每行有三個數字 for a b m
3
8 -7 1
13 -16 1
39 -7 1

輸出
1 1
5 4
2 11

#include<iostream>
using namespace std;
int main(){
 int i;
 cin>>i;
 while(i--){
  bool f=false;
  int a,b,c;
  cin>>a>>b>>c;
  for(int j=1;j<300000;j++){
   for(int k=1;k<300000;k++){
    if(a*j+b*k==c){
     cout <<j<<" "<<k<<endl;
     f=true;
           break;
    }
    
   }
   if(f==true){
    break;
    }
  }
 }
 system("PAUSE");
}

Staircase Walk: 走格子 (Stack)

0

1

2

3


4

5

6

7


8

9

10

11


n rows, m colums 

3 rows, 4 columns

/*
Staircase Walk: 走格子的版本, n rows, m columns
相當於 http://mathworld.wolfram.com/StaircaseWalk.html
n=n+1, m=m+1
*/

#include<iostream>
#include<stack>
using namespace std;
int main()
{   
 int n,m,count=0;
 stack<int> s;
 cin >> n >> m;
 s.push(0);
 while(!s.empty()){
  int c = s.top();s.pop();
  if (c==(n*m-1)){
   count++;
  }
  else{
   if ((c+1)%m!=0) s.push(c+1);   
   if ((c+m)<n*m) s.push(c+m);  
  }
 }
 cout << count;
 system("pause");
 return 0;
}