NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2003國中組決賽
 B 石板

作者 主題: B 石板  (閱讀 427 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
B 石板
« 於: 四月 17, 2015, 04:23:57 pm »

題目大意:一條路共有100個石板,最多10人走過,起點一定是第1塊,
 每人的步距不一,可以1~100,步距2的會踏到1,3,5,...99,距50的1,51
 輸入第一行有一個數字t,代表t組資料,接著2*t列,每組2列
 每組的第1列n,代表有n個人(1<=n<=10),第2列n個數字Li,代表
 這n個人的步距1<=L1~Ln<=100
 每一組資料輸出一列(1個數字),這100塊石板被踩到最多下的有幾塊

解題:n個步距的最小公倍數 g,則ans = 99/g+1
這題若測資 t 不大就沒問題,但若太大呢?

所以我決定先跑一個100x100的lcm[][]:1~100兩兩的最小公倍數
每組的n個數字,前1個a, 後1個b
cin >>a; 
for(i=1;i<n;++i)
{
  cin >> b;
  a = lcm[a][ b];
}
a 即是這 n 個數字的最小公倍數
代碼: [選擇]
/*
npsc03-j2b 石板
題目大意:一條路共有100個石板,最多10人走過,起點一定是第1塊,
 每人的步距不一,可以1~100,步距2的會踏到1,3,5,...99,距50的1,51
 輸入第一行有一個數字t,代表t組資料,接著2*t列,每組2列
 每組的第1列n,代表有n個人(1<=n<=10),第2列n個數字Li,代表
 這n個人的步距1<=L1~Ln<=100
 每一組資料輸出一列(1個數字),這100塊石板被踩到最多下的有幾塊

解題:n個步距的最小公倍數 g,則ans = 99/g+1
這題若測資 t 不大就沒問題,但若太大呢?
所以我決定先跑一個100x100的lcm[][]:1~100兩兩的最小公倍數
每組的n個數字,前1個a, 後1個b
cin >>a; 
for(i=1;i<n;++i)
{
  cin >> b;
  a = lcm[a][b];
}
a 即是這 n 個數字的最小公倍數
*/
#include <iostream>
#include <sstream>
#include <cstring>
using namespace std;
int gcd(int a, int b)
{
int r;
while( r=a%b )
{
a=b;
b=r;
}
return b;
}
int lcm[101][101];
int main()
{
  int i,j,k;
memset(lcm,0,sizeof(lcm));
lcm[100][100]=100;
for(i=1; i<100; ++i)
{
lcm[i][i]=i;
for(j=i+1; j<=100; ++j)
{
if(lcm[i][j]!=0) continue;
k=i*j;
lcm[i][j] = lcm[j][i] = k/gcd(j,i);
}
}
int t,n,a,b;
cin >> t;
while(t--)
{
cin >> n;
cin >> a;
for(i=1;i<n;++i)
{
  cin >> b;
  a = lcm[a][b];
}
cout << (99/a+1) << endl;
}
  return 0;
}
/*
4
1
2
1
5
2
2 3
3
2 3 5
-----------
50
20
17
4
*/

« 上次編輯: 四月 17, 2015, 09:29:06 pm 由 rscpp »
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2003國中組決賽
 B 石板