### vici's blog

By vici, 11 years ago,
/*********************************
mark[]:p=0,c=1(except for evens);
pri[]:p(0..cnt-1)
*********************************/
const int MAXP=10000000;
int pri[MAXP],cnt;
bool mark[MAXP];
int setp() {
int i,j;
cnt=1,pri[0]=2;
for(i=3;i<MAXP;i+=2){
if(!mark[i])pri[cnt++]=i;
for(j=1;j<cnt && pri[j]*i<MAXP;++j){
mark[i*pri[j]]=1;
if(!(i%pri[j]))break;
}
}
return cnt;
}

• +2

By vici, 12 years ago,

• +7

By vici, 12 years ago,

All right I come back. Now we’ll analyze the problem.

According to the sentence the stranger said, “At least one is red”, we can infer three cases:

(1)1  red, 2 black

(2)2 red, 1 black

(3)3 red

Case 1: One red, two black

So after the stranger left the island, the red man would see two black, and then he can infer that he is the red, so he should kill himself in the first dusk. The other two noticed his suicide in the second morning, inferred it is “Case 1”, and went to the Pandora in the second dusk.

Case 2: Two red, one black

In the first day, the red saw one red and one black, he would consider that if he is black, then it is “Case 1”, the red he see will kill himself in the first dusk, and if he is red, it is “Case 2”, the red won’t go. The black saw 2 red, he excluded “Case 1” directly, and would consider that if he is black, then it is “Case 2”, otherwise it is “Case 3”. The next day, no one died. The two red confirmed it is “Case 2”, and did what they should do in the dusk. The third day, the black noticed it is “Case 2”, and found he is the black, so he killed himself in the third dusk.

Case 3: Three red

In the first day, three people saw two red, then they would consider, if he is black, then it is ”Case 2”, two people will die in the second dusk, and if he is red, the other two will wait for the result till the third morning, no one will die in the first two days. As they considered, no one ran a risk before the third day, so in the third morning they all judged it is “Case 3”, and went to the Heaven in the dusk.

The Conclusion:

Case 1: The red went to Heaven in the first day, the two black did it in the second day.

Case 2: The two red went to Heaven in the second day, and the black did it in the third day.

Case 3: The three men went to Heaven synchronously in the third day.

And in the story, it is "Case 2".

All right, is it interesting? But it’s just the beginning! I will take some more interesting stories in my next blogs, coming soon!

• 0

By vici, 12 years ago,

At first I must say that I have no gift in English, or Russian. So if you can’t catch my meaning, but what I can say is sorry. I promise I will try my best to improve my English. And I still have interest in Russian, for the reason that my dad is a great Russian speaker. Maybe I can communicate with you in Russian soon after.

Ok, let’s go! What I want to talk about is an interesting problem, Game Theory. Yes, I will connect Game Theory with ACM, and show you how to deal with these problems.

But what is Game Theory? I quote the explanation in wiki.

Game theory attempts to mathematically capture behavior in   strategic situations , in which an individual's success in making choices depends on the choices of others.

So it seems used in economics mostly. There’re many famous economists mastering it, such as Nash. But compared with the complex economics, I prefer to the games which kids love. Now I will tell you some stories about Game Theory.

Look at the island. What do you think about it? Oh I remember the LOST, a mysterious  American-TV. But this island is so small that the total number of its people is 3. They lived in three separate caves. And there is a word to describe them, “freak”. They all can’t speak, they all feel lonely, they all believe in God.

One day, the Avatar comes to the island and told to them three: “Now I give you a chance to enter the Heaven, Pandora. I had dyed your hair red or black. Each of you can only see the other two’s hair color, but never see your own color, and no one will tell you what’s your color is. When you know your color, please face to the sun and kill yourself at dusk, and then I will take you to the Heaven. Good luck! Bye!”

The three poor men looked at each other, and they don’t know what to do, only to wait. The life returns to normal. They lived in harmony for several years. But in one morning, a stranger invaded the island and broke the peace.

The stranger noticed everything about the three. Soon he left the island and left one sentence: At least one of you three has red hair.

They looked at each other again, and went back to their own caves, dropped into reveries.

In the second morning, they got together in the centre of the island, looked at each other, and returned.

But in the dusk of this day, something happened. Two of the three killed themselves successfully, and went to the world of Pandora!

In the third morning, the last one went to the centre of the island, of course he saw no others, and he also had a success suicide in the dusk.

So, what happened to them? How could they do it? I feel puzzled!

Thank you for reading it, and I think you can solve the problem. I’ll give the analysis in next blog, it will come soon!

• 0

By vici, 12 years ago,
I'm vici.
It was good of Mike to invite me to this web. It's really cool.
I'll write some blogs to share some interesting experience.