数学建模社区-数学中国

标题: POJ-1006问题 [打印本页]
作者: maybe_madio    时间: 2010-10-26 23:30
标题: POJ-1006问题
POJ-1006* ]+ e. D  B# d, ]7 x' I8 k
- k1 @; y  \) V! f
在本地VC6.0下测试，得出正确结果， 为什么提交后总是Wrong Answer
4 u+ F+ U, K2 F( }, X5 j5 r9 V
# b  Q" F% I: R! y% S0 p现将代码贴出，请帮忙看看：: q" V* B' M& M
  1. #include <iostream>
    2 C* t& K& k& d1 z
  2. using namespace std;9 p$ k% y5 \) i  `
  3. #define PH      0, T# z. {7 q6 Y! k) a: o7 G; H
  4. #define EM      1, A9 G' E% D' J
  5. #define IN      2; k: n; G0 D* c
  6. int get_Top(int days, int kind);8 J( u1 m* c- ?4 K. J9 P. P3 f' M
  7. int triple(int ptop, int etop, int itop, int cur);
    & F8 e0 {7 s* a
  8. bool is_Integer(float n);
      N7 ], d" H. D7 E" Z
  9. int main()
    ' L! t  e2 n/ N! U8 |$ O: W) x- h+ H
  10. {
    $ T/ k* b& y7 {( f# a" |" g# h
  11. int ptop,  etop,  itop;. \6 K" o! m* g- ~+ }7 i1 S
  12. int pdays, edays, idays, curdays;
    # B1 B  l" l5 R; A
  13. int count =0;) d- O; k, x; {2 J" J

  14. ! y! E# l5 p* t% q' {
  15. while(cin >> pdays >> edays >> idays >> curdays)! m+ i. J2 t+ E1 t: \3 T
  16. {* S0 R1 j' s: a% P
  17.   if(pdays==edays&&pdays==idays&&pdays==curdays&&pdays==-1)
    $ j' I7 {( k% D3 W
  18.    break;
    1 D2 v& t0 y4 k" m1 p7 f
  19.   count++;. y1 X% x/ H7 }, Y
  20.   ptop = get_Top(pdays,PH);( h: M7 w0 H3 ]  |8 v/ t3 q) V
  21.      etop = get_Top(edays,EM);, f8 `- t# p1 h- {
  22.      itop = get_Top(idays,IN);
    ; ?6 V9 m! ]5 i3 O  |$ h9 j/ [" P
  23.   cout<<"Case "<<count<<": "<<"the next triple peak occurs in "<<triple(ptop, etop, itop, curdays)<<" days.";- X+ I7 |$ i6 w. `+ g$ V
  24. }
    ! @; @" F8 ?) k3 I

  25. . }6 _3 ^, Q, T3 D
  26. return 0;
    , C4 T8 l* x* Q4 f
  27. }
    * {3 Q+ S! ?" [
  28. int get_Top(int days, int kind)
    8 ^! S7 ~! Q! v4 F7 q; r) Z
  29. {
    ! c  @4 J: }7 v' m* Y0 K7 Z4 N
  30. switch(kind)3 m. d+ A- S2 t/ h# |
  31. {# o( L4 c6 v: y: N- T, z0 V
  32. case 0:, f+ |, T' V& L# N, P7 T% C
  33.   return days%23;
    ! n& E/ E  M: E; p& Z: \. u
  34. case 1:& ?9 L3 \+ S8 B# c, L& A7 E1 a7 Q
  35.   return days%28;! P# f0 P$ D% f' M
  36. case 2:  G$ T( d  L: ]; r$ k  T9 B
  37.   return days%33;
    7 A" l# m; C1 s. ~! a
  38. }
    ' j: r+ ^0 n' _
  39. return 0;
    2 w0 k" h% V* i- [4 |) y) A
  40. }
    / h, p6 j9 a7 r/ \; C

  41. 6 V" i2 S8 @6 r' I4 x% |# w
  42. int triple(int ptop, int etop, int itop, int cur)
    0 |" `9 K/ u  n0 U/ ^
  43. {
    5 W+ r3 I. X+ p6 k/ ]$ e& J
  44. float x, y, z;
    4 h: |- ]! S5 u
  45. int m1   = etop-ptop-5,
    0 N7 S( a5 {; L, b7 Q
  46.   m2   = itop-etop-5;
    4 Y* ^9 H0 i, E: _+ r- _
  47. int temp = 0;4 O/ m9 g7 Z4 t: s( l* i/ r) k! ]
  48. for(z=2;  (itop+(z-1)*33) <= 21252;  z++)( q9 d! m4 l9 B2 ^. Z% C
  49. {
    0 W- P& {* {5 X4 W7 l: S, X
  50.   temp = m2 + 33*z;) w6 c2 u9 I2 V) j
  51.   y = (float)temp/28;
    " F4 n; C% H" P( k7 I1 A/ x
  52.   x = (float)(m1+temp)/23;
    % O- Z0 j; t* p
  53.   if(x>0 && y>0 && is_Integer(x) && is_Integer(y))! W* v. r% d9 x* Y
  54.    return itop + (z-1)*33 -cur;: F* _. L% X( B# j' _
  55. }! K* E( S2 o7 Z# n/ O8 y3 v
  56. return 0;6 y8 t* m2 ^' P6 a! ^
  57. }' n( y. ~% x. _( U

  58.   ?. Z) P) O% v3 \* c
  59. bool is_Integer(float n)
    0 _' \$ N: q6 }; y
  60. {/ c% X9 t2 h) h6 Q" f* R) x
  61. if( (int)n - n ==0)' {9 \4 v2 c# }8 z$ a
  62.   return true;
    # U9 W3 K6 a9 K% V7 U. d
  63. else% H1 U/ Q4 q: U& ^2 o
  64.   return false;3 L, @+ K0 u) W! u. Y4 `
  65. }; D. A3 S0 I  u) p. k9 d
  66. # b/ k0 [4 K; e% d0 I! J' A8 p
复制代码

# N" w7 {5 u% l5 y+ G. m6 u, O
作者: ultra1989    时间: 2010-10-27 08:45
本帖最后由 ultra1989 于 2010-10-27 08:54 编辑
3 V$ G# j3 |* k7 x3 n8 i; ^+ f
# T0 q8 X8 B4 D9 @' K+ O+ c! M用float可能会有精度问题用中国剩余定理求解8 J9 J( Y/ s4 C( m# D* L" ^
参考程序：
# P) i. z1 e& x3 n% T; d3 T) b1 p4 h& z2 D0 F+ W7 j( n/ P
#include<stdio.h>3 [1 l5 X  Q. s
int main(){
) r$ Q+ H6 v% p2 r( r3 B   int a,b,c,m,n,i,d=1;! d6 Y* w8 j7 C' t3 U8 F* {4 x
   while(scanf("%d%d%d%d",&a,&b,&c,&m)){
. g/ u6 T/ `+ P- f
9 H4 g6 U4 w) Y" X! Aif(a==-1&&b==-1&&c==-1&&m==-1) break;( t2 b  T3 H. j# a2 _+ A+ v$ _

