|
|
Discussion of Problem 1537. EntsProblem statement is annoying to read. The following shows results from K=0 to K=50 (mod 1000000007). Hope this helps. 0 0 1 1 2 2 3 3 5 5 7 7 10 10 13 13 18 18 23 23 30 30 37 37 47 47 57 57 70 70 83 83 101 101 119 119 142 142 165 165 195 195 225 225 262 262 299 299 346 346 393 This is my code... CONST MaxN = 10000000; VAR K, P : Longint; A : Array [1 .. MaxN] of Longint; PROCEDURE Solve; Var i : Longint; Begin A[1] := 0; A[2] := 1; for i := 3 to K do if i mod 2 = 0 then A[i] := (A[i - 1] + A[i div 2]) mod P else A[i] := A[i - 1] mod P; End; PROCEDURE Run; Begin ReadLn(K, P); Solve; WriteLn(A[K]); End; BEGIN Run; END. Were my mistake is? Sorry for my bad english... A[1] := 0; A[2] := 1; // this line is wrong, must be A[2] := 1 mod P test 1 1 answer is 0
thX AC What a stupid mistake I also made. Edited by author 21.10.2012 19:56 my program works fine on my computer. it even gives right answers :) But when i submit it has crash on 20 test. I cannot understant why. Please help!! import java.io.*; import java.util.Arrays; public class Task_1537 { public static void main(String[] args) throws Exception{ StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in)); st.nextToken(); int k = (int) st.nval; st.nextToken(); int p = (int) st.nval;
int t[] = new int[k+1]; t[2] = 1 % p; for (int i = 3; i <= k; i++){ if ((i & 1) == 1) t[i] = t[i-1]; else t[i] = t[i-1] + t[i/2]; if (t[i] >= p) t[i] = t[i] - p; } //System.out.println(Arrays.toString(t)); System.out.println(t[k]); } } // JAVA : import java.io.*; import java.util.Arrays; public class Task_1537 { public static void main(String[] args) throws Exception{ StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in)); st.nextToken(); int k = (int) st.nval; st.nextToken(); int p = (int) st.nval; if(k<2)System.out.println(0); else { int t[] = new int[k+1]; t[2] = 1 % p; for (int i = 3; i <= k; i++){ if ((i & 1) == 1) t[i] = t[i-1]; else t[i] = t[i-1] + t[i/2]; if (t[i] >= p) t[i] = t[i] - p; } //System.out.println(Arrays.toString(t)); System.out.println(t[k]); } } } // C++ : #include<stdio.h> int main(){ int k,p,i; int *t; scanf("%i%i",&k,&p); if(k<2)printf("0"); else { t = new int[k+3]; t[2] = 1 % p; for (i = 3; i <= k; i++){ if ((i & 1) == 1) t[i] = t[i-1]; else t[i] = t[i-1] + t[i/2]; if (t[i] >= p) t[i] = t[i] - p; } printf("%i",t[k]); } } CONST MaxN = 10000000; VAR K, P : Longint; A : Array [0 .. MaxN] of Longint; PROCEDURE Solve; Var i : Longint; Begin A[1] := 0; A[2] := 1 mod P; for i := 3 to K do if i mod 2 = 0 then A[i] := (A[i - 1] + A[i div 2]) mod P else A[i] := A[i - 1] mod P; End; PROCEDURE Run; Begin Read(K, P); if K<2 then WriteLn(0) else begin Solve; WriteLn(A[K]); end; End; BEGIN Run; END. I've did it with printing the code in the notepad, with any testing.. this was an epic luck! [code deleted] Edited by author 07.02.2012 02:46 Edited by author 07.02.2012 02:46 delete it Edited by author 13.06.2011 19:30 give me test. 1)50 100 ans:93 2)1000 1000 ans:939 3)10000 987 ans:697 4)20 20 ans:10 5)10000000 1000000000 ans:636184067 I hope it will help you!!! Edited by author 08.05.2007 19:22 #include <iostream.h> #define MAX 10000000 using namespace std; int main() { __int64 k,p,i; __int64 A[MAX]; cin>>k>>p;
A[0] = 0; A[1] = 1 % p; for(i = 2; i <= k; i++){ if(i % 2 == 0) A[i] = (A[i-1] + A[i / 2]) % p; else A[i] = A[i-1] % p; } cout<<A[k-1]; return 0; } Edited by author 21.05.2008 05:37 local variables are located in stack, so if you want to avoid stack overflow(crash) you can't declare big arrays inside functions int main() { __int64 k,p,i; __int64 A[MAX]; => __int64 A[MAX]; int main() { __int64 k,p,i; Try test 1 1 0 true? I also get 0. But WA15 Edited by author 03.03.2007 14:22 Edited by author 03.03.2007 14:22 Edited by author 03.03.2007 14:22 YES!!!!!!! Try this test 2 1 ))))) Thanks, AlMag! Sorry Edited by author 03.03.2007 15:44 Thanks to AlMag Why Wa 15 {$Apptype console} Const Find = 12344321; Type Longint = int64; Var a , b : array [1..10000000] of longint; N , k : longint; Function Ans(x : longint):longint; begin if b[x] = Find then begin Ans := a[x]; exit; end; b[x] := Find; if odd(x) then a[x] := Ans(x - 1) else a[x] := (Ans(x div 2) + Ans(x - 1)) mod k; Ans := a[x]; end; Begin Read(N , K); // if k = 1 then k := Trunc(1e14); b[2] := Find; a[2] := 1; if n < 2 then write(0) else Write(Ans(N)); readln; readln; end. Edited by author 16.03.2007 22:42 Pay attention on this line a[i]=a[i-1]+a[i/2]; What mistake can be in this line?THANK! overflow I try to correct it!If I cant,please, say how i must correct!THANK!!! I cant correct!IF YOU can,help me!!!THANK!!!!! Edited by author 16.03.2007 19:22 a[i]=(a[i-1]+a[i/2])%p; THANK for hint! Edited by author 16.03.2007 22:21 NOW I HAVE MLE on 24 test! Use int instead of __int64 and you'll get AC! WOW!!!NOW I GOT AC!!!THANK to KIRILL(ArcSTU) & Romko [Lviv NU]!!!! Edited by author 16.03.2007 22:41 [code deleted] Edited by author 18.06.2007 16:58 [code delete] Edited by author 30.06.2007 15:04 I think, it's a simple recursion. If N is even, then f(N)=f(N-1)+f(N/2) else if N is odd, then f(N)=f(N-1) Am I right? mod P also important espacially if P==1 I count it at the end before the output. There is my code: #include <iostream> using namespace std; __int64 FindAnswer(const __int64 &num); int main(void) { // Input data __int64 K, P; cin >> K >> P; // Outputs the result cout << (FindAnswer(K)%P) << endl; return 0; } // Function finds the answer __int64 FindAnswer(const __int64 &num) { if(num==2) return 1; if(num<2) return 0; if(num%2) return num/2; return FindAnswer(num-1) + FindAnswer(num/2); } It should to combine recursion and Dynamic prog. At the beggining build array F1[10000000] using formula and from K>10000000 go by recursion not to 1 as you but only to first value in [1..10000000] But %P we must make in FindAnswer befor return or we will have overflow and i don't understand conditiom if (num%2) must be if (num%2==0) To Duzhy Igor Your solution has non polynomial complexity Why you are using this way Just fill array[2..10000000] from 2 to k using your formula at the end out (mas[k]%p) Edited by author 05.03.2007 17:00 Thank you very much, I have solved it. Good luck!!! it should be 0... am i correct? |
|
|