Advertisement
Guest User

Untitled

a guest
Oct 30th, 2011
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.66 KB | None | 0 0
  1. import java.io.*;
  2. import java.math.*;
  3. import java.util.*;
  4. import java.awt.geom.*;
  5.  
  6. import static java.lang.Math.*;
  7.  
  8. public class Solution implements Runnable {
  9.  
  10.     public static void main(String[] args) throws Exception {
  11.         new Thread(null, new Solution(), "", 1 << 25).start();
  12.     }
  13.  
  14.     BufferedReader in;
  15.     PrintWriter out;
  16.     StringTokenizer st;
  17.  
  18.     final String fname = "";
  19.    
  20.     private String next() throws Exception {
  21.         if (st == null || !st.hasMoreElements())
  22.             st = new StringTokenizer(in.readLine());
  23.         return st.nextToken();
  24.     }
  25.  
  26.     private int nextInt() throws Exception {
  27.         return Integer.parseInt(next());
  28.     }
  29.  
  30.     private long nextLong() throws Exception {
  31.         return Long.parseLong(next());
  32.     }
  33.  
  34.     private double nextDouble() throws Exception {
  35.         return Double.parseDouble(next());
  36.     }
  37.    
  38.     public void run() {
  39.         try {
  40.             //in = new BufferedReader(new FileReader(fname+".in"));
  41.             //out = new PrintWriter(new FileWriter(fname+".out"));
  42.             in = new BufferedReader(new InputStreamReader(System.in));
  43.             out = new PrintWriter(new OutputStreamWriter(System.out));
  44.             solve();
  45.         } catch (Exception ex) {
  46.             throw new RuntimeException(ex);
  47.         } finally {
  48.             out.close();
  49.         }
  50.     }
  51.    
  52.     String s[]=new String [4000];
  53.    
  54.     int memo[]=new int[127];
  55.    
  56.     String ans="";
  57.    
  58.     void check(int nums[]) {
  59.         int cnt[]=new int[127];
  60.         int md=1;
  61.         String t = "";
  62.         for (int i=0;i<nums.length;i++) {
  63.             nums[i]=nums[i]*md;
  64.             md*=10;
  65.         }
  66.         for (int i=nums.length-1;i>=0;i--) {
  67.             if (nums[i]==0) continue;
  68.             t+=s[nums[i]];
  69.             for (int j=0;j<s[nums[i]].length();j++) {
  70.                 cnt[s[nums[i]].charAt(j)]++;
  71.                 if (cnt[s[nums[i]].charAt(j)]>memo[s[nums[i]].charAt(j)]) return;
  72.             }
  73.         }
  74.         if (t.length()>ans.length())
  75.             ans=t;
  76.     }
  77.    
  78.     public void solve() throws Exception {
  79.         s[1]="I";
  80.         s[2]="II";
  81.         s[3]="III";
  82.         s[4]="IV";
  83.         s[5]="V";
  84.         s[6]="VI";
  85.         s[7]="VII";
  86.         s[8]="VIII";
  87.         s[9]="IX";
  88.         s[10]="X";
  89.         s[20]="XX";
  90.         s[30]="XXX";
  91.         s[40]="XL";
  92.         s[50]="L";
  93.         s[60]="LX";
  94.         s[70]="LXX";
  95.         s[80]="LXXX";
  96.         s[90]="XC";
  97.         s[100]="C";
  98.         s[200]="CC";
  99.         s[300]="CCC";
  100.         s[400]="CD";
  101.         s[500]="D";
  102.         s[600]="DC";
  103.         s[700]="DCC";
  104.         s[800]="DCCC";
  105.         s[900]="CM";
  106.         s[1000]="M";
  107.         s[2000]="MM";
  108.         s[3000]="MMM";
  109.         String t = in.readLine();
  110.         for (int i=0;i<t.length();i++) {
  111.             if (t.charAt(i)>='a' && t.charAt(i)<='z') {
  112.                 memo[Character.toUpperCase(t.charAt(i))]++;
  113.             }
  114.             if (t.charAt(i)>='A' && t.charAt(i)<='Z')
  115.                 memo[t.charAt(i)]++;
  116.         }
  117.         for (int num=3999;num>=1;num--) {
  118.             int tmp=num;
  119.             int nums[]=new int [4];
  120.             int it=0;
  121.             while (tmp>0) {
  122.                 nums[it++]=tmp%10;
  123.                 tmp/=10;
  124.             }
  125.             check(nums);
  126.         }
  127.         out.println(ans);
  128.     }
  129. }
  130.  
  131.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement