Advertisement
_rashed

UVA 10759

Jun 27th, 2022
46
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.67 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.io.OutputStreamWriter;
  6. import java.math.BigInteger;
  7. import java.util.StringTokenizer;
  8.  
  9. class Fraction {
  10.     public BigInteger num;
  11.     public BigInteger denum;
  12.    
  13.     public Fraction() {
  14.         num = BigInteger.valueOf(-1);
  15.         denum = BigInteger.valueOf(-1);
  16.     }
  17.    
  18.     public Fraction(long a, long b) {
  19.         num = BigInteger.valueOf(a);
  20.         denum = BigInteger.valueOf(b);
  21.     }
  22.    
  23.     public void fsum(Fraction b) {
  24.         BigInteger rnum = num.multiply(b.denum).add(b.num.multiply(denum));
  25.         BigInteger rdenum = denum.multiply(b.denum);
  26.         BigInteger g = rnum.gcd(rdenum);
  27.         rnum = rnum.divide(g);
  28.         rdenum = rdenum.divide(g);
  29.         num = rnum;
  30.         denum = rdenum;
  31.     }
  32.    
  33.     public void fmul(Fraction b) {
  34.         BigInteger rnum = num.multiply(b.num);
  35.         BigInteger rdenum = denum.multiply(b.denum);
  36.         BigInteger g = rnum.gcd(rdenum);
  37.         rnum = rnum.divide(g);
  38.         rdenum = rdenum.divide(g);
  39.         num = rnum;
  40.         denum = rdenum;
  41.     }
  42. }
  43.  
  44. public class Main {
  45.     public static int n,x;
  46.     public static Fraction mem[][];
  47.    
  48.     public static Fraction solve(int idx, int sum) {
  49.         if(idx == n) {
  50.             if(sum >= x) {
  51.                 return new Fraction(1,1);
  52.             }
  53.             else {
  54.                 return new Fraction(0,1);
  55.             }
  56.         }
  57.         if(mem[idx][sum] != null) {
  58.             return mem[idx][sum];
  59.         }
  60.  
  61.         mem[idx][sum] = new Fraction(0,1);
  62.         for(int h = 1; h <= 6; h++) {
  63.             mem[idx][sum].fsum(solve(idx+1,sum+h));
  64.         }
  65.         mem[idx][sum].fmul(new Fraction(1,6));
  66.         return mem[idx][sum];
  67.     }
  68.    
  69.     public static void main(String[] args) throws IOException {
  70.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  71.         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  72.        
  73.         while(true) {
  74.             StringTokenizer st = new StringTokenizer(br.readLine());
  75.             n = Integer.parseInt(st.nextToken());
  76.             x = Integer.parseInt(st.nextToken());
  77.             if(n == 0 && x == 0) {
  78.                 break;
  79.             }
  80.             mem = new Fraction[26][200];
  81.             Fraction ans = solve(0,0);
  82.             if(ans.denum.compareTo(BigInteger.ONE) == 0) {
  83.                 bw.write(ans.num + "\n");
  84.             }
  85.             else {
  86.                 bw.write(ans.num + "/" + ans.denum + "\n");
  87.             }
  88.         }
  89.         bw.flush();
  90.     }
  91.    
  92. }
  93.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement