2017年5月24日 星期三

UVA Q591:Box of Bricks

Q591:Box of Bricks
3歲的小明喜歡玩他的方塊積木,他總是把方塊疊在一起形成高度不一的方塊堆。然後他說:這是一面牆。5歲的姊姊小美聽到了就跟小明說:真正的牆高度應該要一樣才行。小明聽了覺得有道理於是決定要搬動一些方塊使所有方塊堆的高度一樣。如下圖。由於小明是個懶惰的小孩,他想要搬動最小數目的方塊以達成這個目的,你能幫助他嗎?

  
Input
輸入包含好幾組資料,每組資料有2行,第一行有一個數字n,代表有幾堆方塊。第二行有n個數字分別代表這n堆方塊的高度hi。你可以假設1<=n<=50  1<=hi<=100
方塊的總數一定可以整除堆數
n,也就是說一定可以使所有的方塊堆同樣高度。
如果輸入的
n=0,代表輸入結束。 
Output
對每一組輸入資料,首先輸出一行這是第幾組測試資料,下一行為"The minimum number of moves is k." k在這裡就是需搬動方塊最小的數目以使所有的方塊堆同一高度。每組測試資料後亦請空一行。請參考Sample Output. 
Sample Iutput
6
5 2 4 1 7 5
3
1 1 1
0
Sample Output
Set #1
The minimum number of moves is 5.

Set #2
The minimum number of moves is 0.

#include<iostream>
#include<math.h>
#include<cstring>
#include<iomanip>
using namespace std;
int main(){
 int a,b[50],c,d,e=0;
 while(cin>>a){
  e++;
  if(a==0){
   break;
  }
  c=0;
  d=0;
  for(int x=0;x<a;x++){
   cin>>b[x];
   c=c+b[x]; 
  }
  c=c/a;
  for(int x=0;x<a;x++){
   if(b[x]>c){
    d=d+b[x]-c;
   }
  }
  cout<<"Set #"<<e<<endl<<"The minimum number of moves is "<<d<<"."<<endl<<endl;
 }
system ("pause");
return 0;
}

2017年5月15日 星期一

TCGS b004: 一個都不能少

內容: 
進德女子監獄座落於自由女中旁,是間作風開放的監獄,每到中午時間便會放風讓收容人到外面用餐。當然還是會有人逾時不歸,身為管理者的美惠,每天總是要為哪些人沒有回來而傷透腦筋。現在想請你寫一個程式,幫助美惠找出哪些人沒有回來。
輸入說明:
一開始有兩個正整數 N、M (0<=M<N<=20),N 代表收容人的人數(編號從 1 到 N),M 代表回來的人數,接下來有 M 個正整數,分別代表這 M 位已經回來的收容人編號(不用考慮編號超出範圍或其他錯誤)。
輸出說明:
請將沒有回來的收容人編號從小到大輸出,兩個編號中間請空一格。
範例輸入:
輸入1:
4 3 1 2 3

輸入2:
5 3 5 3 1
範例輸出 :
輸出1:
4

輸出2:
2 4

程式碼:
#include <iostream>
using namespace std;
int main()
{
int a,n,b,c[20];
cin>>a>>n;
for(int x=0;x<a;x++){
c[x]=x+1;
}
for(int x=0;x<n;x++){
cin>>b;
c[b-1]=0;
}
for(int x=0;x<a;x++){
if(c[x]!=0){
cout<<c[x]<<" ";
}
}
system("PAUSE");
return 0;

}

UVA Q11614 - Etruscan Warriors Never Play Chess

這題我是用等差級數然後再用一元二次方的公式解解題的(一元二次方程式求出來的值若非整數直接無條件捨去)。
程式碼:
#include<iostream>
#include<cmath>//sqrt()(平方根)的函數庫
using namespace std;
int main(){
long long int n,b,c;
cin>>c;//輸入有幾個測資
for(int x=0;x<c;x++){//連續輸入
cin>>n;//連續輸入
b=((-1)+sqrt(1+(8*n)))/2;//用公式解解
cout<<b<<endl;//輸出答案
}

system ("pause");
return 0;
}


UVA Q12405 - Scarecrow

           這題是貪婪解法,在陣列依依搜尋,如果遇到良田(.),就在良田後一塊地建一個稻草人,所以被搜尋到的那塊良田與接下來的兩塊地都被保護到了,所以一搜尋到良田就直接跳到後三格並繼續搜尋直到結束,這樣就知道最少要放幾個稻草人了。

程式碼:


#include<iostream>
using namespace std;
int main(){
int a,b,d;
char c[100];
cin>>a;//輸入有幾組測資
for(int x=1;x<=a;x++){//連續輸入
        cin>>b;//輸入陣列有幾項
cin>>c;//輸入陣列
d=0;//初始化d(稻草人數)
for(int y=0;y<b;y++){//搜尋陣列裡的良田
if(c[y]=='.'){//當遇到良田
d++;//有幾個稻草人
y=y+2;//跳三格(包括for迴圈裡的y++)
}
}
cout<<"Case "<<x<<": "<<d<<endl;//輸出這是第幾組測資(x)與最少要見幾個稻草人(d)
system("pause");
return 0;
}

2014年5月29日 星期四

2013 國中組初賽-題目 A 挑食的大胃王

[解法ㄧ] #include<iostream>
using namespace std;
int main(){
int T,M,N,K,ans;
cin>>T;
while(T--){
ans=0;
cin>>M>>N>>K;
int eat[M][N];

for(int i=0;i<M;i++){            //輸入原始陣列值
for(int j=0;j<N;j++){
cin>>eat[i][j];
}
}


for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
if(eat[i][j]%2==1){          //除以2餘數等於1
if(i-1>=0)               //將會被挖掉的位置確定
eat[i-1][j]+=2;     //eat[i][j]=eat[i][j]+2
if(j-1>=0)
eat[i][j-1]+=2;
if(i+1<M)
eat[i+1][j]+=2;
if(j+1<N)
eat[i][j+1]+=2;
eat[i][j]+=2;
}
}
}


for(int i=0;i<M;i++){               //計算出會被挖掉的值
for(int j=0;j<N;j++){
if(eat[i][j]){
ans++;                  //ans=ans+1
}
}
}
if(K>=3)                            //可食用的白飯量
       cout<<N*M*K-ans*3<<endl;
else
cout<<N*M*K-ans*K<<endl;  
}
return 0;

[解法二]
#include <cstdio>
#include <cstring>
int main()
{
int T , M , N , K , Map[60][60] , Answer;
scanf("%d",&T);
while( T-- )
{
scanf("%d%d%d",&M,&N,&K);

memset( Map , -1 , sizeof(Map) );      //設定陣列內的值全為-1

for( int i = 1; i <= M; i++ )          //輸入原始陣列值
for( int j = 1; j <= N; j++ )
scanf("%d",&Map[i][j]);

Answer = 0;

for( int i = 1; i <= M; i++ )               //尋找位置上的值=1時, 將附近的位置替換成-1,
for( int j = 1; j <= N; j++ )           // 且計數本身及被替換的位置數量
{
if( Map[i][j] != 1 )continue;      
else
{
Answer++;
if( Map[i-1][j] == 0 )Answer++ , Map[i-1][j] = -1;
if( Map[i+1][j] == 0 )Answer++ , Map[i+1][j] = -1;
if( Map[i][j-1] == 0 )Answer++ , Map[i][j-1] = -1;
if( Map[i][j+1] == 0 )Answer++ , Map[i][j+1] = -1;
}
}
printf("%d\n",M*N*K-Answer*3);


}
return 0;
}
資料來源:
NPSC補完計劃 http://www3.tcgs.tc.edu.tw/npsc/index.php

NPSC補完計劃