做一个WaterOverflow

Question

你和一个朋友在玩游戏-谁能溢出最多的容器？有编号为1到n的n容器。每个容器都有一定的最大水容量，以升为单位。

你和你的朋友轮流往容器里倒离散量的水。轮到你的时候，你可以把2升水倒进一个容器里(你不能把水分散到多个容器里)，而在你朋友的时候，他必须倒3升。你也可以选择，在你的时候，不倒水在任何一个容器(但是，你不能选择只倒1升)。设法使容器溢出的人--即，在他们完成他们的轮值后，容器内的升水大于其最大容量--得到了一个点。

输入以空格分隔整数的形式出现。最左边的标记为1，最右边的标记为n。例如：

Y 2 1 4 3

请注意，这封信表明谁是第一位。Y的意思是你先走，F的意思是你的朋友先走。2升集装箱标为1，1升集装箱标为2等，因此我们将2升集装箱称为“集装箱1"，因为它被标为1。

现在，你的朋友有一个非常幼稚的策略。他总是把他所有的3升水倒进最接近溢出的容器里。如果有多个同样最接近溢水的容器，他将把所有的水倒在一个标有最低数量的容器里。

假设我使用同样天真的策略，将我所有的2升水倒入最接近溢出的容器中。示例输入的结果如下：

1. 我把所有的水倒进2号容器，水溢出来了，我得到了一个点。
2. 我的朋友把所有的水都倒进了一号容器，水溢出来了，他得到了一分。
3. 我把所有的水倒入容器4，里面现在有2L的水，所以它需要另一个2L才能溢出。
4. 我的朋友把所有的水都倒进4号集装箱，水溢出来了，他得到了一分。
5. 我把所有的水倒进3容器，里面现在有2L的水，所以它还需要3L才能溢出。
6. 我的朋友把所有的水都倒进了3号容器，水溢出来了，他得到了一分。

总之，我只得了一分，而我的朋友得了三分。这可不妙。我可以做得更好，如果我利用我的能力，通过我的轮值，而不倒水：

1. 我把所有的水倒进2号容器，水溢出来了，我得到了一个点。
2. 我的朋友把所有的水都倒进了一号容器，水溢出来了，他得到了一分。
3. 我过去了。
4. 我的朋友把所有的水都倒进了4号容器，里面现在有3L的水，所以它还需要1L才能溢出。
5. 我把水倒进4号集装箱，水溢了，我得到了一个点。
6. 我的朋友把所有的水都倒进了3号容器，里面现在有3L的水，所以它还需要2L才能溢出。
7. 我把水倒进3号容器，水溢了，我得到了一个点。

通过战略性地选择要倒水的容器，我成功地获得了3点而不是1点。输出格式是一个空格分隔的指令列表，其中P表示一个传递，从1到n的一个整数表示我将水倒入的容器。例如，上文所列的天真非最佳战略可以表示为：

2 4 3

这意味着我倒进了容器2，然后是容器4，然后是容器3。最优的策略是：

2 P 4 3

这意味着我倒入容器2，然后传递，然后容器4，然后容器3(顺便说一句，这是输出格式)。

您的程序将接受上述输入，并返回最优的解决方案，以获得尽可能多的点。如果有多个最优解，也可以输出。

Answer 1

Java - 718

一般说来，我回合开始时桶中的最佳水量应该是容量-1或满。因此，上一轮(理想情况下)应该是容量-4或容量-3，容量-7或容量-6。

因此，唯一对我不利的选项是容量-n%3 == 2，所以我的策略是等到最后，然后在最后一分钟抓起桶，注意保持桶的水平在"ok范围“。如果所有的桶都在范围内，那就什么也不做！

因为当容量是2时，你不能获胜，所以我干脆忽略了它。

我认为这可能是最佳解决方案。当能力大于2的时候，它会100%地击败朋友。

下面是函数(用于上面的模拟器)：

BucketChoice makeMove(){
    ArrayList<Bucket> bucketsNotOk = new ArrayList<Bucket>();
    ArrayList<Bucket> bucketsOk = new ArrayList<Bucket>();
    //sort buckets
    for(Bucket b:buckets){
        if(b.litersLeft() % 3 == 2){bucketsNotOk.add(b);}
        if(b.litersLeft() % 3 == 0){bucketsOk.add(b);}
        if(b.litersLeft() % 3 == 1){bucketsOk.add(b);}
    }
    //first I want to grab any buckets ready for overflowing
    for(Bucket b:bucketsOk){
        if(b.litersLeft()<2){System.out.println(buckets.indexOf(b));return new BucketChoice(b,2);}
    }
    //next change buckets to OK
    for(Bucket b:bucketsNotOk){
        //no use adding water if it is doomed
        if(b.litersLeft()>2){System.out.println(buckets.indexOf(b));
            return new BucketChoice(b,2);
        }
    }
    return new BucketChoice(buckets.get(0),0);  
}

