package test;
import java.io.BufferedReader;
import java.io.IOException;
import java.nio.charset.Charset;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
/**
* Created by nemo_odissey on 10.07.2017 12:45 for
* <a href="https://toster.ru/q/440261?utm_source=email_notifications&utm_medium=email&utm_content=mention&utm_campaign=notifications#comment_1428657" >Какую сортировку применять?</a>.
*/
public class JapanEditor
{
/**
* Class to store vocabulary item and make it comparable only lexicographically
*/
public static class WordItem implements Comparable
{
public String word;
public int count;
public WordItem( String word, int count )
{
this.count = count;
this.word = word.split( "/",0 )[0];
}
@Override
public int compareTo( Object obj )
{
return this.word.compareTo( ((WordItem)obj).word );
}
public int compareByFrequency( Object obj )
{
return this.count - ((WordItem)obj).count;
}
}
/**
* Сортирует и извлекает из массива source начиная с индекса pos1 и до индекса pos2 (не включая его самого) максимальные элементы,
* по размеру массива result или меньше.
* @param maxLen максимальный размер массива с максимальными элементами
* @param dstList {@link ArrayList} для размещения результатов работы. Если {@code null}, то будет создан внутри. Очищается перед работой и заполняется результатами
* @param source исходный массив
* @param pos1 начальный индекс массива source
* @param pos2 конечный инидекс в массиве source (не включается в сортировку)
* @return {@link ArrayList} (не может быть {@code null})
*/
public static final ArrayList<WordItem> partialSort( int maxLen, ArrayList<WordItem> dstList, WordItem[] source, int pos1, int pos2 )
{
if ( dstList == null )
dstList = new ArrayList<WordItem>( 10 );
else
dstList.clear();
dstList.add( source[ pos1++ ] );
// Проверим все слова с префиксом на предмет их частоты и отберём до 10 самых часто встречающихся
for( int i = pos1; i< pos2; i++ )
{
WordItem item = source[ i ];
int placeFound = 0;
int listPos;
int cmp;
// Найдём, надо ли вставлять и куда вставить
for ( listPos = dstList.size() - 1; listPos >= 0; listPos-- )
{
if ( ( cmp = item.compareByFrequency( dstList.get( listPos ) ) ) < 0 ) // нашли элемент из списка проверенных, который больше проверяемого
break; // дальше не идём, может сможем добавить в конец списка, если там ещё есть место
if (cmp == 0) // по частоте он равен
if ( item.compareTo( dstList.get( listPos ) ) > 0 ) // но элемент из списка проверенных оказался меньше лексически
break;
}
// пытаемся вставить в массив либо на место элемента, который меньше, либо в конец списка, если там ещё есть место
if ( listPos == (dstList.size()-1) ) // младший элемент списка больше проверяемого элемента, попробуем просто сдобавить в конец
{
if ( dstList.size() < maxLen ) // массив результата ещё не полон, добавляем в конец
dstList.add( item );
continue; // переходим к следующему элементу
}
// нашли, куда вставить
if ( dstList.size() == maxLen )
{
// массив результата уже полностью заполнен, сразу удаляем нижний,
// т.к. он выйдет за разрешённые пределы при вставке нового элемента
dstList.remove( maxLen - 1 );
}
// вставляем ниже большего элемента, или, если listPos == -1, вместо самого большого
dstList.add( listPos + 1, item );
}
return dstList;
}
/**
* Обработки ошибок НЕТ
* @param args путь_к_файлу_с_данными, где хранится задание
* @throws IOException
*/
public static void main( String[] args ) throws IOException
{
long start = System.nanoTime();
BufferedReader brd = java.nio.file.Files.newBufferedReader( Paths.get( args[ 0 ] ), Charset.forName( "utf-8" ) );
// читаем число слов
int wordCnt = Integer.parseInt( brd.readLine() );
WordItem[] wordArr = new WordItem[wordCnt];
// Читаем все слова и их частоты
for(int i = 0; i < wordCnt; i++)
{
String word = brd.readLine();
String[] elems = word.split( " " );
wordArr[ i ] = new WordItem( elems[0], Integer.parseInt( elems[1] ) );
// wordArr[ i ] = new WordItem( word.toLowerCase(), freq );
}
// сортируем массив словаря
Arrays.sort( wordArr );
// считываем и обрабатываем каждый префикс один за другим
int prefCnt = Integer.parseInt( brd.readLine() );
System.out.printf( "Счётчик слов %d, счётчик префиксов %d\n", wordCnt, prefCnt );
System.out.printf( "Словарь считан и отсортирован за %,f млс.\n\n", 1e-9 * (System.nanoTime() - start) );
int summaryWordCount = 0;
WordItem prefixItem = new WordItem( "", 1 );
ArrayList<WordItem> list = new ArrayList<>( 11 );
for(int i = 0; i < prefCnt; i++)
{
String prefix = brd.readLine().trim();
prefixItem.word = prefix;
int pos1 = Arrays.binarySearch( wordArr, prefixItem ); // if positive, point to a word in vocabulary started from prefix or equal to it
if ( pos1 < 0) // no precise prefix value found in vocabulary
pos1 = -(pos1 + 1); // pos1 to the first element starting from prefix
if ( pos1 >= wordCnt) // префикс отсутствует в словаре
continue;
System.out.printf( " ~ %s\n", prefix );
if ( wordArr[pos1].word.startsWith( prefix ) ) // Если префикс есть, ищем последнюю его позицию в словаре
{
char nextLastChar = prefix.charAt( prefix.length() - 1 );
prefixItem.word = prefix.substring( 0, prefix.length() -1 ) + (++nextLastChar); // готовим следующую не строку
int pos2 = Arrays.binarySearch( wordArr, pos1, wordCnt, prefixItem ); // ищем последнее вхождение префикса в словаре
if ( pos2 < 0)
pos2 = -pos2 -1;
if ( pos2 > wordCnt)
pos2 = wordCnt;
summaryWordCount += pos2 - pos1;
list = partialSort( 10, list, wordArr, pos1, pos2 );
for( WordItem item: list )
System.out.printf( "%6d %s\n", item.count, item.word );
}
}
brd.close();
System.out.printf( ">>> Длительность обработки %,f сек., средний размер выборки по каждому префиксу %d\n", 1e-9 * (System.nanoTime() - start), summaryWordCount / prefCnt);
}
}package test;
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Date;
/**
* Created by nemo_odissey on 10.07.2017 12:45 for <a href="https://toster.ru/q/440261?utm_source=email_notifications&utm_medium=email&utm_content=mention&utm_campaign=notifications#comment_1428657" >Какую сортировку применять?</a>.
*/
public class JapanEditor
{
/**
* Compare by frequence and if equal, compare lexicographically
*/
public static class ComparePrefixWithFreq implements Comparator
{
@Override
public int compare( Object obj1, Object obj2 )
{
int cmp = ((WordItem) obj2).count - ((WordItem) obj1).count; // compare in reverse frequencies
if ( cmp != 0 ) // texts are not equals
return cmp;
return((WordItem)obj1).word.compareTo( ((WordItem)obj2).word ); // if freqs are equal, compare lexicographically
}
}
/**
* Class to store vocabulary item and make it comparable only lexicographically
*/
public static class WordItem implements Comparable
{
public String word;
public int count;
public WordItem( String word, int count )
{
this.count = count;
this.word = word;
}
@Override
public int compareTo( Object obj )
{
return this.word.compareTo( ((WordItem)obj).word );
}
}
/**
* Обработки ошибок НЕТ
* @param args путь_к_файлу_с_данными, где хранится задание
* @throws IOException
*/
public static void main( String[] args ) throws IOException
{
long start = new Date().getTime();
BufferedReader brd = new BufferedReader( new FileReader(args[0]), 32 * 1024 );
// читаем число слов
int wordCnt = Integer.parseInt( brd.readLine() );
WordItem[] wordArr = new WordItem[wordCnt];
// Читаем все слова и их частоты
for(int i = 0; i < wordCnt; i++)
{
String[] elems = brd.readLine().split( " " );
wordArr[ i ] = new WordItem( elems[0], Integer.parseInt( elems[1] ) );
}
// сортируем массив словаря
Arrays.sort( wordArr );
// сортировщик по частоте
ComparePrefixWithFreq compareWithFrequence = new ComparePrefixWithFreq();
// считываем и обрабатываем каждый префикс один за другим
int prefCnt = Integer.parseInt( brd.readLine() );
System.out.printf( "Счётчик слов %d, счётчик префиксов %d\n", wordCnt, prefCnt );
System.out.printf( "Словарь считан и отсортирован за %,d млс.\n\n", new Date().getTime() - start );
int summaryWordCount = 0;
WordItem prefixItem = new WordItem( null, 1 );
for(int i = 0; i < prefCnt; i++)
{
String prefix = brd.readLine().trim();
prefixItem.word = prefix;
int pos = Arrays.binarySearch(wordArr, prefixItem ); // if positive, point to a word in vocabulary started from prefix or equal to it
if ( pos < 0) // no precise prefix value found in vocabulary
pos = -(pos + 1); // pos to the first element starting from prefix
if ( pos >= wordCnt) // префикс отсутствует в словаре
continue;
if ( wordArr[pos].word.startsWith( prefix )) // Если префикс есть, ищем его конец в словаре
{
char nextLastChar = prefix.charAt( prefix.length() - 1 );
prefixItem.word = prefix.substring( 0, prefix.length() -1 ) + (++nextLastChar); // готовим следующую не строку
int pos1 = Arrays.binarySearch( wordArr, pos, wordCnt, prefixItem ); // ищем последнее вхождение префикса в словаре
if ( pos1 < 0)
pos1 = -pos1;
if ( pos1 > wordCnt)
pos1 = wordCnt;
summaryWordCount += pos1 - pos;
// pos -> first word with prefix, pos1 -> first word without prefix
WordItem[] wordsWithPrefix = Arrays.copyOfRange( wordArr, pos, pos1 );
Arrays.sort( wordsWithPrefix, compareWithFrequence );
int wordWithPrefCnt = Math.min( wordsWithPrefix.length, 10 );
for( int j = 0; j < wordWithPrefCnt; j++ )
//System.out.printf("%s %d\n", item.word, item.count); // debug output
System.out.println( wordsWithPrefix[j].word );
System.out.println(""); // add empty line according to the task requirements
}
}
brd.close();
System.out.printf( ">>> Длительность обработки %,d млс., средний размер выборки по каждому префиксу %d\n", new Date().getTime() - start, summaryWordCount / prefCnt);
}
}package ru.ts.common.records;
/**
* Utility methods for packing/unpacking primitive values in/out of bytes and
* integer arrays using <b>big-endian</b> byte ordering.
*/
public class Bits
{
/*
* Methods for unpacking primitive values from byte arrays starting at given
* offsets.
*/
public static boolean getBoolean(byte[] b, int off)
{
return b[ off ] != 0;
}
static int[] BYTE_MASK;
static int[] BYTE_SHIFT;
static
{
BYTE_MASK = new int[] { 0xFF, 0xFF00, 0xFF0000, 0xFF000000 };
BYTE_SHIFT = new int[] { 0, 8, 16, 24 };
}
static byte getByte(int[] b, int off, int ind)
{
return (byte)((b[ off ] & BYTE_MASK[ ind ]) >> BYTE_SHIFT[ ind ]);
}
static boolean getBoolean(int[] b, int off, int ind)
{
return ((b[ off ] & BYTE_MASK[ ind ]) >> BYTE_SHIFT[ ind ]) != 0;
}
public static char getChar(byte[] b, int off)
{
return (char) (((b[ off + 1 ] & 0xFF) << 0) + ((b[ off + 0 ] & 0xFF) << 8));
}
static int[] CHAR_MASK;
static int[] CHAR_SHIFT;
static
{
CHAR_MASK = new int[] { 0xFFFF, 0xFFFF0000 };
CHAR_SHIFT = new int[] { 0, 16 };
}
/**
*
* @param b bit array containing of char looked for
* @param off offset to the array
* @param ind index of char packed into int. May be 0 or 1 ONLY!!!
* @return character stored in the array
*/
public static char getChar(int[] b, int off, int ind)
{
return (char) ( (b[off] & CHAR_MASK[ind]) >> CHAR_SHIFT[ind]);
}
static short getShort(byte[] b, int off)
{
return (short) (((b[ off + 1 ] & 0xFF) << 0) + ((b[ off + 0 ] & 0xFF) << 8));
}
/**
* the same as char
* @param b
* @param off
* @param ind index of short packed into int may be 0 or 1 ONLY
* @return
*/
static short getShort(int[] b, int off, int ind)
{
return (short) ( (b[off] & CHAR_MASK[ind]) >> CHAR_SHIFT[ind] );
}
public static int getInt(byte[] b, int off)
{
return ((b[ off + 3 ] & 0xFF) << 0) + ((b[ off + 2 ] & 0xFF) << 8)
+ ((b[ off + 1 ] & 0xFF) << 16) + ((b[ off + 0 ] & 0xFF) << 24);
}
static int getInt(int[] b, int off)
{
return b[ off ];
}
static float getFloat(byte[] b, int off)
{
int i = ((b[ off + 3 ] & 0xFF) << 0) + ((b[ off + 2 ] & 0xFF) << 8)
+ ((b[ off + 1 ] & 0xFF) << 16) + ((b[ off + 0 ] & 0xFF) << 24);
return Float.intBitsToFloat(i);
}
static float getFloat(int[] b, int off)
{
return Float.intBitsToFloat( b[off] );
}
static long getLong(byte[] b, int off)
{
return ((b[ off + 7 ] & 0xFFL) << 0) + ((b[ off + 6 ] & 0xFFL) << 8)
+ ((b[ off + 5 ] & 0xFFL) << 16)
+ ((b[ off + 4 ] & 0xFFL) << 24)
+ ((b[ off + 3 ] & 0xFFL) << 32)
+ ((b[ off + 2 ] & 0xFFL) << 40)
+ ((b[ off + 1 ] & 0xFFL) << 48)
+ ((b[ off + 0 ] & 0xFFL) << 56);
}
public static long getLong(int[] b, int off)
{
return ((long)b[ off ] & 0xFFFFFFFFL) + ( ((long)(b[ off + 1 ])) << 32L);
}
public static double getDouble(byte[] b, int off)
{
long j = ((b[ off + 7 ] & 0xFFL) << 0) + ((b[ off + 6 ] & 0xFFL) << 8)
+ ((b[ off + 5 ] & 0xFFL) << 16)
+ ((b[ off + 4 ] & 0xFFL) << 24)
+ ((b[ off + 3 ] & 0xFFL) << 32)
+ ((b[ off + 2 ] & 0xFFL) << 40)
+ ((b[ off + 1 ] & 0xFFL) << 48)
+ ((b[ off + 0 ] & 0xFFL) << 56);
return Double.longBitsToDouble(j);
}
public static double getDouble(int[] b, int off)
{
long j = ((long)b[ off ] & 0xFFFFFFFFL) + ( ((long)(b[ off + 1 ])) << 32L);
return Double.longBitsToDouble(j);
}
/*
* Methods for packing primitive values into byte arrays starting at given
* offsets.
*/
static void putBoolean(byte[] b, int off, boolean val)
{
b[ off ] = (byte) (val ? 1 : 0);
}
static void putBoolean(int[] b, int off, int ind, boolean val)
{
b[ off ] &= ~(BYTE_MASK[ind]);
b[ off ] |= (byte) (val ? 1 : 0) << BYTE_SHIFT[ind];
}
static void putByte(int[] b, int off, int ind, byte val)
{
b[ off ] &= ~(BYTE_MASK[ind]);
b[ off ] |= val << BYTE_SHIFT[ind];
}
static void putChar(byte[] b, int off, char val)
{
b[ off + 1 ] = (byte) (val >>> 0);
b[ off + 0 ] = (byte) (val >>> 8);
}
static void putChar(int[] b, int off, int ind, char val)
{
b[off] &= ~CHAR_MASK[ind];
b[off] |= ((short)val) << CHAR_SHIFT[ind];
}
static void putShort(byte[] b, int off, short val)
{
b[ off + 1 ] = (byte) (val >>> 0);
b[ off + 0 ] = (byte) (val >>> 8);
}
static void putShort(int[] b, int off, int ind, short val)
{
b[off] &= ~CHAR_MASK[ind];
b[off] |= val << CHAR_SHIFT[ind];
}
public static void putInt(byte[] b, int off, int val)
{
b[ off + 3 ] = (byte) (val >>> 0);
b[ off + 2 ] = (byte) (val >>> 8);
b[ off + 1 ] = (byte) (val >>> 16);
b[ off + 0 ] = (byte) (val >>> 24);
}
static void putInt(int[] b, int off, int val)
{
b[ off ] = val;
}
static void putFloat(byte[] b, int off, float val)
{
int i = Float.floatToIntBits(val);
b[ off + 3 ] = (byte) (i >>> 0);
b[ off + 2 ] = (byte) (i >>> 8);
b[ off + 1 ] = (byte) (i >>> 16);
b[ off + 0 ] = (byte) (i >>> 24);
}
static void putFloat(int[] b, int off, float val)
{
int i = Float.floatToIntBits(val);
b[ off ] = (i);
}
public static void putLong(byte[] b, int off, long val)
{
b[ off + 7 ] = (byte) (val >>> 0);
b[ off + 6 ] = (byte) (val >>> 8);
b[ off + 5 ] = (byte) (val >>> 16);
b[ off + 4 ] = (byte) (val >>> 24);
b[ off + 3 ] = (byte) (val >>> 32);
b[ off + 2 ] = (byte) (val >>> 40);
b[ off + 1 ] = (byte) (val >>> 48);
b[ off + 0 ] = (byte) (val >>> 56);
}
public static void putLong(int[] b, int off, long val)
{
b[ off ] = (int) (val & 0x00000000FFFFFFFFL);
b[ off + 1 ] = (int) ( val >>> 32);
}
public static void putDouble(byte[] b, int off, double val)
{
long j = Double.doubleToLongBits(val);
b[ off + 7 ] = (byte) (j >>> 0);
b[ off + 6 ] = (byte) (j >>> 8);
b[ off + 5 ] = (byte) (j >>> 16);
b[ off + 4 ] = (byte) (j >>> 24);
b[ off + 3 ] = (byte) (j >>> 32);
b[ off + 2 ] = (byte) (j >>> 40);
b[ off + 1 ] = (byte) (j >>> 48);
b[ off + 0 ] = (byte) (j >>> 56);
}
public static void putDouble(int[] b, int off, double val)
{
long j = Double.doubleToLongBits(val);
b[ off ] = (int) (j & 0xFFFFFFFFL);
b[ off + 1 ] = (int) (j >>> 32L);
}
}
Даже если требования стандартов к карте не предъявляются и карта является временной или рабочей, не для распространения, всё равно масштаб стараются сделать таким, чтобы хотя бы несколько последних цифр в нём были нулями. Скажем, 1:66 000 и т.д.
На компьютерных "картах" лучше просто рисовать отрезок (внизу справа обычно) на экране и надписывать над ним число км на местности, помещающиеся в этом отрезке.