[伯俊]#1111 IQテスト

質問する

IQテストの問題では、共通のパターンを探す問題があります.数列をタイミングにして、次の数の問題を探します.
例えば、1,2,3,4,5が与えられる.次のステップは何ですか?答えはもちろん6です.もっと難しい問題を見ると、3,6,12,24,48が与えられたとき、次のステップは何ですか.やっぱり答えは96
今から見れば一番難しい問題です.
1,4,13,40を与えると、次のステップは何ですか.答えは121です.次の数字は常に前数*3+1だからです.
うん、本当に上の3つの問題が終わっていないので、自動解答プログラムを書くことにしました.いつもすべての答えは前数*a+bを求めます.また、aとbは整数です.
与えられた個数がNの場合、ルールに合致する次の数を求めるプログラムを作成します.

入力

1行目はNです.Nは50以下の自然数である.2行目にはN個の数字が与えられる.この数はいずれも節値が100以下の整数である.

しゅつりょく

次の数値を出力します.次の数が複数であればAを出力し、次の数が求められなければBを出力する.

入力例1

4
1 4 13 40

サンプル出力1

121

に答える

この問題はdfs(深さ優先探索)アルゴリズムを用いて,すべての場合に最善を尽くすことができる.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    static int[] arr;
    static int N;
    static HashSet<Integer> ans = new HashSet<>();    //가능한 다음 수 set

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        String[] input = br.readLine().split(" ");
        for(int i=0; i<N; i++)
            arr[i] = Integer.parseInt(input[i]);

        if(N==1)    //하나의 수만 주어지면 다음에 올 수는 무조건 2개 이상
            System.out.println("A");

        else if(N==2) {   //두 수가 주어졌을 때
            if(arr[0]==arr[1])  //두 수가 같으면 다음 수는 무조건 둘과 같은 수
                System.out.println(arr[0]);

            else          //두 수가 다르면 다음 수는 무조건 2개 이상
                System.out.println("A");
        }

        else {
            dfs(0, 0, 0);

            if(ans.size()==0)     //다음에 올 수가 없으면 B
                System.out.println("B");

            else if(ans.size()==1) {
                for(int res : ans)
                    System.out.println(res);
            }

            else      //다음에 올 수가 둘 이상이면 A
                System.out.println("A");
        }
    }

    public static void dfs(int idx, int a, int b) {
        if(idx==N-2) {
            boolean flag = true;

            for(int i=0; i<N-1; i++) {    //마지막에 도달 했을 때 전체 배열에서 만족하는 a,b인지 체크
                if(arr[i]*a + b==arr[i+1]) continue;
                flag = false;
            }

            if(flag)
                ans.add(arr[N-1]*a + b);

            return;
        }

        int pre = arr[idx];
        int temp = arr[idx+1];
        int next = arr[idx+2];

        if(temp-pre==0) {   //temp-pre==0 이면 나눌 수 없으므로 a를 0으로
            dfs(idx+1, 0, temp);
        }

        else {
            int x = (next-temp)/(temp-pre);   //공비
            int y = temp-pre*x;     //공차

            if(next==temp*x+y) {
                dfs(idx+1, x, y);
            }
        }
    }
}