golfed...hmmm似乎很长：

import java.util.*;class o{List<int[]>b=new ArrayList<int[]>(),r=new ArrayList<int[]>();public o(String[]a){for(int x=1;x<a.length;x++){b.add(new int[]{Integer.valueOf(a[x]),0});}while(b.size()>0){if(a[0].equals("F")){e();}int m=0,n=-1,i=0;for(;i<b.size();i++){int[]g=b.get(i);if(g[0]-g[1]<2){n=i;m=1;g[1]+=2;break;}}for(i=0;i<b.size();i++){int[]g=b.get(i);if((g[0]-g[1])%3==2&&m==0){n=i;g[1]+=2;break;}}for(int[]h:b){if(h[0]-h[1]<0){r.add(h);}}for(int[]h:r){b.remove(h);}if(a[0].equals("Y")){e();}if(n!=-1){System.out.print(n+" ");}else{System.out.print("p ");}}}void e(){int[]r={99999,0};for(int[]i:b){if(i[0]-i[1]<r[0]-r[1]){r=i;}}r[1]+=3;if(r[0]-r[1]<0){b.remove(r);}}public static void main(String[]a){new o(a);}}

Answer 2

Java模拟器

我知道外面有懒人！下面是：

要继续，只需在控制台中按任意键+ enter即可。

OverflowChallenge：

import java.util.ArrayList;
import java.util.Scanner;

    public class OverflowChallenge {
        ArrayList<Bucket> buckets = new ArrayList<Bucket>();
        int myScore=0,friendScore=0;
        public static void main(String[] args) {
            new OverflowChallenge(args);
        }
        public OverflowChallenge(String[]args){
            for(int x=1;x<args.length;x++){
                buckets.add(new Bucket(Integer.valueOf(args[x])));
            }
            while(buckets.size()>0){
                Scanner s = new Scanner(System.in);     
                if(args[0].equals("F")){naivePlayerMove();}

                BucketChoice myMove=null;
                if(buckets.size()>0){myMove = makeMove();}else{System.exit(0);}
                myMove.bucket.addWater(myMove.litersAdded);
                if(myMove.bucket.overflowing){buckets.remove(myMove.bucket);}

                System.out.println("you added "+myMove.litersAdded+" to bucket "+buckets.indexOf(myMove.bucket));
                if(myMove.bucket.overflowing){System.out.println("...and you overflowed it!");}

                if(!args[0].equals("F")){naivePlayerMove();}
                for(Bucket b:buckets){
                    System.out.println("bucket "+buckets.indexOf(b)+" has " + b.litersFilled +"/"+b.capacity);
                }
                System.out.println("friend score = "+friendScore);
                System.out.println("my score = "+myScore);
                s.next();
            }
        }
        BucketChoice makeMove(){
            return new BucketChoice(buckets.get(0),2);
        }
        void naivePlayerMove(){
            Bucket lowestBucket=new Bucket(999999999);
            for(int x=0;x<buckets.size();x++){
                if(buckets.get(x).litersLeft()<lowestBucket.litersLeft()){
                    lowestBucket=buckets.get(x);
                }
            }
            lowestBucket.addWater(3);
            System.out.println("your friend added 3 liters to bucket "+buckets.indexOf(lowestBucket));
            if(lowestBucket.overflowing){
                friendScore++;
                buckets.remove(lowestBucket);
                System.out.println("...and overflowed it!");
            }
        }
}

桶：

public class Bucket {
    int capacity,litersFilled;
    boolean overflowing = false;
    public Bucket(int capacity){
        litersFilled=0;
        this.capacity=capacity;
    }
    public int litersLeft(){
        return capacity-litersFilled;
    }
    public void addWater(int liters){
        litersFilled+=liters;
        if(litersFilled>capacity){
            overflowing=true;
        }
    }
}

BucketChoice：

public class BucketChoice {
    public BucketChoice(Bucket myBucket, int liters){
        bucket = myBucket;
        litersAdded = liters;
    }
    public Bucket bucket;
    public int litersAdded;
}

享受吧！