| Show all threads Hide all threads Show all messages Hide all messages |
| hint | So Sui Ming | 1537. Ents | 4 Mar 2024 10:59 | 1 |
hint So Sui Ming 4 Mar 2024 10:59 Problem 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 |
| I got WA#15... Because I think that my algorithm is right... | [LG]_NAPSTER | 1537. Ents | 21 Oct 2012 19:55 | 5 |
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
What a stupid mistake I also made.
Edited by author 21.10.2012 19:56 |
| crash!! please help!! | Dmitriy Black | 1537. Ents | 15 Apr 2012 18:06 | 3 |
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 got AC!! | Mikhail Svyatlovskiy | 1537. Ents | 7 Feb 2012 02:20 | 1 |
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 | Elday | 1537. Ents | 13 Jun 2011 18:55 | 1 |
delete Elday 13 Jun 2011 18:55 delete it
Edited by author 13.06.2011 19:30 |
| WA 20 | AiD | 1537. Ents | 28 Aug 2009 05:28 | 3 |
WA 20 AiD 8 May 2007 18:30 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 Re: WA 20 Childofbodom_(It-Team) 28 Aug 2009 05:28 |
| please help, crash... stack overflow, here's code: | radio | 1537. Ents | 21 May 2008 19:11 | 2 |
#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:37local 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; |
| Damn, Always WA#15 (-) | AlMag | 1537. Ents | 28 Oct 2007 14:19 | 12 |
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
))))) Sorry
Edited by author 03.03.2007 15:44 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. |
| WhY WA#16???????????????!!!!!!!! I think it true solution | CHIDEMYAN SERGEY | 1537. Ents | 30 Jun 2007 15:00 | 13 |
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! 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 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 |
| WA#8 | Duzhy Igor | 1537. Ents | 7 Mar 2007 12:39 | 6 |
WA#8 Duzhy Igor 5 Mar 2007 12:03 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) Re: WA#8 KIRILL(ArcSTU) 5 Mar 2007 16:50 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!!! |
| what should be the answer for 1 10 | shilp | 1537. Ents | 3 Mar 2007 18:25 | 2 |
it should be 0... am i correct? |
