[isteam test 2011] k4,5,6

[09520019]

Có vẻ bài này đấu toán học chứ không phải đấu thuật toán hay tối ưu gì cả =))

Sau khi em xem đề thì bài này rất mánh anh, không phải vấn đề toán học mà là vấn đề ai google ra cái engine nào tính đc cái công thức đó trước. Chứ cách để tính bài này thì phải qua 1 phương trình (có công thức), mà cách giải phương trình đó nằm trong tài liệu hướng dẫn thi của IMO. Nên chắc chắn rằng trừ siêu nhân toán ra thì người bình thường không giải được (cho đến khi đọc đc tài liệu đó)

[11520118]

Sau khi em xem đề thì bài này rất mánh anh, không phải vấn đề toán học mà là vấn đề ai google ra cái engine nào tính đc cái công thức đó trước. Chứ cách để tính bài này thì phải qua 1 phương trình (có công thức), mà cách giải phương trình đó nằm trong tài liệu hướng dẫn thi của IMO. Nên chắc chắn rằng trừ siêu nhân toán ra thì người bình thường không giải được (cho đến khi đọc đc tài liệu đó)

Quên post cái bài cũ:

#!/usr/bin/env python2
import math
n=1
delta=lambda n:8*n*n+8*n+1
k=lambda n : (-(2*n+1)+math.sqrt(delta(n)))/2
while True:
if int(k(n)) == k(n):
print n,'\t',int(k(n))
n+=1

[09520019]

Quên post cái bài cũ:

Em ơi anh không biết code python, nhưng không có nghĩa là anh không biết đọc code python. Em code vậy mà
real 0m0.035s
user 0m0.027s
sys 0m0.007s

Thì quả là ảo vật vã

[11520118]

Em ơi anh không biết code python, nhưng không có nghĩa là anh không biết đọc code python. Em code vậy mà
real 0m0.035s
user 0m0.027s
sys 0m0.007s

Thì quả là ảo vật vã

đã nói còn gà mà, thế mới vô đây học hỏi chứ anh

[09520019]

đã nói còn gà mà, thế mới vô đây học hỏi chứ anh

Anh post 1/2 cách giải rồi và em nên post phần còn lại. Tại sao em ra đc file đó. Em nhìn thấy cái code C++ của anh rõ ràng đã có công thức k và một phần công thức n rồi đúng không. Bây giờ anh chỉ cần xem công thức tính n của em trong cái bài thứ 2 thôi. Lý do rất đơn giản: nếu em không tính được n một cách trực tiếp thì em chép code công thức của anh rồi

[11520118]

Anh post 1/2 cách giải rồi và em nên post phần còn lại. Tại sao em ra đc file đó. Em nhìn thấy cái code C++ của anh rõ ràng đã có công thức k và một phần công thức n rồi đúng không. Bây giờ anh chỉ cần xem công thức tính n của em trong cái bài thứ 2 thôi. Lý do rất đơn giản: nếu em không tính được n một cách trực tiếp thì em chép code công thức của anh rồi

cái code lúc trước giải pt bậc 2 theo biến k
pt có dạng k*k + 2*n*k -n(n+1) = 0
delta = 8*n*n +8*n+1
tính ra k rồi so dk thôi

[09520019]

cái code lúc trước giải pt bậc 2 theo biến k
pt có dạng k*k + 2*n*k -n(n+1) = 0
delta = 8*n*n +8*n+1
tính ra k rồi so dk thôi

Anh bảo em là cái bài số 2 đấy
cái này này

