数学建模社区-数学中国

标题: POJ-1006问题 [打印本页]
作者: maybe_madio    时间: 2010-10-26 23:30
标题: POJ-1006问题
POJ-1006
2 P5 s/ G+ \! A) A% G2 S: _
8 h" Y) ]: |) f- z$ X在本地VC6.0下测试，得出正确结果， 为什么提交后总是Wrong Answer6 M1 ?/ c, n% o* r( R- |3 O; r
  B/ n3 |* q, ?* a8 N8 i8 ~' P
现将代码贴出，请帮忙看看：
/ z' D4 D. H) ~/ l
  1. #include <iostream>
    6 {5 D( O7 u5 V. i% Z& {3 I. B
  2. using namespace std;7 G/ H/ ~- ?" z1 T( D+ H& [" v- k
  3. #define PH      0
    8 f8 ?6 N; v- Z: i2 ^0 j* ?+ o
  4. #define EM      1
    8 B. ^3 n) m8 h3 \) L4 O  w0 F, d
  5. #define IN      2
    - r6 A% A8 D2 I9 ?; z  C
  6. int get_Top(int days, int kind);
    , I; m2 d8 U  @3 D: l% Q1 w) X% Q
  7. int triple(int ptop, int etop, int itop, int cur);
    0 v+ F& i  H+ ]) d5 D
  8. bool is_Integer(float n);
    8 D$ J- y7 K1 {5 W0 \
  9. int main()
    1 E% y5 }3 W, B% S& s% \/ T, X% t; ?
  10. {3 G7 R: f' V7 F! h
  11. int ptop,  etop,  itop;
    : ~: R9 q& i9 x: n& o6 @/ [# V8 l
  12. int pdays, edays, idays, curdays;: r) H! r! r9 i, U( H
  13. int count =0;
    5 R# |3 Z; M2 x8 w( A. F
  14. 5 i2 B3 q" [8 S: z5 s# E5 W( [
  15. while(cin >> pdays >> edays >> idays >> curdays)" r5 _( t& S1 ]# b. L, F# X
  16. {* w& R) N- K9 Y8 R
  17.   if(pdays==edays&&pdays==idays&&pdays==curdays&&pdays==-1)" y( f1 k3 U/ q( M
  18.    break;( A$ W; p7 r: \' A5 [
  19.   count++;& K  Y! i6 Y& K
  20.   ptop = get_Top(pdays,PH);
    . Z1 z# S5 c. s( K: ~, N6 [+ ]
  21.      etop = get_Top(edays,EM);! @, Y0 q/ T, S# G
  22.      itop = get_Top(idays,IN);
    $ e4 U* J6 W) S/ I# G
  23.   cout<<"Case "<<count<<": "<<"the next triple peak occurs in "<<triple(ptop, etop, itop, curdays)<<" days.";
    ' @- [7 J! n1 }
  24. }
    - U5 y9 t: u$ D( T" C
  25. % E, t* M7 M6 D) c
  26. return 0;. i% w  G# S9 U1 e' i
  27. }
    $ s2 {) k1 M( e; z/ K& r
  28. int get_Top(int days, int kind)
    " n) f0 N$ A) R" i9 J
  29. {
    % H' q' V1 h% U  e* K, V/ r, F
  30. switch(kind)
    2 B$ ~4 y! K5 P( E+ E1 Y) v1 T
  31. {
    $ _5 k9 v0 s* m  u& U  k
  32. case 0:
      m& s0 [) j0 F- L( k! W4 H
  33.   return days%23;
    - k' K4 X7 ]& r3 {
  34. case 1:: V6 ~8 ?2 O7 |2 w" g
  35.   return days%28;
    5 ?. ?6 x+ o; M/ U  @* ]8 L
  36. case 2:* B' S; [; B, d3 k
  37.   return days%33;
      {! k+ d+ V7 t' U; e. E
  38. }
    6 S$ F4 A3 x8 A4 z9 z) A
  39. return 0;
    + f6 i, h5 h5 \3 r
  40. }
    8 f' c+ ^# Y  f& N; E% x

  41. 3 r5 C* ?5 k4 I3 c7 j$ N4 u* s
  42. int triple(int ptop, int etop, int itop, int cur)
    + p; z0 x; v* p! }
  43. {2 V+ ]' r2 |6 a) M
  44. float x, y, z;& H; `% U6 Z% F4 F2 [
  45. int m1   = etop-ptop-5,& z  `" q% o) Z! J+ r! M$ l3 S
  46.   m2   = itop-etop-5;
    1 T+ [# F# B. e+ R2 y6 O
  47. int temp = 0;
    & {8 D& f2 w4 v9 X% F- x1 ]
  48. for(z=2;  (itop+(z-1)*33) <= 21252;  z++)* z2 P# m. O' _' k. G/ J, i
  49. {% @/ x1 h! b! M7 Z+ Y
  50.   temp = m2 + 33*z;" b: s) w7 H& w0 n0 f4 H4 b
  51.   y = (float)temp/28;9 Q$ k" ^' J6 F( P2 T
  52.   x = (float)(m1+temp)/23;6 f; }( X6 `6 z7 O% W9 \( E
  53.   if(x>0 && y>0 && is_Integer(x) && is_Integer(y))
    ) @3 W# x( d2 u5 [
  54.    return itop + (z-1)*33 -cur;: i+ D& N7 N7 D+ a% k
  55. }0 q! B' _' q2 D
  56. return 0;
    8 p! r& n7 \* n# b2 q7 n6 v8 C7 X
  57. }2 _  @& |% R* @% a/ ^

  58. 5 B  l/ r7 F! J
  59. bool is_Integer(float n); @' v* y7 d: I6 e
  60. {
    & J* Z3 X) @6 @/ p4 @6 N% z! r8 e
  61. if( (int)n - n ==0)& b& J! N; ^1 X0 g7 }
  62.   return true;' `- T& b! o" k, W3 P2 N
  63. else
    " l6 R- c* ?$ j* Z
  64.   return false;5 h6 F0 `$ E$ u0 f$ U8 f' w
  65. }& Z8 o7 y+ e. L" Q! u) ]
  66. + T7 X& _) S4 |/ O5 i8 H
复制代码

6 F7 `; S4 p- z& T" Z8 `8 M
作者: ultra1989    时间: 2010-10-27 08:45
本帖最后由 ultra1989 于 2010-10-27 08:54 编辑
: ^# d* S, @+ e1 J) X7 F
  C% E1 y( I8 h/ J& g用float可能会有精度问题用中国剩余定理求解
: G, k7 }. |- ?: U0 s参考程序：2 i* R  v' i  Q2 T/ c) m
" M8 n  g1 {+ R' c9 k
#include<stdio.h>
- a0 B9 q& g( n, ]* Gint main(){ 5 @/ @" v! U" G) @  K5 {; ]
   int a,b,c,m,n,i,d=1;
. g  u; A$ e/ r% J9 V" d   while(scanf("%d%d%d%d",&a,&b,&c,&m)){
0 J7 q$ q7 u7 o. j- l: c" W! c) L7 _. N9 o% a1 d2 z
if(a==-1&&b==-1&&c==-1&&m==-1) break;
- S0 E. D8 T1 ~, I+ T6 j! D6 i( x' W! j' _& N) D7 P' X* Y- N
n=0;
. X& K# Z! \2 M+ N6 s
$ s  M$ [" T! O  Q  }" D# f: Bi=(5544*a+14421*b+1288*c-m+21252)%21252;# \0 b( x* y. Y' g
. u7 r7 O$ Q4 c- E
if(!i)
- l( g; g- v1 S- S. l6 c: k/ u. g4 x
i=21252;
7 Q, W8 S. `0 D" F- c+ Q, J  {1 b$ Q# U/ B
printf("Case %d: the next triple peak occurs in %d days.\n",d++,i);
, n4 {, v' n. G$ u+ g' X9 T/ f' t: j. t) t
   }
* I( u3 F% |, q1 p9 Y, }3 J& ~! P( F8 x) {5 `
return 0;% N+ j" S% s( Z) T+ n8 l
}
; Y) u0 ?' Z8 a1 G8 W
: E& p9 X. n; r* l
作者: qbist    时间: 2010-10-27 13:20
作者: 小草远在天涯    时间: 2010-10-27 17:27
好复杂啊，我是初级的。。。路过。。。
作者: maybe_madio    时间: 2010-10-27 22:23
回复 ultra1989 的帖子
) y4 E; C: X! v6 c+ d, z. X; {/ }& C  o4 X

3 K  [9 J. T  F3 m    确实这道题使用剩余定理解效率太高了！ 哈哈！ 学习了！  我还没有看过数论方面的书！ 以后肯定要看看1 R5 u$ ]* J0 T3 ]$ F7 p
6 {& h0 U5 z  ~
两个程序一对比，一下就体现出数学的强大力量！
0 y3 `. o6 Z& ]+ e5 e
作者: 39133120    时间: 2010-10-28 23:11
好复杂啊，得仔细
作者: 鸿光满面    时间: 2011-2-4 13:40
好复杂啊         



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