Блог пользователя Arsenal911

Автор Arsenal911, 11 лет назад, По-русски

Мне вот захотелось реализовать шаблон, что бы можно было иметь один шаблон для задач с разным вводом и выводом.


import java.io.BufferedReader; import java.io.File; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.Scanner; import java.util.StringTokenizer; interface TypeIO { void solve() throws IOException; } class FileIO implements TypeIO { @Override public void solve() throws IOException { Scanner sc = new Scanner(new File("input.txt")); PrintWriter pw = new PrintWriter(new File("output.txt")); // Пишем свое решение используя файловый ввод вывод sc.close(); pw.close(); } } class ConsoleIOFast implements TypeIO { BufferedReader in; StringTokenizer tok; PrintWriter out; String readToken() throws IOException { while (tok == null || !tok.hasMoreTokens()) { tok = new StringTokenizer(in.readLine()); } return tok.nextToken(); } int readInt() throws IOException { return Integer.parseInt(readToken()); } String readString() throws IOException { return readToken(); } @Override public void solve() throws IOException { in = new BufferedReader(new InputStreamReader(System.in)); out = new PrintWriter(System.out); // Пишем свое решение используя быстрый ввод на Java out.close(); in.close(); } } class ConsoleIO implements TypeIO { @Override public void solve() throws IOException { Scanner sc = new Scanner(System.in); // Пишем свое решение используя Scanner sc.close(); } } class Solve { private TypeIO typeIO; public Solve(TypeIO typeIO) { this.typeIO = typeIO; } void getSolve() throws IOException { typeIO.solve(); } } public class Main { public static void main(String[] args) throws IOException { Solve solve = new Solve(new ConsoleIO()); // стандартный ввод вывод // Solve solve = new Solve(new ConsoleIOFast()); // быстрый ввод вывод // Solve solve = new Solve(new FileIO()); // файловый ввод вывод solve.getSolve(); } }

Полный текст и комментарии »

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

Автор Arsenal911, 12 лет назад, По-русски

Постановка задачи:

Массив из n =2k+2 элементов, 2 элемента не имеют пары, остальные парные. Найти эти 2 элемента, при условии, что алгоритм должен работать за O(n) времени и использовать O(1) дополнительной памяти.

Решение для поиска одного не повторяющего элемента:

Сначала рассмотрим задачу, когда один элемент различен. Вспомним свойство xor, применение к 2 одинаковым числа даст ноль. Следовательно если мы пропустим весь массив, то в результате у нас останется как раз искомый элемент.

int mas[] = {4,5,23,7,7,23,4,5,9};
int ans = mas[0];
for(int i = 1; i < mas.length; i++){
   ans ^= mas[i];
}
System.out.print(ans);

Решение для поиска 2 не повторяющихся элементов:

Для поиска двух элементов мы делаем сначала аналогично первому варианту, но теперь у нас в ответе пока находится xor этих двух чисел. Но если в бите установлена 1 значит в одном числе она есть, а во втором ее нет. Поэтому найдем также xor для все чисел которые имееют бит 1 в этом разряде. А второе число находится исходя из свойства xor.

int mas[] = {4,5,23,7,7,23,4,9};
int ans = mas[0];
for(int i = 1; i < mas.length; i++){
    ans ^= mas[i];
}
int tmp = 1;
Находим первый разряд в котором есть 1
while ((ans & tmp) == 0) {
    tmp *= 2;
}
int res = 0;
Находим xor для всех элементов у которых этот бит установлен в 1
for (int i = 0; i < mas.length; i++) {
     if ((mas[i] & tmp) > 0) {
         res ^= mas[i];
     }
}
System.out.println(res);
System.out.println(res ^ ans);

Полный текст и комментарии »

  • Проголосовать: нравится
  • +25
  • Проголосовать: не нравится

Автор Arsenal911, 12 лет назад, По-русски

Нужно будет сделать программу, сжимающую числа в двоичном коде, о которых, мы знаем, что они находятся в диапазоне от 0 до 255. Или от 1 до 256. Так же мы знаем, что последующее число будет равно или больше предыдущего. То есть мы можем каждое число выразить одним байтом, указав на его месторасположение. Сжимать можно по две, четыре, восемь, шестнадцать, тридцать две и шестьдесят четыре числа. Сжатие пакетное. То есть если сжимать по два числа, то и последующие числа сжимать по два числа. Мы все знаем, если бы числа были бы расположены в случайном порядке, сжатие без потерь было бы невозможно. Но у нас одно преимущество (последующее число будет равно или больше предыдущего). Можно ли использовать это преимущество что бы сжать числа свыше приведённых пакетов используя при этом приведенное ниже количество бит на число.

При сжатии 2 чисел использовать по 7 бит на число.

При сжатии 4 чисел использовать по 6 бит на число.

При сжатии 8 чисел использовать по 5 бит на число.

При сжатии 16 чисел использовать по 4 бит на число.

При сжатии 32 чисел использовать по 3 бит на число.

При сжатии 64 чисел использовать по 2 бит на число.

Кто найдёт алгоритм соответствующим этим условиям вознаграждение 30000 рублей.


Ссылка на источник

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится