Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 18th, 2012  |  syntax: Java  |  size: 4.23 KB  |  hits: 42  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.io.*;
  2. import java.util.*;
  3. import java.math.*;
  4. import java.awt.geom.*;
  5.  
  6. import static java.lang.Math.*;
  7.  
  8. public class Solution implements Runnable {
  9.        
  10.         static final long INF = Integer.MAX_VALUE / 2;
  11.        
  12.         public void solve () throws Exception {
  13.                 int n = nextInt();
  14.                 String a = in.readLine();
  15.                 String b = in.readLine();
  16.                
  17.                 if (a.compareTo(b) >= 0) {
  18.                         out.println(-1);
  19.                         return;
  20.                 }
  21.                
  22.                 int m = max (a.length(), b.length());
  23.                 long d [][] = new long [m + 10001][4];
  24.                
  25.                 d[0][0] = 1L;
  26.                
  27.                 for (int i = 0; i < m + 10000; i++) {
  28.                         for (int state = 0; state < 4; state++) {
  29.                                 if (d[i][state] > 0) {
  30.                                         if (state == 0) {
  31.                                                 if (i < a.length() && i < b.length()) {
  32.                                                         int diff = b.charAt(i) - a.charAt(i);
  33.                                                         if (diff == 0) {
  34.                                                                 d [i + 1][state] += d[i][state];
  35.                                                                 if (d[i + 1][state] > INF) {
  36.                                                                         d[i + 1][state] = INF;
  37.                                                                 }
  38.                                                         } else if (diff >= 1) {
  39.                                                                 d[i + 1][1] += d[i][state];
  40.                                                                 if (d[i + 1][1] > INF) {
  41.                                                                         d[i + 1][1] = INF;
  42.                                                                 }
  43.                                                                 d[i + 1][2] += d[i][state];
  44.                                                                 if (d[i + 1][2] > INF) {
  45.                                                                         d[i + 1][2] = INF;
  46.                                                                 }
  47.                                                                 d[i + 1][3] += (long)(diff - 1) * d[i][state];
  48.                                                                 if (d[i + 1][3] > INF) {
  49.                                                                         d[i + 1][3] = INF;
  50.                                                                 }
  51.                                                         }
  52.                                                 } else if (i < a.length() && i >= b.length()) {
  53.                                                        
  54.                                                 } else if (i >= a.length() && i < b.length()) {
  55.                                                         int diff = b.charAt(i) - 'a';
  56.                                                         d[i + 1][2] += d[i][state];
  57.                                                         if (d[i + 1][2] > INF) {
  58.                                                                 d[i + 1][2] = INF;
  59.                                                         }
  60.                                                         d[i + 1][3] += (long) diff * d[i][state];
  61.                                                         if (d[i + 1][3] > INF) {
  62.                                                                 d[i + 1][3] = INF;
  63.                                                         }
  64.                                                 } else {
  65.                                                         d[i + 1][3] += d[i][state] * 26L;
  66.                                                         if (d[i + 1][3] > INF) {
  67.                                                                 d[i + 1][3] = INF;
  68.                                                         }
  69.                                                 }
  70.                                         } else if (state == 1) {
  71.                                                 if (i < a.length()) {
  72.                                                         d[i + 1][state] += d[i][state];
  73.                                                         if (d[i + 1][state] > INF) {
  74.                                                                 d[i + 1][state] = INF;
  75.                                                         }
  76.                                                         int diff = 'z' - a.charAt(i);
  77.                                                         d[i + 1][3] += (long) diff * (d[i][state]);
  78.                                                         if (d[i + 1][3] > INF) {
  79.                                                                 d[i + 1][3] = INF;
  80.                                                         }
  81.                                                 } else {
  82.                                                         d[i + 1][3] += d[i][state] * 26L;
  83.                                                         if (d[i + 1][3] > INF) {
  84.                                                                 d[i + 1][3] = INF;
  85.                                                         }
  86.                                                 }
  87.                                         } else if (state == 3) {
  88.                                                 d[i + 1][state] += d[i][state] * 26L;
  89.                                                 if (d[i + 1][state] > INF) {
  90.                                                         d[i + 1][state] = INF;
  91.                                                 }
  92.                                         } else if (state == 2) {
  93.                                                 if (i < b.length()) {
  94.                                                         d[i + 1][state] += d[i][state];
  95.                                                         if (d[i + 1][state] > INF) {
  96.                                                                 d[i + 1][state] = INF;
  97.                                                         }
  98.                                                         int diff = b.charAt(i) - 'a';
  99.                                                         d[i + 1][3] += (long) diff * d[i][state];
  100.                                                         if (d[i + 1][3] > INF) {
  101.                                                                 d[i + 1][3] = INF;
  102.                                                         }
  103.                                                 } else {
  104.                                                         //
  105.                                                 }
  106.                                         }
  107.                                 }
  108.                         }
  109.                 }
  110.                
  111.                 long ans = 0;
  112.                 for (int i = 1; i <= m + 10000; i++) {
  113.                         if (n > 0) {
  114.                                 if (d[i][3] > n) {
  115.                                         ans += (long) n * i;
  116.                                         n = 0;
  117.                                 } else {
  118.                                         ans += (long) d[i][3] * i;
  119.                                         n -= d[i][3];
  120.                                 }
  121.                                 if (i < b.length()) {
  122.                                         if (d[i][2] > n) {
  123.                                                 ans += (long) n * i;
  124.                                                 n = 0;
  125.                                         } else {
  126.                                                 ans += (long) d[i][2] * i;
  127.                                                 n -= d[i][2];
  128.                                         }
  129.                                 }
  130.                         }
  131.                 }
  132.                 if (n > 0) {
  133.                         out.println(-1);
  134.                 } else {
  135.                         out.println(ans);
  136.                 }
  137.         }
  138.        
  139.         static final String fname = "dictionary";
  140.         static long stime = 0;
  141.        
  142.         BufferedReader in;
  143.         PrintWriter out;
  144.         StringTokenizer st;
  145.        
  146.         private String nextToken () throws Exception {
  147.                 while (st == null || !st.hasMoreTokens()) {
  148.                         st = new StringTokenizer(in.readLine());
  149.                 }
  150.                 return st.nextToken();
  151.         }
  152.        
  153.         private int nextInt () throws Exception {
  154.                 return Integer.parseInt(nextToken());
  155.         }
  156.        
  157.         private long nextLong () throws Exception {
  158.                 return Long.parseLong(nextToken());
  159.         }
  160.        
  161.         private double nextDouble () throws Exception {
  162.                 return Double.parseDouble(nextToken());
  163.         }
  164.        
  165.         @Override
  166.         public void run() {
  167.                 try {
  168.                         in = new BufferedReader(new FileReader(fname+".in"));
  169.                         out = new PrintWriter(new FileWriter(fname+".out"));
  170.                         solve ();
  171.                 } catch (Exception e) {
  172.                         throw new RuntimeException(e);
  173.                 } finally {
  174.                         out.close();
  175.                 }
  176.         }
  177.        
  178.         public static void main(String[] args) {
  179.                 new Thread(null, new Solution(), "", 1<<25).start();
  180.         }
  181.  
  182. }
create a new version of this paste RAW Paste Data