3 k+ y7 u1 n9 d5 h4 [n=0;
6 S) q. U# Y% {0 S. M$ B/ p8 Q( O& y3 ^% j; \
i=(5544*a+14421*b+1288*c-m+21252)%21252;
1 Y9 w" _0 ]$ [& L$ m) w3 I6 o# |- E1 E. `( H, t$ T* ~
if(!i)
1 {& r# V8 A& b. J+ M% Q3 B( a/ [. ~3 w" a
i=21252;. d% F5 Q6 L/ _9 F1 w, E. w
4 X3 C3 z) ]- s, ^) {
printf("Case %d: the next triple peak occurs in %d days.\n",d++,i);
+ l; B0 h4 d, ^  q  U* y( }$ K1 [6 p. [( l( n7 K
   }
8 Q- Q% Y( C9 _0 o3 f2 p& @$ u
return 0;( ]) B7 t( s: S- [- ?+ C7 i. D' k8 d
}# A3 j: U/ L: A- Z
; l! `2 \1 r; T0 c9 W# k2 O
作者: qbist    时间: 2010-10-27 13:20
作者: 小草远在天涯    时间: 2010-10-27 17:27
好复杂啊，我是初级的。。。路过。。。
作者: maybe_madio    时间: 2010-10-27 22:23
回复 ultra1989 的帖子) H* z/ t6 R) L" k1 I
  w' x9 U  }0 I7 r- @

/ W/ z, Q9 }5 l. Y8 u$ l6 }7 k    确实这道题使用剩余定理解效率太高了！ 哈哈！ 学习了！  我还没有看过数论方面的书！ 以后肯定要看看5 S& Y: R' A" \  j! P4 h0 W

8 F0 U8 k5 I5 E' k" s% b两个程序一对比，一下就体现出数学的强大力量！
- t; o: @/ i& p" z4 f
作者: 39133120    时间: 2010-10-28 23:11
好复杂啊，得仔细
作者: 鸿光满面    时间: 2011-2-4 13:40
好复杂啊         



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5