2 1
14 6
84 35
492 204
2870 1189
16730 6930
97512 40391
568344 235416
3312554 1372105
19306982 7997214
112529340 46611179
655869060 271669860
3822685022 1583407981
22280241074 9228778026
129858761424 53789260175
756872327472 313506783024
4411375203410 1827251437969
25711378892990 10650001844790
149856898154532 62072759630771
873430010034204 361786555939836
5090723162050694 2108646576008245
29670908962269962 12290092900109634
172934730611569080 71631910824649559
1007937474707144520 417501372047787720
5874690117631298042 2433376321462076761
34240203231080643734 14182756556724672846
199566529268852564364 82663163018885960315
1163158972382034742452 481796221556591089044
6779387305023355890350 2808114166320660573949
39513164857758100599650 16366888776367372354650
230299601841525247707552 95393218491883573553951
1342284446191393385645664 555992422174934068969056
7823407075306835066166434 3240561314557720840260385
45598158005649617011352942 18887375465171390972593254
265765540958590867001951220 110083691476470624995299139
1548995087745895585000354380 641614773393652358999201580
9028204985516782643000175062 3739604948885443528999910341
52620234825354800273000695994 21796014919919008815000260466
306693203966612018995004000904 127036484570628609361001652455
1787538988974317313697023309432 740422892503852647351009654264
10418540729879291863187135855690 4315500870452487274745056273129
60723705390301433865425791824710 25152582330211071001119327984510
353923691611929311329367615092572 146599993110813938731970911633931
2062818444281274434110779898730724 854447376334672561390706141819076
12022986974075717293335311777291774 4980084264897221429612265939280525
70075103400173029325901090765019922 29026058213048656016282889493864074
408427633426962458662071232812827760 169176265013394714668085071023903919
2380490697161601722646526306111946640 986031531867319631992227536649559440
13874516549542647877217086603858852082 5747012926190523077285280148873452721
80866608600094285540655993317041165854 33496046025275818831719453356591156886
471325135051023065366718873298388143044 195229263225464389913031439990673488595
2747084201706044106659657246473287692412 1137879533327510520646469186587449774684
16011180075185241574591224605541338011430 6632047936739598733965783679534025159509
93319996249405405340887690386774740376170 38654408087110081883148232890616701182370
543908797421247190470734917715107104245592 225294400585920892564923613664166181934711
3170132788278077737483521815903867885097384 1313111995428415273506393449094380390425896
18476887932247219234430395977708100206338714 7653377571984570748473437080902116160620665
107691194805205237669098854050344733352934902 44607153436479009217334229036318316573298094
627670280898984206780162728324360299911270700 259989543046889484555531937137007783279167899
3658330490588700003011877515895817066114689300 1515330104844857898115857393785728383101709300
21322312662633215811291102367050542096776865102 8831991086022257904139612425577362515331087901
124275545485210594864734736686407435514546501314 51476616411288689526721817159678446708884818106
724330960248630353377117317751394070990502142784 300027707381709879256191290532493317737977820735
4221710216006571525397969169821956990428466355392 1748689627878970586010425926035281459718982106304
24605930335790798799010697701180347871580295989570 10192110059892113636806364265679195440575914817089
14341387179873822126866621703726013023905330958203 0 59403970731473711234827759668039891183736506796230
83587730045663852881298660452238043356273956150261 2 34623171432895015377216019374256015166184312596029 1
48718499309410929516092534100970224711373840594336 44 20179863152422272113981334027873210187873222489655 16
28395222285189919180842533856059754393261564795099 254 11761686177124413114616640222981365961062090367832 805
16549948378019842213344594972626150388843200471116 1882 68552130747504251476301707935100874747585219958031 314
96460168039600061361983316450150926893733046347187 2040 39955109830790109574319360738762388252444922938035 5079
56221105985958052595855530372827941097355507761200 70360 23287544590999023229828599363906424203991101563240 99160
32768061911178830943893485059195255389475974193248 550122 13572975656291512842153966010956230639870211708564 239881
19098626086847718040377535731788873822712029438337 1230374 79109099478649174729940936129346741418822160095061 340126
11131495032996842514787586588481371739732457921069 78832124 46108162121560353553749165076512421787306274886180 3800875
64879107589296283284687765957709343056123544582585 01762372 26873806278149720384950089684613985658195543330757 61465124
37814315050278085719333900915777468659700880957444 031742110 15663202145674228695432562160003267177044263249592 764989869
22039797954273888598753462889889387765259293128640 5688690290 91291832246230400134100363991558204496446025164480 828474090
12845735622061552302058738724775857972558567067609 90100399632 53208779133170817210916962178934595980163188773729 2205854671
74870433936941924952477086059666209058825473092795 34913707504 31012349157440186325209173667445175543133453012592 72406653936
43637686799958999741280377763322139638039427148916 219381845394 18075321703132403623016334578677759366078439919818 342234068945
25433907740605980595243455797396621692235401558421 7781377364862 10535069530305040310557709010532203864215729421765 0780997759734
14823967776363998359733269700804751618960846663563 90468882343780 61402885011517001501044620605325447248686532538608 6343752489459
86400415884123392098875272625088847544541539825541 25031916697820 35788224053879696869571001462142047962790346580988 67281517177020
50357852752837635423351836604972833364828839228968 359722617843142 20858905582212648106732154671231974305187342623207 117345350572661
29350707492861347333022349236732811543451888139125 6033303790361034 12157461108788791895343582788117764103484502108114 3836790586258946
17106845968188432045579891175989958592422844491185 67840100124323064 70858876094511486561388281261583387190388278386365 5903398166981015
99706005059844457540177112132266470400191878133201 51007296955577352 41299579545828012747298610478138255903884516821007 91583598415627144
58112918439087831319548278161760886380872842430802 338203681609141050 24071158966551692782765283474267119670426827308741 093598192326781849
33870691012854254216327195775733867124521786677149 3878214792699268950 14029699584472735542186183979778889243217251217034 5770005555545063950
19741285423321674216600834683822711410904343581981 60931085074586472652 81771081610181243974840575531246623492260824571333 3526435140943601851
11506064343864461987797228852536288175297388282417 471708295654819566964 47659679007661472830685726920770085171034769621096 55388605290116547156
67062257520854604505123289646835457910693895336306 669318688854330929134 27778096588495071258663030397149584867698253526944 598805196599755681085
39086748078126316504294250902847645928886598373542 2544203837471166007842 16190261163020428026890960969082050068908604419955 7937442574308417539354
22781426271667243857525317645240232978225020070762 28595904335972665117920 94363757319273061035479462774777341926681801167040 3025850249250749555039
13277988282219083149472248078115663327646146058721 949031222178364824699680 54999228275261793818598581567958200149118220258228 60217658921196079790880
77389787066147774511080956704169956668054374345255 465591428734216283080162 32055899391964345680804354313027146670204114143266 758280103277925729190241
45106073411466756391701349214690407668068010001281 0844517350226932873781294 18683547352425989470296626772136706000631286283377 7689462960746358295350566
26289746176218576089909999961772545034160262257316 09601512672627380959607604 10889569417535950225369932520151752133676730628593 99378497661200224042913155
15322786971616478090028986484916622943815477254376 846764558685537352883864332 63469061769973102405189932443696842201997255143226 18581523006454985962128364

