Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
this is my answer | Sunnat | 1013. K-ичные числа. Версия 3 | 26 фев 2012 13:52 | 3 |
#include<cstdio> int main() { short a[2000]={0},b[2000]={0},c[2000]={0}; short g,i,j,m=1; int n,k; scanf("%i %i",&n,&k); a[0]=1; b[0]=k-1; for(i=2;i<=n;i++) { g=0; for(j=0;j<m;j++) { c[j]=a[j]+b[j]; c[j]=c[j]*(k-1)+g; (c[j]>9)?g=c[j]/10,c[j]=c[j]%10:g=0; a[j]=b[j]; b[j]=c[j]; } (g!=0)?b[m++]=g:b[m]=g; } for(j=m-1;j>=0;j--)printf("%d",b[j]); return 0; } Can u pls explain me the concep of this problem. for wat we ve given the k value.? congratulation for excellent code. The only suggestion. May be (g!=0)?b[m++]=g:b[m]=g; better to replace by if(g) b[m++]=g; |
I have TLE on test#9. What I have to do? | HellDred | 1013. K-ичные числа. Версия 3 | 25 янв 2012 14:38 | 2 |
{$APPTYPE CONSOLE} uses SysUtils, Math; Function Sum(f1,f2:string):string; var f,ff,a:string; i,n,p,s:integer; begin n:=Max(length(f1),length(f2)); if n=length(f2) then begin f:=f2;ff:=f1;end else begin f:=f1;ff:=f2;end; while length(f)<>Length(ff) do ff:='0'+ff; p:=0; a:=''; s:=0; for i:=n downto 1 do begin s:=StrToInt(f[i])+StrToInt(ff[i])+p; Str(s,a); f[i]:=a[length(a)]; p:=s div 10; a:=''; end; if p<>0 then f:=IntToStr(p)+f; Result:=f; end; Function Mult(k:integer;f1,f2:string):string; var f,a:string; i,s,p:integer; begin f:=Sum(f1,f2); p:=0; a:=''; s:=0; for i:=length(f) downto 1 do begin s:=StrToInt(f[i])*k+p; Str(s,a); f[i]:=a[length(a)]; p:=s div 10; a:=''; end; if p<>0 then f:=IntToStr(p)+f; Result:=f; end; var n,k,i:integer; f1,f2,f:string; begin readln(n); readln(k); f1:=IntToStr(k-1); f2:=IntToStr(StrToInt(f1)*k); for i:=2 to n do begin f:=Mult(k-1,f1,f2); f1:=f2; f2:=f; end; writeln(f1); end. Edited by author 30.03.2008 23:29 Obviously, write normal bignum arithmetic. |
Is it possible ? | Todor Tsonkov | 1013. K-ичные числа. Версия 3 | 12 янв 2012 01:38 | 7 |
I don't think it's possible. In FAQ it's written that minimal memory is over 100k because of compilator.Even only 2 variables need more than 2 k.And time is impossible to :) I really can't understand the reason. And 'vongang ' please respect others.Use English. |
[Hint] How to save memory | Nguyen Khac Tung | 1013. K-ичные числа. Версия 3 | 29 апр 2011 19:55 | 2 |
Look at your formula again. Actually, you only need the results for F[n-1,..] to calculate F[n,..] . Use variable to store them temporarily |
why WA in 6 | zzzlll | 1013. K-ичные числа. Версия 3 | 21 мар 2010 18:34 | 2 |
there is my program var c:array[0..1800] of real; n,m,i ,fn:longint; begin readln(n,m); c[0]:=1; c[1]:=m-1; i:=1; repeat i:=i+1; {for i:=2 to n do } c[i]:=(m-1)*(c[i-1]+c[i-2]); until i>=n; writeln(c[n]:0:0); end. Because There is some testcases that have more than 1800 decimal digits.You should write Big int for this problem. |
How you use so little memory??? | Chabanenko Vlad | 1013. K-ичные числа. Версия 3 | 6 фев 2010 16:32 | 3 |
I do not understand, how to solve with memory 200KB, I have a massiv [0..1800,0..9]of [0..10000], and of course my solve loses with memory and time. I do with standart dynamic, Help me, please! Thank to everybody, I have understood myself!!!! |
give me some tests please | Головченко Дмитрий | 1013. K-ичные числа. Версия 3 | 12 май 2009 22:43 | 1 |
|
I have Acc at 0.218 c, to | Валентин | 1013. K-ичные числа. Версия 3 | 2 апр 2009 10:56 | 1 |
I believe that after some simplifications can be obtained even faster code |
Amazing? I accepted Ural 1012,but I WA in 1013 | S▓i.l.e.n.t | 1013. K-ичные числа. Версия 3 | 27 фев 2009 12:12 | 2 |
RT, I have checked the arrange. But I WA at #9 Help! Try max test. The answer has more than 1700 decimal digits. |
I'm puzzled | xwj1234 | 1013. K-ичные числа. Версия 3 | 18 янв 2009 20:52 | 2 |
How can some of the programs solve this problem within 0.001 s? Simply because this problem has nothing to do with iterations but with permutation and combination. How many different representation for the sample are there [0, 1] over 10 positions it is 2^10 = 1024 but you cannot have "0" at 1st position so 2^10 - 2^9 = 512 and like so you continue to subtract the permutations where you would have two successive zeros and at the end you should get 90.
|
If you want to check your program here is answer for n=1800 k=10 | Nickolas | 1013. K-ичные числа. Версия 3 | 26 окт 2008 13:15 | 3 |
578757056862334899165386755574542961035018961384746496922121998413414 760578182667592445243789096415796683784227403924744723018491482416669 583482398922538253661908580120448244915999799871558380368176603050559 510718284952242760194267347067123980934918801967607536469254034237855 004802696022500822172028398423844181519062416396935137327709596075152 735669152169110801968382442244041567095126300108993003699366100747388 317910001503702242232876832468136833706279128186553604889872071700426 036131859303238586562176695339522070686158319498115704647672049305508 967900683916271481984259265546356412140086789757225512541731310323935 465682724467659536689371357372914882072915082178670642329922381122275 468063370016704705831888401388113877883071853045716833529742834352672 724383287190741642453977167289524175574818905457159394451552772137292 488320334403152854433233102668615521440710891545314660751974297836931 960344433170067572075073148241931611479767495629397929628139141880637 989092914568731174905142673360305672949338207556968549473017117468827 284519728547200726208072433397564194838002665675662311399400888368781 978474075164605331088146108539042375572214938643357857365785518398241 331586137392525667520443971761280252462702157845931972397850694852408 175842881290034219718513679989695433894555165544194154985658919590072 834353665620602624018084160454588232743604457892810545037909657962721 015357460269322147036550672667818736987298257001343500000127759081331 342259975035657526096273951774789390285967686426895591017628858005630 345299494887070844487552423092400976960882414257386427295509443688581 404929103326521825760465770078754255614451223600182778301246454644360 519407068303890382956047923339271967598500824214773103912508358944293 85287661810322936028474039484807146122948136437705880627901328134001 My answer is the same to you,but I got a WA |
Java | Gustavo Villegas | 1013. K-ичные числа. Версия 3 | 12 окт 2008 13:05 | 1 |
Java Gustavo Villegas 12 окт 2008 13:05 Hi, Just as a Recommendation for Java programmers Using BigInteger this problem is the same as 1009, well' u Just will have to find a way to run faster so you dont get TL, but BigInteger works fine! ;) |
what compiler? | ste | 1013. K-ичные числа. Версия 3 | 28 июн 2008 20:23 | 2 |
I use C, & I tryed to use unsigned long long with base 1e18, but it gives me Compilation Error, so I changed long long to int and then all works well. On gnu gcc 3.1 it works well also with long long. Isn't a iso/ansi c standard feature? What is the compiler used here? Compiler is Visual C++. Please use unsigned __int64. |
wrong with #8 | Liu Yizhou | 1013. K-ичные числа. Версия 3 | 11 сен 2007 23:31 | 2 |
Could anybody tell my what the test data#8 is, or tell me where my program wrong: var a,b,c:array [1..20000] of 0..9; n,k:longint; i,j:int64; procedure mul; var i,j,r,c:byte; begin c:=0; inc(j); while a[j]=0 do dec(j); i:=0; repeat inc(i); r:=a[i]*(k-1)+c; a[i]:=r mod 10; c:=r div 10; until i=(j+1); end; procedure add; var i,j,r,c:byte; begin c:=0; inc(j); while a[j]=0 do dec(j); i:=0; repeat inc(i); r:=a[i]+b[i]+c; a[i]:=r mod 10; c:=r div 10; until i=(j+1); end; begin read(n,k); fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); a[1]:=k-1; j:=1793; i:=1; repeat inc(i); c:=a; add; mul; b:=c; until i=n; add; inc(j); while a[j]=0 do dec(j); inc(j); repeat dec(j); write(a[j]); until j=1; writeln; end. (like this one: var a,b,c:extended; n,k,i:integer; begin readln(n,k); a:=k-1; for i:=2 to n do begin c:=a; a:=(a+b)*(k-1); b:=c; end; a:=a+b; writeln(a); end.) [quote] procedure mul; var i,j,r,c:byte; begin c:=0; inc(j); while a[j]=0 do dec(j); i:=0; repeat inc(i); r:=a[i]*(k-1)+c; a[i]:=r mod 10; c:=r div 10; until i=(j+1); end; [/quote] r and others must not to be byte "r:=a[i]*(k-1)+c;" a[i]*(k-1)+c can be >255 use longint maybe Edited by author 11.09.2007 23:33 |
J# rulezzz | CF# {Anoshin,Sotov,Khuramshin} | 1013. K-ичные числа. Версия 3 | 16 май 2007 22:46 | 1 |
J# rulezzz CF# {Anoshin,Sotov,Khuramshin} 16 май 2007 22:46 Learn J# and no problems on olympiads! [code deleted] Edited by moderator 17.05.2007 10:03 |
0.375 AC!!! | And IV (ucs-usty-forever) | 1013. K-ичные числа. Версия 3 | 2 май 2007 02:13 | 1 |
|
I got WA on test1.I used long arithmetic.I'm sure it works good.Help me! | aaa | 1013. K-ичные числа. Версия 3 | 19 мар 2007 17:06 | 1 |
|
why WA in 6 | zzzlll | 1013. K-ичные числа. Версия 3 | 9 мар 2007 15:40 | 5 |
there is my program var c:array[0..1800] of real; n,m,i ,fn:longint; begin readln(n,m); c[0]:=1; c[1]:=m-1; i:=1; repeat i:=i+1; {for i:=2 to n do } c[i]:=(m-1)*(c[i-1]+c[i-2]); until i>=n; writeln(c[n]:0:0); end. Use long arithmetics! с этим не катит! всё равно WA #7 Send me your solution to my e-mail w_soulreaver[at]ukr[dot]net .And I'll try to help you! :) I send to you my solution |
WA #7 | Shady TKTL | 1013. K-ичные числа. Версия 3 | 7 мар 2007 10:35 | 1 |
WA #7 Shady TKTL 7 мар 2007 10:35 Can somebody give me some tests (hard tests) |
how can i use log (or ln) without math header | starforever | 1013. K-ичные числа. Версия 3 | 27 дек 2006 20:52 | 3 |
as you know, it is forbidden to use math. but then how to use log? If you need ln try to use teylor series to calculate in manually... However, i think there isn't any nessesity for log... But I may be wrong, because i didn't solve this yet (solved only version 2). |