| Show all threads Hide all threads Show all messages Hide all messages |
| WA10 | Серовиков Андрей | 1564. Counting Ones | 23 Feb 2011 21:32 | 8 |
WA10 Серовиков Андрей 13 Oct 2007 14:53 What's wrong, if the second test is 10^18?
the ones of 1 to 10^18 have over the range of int64 Re: WA10 NickSergeev[MSU MindCraft] 16 Mar 2008 18:14 The number of ones is less than number of floor. For me tha answer must be in Int64 Re: WA10 Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 17 Mar 2008 22:03 The answer is within Int64. So, try to find bug in your code or algorithm... Re: WA10 Chmel_Tolstiy 18 Mar 2008 19:44 if you use line like this at TIMUS will a bug ...
long long INF = 1e18;
you should use
long long INF = 1e9;
INF *= INF; Use unsigned __int64, might help. Also, if you use binary search, make sure that left+right does not overflow prior to /2 or >>1. if you use line like this at TIMUS will a bug ...
long long INF = 1e18;
you should use
long long INF = 1e9;
INF *= INF; Thank you! Try this test
12
Answer 19 (not 20) |
| Is the test case correct??? | vanvector | 1817. Merry-go-round | 22 Feb 2011 05:58 | 15 |
consider the test case in problem statement. Will the kid really wait for 0.6875 sec, when 2 kids are riding merry-go round?? Mb this value should be 0.625 = 5/8???
Edited by author 30.01.2011 13:22 The test case is correct. it seems to be wrong at all
there are 6 posibilities in this hypothesis (there are 2 childrens) they are:
1100 - 2
1010 - 1
1001 - 1
0110 - 0
0101 - 0
0011 - 0
so, the posibility must be 2*1/6 + 1*1/6 + 1*1/6 = 0.66666667
isn't it right??
Edited by author 30.01.2011 14:15
_________________________________________
test case is right. there are sub-hypothesis with different posibilities
Edited by author 30.01.2011 14:54 Seems like the possibility of each case isn't equal to 1/6, some of the cases have more then 1/6, others - less. How did you do that??
Edited by author 30.01.2011 16:45 Yes, test case is correct.
Look:
1010 you can get from 1000 and 0010, p = 2/16
0101 you can get from 0100 and 0001, p = 2/16
But:
1100 you can get from 1000 (2 times!) and 0100, p = 3/16
0110 you can get from 0100 (2 times!) and 0010, p = 3/16
0011 you can get from 0010 (2 times!) and 0001, p = 3/16
1001 you can get from 0001 (2 times!) and 1000, p = 3/16
Thus, we get:
p(1100) = 3/16, p(1001) = 3/16, p(1010) = 2/16
And the answer is:
(3/16)*2 + (3/16)*1 + (2/16)*1 = 11/16 = 0.6875
Nice problem! Look:
1010 you can get from 1000 and 0010, p = 2/16
0101 you can get from 0100 and 0001, p = 2/16
But:
1100 you can get from 1000 (2 times!) and 0100, p = 3/16
0110 you can get from 0100 (2 times!) and 0010, p = 3/16
0011 you can get from 0010 (2 times!) and 0001, p = 3/16
1001 you can get from 0001 (2 times!) and 1000, p = 3/16 Can you please explain why for 1010 -> p = 2/16 but 1100 -> p = 3/16 How does 1000 come 2 times in this case ? 1000 -> 1010 if start position = 3
0010 -> 1010 if start position = 1
(2 times)
1000 -> 1100 if start position = 1
1000 -> 1100 if start position = 2
0100 -> 1100 if start position = 1
(3 times) "And the answer is:
... + (3/16)*1 + = 11/16 = 0.6875"
Could you explain why (3/16)*1 but not (3/16)*2,
though max waiting time is 2 (1001 - if we stand at place 1)??
Mask Time
0011 0
0101 0
0110 0
1001 1
1010 1
1100 2 Sorry, but why 11/16? Why not 3/16 + 3/16 + 3/16 + 3/16 + 2/16 + 2/16 = 16/16
I understand that
4/16 == 0.250000 ======
1000 1/16
0100 1/16
0010 1/16
0001 1/16
24/16 == 1.500000 =====
1110 (3+2+1=6)/16
1101 (3+2+1=6)/16
1011 (3+2+1=6)/16
0111 (3+2+1=6)/16
But why 11/16? Just some basic knowledge from probability theory...
3/16 + 3/16 + 3/16 + 3/16 + 2/16 + 2/16 = 16/16
It's a normalization requirement (p1 + p2 + ... + pn = 1).
And mean MX = p1*x1 + p2*x2 + ... + pn*xn,
where pi - probabilities, xi - values.
So we have (3/16)*2 + (3/16)*1 + (2/16)*1 + (3/16)*0 + (3/16)*0 + (2/16)*0 = 11/16. In Buffon problem there are 3 different
solution and all of them are right.
Answer depend on exact understanding
all conditions of random experiment.
I think that this problem also safer from too
brief explanation.
i've used this explanation of test:
let it be some kind of class:
1100 0110 0011 1001 - first class, maked by all rotations of first one, and it's representative would be a smallest, so:
[1100] : {1100 0110 0011 1001}
[1010] : {1010 0101 1010 0101} - second class, we have repeatings here, but it must be always n rotations
so, we could get [1100] from:
1000 - waiting 1 sec,
0001 - not waiting
0100 - not waiting
all of them is class [1000] which comes from [0000] with 100% posibility
so posibilities of [1000] would be:
1000 - 100% * 1 / 4
0001 - 100% * 1 / 4
0100 - 100% * 1 / 4
so posibility of getting in class [1100] is 3/4
[1010] we could get from:
0010 which posibility is 100% * 1 / 4
so our classes have such posibilities:
[1100] - 3 / 4
[1010] - 1 / 4
[1100]:
mask sec posibility
1100 2 1/4*3/4
0110 0 1/4*3/4
0011 0 1/4*3/4
1001 1 1/4*3/4
[1010]:
mask sec posibility
1010 1 1/4*1/4
0101 0 1/4*1/4
1010 1 1/4*1/4 - it repeats, but it is another rotation, 3rd
0101 0 1/4*1/4 - 4th
so, our result would be:
MX = 2 * 3/16 + 1 * 3/16 + 1 * 1/16 + 1 * 1/16 = 11/16 = 0.6875
like in our test case
i've used DP for this problem, just filling array of posibilities in recursive with saving way, rotating my current mask, and looking from where i could go here |
| ...delete... | The Godfather | | 21 Feb 2011 23:46 | 1 |
...delete...
Edited by author 21.02.2011 23:47 |
| beware! problem statement is absolutely correct now | Radi Muhammad Reza | 1334. Checkers | 21 Feb 2011 11:31 | 2 |
may b something was wrong previously. now it is correct.
can't fall over boundary. must jump to empty cell. and only black cells. however, u must check - new checker may attack or be attacked :P Yes, it is somehow strange but if one of players put checker and this checker can attack the checker of another colour, so the game is stopped with the fool (!) of this player.
Naturally, if this put checker could be attacked the end is the same. |
| Wa on Test#5,who can tell me why? | xkszltl | 1627. Join | 20 Feb 2011 18:41 | 1 |
|
| Pay attention | FranckRibery | 1519. Formula 1 | 20 Feb 2011 16:03 | 1 |
There could be blanks between adjacent characters. |
| why there is a string in test#2 doesn't show up in the map ? | William Chou | 1575. Yekaterinburg Subway 2 | 20 Feb 2011 12:15 | 3 |
I insert all string that show up in the map into index (std::map<string,int> index).
And I use these code to debug:
string s1,s2;
cin >> s1 >> s2;
if (index.find(s1) == index.end() || index.find(s2) == index.end())
while (true);//if the string doesn't show up in the map,I will get TLE.
...
And I got TLE #2.
Who can help me?
Thanks.
Sorry for my poor English.
PS:It's guarantee that I won't insert wrong string into index.
Edited by author 17.02.2011 14:50 Test for you:
1
Himmash Nizhne_Isetskaya
Good luck! :) ありがど ございます。
thanks for your test,I found I forgot a comma in my code.
But passed compile.
- -
AC now. |
| WA#3 | Muhabbat | 1630. Talisman | 20 Feb 2011 01:37 | 3 |
WA#3 Muhabbat 11 Oct 2008 17:58 3- TEST NIMA? WHAT IS 3 TEST
REAL Re: WA#3 Oleg Strekalovsky [Retired] 21 Feb 2010 16:39 I think there are sets of unconnected points.
They are lucky, i think test#3 is a M=0. it's lucky. |
| WA #9 | 2rf | 1757. Gold Bars | 19 Feb 2011 19:26 | 2 |
WA #9 2rf 14 Sep 2010 02:15 I need help. Please tell if you had the same problem. Any tricky test will help as well. After 5 months I have finally got AC by just rewriting my program from C++ to Java. I now really want to know what was wrong with my older program. Can admins send me this test? |
| Wa7 please give some tests!! | Stankov | 1786. Sandro's Biography | 19 Feb 2011 18:50 | 4 |
test №1: "sANDRO" ; correct answer: 30
test №2: "ZZZZZZZ" ; correct answer: 55
test №3: "sandro" ; correct answer: 5 |
| is contain zero | shahed adnan | | 16 Feb 2011 00:40 | 2 |
how can i check an integer ,is that contain zero? i know a solution using char array.
but on the mentioned case, i m unable to do. help me..plz. boolean containZero(int x){
do{
if (x%10==0) return true;
x/=10;
}while(x!=0)
return false;
}
Edited by author 16.02.2011 00:45 |
| wrong answer test #15 | Ravi Maggon | 1083. Factorials!!! | 15 Feb 2011 22:13 | 3 |
can anyone tell me whats wrong with my code. it displays wrong answer test #15 #include<iostream> #include<string.h> using namespace std; int main() { long int n; long int ans=1; char k[20]; cin>>n>>k; if(n<1||n>10) return 0; long int res; res=n%strlen(k); long int i=0,length=strlen(k); if(length<1||length>20) return 0; if(res==0) { while(n-i*length>=length) { ans=ans*(n-i*length); i++; } } else { while(n>=i*length) { ans=ans*(n-i*length); i++; } } cout<<ans; return 0; } Edited by author 21.08.2010 11:3215 test
n=10
k=20
it's last test > char k[20]
You forgot about the null character ( '\0' ). Correct is
char k[21] |
| my solution | Rainsoul | 1209. 1, 10, 100, 1000... | 15 Feb 2011 21:09 | 1 |
#include <iostream>
#include <cstdlib>
#include <cmath>
int main(){
long N;
long *array;
std::cin >> N;
array = ( long * )malloc( sizeof( long ) * N );
for( long i = 0; i < N; i++ )
std::cin >> array[ i ];
for( long i = 0; i < N; i++ )
std::cout
<< ( floor( ( 1 + sqrt( 1 + 8.0 * ( array[ i ] - 1 ) ) ) / 2 ) ==
( ( 1 + sqrt( 1 + 8.0 * ( array[ i ] - 1 ) ) ) / 2 ) )
<< ' ';
free( ( void * )array );
} |
| 1001 solution | Levan | 1001. Reverse Root | 15 Feb 2011 20:36 | 3 |
Here the answer:
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main(){
double x;
vector<double>a;
while(cin>>x)a.push_back(sqrt(x));
for(int i=a.size()-1;i>=0;i--)printf("%.4f\n",a[i]);
return 0;
} Didn't "while(cin>>x)" lead to endless loop? |
| Why WA10 plz | Kurpilyansky Eugene (USU) | 1351. Good Gnusmas – Dead Gnusmas | 15 Feb 2011 20:22 | 3 |
If you use Real types of variables, replace it by Extended. in 10th test x1=y1 and x2=y2 |
| WTF? | Levan Arabuli [Tbilisi SU] | 1083. Factorials!!! | 15 Feb 2011 18:26 | 3 |
WTF? Levan Arabuli [Tbilisi SU] 15 Feb 2011 18:25 what the fuck is test # 15? :lol:
Edited by author 15.02.2011 18:26 Re: WTF? Levan Arabuli [Tbilisi SU] 15 Feb 2011 18:26
Edited by author 15.02.2011 18:26 Re: WTF? Levan Arabuli [Tbilisi SU] 15 Feb 2011 18:26 what the fuck is test # 15? :lol: |
| TL11 | airibo | 1803. The Czechs' Rifles | 15 Feb 2011 04:52 | 6 |
TL11 airibo 7 Nov 2010 07:04
Edited by author 11.11.2010 07:28 Re: TL11 Alexey Dergunov [Samara SAU] 7 Nov 2010 13:28 Of course, it's slow! BigIntegers are not allowed in this problem!
And replace your precalculations by while cycle and in k-based numeral system!
Edited by author 07.11.2010 13:42
Edited by author 11.11.2010 07:28 AC dont use ArrayList for adding two big numbers just used array (in java) If you have TLE#11 consider to use not "one byte per one digit" representation, but rather one 16/32 bit int per group of digits. Another hint: when you sum all digits in your next fibonacci number and use 16-24 bits per group approach, you can precalculate sum of digits in every possible of such groups before the main loop. |
| help, plz | quick(YaroslavlSU) | 1411. 40 Islands Knights | 15 Feb 2011 01:08 | 2 |
help, plz quick(YaroslavlSU) 25 Aug 2009 20:48 please give me test #35 or answer n=7 m=5 There must be exactly 3 * n * m / 2 bridges. So if n and m are both odd then no valid map possible |
| please help: can an edge be shared by 2 different routs? | Radi Muhammad Reza | 1434. Buses in Vasyuki | 14 Feb 2011 20:14 | 1 |
like
...
3 10 6 8
4 10 6 9 11
...
???
please help |
| What's wrong with my solution. please help, i don't understand... | system crash | 1427. SMS | 13 Feb 2011 18:37 | 1 |
int main(int argc, char** argv)
{unsigned long long int min = 0, max = 0;
unsigned long long int len = 0;
unsigned long long int tt = 0;
unsigned long long int counter = 0;
char a[100001];
int i;
scanf("%lld %lld",&min,&max);
gets(a);
gets(a);
len = strlen(a);
for(i = 0;i<len;i++)
{
if((unsigned char)(a[i])==' ' || isalpha((unsigned char)(a[i])))
{
tt++;
if(tt == max)
{
tt = 0;
counter++;
}
}
else
{
tt = 0;
}
}
if((len-(counter*max))%min == 0)
counter+=(len-(counter*max))/min;
else
counter+=(len-(counter*max))/min+1;
printf("%lld",counter);
return 0;
}
Edited by author 13.02.2011 18:48 |
