Announcement

Collapse
No announcement yet.

Giả định Collatz - Bài toán 3n+1

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Giả định Collatz - Bài toán 3n+1

    Theo em thấy thì đã lâu lắm rồi chưa ai post gì vào Box này, sẵn có 1 vấn đề đang nhức đầu nên em post lên đây hỏi ae.

    Đề: http://www.spoj.com/problems/PROBTNPO/

    Em nộp code bằng Java nó cứ báo Runtime Error NZEC :beatbrick: trong khi cái e chuyển thể y chang sang CPP14 lại AC với thời gian 0.2s :salute:
    Ai rảnh tư vấn cho em với :sosad: định đi theo con đường Java mà thế này thì nát, mất cả ngày của e r :surrender:

    code Java
    Code:
    import java.io.*;
    import java.util.*;
    
    public class Main {
        public static void main(String[] args) throws IOException, InterruptedException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
            final Solver solver = new Solver();
            for ( ; ; ) {
                String line = br.readLine();
                if (line == null) {
            	break;
                }
                StringTokenizer st = new StringTokenizer(line);
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int l = a, r = b;
                if (a > b) {
                    l = b;
                    r = a;
                }
                pw.println(a + " " + b + " " + solver.solve(l, r));
            }
            br.close();
            pw.close();
        }
    }
    
    class Solver {
        private int[] dict = new int[1000000];
        int solve(int l, int r) {
            int res = 0;
            for (int i = l; i <= r; ++i) {
                if (dict[i] == 0) {
                    dict[i] = alg(i);
                }
                if (dict[i] > res) {
                    res = dict[i];
                }
            }
            return res;
        }
        private int alg(long n) {
            int res = 1;
            while (n != 1) {
                if (n % 2 != 0) {
                    n = 3 * n + 1;
                    n >>= 1;
                    res += 2;
                }
                else {
                    n >>= 1;
                    ++res;
                }
            }
            return res;
        }
    }
    code CPP14
    Code:
    #include <iostream>
    #include <string>
    #include <sstream>
    using namespace std;
    
    int *dict;
    
    int alg(long long n) {
        int res = 1;
        while (n != 1) {
            if (n % 2 != 0) {
                n = 3 * n + 1;
                n >>= 1;
                res += 2;
            }
            else {
                n >>= 1;
                ++res;
            }
        }
        return res;
    }
    int solve(int l, int r) {
        int res = 0;
        for (int i = l; i <= r; ++i) {
            if (dict[i] == 0) {
                dict[i] = alg(i);
            }
            if (dict[i] > res) {
                res = dict[i];
            }
        }
        return res;
    }
    
    int main() {
        ios::sync_with_stdio(false);
        dict = new int[1000000];
        for ( ; ; ) {
            string s;
            getline(cin, s);
            if (s == "") {
                break;
            }
            int a, b, i, j;
            stringstream(s) >> a >> b;
            i = a;
            j = b;
            if (a > b) {
                i = b;
                j = a;
            }
            cout << a << " " << b << " " << solve(i, j) << endl;
        }
        return 0;
    }
    EDIT:
    thay (line == null) thành (line == null || line.isEmpty())
    15520878
    La Văn Tiến
    Last edited by 15520878; 01-04-2017, 11:49. Reason: Add solution

LHQC

Collapse
Working...
X