Box and Ball [AtCoder – 1996]题解

Box and Ball [AtCoder – 1996]题解

Problem Statement

We have N boxes, numbered 1 through N. At first, box 1 contains one red ball, and each of the other boxes contains one white ball.

Snuke will perform the following M operations, one by one. In the i-th operation, he randomly picks one ball from box xi, then he puts it into box yi.

Find the number of boxes that may contain the red ball after all operations are performed.

题意简述:有N个盒子,初始时只有1号盒子有1个红球,其它N-1个盒子都有1个白球。每次都可以从第x个盒子中取出一个球放入y号盒子,这样的进行M次,给出操作序列,当这些次取放之后,要计算共有几个盒子中可能有红球。

问题分析

刚开始只有1号盒有红球,如果操作时不在1号盒中进行,那么这些球不论怎么取都只有1号盒有红球。而若从1号盒将球取到k号,则1号盒的红球就到了k号。如果刚开始先将其它的白球放入1号盒,再从1号盒中取一个球到其它盒中,这时从1号盒中取出的也可能是红也可能是白,这样就有两个盒出现红球。归纳下来发现,我们可以对问题进行这样建模:

有N个容量极大的杯子,第1号杯中有1升红墨水,其它N-1杯中都是透明的水。从x杯中倒入y杯的时候,当x杯中是红的,则y杯同样是红的,并且将x与y杯的体积进行调整(x-=1,y+=1),若此时x杯已空,则记x杯不是红的。操作之后再统计一下所有杯中有多少红色的即可。

using System;
namespace malicApplication
{
   class p1
   {
     public static void Main(string[] args)
	{
            int[] volume;
            Boolean[] isRed;
            int N, M, x, y,i,k,count;
            String[] input;
            input=Console.ReadLine().Split(' ');
            N = Convert.ToInt32(input[0]);
            volume = new int[N];
            isRed = new bool[N];
            isRed[0] = true;
            volume[0]=1;

            for(i=1;i<N;i++)
            {
                volume[i] = 1;
                isRed[i] = false;
            }

            M = Convert.ToInt32(input[1]);
            for(i=0;i<M;i++)
            {
                input = Console.ReadLine().Split(' ');
                x = Convert.ToInt32(input[0])-1;
                y = Convert.ToInt32(input[1])-1;

                volume[x] -= 1;
                volume[y] += 1;
                if(isRed[x]==true)
                {
                    isRed[y] = true;
                }
                if (volume[x] == 0)
                {
                    isRed[x] = false;
                }
            }
            count=0;
            for(i=0;i<N;i++)
            {
                if(isRed[i]==true)
                    count+=1;
            }
            Console.WriteLine(count);

        }
   }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注