fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.FileReader;
  4. import java.io.PrintWriter;
  5. import java.util.ArrayList;
  6. import java.util.List;
  7.  
  8. public class Osmos {
  9.  
  10.     public static String caseString = "Case #?: ";
  11.  
  12.     public static String[] read(String file) throws Exception {
  13.         BufferedReader br = new BufferedReader(new FileReader(file));
  14.         String line = null;
  15.         List<String> arrayList = new ArrayList<String>();
  16.         while((line = br.readLine()) != null)  {
  17.             if(!line.trim().equalsIgnoreCase("")) {
  18.                 arrayList.add(line);
  19.             }
  20.         }
  21.         return arrayList.toArray(new String[0]);
  22.     }
  23.  
  24.     public static void write(String file, String[] content) throws Exception {
  25.         BufferedWriter bw = new BufferedWriter(new PrintWriter(file));
  26.         for (int i = 0; i < content.length; i++) {
  27.             String caseS = caseString.replace("?", (i+1)+"");
  28.             bw.append(caseS+content[i]+"\n");
  29.         }
  30.         bw.flush();
  31.         bw.close();
  32.     }
  33.  
  34.     public static void main(String[] args) throws Exception {
  35.         String inputfile = "/Users/sumitkumar/Desktop/codejam/1/A-large-practice.in";
  36.         String outputfile = "/Users/sumitkumar/Desktop/codejam/1/A-large-practice.out";
  37.         String[] input = read(inputfile);
  38.         int testCases = Integer.parseInt(input[0]);
  39.         String[] output = new String[testCases];
  40.         int counter = 1;
  41.         System.out.println("testCases ::"+testCases);
  42.         for (int i = 0; i < testCases; i++) {
  43.             System.out.println(i);
  44.             String [] line1 = input[counter++].split(" ");
  45.             int yourBot = Integer.parseInt(line1[0]);
  46.             int botsCount = Integer.parseInt(line1[1]);
  47.             String [] botsString = input[counter++].split(" ");
  48.             int [] bots = new int[botsCount];
  49.             for (int j = 0; j < botsCount; j++) {
  50.                 bots[j] = Integer.parseInt(botsString[j]);
  51.             }
  52.             output[i] = solve(yourBot, bots, botsCount);
  53.         } 
  54.         write(outputfile, output);
  55.     }
  56.  
  57.     private static String solve(int yourBot, int[] bots, int botsCount) {
  58.         sort(bots, botsCount);
  59.         int myBot = yourBot;
  60.         int change = 0;
  61.         int i = 0;
  62.         for (i = 0; i < botsCount; i++) {
  63.             if(myBot > bots[i]) {
  64.                 myBot += bots[i];
  65.                 continue;
  66.             }
  67.             if((2*myBot-1) > bots[i]) {
  68.                 myBot = 2*myBot-1 + bots[i];
  69.                 change++;
  70.                 continue;
  71.             }
  72.             break; 
  73.         }
  74.         int changesWithoutAddition = changesWithoutAddition(myBot, bots, i, botsCount);
  75.         int changesWithAddition = -1;
  76.         if(i < botsCount)
  77.             changesWithAddition = changesWithAddition(myBot, bots, i, botsCount);
  78.         int min = changesWithoutAddition;
  79.         if(changesWithAddition >= 0) {
  80.             min = (changesWithoutAddition < changesWithAddition) ? changesWithoutAddition : changesWithAddition;
  81.         }
  82.         change+=min;
  83.         return change+"";
  84.     }
  85.  
  86.     private static int changesWithoutAddition(int myBot, int bots[], int index, int botsCount) {
  87.         System.out.println("changesWithoutAddition"+index);
  88.         return botsCount-index;
  89.     }
  90.     private static int changesWithAddition(int myBot, int bots[], int index, int botsCount) {
  91.         System.out.println("changesWithAddition"+index);
  92.         int tempBot = myBot;
  93.         int counter = 0;
  94.         while(bots[index] >= tempBot) {
  95.             tempBot = 2*tempBot - 1;
  96.             counter++;
  97.             if(counter >= (botsCount-index)) {
  98.                 return -1;
  99.             }
  100.         }
  101.         for (int i = index; i < botsCount; i++) {
  102.             if(tempBot > bots[i]) {
  103.                 tempBot += bots[i];
  104.                 continue;
  105.             }
  106.             if((2*tempBot-1) > bots[i]) {
  107.                 tempBot = 2*tempBot-1 + bots[i];
  108.                 counter++;
  109.                 continue;
  110.             }
  111.             int changesWithoutAddition = changesWithoutAddition(tempBot, bots, i, botsCount);
  112.             int changesWithAddition = -1;
  113.             if(i < botsCount)
  114.                 changesWithAddition = changesWithAddition(tempBot, bots, i, botsCount);
  115.             int min = changesWithoutAddition;
  116.             if(changesWithAddition >= 0) {
  117.                 min = (changesWithoutAddition < changesWithAddition) ? changesWithoutAddition : changesWithAddition;
  118.             }
  119.             counter+=min; 
  120.             break;
  121.         }
  122.         return counter;
  123.     }
  124.  
  125.     public static void sort(int[] values, int size) {
  126.         if (values ==null || size==0){
  127.           return ;
  128.         }
  129.         quicksort(0, size - 1, values);
  130.       }
  131.  
  132.       private static void quicksort(int low, int high,int[] numbers) {
  133.         int i = low, j = high;
  134.         int pivot = numbers[low + (high-low)/2];
  135.         while (i <= j) {
  136.           while (numbers[i] < pivot) {
  137.             i++;
  138.           }
  139.           while (numbers[j] > pivot) {
  140.             j--;
  141.           }
  142.           if (i <= j) {
  143.             exchange(i, j, numbers);
  144.             i++;
  145.             j--;
  146.           }
  147.         }
  148.         if (low < j)
  149.           quicksort(low, j, numbers);
  150.         if (i < high)
  151.           quicksort(i, high,numbers);
  152.       }
  153.  
  154.       private static void exchange(int i, int j, int[] numbers) {
  155.         int temp = numbers[i];
  156.         numbers[i] = numbers[j];
  157.         numbers[j] = temp;
  158.       }
  159.  
  160. }
  161.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:8: error: class Osmos is public, should be declared in a file named Osmos.java
public class Osmos {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/gPoM1g
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!