NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2003國中組決賽
 A 數饅頭

作者 主題: A 數饅頭  (閱讀 546 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
A 數饅頭
« 於: 四月 17, 2015, 04:10:16 pm »

題目大意:第1行0<=n<=365假日的個數,接著n列為n個日期 m d
第n+2列為一個數字s代表有s個學期,然後有s列,各八個數字
y1 m1 d1 w1 y2 m2 d2 w2 每學期的開學日及結束日
1900<=y1,y2 、1<=m1,m2<=12、 1<=d1,d2<=12、
1<=w1,w2<=7{代表星期一~星期日}
每週六、日不用上課,假日也不用上課,請問每學期上課天數

解題方式:因為沒說明一學期是否會超過一年(365天以上),若不會的話
     100組*366程式用列舉每一天看是否為假日來計數應該可以使用每一天判斷的方式,程式碼如下
代碼: [選擇]
// NPSC 2003 國決 A 數饅頭
#include <iostream>
using namespace std;
bool isleap(int y)  // 是否閏年
{
  return (y%400==0) || (y%4==0 && y%100!=0);
}
bool hd[13][32]; // 假日則為true
int md[]={366,31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; // 12個月的日期,以366日計
int count( int m1,int d1,int m2,int d2, int *w1)
{
int mi, di, wi = *w1-1, ans=0;  // wi 星期改為 0~6
for(di=d1; di<=md[m1]; ++di, wi=(wi+1)%7 )  // m1月的剩下日期
if( !(wi==5 || wi==6 || hd[m1][di]) ) ++ans;  // 非假日,要上課
for(int mi=m1+1; mi<m2; ++mi)
for(di=1; di<=md[mi]; ++di, wi=(wi+1)%7)  // m1+1 ~ m2-1 月各月的上課日
if( !(wi==5 || wi==6 || hd[mi][di]) ) ++ans;  // 非假日,要上課
if( m2>m1)
  for(di=1; di<=d2; ++di, wi=(wi+1)%7 )  // m2月到d2日之前的日期
if( !(wi==5 || wi==6 || hd[m2][di]) ) ++ans;  // 非假日,要上課
  *w1 = (wi+1);  // 傳回下一日的 w1(改回 1~ 7)
return ans;
}
int main()
{
  int i,n,m,d,s;
  // 假日
  memset(hd,0,sizeof(hd));
  cin >>n;
  for(i=0;i<n;++i)  //
  {
cin >> m >> d;
hd[m][d]=true;
  }
  cin >> s;  // 學期數
  int  y1,m1,d1,w1, y2,m2,d2,w2;
  for(i=0; i<s; ++i)
  {
cin >> y1 >> m1 >> d1 >> w1
>> y2 >> m2 >> d2 >> w2 ;
// 假設開學日在前、結束日在後 ,且一學期不會超過一年
int ans = 0;
if(y1==y2)
{
if( isleap(y1) ) md[2]=29; else md[2]=28;
ans = count(m1,d1,m2,d2,&w1);
} else {
if( isleap(y2) ) md[2]=29; else md[2]=28;
   ans = count(m1,d1,12,31,&w1);
ans += count(1,1,m2,d2,&w1);
}
cout << ans  <<endl;
}
  return 0;
}

但我想寫一個可以超過一年以上的學期{如果要給個期限,就最多一萬年}
另如果開學日比結束日晚或中間都是假日就是0天不會有負的
程式碼另補吧!
想了幾個方式,都不是很滿意,目前的想法是建7x2的整年上課的日數表ytot[7][2]
分別為該年元日為週一~週日的上課日數,又分平閏年:ytot[0][0]元旦為週一的平年
ytot[0][1]為週一閏年,ytot[1][0]為週二平年,ytot[1][1]為週二閏年…
有了這個表應可以計算 y1+1 ~ y2-1之間的上課日數,公式及程式碼懶得做,
留給熱心的「補完人」來補完吧, 應有更好的方式,期待熱心人士。
« 上次編輯: 四月 19, 2015, 11:18:41 am 由 rscpp »
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2003國中組決賽
 A 數饅頭