数学建模社区-数学中国

标题: POJ-1006问题 [打印本页]
作者: maybe_madio    时间: 2010-10-26 23:30
标题: POJ-1006问题
POJ-10065 g/ h0 B1 {, V6 `' z$ e8 I" |9 q

1 h, i$ P, l; _  G( B在本地VC6.0下测试，得出正确结果， 为什么提交后总是Wrong Answer0 x2 d2 q/ w5 ~% K" n& d

$ _( b1 G6 }- c7 q- _4 V8 [& ~" t现将代码贴出，请帮忙看看：
% P% q  b% p8 L# P1 h: ~' N
  1. #include <iostream>
    3 J7 Y8 Y+ \7 Y' C2 }- o
  2. using namespace std;
    2 A' E1 q! r" R* p; |3 a
  3. #define PH      0
    , ?! B7 X) H+ ?) K: s& T
  4. #define EM      14 ], r( }0 I( k+ |% c6 m
  5. #define IN      2
    & G& Q8 [' a. D* `" O0 b  @
  6. int get_Top(int days, int kind);
    3 t; v0 s+ u. \) c* T4 P4 D3 r; |
  7. int triple(int ptop, int etop, int itop, int cur);) H# d4 k% b7 `$ v! N$ \
  8. bool is_Integer(float n);3 h. l9 Z% j/ K% E
  9. int main(). Y% p7 n. Z8 M$ T" H( T. M7 a
  10. {+ k* t5 K/ A  z
  11. int ptop,  etop,  itop;
    0 |8 Z' g2 |8 u! G5 M
  12. int pdays, edays, idays, curdays;
      C% T3 P- p( ^) ]& i4 {5 C
  13. int count =0;" P- o7 I4 L( j
  14. ) A+ w# Z4 o, U7 D7 x  i4 i) o  E2 ]$ m
  15. while(cin >> pdays >> edays >> idays >> curdays)
    ! g. D3 [3 D8 h2 X/ A( I- }8 P
  16. {
    & r5 f8 K) T8 d% A' ^
  17.   if(pdays==edays&&pdays==idays&&pdays==curdays&&pdays==-1)
    ' F1 e% N) w* k# u% K
  18.    break;
    1 ]  c' n: l- E) n" r" k
  19.   count++;
    4 F- w& K/ p1 D
  20.   ptop = get_Top(pdays,PH);5 |, _! p8 N2 z9 v+ s
  21.      etop = get_Top(edays,EM);
    " N5 w! }# B5 k# ]
  22.      itop = get_Top(idays,IN);/ M* x' o. F: i+ l8 e  b
  23.   cout<<"Case "<<count<<": "<<"the next triple peak occurs in "<<triple(ptop, etop, itop, curdays)<<" days.";# q  G; n  V( P- B) L
  24. }; @) Z& |; z, K5 \1 V3 V6 B7 i3 z, {

  25. ' G6 o2 z0 q! u8 M: F) ~
  26. return 0;
    . A: _) N/ y4 t3 H2 \
  27. }
    , y9 m0 z: T$ H0 n* H/ E9 l
  28. int get_Top(int days, int kind)
    + r  x- |2 R0 |" V9 x
  29. {
    # Q$ p! F; m% Z  ^2 f: I
  30. switch(kind)8 R) _0 k9 n  e8 \- n' C  C4 `
  31. {" `+ S+ S. }  J1 J6 ?' q
  32. case 0:0 |+ B# ^0 k4 A& f- R0 D
  33.   return days%23;
    6 o2 z/ W) ^) A
  34. case 1:
    ! S3 @6 r2 Y$ h6 M
  35.   return days%28;
    + Z9 C$ R# {. a( r! T/ O
  36. case 2:
    9 K8 P& G9 \* b; j4 C
  37.   return days%33;% v. v" M5 Z# ^4 N
  38. }
    % ?5 |" n+ C( q4 k3 u# F" ]% T  Z
  39. return 0;
    7 T# m9 ~% I. s
  40. }
    # S" t; X6 y8 ?) y1 o( _; C

  41. 1 x9 o4 z4 |! y1 u
  42. int triple(int ptop, int etop, int itop, int cur)
    + R% ~; s+ |& P/ {( b
  43. {
    0 }; C; ?8 U& p) o
  44. float x, y, z;' s& {/ h) y2 ^8 e/ Z) t2 _
  45. int m1   = etop-ptop-5,6 L( E7 x& g" S+ _! u
  46.   m2   = itop-etop-5;2 G' i' l8 E$ n# D2 z4 r2 C  V
  47. int temp = 0;
    1 c- @, V  t+ R! Q: e5 e$ R  E
  48. for(z=2;  (itop+(z-1)*33) <= 21252;  z++)$ F. \9 ?, U/ C! c
  49. {
    9 t! e2 E  ^5 V/ A) u
  50.   temp = m2 + 33*z;3 j. k8 @! m  W' a7 X6 N6 F9 S1 S' ~
  51.   y = (float)temp/28;( _! l4 Z' }  U+ y6 N+ j: ?
  52.   x = (float)(m1+temp)/23;% q$ M% G# @0 e
  53.   if(x>0 && y>0 && is_Integer(x) && is_Integer(y))
    ( T( s% f# U' B
  54.    return itop + (z-1)*33 -cur;, ]. z: V! n: O+ w1 Y6 I5 u7 m
  55. }
    8 k/ L+ B5 A3 Q6 i0 Y8 k: b
  56. return 0;
    7 z) k1 v' [( u* ?  Z5 ^5 w
  57. }2 K$ p  g5 v/ d/ n# y( e% ?
  58. ( \; h. Z0 Y1 z( G: a4 y
  59. bool is_Integer(float n)
      [( c4 ?% ~) l
  60. {% `3 o7 `8 `5 U/ q  {8 T
  61. if( (int)n - n ==0)
    4 R, U3 r8 @9 v9 w! @
  62.   return true;
    2 L1 a" `9 H! p5 s; _
  63. else6 z! M; C# j+ }# I5 ^# \5 @
  64.   return false;" ?) X5 B: k; }
  65. }, x+ u  G3 w+ t3 u  H7 x

  66. $ E  ]. ~& P1 P/ g0 ~" d
复制代码

: m8 U% A( d; L% j2 y
作者: ultra1989    时间: 2010-10-27 08:45
本帖最后由 ultra1989 于 2010-10-27 08:54 编辑 # n7 j3 S7 C' v, ~5 i5 f1 k( |

% H& F# r, Q0 [& w  m, u) I用float可能会有精度问题用中国剩余定理求解
, e& w+ a+ ^# G# `, a参考程序：
5 y8 O$ n4 R$ E5 n+ d/ i1 f- C: T% @5 |% t) e
#include<stdio.h>
/ e9 w/ u! f% t& f- B0 U& pint main(){
; d  E) ^# M8 b7 C7 R   int a,b,c,m,n,i,d=1;8 R9 T" I" w; P
   while(scanf("%d%d%d%d",&a,&b,&c,&m)){+ I- s. q6 |1 g( ^1 O9 j1 \7 h
4 r- J- d0 |" H- M: H
if(a==-1&&b==-1&&c==-1&&m==-1) break;; `% c' i6 U9 u6 D/ Z

" i0 w3 {7 o% s8 rn=0;
+ ~5 W% q' ]6 q& @( N4 p0 v( B; j# V2 \! }+ K8 P7 i) d3 `
i=(5544*a+14421*b+1288*c-m+21252)%21252;7 I& ~3 @, P( Z& p, d

$ L) q+ a/ M/ y" c! aif(!i)
+ V8 S( K! |( Z* i7 w. O  o1 i1 ?1 Y
i=21252;
8 j2 h' b  v# O) w; G4 Q
/ j" j0 a' s' h# Gprintf("Case %d: the next triple peak occurs in %d days.\n",d++,i);
, |, _! J2 J. G/ u$ \2 i8 b* k$ t6 f
   }
2 X7 u9 I: I0 @+ o0 @( E9 g+ q; C4 f% x3 V; I4 e# Y6 l8 L' b! J
return 0;
4 Q  `' k9 A  Q6 _& E& c& i}
5 |3 }; }( g" ]- g6 Q
/ h3 w( A, P  _8 d7 h0 p- b4 I: s
作者: qbist    时间: 2010-10-27 13:20
作者: 小草远在天涯    时间: 2010-10-27 17:27
好复杂啊，我是初级的。。。路过。。。
作者: maybe_madio    时间: 2010-10-27 22:23
回复 ultra1989 的帖子9 N6 ~; e, w! ^' `

* O8 h" f+ L) ?' C( c2 q2 K  X  o! d( O; s
    确实这道题使用剩余定理解效率太高了！ 哈哈！ 学习了！  我还没有看过数论方面的书！ 以后肯定要看看
8 R- ?- j$ w; L# f/ }
+ _1 Y, j/ H) L9 u6 k6 Q两个程序一对比，一下就体现出数学的强大力量！ , y) w: ~5 V, b) m/ y; i( \# J
作者: 39133120    时间: 2010-10-28 23:11
好复杂啊，得仔细
作者: 鸿光满面    时间: 2011-2-4 13:40
好复杂啊         



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