Раунд 1C 2019. Задача A

 

Задача в оригинале. Краткий перевод: роботы играют в игру "Камень-Ножницы-Бумага". У каждого робота есть свой зацикленный алгоритм показа символов. Надо вывести последовательность символов, стабильно обыгрывающую любого робота или "IMPOSSIBLE", если такой последовательности не существует.

Решение: на каждом ходу проверяем количество разнообразных ходов роботов. Если их 3 - победа импоссибл, о чем и сообщаем. Если 2 - получаем непроигрышный ход и вычеркиваем проигравших на этом ходу роботов. Если 1 - получаем победный ход и цепочка на этом завершается

import java.io.File;
import java.io.IOException;
import java.util.*;

public class Solution {

    static boolean win;
    static ArrayList<Integer> wasWin = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        Scanner sc;

        if (args.length > 0) {
            sc = new Scanner(new File(args[0]));
        } else {
            sc = new Scanner(System.in);
        }

        int t = sc.nextInt();
        for (int tt = 1; tt <= t; ++tt) {
            win = false;
            wasWin.clear();
            System.out.println("Case #" + tt + ": " + _s(sc));
        }
        sc.close();
    }

    static String _s(Scanner sc){
        int a = sc.nextInt();
        String[] m = new String[a];
        HashSet<Character> freeMove = new HashSet<>();
        HashMap<Integer, Character> currMove = new HashMap<>();
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < a; ++i) {
            String s = sc.nextLine();
            while (s.equals("")) {
                s = sc.nextLine();
            }
            m[i] = s;
            freeMove.add(s.charAt(0));
            currMove.put(i, s.charAt(0));
        }
        if (freeMove.size() == 3)
            return "IMPOSSIBLE";
        int i= 1;
        while (!win){
            if (i == 501)
                break;
            ans.append(getMove(freeMove, currMove));
            if (win)
                break;
            freeMove.clear();
            currMove.clear();
            for (int j = 0; j < a; ++j){
                if (!wasWin.contains(j)) {
                    freeMove.add(m[j].charAt(i % m[j].length()));
                    currMove.put(j, m[j].charAt(i % m[j].length()));
                }
            }
            if (freeMove.size() == 3) {
                return "IMPOSSIBLE";
            }
            ++i;
        }
        if (!win) {
            return "IMPOSSIBLE";
        }
        else
            return ans.toString();
    }

    static char getMove(HashSet<Character> move, HashMap<Integer,Character> map){
        char a;
        if (move.size() == 1 && move.contains('P')) {
            win = true;
            return 'S';
        }
        else if (move.size() == 1 && move.contains('S')) {
            win = true;
            return 'R';
        }
        else if (move.size() == 1 && move.contains('R')) {
            win = true;
            return 'P';
        }
        if (move.contains('P') && move.contains('S'))
            a = 'S';
        else if (move.contains('R') && move.contains('S'))
            a = 'R';
        else
            a = 'P';
        for (Map.Entry<Integer, Character> m : map.entrySet()) {
            if (m.getValue() != a) {
                wasWin.add(m.getKey());
            }
        }
        return a;
    }

}

 

Published on May 23rd, 2019