real 0m0.035s
user 0m0.027s
sys 0m0.007s

[07520004]

Anh bảo em là cái bài số 2 đấy
cái này này

Nó paste trong #152 ấy, cái link tới paste bin của ubuntu.com đó, bắt bẻ em nó quá

[09520019]

Nó paste trong #152 ấy, cái link tới paste bin của ubuntu.com đó, bắt bẻ em nó quá

À em không để ý cái #152 :| Chỉ thấy cái #153 thôi =.=
Cách giải của mình dùng công thức giải pt Pell's : x^2 - dy^2 = a có nghiệm là x = (z^n + z'^n) / 2; y = (z^n - z'^n) / 2*sqrt(d); [1]
Ở đây bạn lại có n^2 + n - k^2 - k - 2*k*n có thể nhóm lại thành dạng phía trên: (2n - 2k + 1)^2 - 8k^2 = 1, đặt x = 2n - 2k + 1, y = k, d = 8, a = 1, ráp công thức vào ,giải, rồi ra đc x,y thì tính n và k dựa vào đó
bạn tham khảo cách giải Pell's equation tại http://www.imomath.com/tekstkut/pelleqn_ddj.pdf trang 2 đó.

Wolfram alpha đã nhúng luôn giải công thức nghiệm pt dạng diophant và pell's equation tại: http://www.wolframalpha.com/input/?i...+2*n+*+k+%3D+0

Vậy bạn post luôn cách giải của anh Nam đi vì cách giải khá đơn giản.....có thể là do tiếp xúc ở khía cạnh khác của bài toán....

[11520118]

mấu chốt sao cái đó nó nhanh nằm ở chỗ này:
n=k=0
k+=2*n+1
n+=2*k
anh ấy xem n,k là cặp số phụ thuộc vào nhau, nếu có k thì nó n

[09520019]

mấu chốt sao cái đó nó nhanh nằm ở chỗ này:
n=k=0
k+=2*n+1
n+=2*k
anh ấy xem n,k là cặp số phụ thuộc vào nhau, nếu có k thì nó n

Bạn nói rõ hơn đc ko mình không hiểu cái mấu chốt đó: bằng cách nào nghĩ ra đc. Mình không quan trọng đáp án làm thế nào , mà mình quan trọng làm sao để ra đc

[07520004]

Càng ngày càng nhiều công thức. =))

Anh nói cái này là cuộc thi toán chứ không phải thuật toán mà (cái topic của vithon.org cũng ghi là thi giải toán, chuẩn phết). Bây giờ chắc ý nghĩa chỉ là chứng minh công thức cho bỏ tức chứ không ai còn ý muốn tối ưu nữa đâu nhỉ, áp dụng toán thì vô địch rồi.

[09520019]

Càng ngày càng nhiều công thức. =))

Anh nói cái này là cuộc thi toán chứ không phải thuật toán mà (cái topic của vithon.org cũng ghi là thi giải toán, chuẩn phết). Bây giờ chắc ý nghĩa chỉ là chứng minh công thức cho bỏ tức chứ không ai còn ý muốn tối ưu nữa đâu nhỉ, áp dụng toán thì vô địch rồi.

Nó quá imba rồi anh.....vấn đề là làm sao ra dc công thức đó )

[07520004]

Nó quá imba rồi anh.....vấn đề là làm sao ra dc công thức đó )

Câu trả lời đây: Nghiệm đệ quy của phương trình Pell

http://en.wikipedia.org/wiki/Pell's_equation#Additional_solutions_from_the_fundamental_solution

Khóa sổ bài này được rồi, để cho khoa Toán Tin của KHTN làm thì hợp hơn =))