数学建模社区-数学中国

标题: POJ-1006问题 [打印本页]
作者: maybe_madio    时间: 2010-10-26 23:30
标题: POJ-1006问题
POJ-1006
2 I9 o( u0 K" m8 M9 ?" S: \& _
4 T& G- {2 m& [) C# t+ [在本地VC6.0下测试，得出正确结果， 为什么提交后总是Wrong Answer
/ H" p  s$ }7 D5 y4 j2 G1 p# U' u# _* ]( Z
现将代码贴出，请帮忙看看：
! L$ Y" K& m  P- Z1 H' i/ A
  1. #include <iostream>
    ' l+ S2 A% T( u8 i3 o
  2. using namespace std;
    4 _7 s! w4 k6 E; R3 N# i( ]6 x
  3. #define PH      0
    " T$ o" A) h; G9 x. Y9 D
  4. #define EM      1
    ' X8 e! u2 p$ p
  5. #define IN      2! g( X* o/ t% y5 c" ^- O
  6. int get_Top(int days, int kind);  ?1 K* k  E* p# ~
  7. int triple(int ptop, int etop, int itop, int cur);
    - X; I) t  R8 K$ a/ O
  8. bool is_Integer(float n);
    5 V7 J* W" m: c7 N+ M8 H
  9. int main()
    6 F3 ~6 f. z% q* _  y2 v
  10. {
    ) h* K, N( T% _/ W# ~1 L9 E& b
  11. int ptop,  etop,  itop;# r' N) l' k! ~& C4 [5 m" p
  12. int pdays, edays, idays, curdays;
    4 \9 ~/ N$ Z% ?
  13. int count =0;
    8 ?% C3 z; B7 h" k. Q

  14. 7 u: J/ y4 N. J/ q. d
  15. while(cin >> pdays >> edays >> idays >> curdays)+ O# |* P3 Q) b. U* |* b6 d& Q
  16. {# X5 L3 C0 `/ D/ ^  V
  17.   if(pdays==edays&&pdays==idays&&pdays==curdays&&pdays==-1)
    ( d1 @4 o9 x) o  \  [5 N
  18.    break;" `4 _6 v4 E/ d
  19.   count++;) k  W3 `( f, b; d3 W
  20.   ptop = get_Top(pdays,PH);
    . z) y& S$ ^$ A# @) a- S* v
  21.      etop = get_Top(edays,EM);$ u  N8 q* ^6 e9 }
  22.      itop = get_Top(idays,IN);. o" ~3 J! Z. G7 i4 z" |8 n0 B& ]+ A
  23.   cout<<"Case "<<count<<": "<<"the next triple peak occurs in "<<triple(ptop, etop, itop, curdays)<<" days.";9 }1 |- B" b: \  a; _  ?: K
  24. }
    . p7 S$ j: I9 @# E, A0 ?
  25. . c4 `) t/ M9 r( }8 N; w6 _2 b# Y& R- {
  26. return 0;
    " O5 l& M- p' K9 ^5 Y9 \
  27. }
    2 f+ Y0 f: Z2 a; G& k" g
  28. int get_Top(int days, int kind)
    % q  N& t4 G) f
  29. {$ R! b0 [4 G1 e& M" \
  30. switch(kind): ], t: k- X$ m+ Y. l8 {
  31. {; \( p6 y6 ^3 u' R
  32. case 0:
      W! |! d- C2 u
  33.   return days%23;
    # R2 ^: D5 g1 C- c* p
  34. case 1:
    3 S/ c  A: x4 R/ W3 Z+ k- s
  35.   return days%28;! }4 {% {; p# y5 L0 m0 s
  36. case 2:
    * R4 Q. n7 B4 Y- w3 Y
  37.   return days%33;
    0 i: B" P; W8 n& ?( _
  38. }
    1 t3 i# r: c. l7 ?
  39. return 0;8 F% f3 J$ v+ ?( r: m; m! u
  40. }1 x" W  Z7 T, Y  N- H1 J
  41. ; P7 @+ n0 ~" v* ?6 s
  42. int triple(int ptop, int etop, int itop, int cur)
    8 j# v* [; X. Z0 l1 Z0 [
  43. {! Y% {; ?3 }) C- `
  44. float x, y, z;/ W% C- y7 q" i+ e, I
  45. int m1   = etop-ptop-5,1 v& K% d; l) Q( i
  46.   m2   = itop-etop-5;; u2 V- Q# v# M1 ^4 i8 G
  47. int temp = 0;/ b. I6 E1 a5 F' A" j
  48. for(z=2;  (itop+(z-1)*33) <= 21252;  z++)* u( D1 Y; H5 p2 B$ @
  49. {
    + r4 j, `1 S, [+ ^
  50.   temp = m2 + 33*z;
    6 M: ^! C' o7 |: a. L
  51.   y = (float)temp/28;
    7 j) _1 T% u3 I( C. X: T8 D
  52.   x = (float)(m1+temp)/23;) V& }, J1 Z6 m
  53.   if(x>0 && y>0 && is_Integer(x) && is_Integer(y))1 L0 U. m4 H& C% }/ N) i4 H, l+ U3 }
  54.    return itop + (z-1)*33 -cur;
    " v1 e8 |7 ~! G7 U5 h/ H
  55. }! a3 _( u# p$ C/ W# H
  56. return 0;
    3 b! N" o$ J5 M. \8 P
  57. }2 O2 T9 m- T/ \4 I6 T

  58. $ K' E3 e) _, F; S: i
  59. bool is_Integer(float n)& `7 h! `. R3 w. M" |
  60. {4 i2 A+ [+ u3 o
  61. if( (int)n - n ==0)
    ! {3 Z8 {# ~0 L7 y* c6 U+ P% c
  62.   return true;
    5 e% E, y5 Y% C8 c) d+ B4 w# f* Z
  63. else
    9 c) D4 Y7 U; Z8 E
  64.   return false;  m. Z9 C0 U3 S( F
  65. }
    ' ?3 a! Q+ F3 z8 x: p( x
  66.   B7 h- P/ h. I3 s  n8 o
复制代码

% D# t/ N% Y$ s$ Y
作者: ultra1989    时间: 2010-10-27 08:45
本帖最后由 ultra1989 于 2010-10-27 08:54 编辑 , j# X0 Z7 R2 `; I+ }8 K
0 v, w4 K' `. S$ O
用float可能会有精度问题用中国剩余定理求解
& `1 G# V, H! T: e参考程序：
0 \/ r$ {# `: j. i+ B
4 A3 w+ Z  j% v% A#include<stdio.h>0 m# z; m9 d8 J" b) _
int main(){ 4 d, n6 ^2 V/ P1 a
   int a,b,c,m,n,i,d=1;
3 ?5 _% j9 f4 R8 }; ^' \; s   while(scanf("%d%d%d%d",&a,&b,&c,&m)){  L% J$ m4 a7 l

# Z+ A3 {5 d7 m# Jif(a==-1&&b==-1&&c==-1&&m==-1) break;  d9 n& A/ M& x3 _) J
# ]& X+ U5 z- C+ U) @! U; g$ Q6 r7 C
n=0;
8 @: E* _) G0 \! Y! v/ J: _% x5 c5 X$ l2 r5 j! U& v- G0 o8 g
i=(5544*a+14421*b+1288*c-m+21252)%21252;, t" j* Z, R% E% n0 L

# E( u! Y! A6 e$ K* F' oif(!i)
: h& x9 j( q( A; F. L. e) c7 ^! ?1 G$ W/ X+ t" v
i=21252;
5 [+ u2 J6 A0 u- u3 o: _0 l: z. t. J
printf("Case %d: the next triple peak occurs in %d days.\n",d++,i);6 ^' A9 `+ B* c- |' E
) h3 s  G+ W9 g, S
   }
( O" ~( o5 u+ D) s) E: P1 D% h6 O5 |+ J  M: j3 Y
return 0;( |, L7 f; r' W- `# k4 A
}
9 \$ q3 I5 i) s6 s: B$ y5 u) ~% {4 ~
作者: qbist    时间: 2010-10-27 13:20
作者: 小草远在天涯    时间: 2010-10-27 17:27
好复杂啊，我是初级的。。。路过。。。
作者: maybe_madio    时间: 2010-10-27 22:23
回复 ultra1989 的帖子  e8 r# g% c; k  c6 u6 m; w
5 a0 W  F# C9 }) U) y8 ^

; J8 d5 g8 a4 p! s    确实这道题使用剩余定理解效率太高了！ 哈哈！ 学习了！  我还没有看过数论方面的书！ 以后肯定要看看( w8 o3 L$ v4 q6 X, f4 L) i
  c4 h) z# N% D4 G5 H* |- t
两个程序一对比，一下就体现出数学的强大力量！ ' V* p$ v, u6 D+ y* y
作者: 39133120    时间: 2010-10-28 23:11
好复杂啊，得仔细
作者: 鸿光满面    时间: 2011-2-4 13:40
好复杂啊         



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