Codeforces Round 370 Div2 Problem C

Posted on | In ,

CF712C Memory and De-Evolution

Solution Sketch

Key observation: It’s pretty hard to come up with the solution working from x to y. But, how about working your way back from y to x?

Hint: The next possible/best move is turn $(4, 4, 4)$ into $(4, 4, 7)$. Why 7? Because it’s in the range of $4 \leq x < 4 + 4 = 8$, which won’t form a degenerate triangle. Better yet, it’s the greatest among the range!

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.io.*;
import java.util.*;
public class C
{
    public static void main(String[] args)
    {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        int a = sc.nextInt(), b = sc.nextInt();
        ArrayList<Integer> inp = new ArrayList<Integer>();
        inp.add(b);
        inp.add(b);
        inp.add(b);
        Collections.sort(inp);
        int ans = 0;
        while(true) {
        	if( inp.get(0).intValue() == inp.get(1).intValue()
                && inp.get(1).intValue() == inp.get(2).intValue()
                &&  inp.get(0).intValue() == a )
        		break;
        	ans++;
        	inp.remove(0);
        	inp.add(Math.min(inp.get(0) + inp.get(1) - 1, a));
        	Collections.sort(inp);
        }
        out.println(ans);
        out.close();
    }
    public static PrintWriter out;
    public static class MyScanner
    {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        boolean hasNext()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    return false;
                }
            }
            return true;
        }
        String next()
        {
            if (hasNext())
                return st.nextToken();
            return null;
        }
        int nextInt()
        {
            return Integer.parseInt(next());
        }
    }
}