Автор задачи: Кирилл Бороздин Источник задачи: Уральская региональная командная олимпиада по программированию 2013 Ограничения: Время: 0.5 секунды Память 64 Мб Условие Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за … Continue reading
Binary Heap (двоичная куча)
В данном отчёте я напишу о структуре данных под названием куча (Heap), а точнее — о её разновидности. Двоичная куча Двоичная куча — структура данных, двоичное дерево, для которого выполнены три условия: Значение в любой вершине не меньше чем значение в потомках Расстояние до корня отличается не более чем на один уровень Заполняется слева на … Continue reading
Частотный словарь
Определение понятия «частотный словарь» можно посмотреть в Википедии. Реализовывалось на своем АВЛ-дереве. Сначала надо распарсить строку на слова, которые удовлетворяют условию задачи 1. Потому, надо с помощью структуры данных как map реализовать дерево, поддерживающее ключ -> значение структуру. АВЛ-дерево в каком-то роде схоже с map, так что можно использовать его. Правда оно не имплемирует ни … Continue reading
Обратная польская запись
Что такое обратная польская запись можно прочитать в Википедии. Использовался свой стек, выложенный ранее тут. Поскольку не было необходимости реализовывать дополнительные функции, то то я обошелся для хранения переменных одним стеком и одной строкой, в отличии от реализации моей коллеги. Лексемы по сути те же самые, только нет ни слова про функции. Для вычисления строки была … Continue reading
Стек v.Java
Stack test = new Stack(4); System.out.println(test.isEmpty()); test.push(12); System.out.println(test.isEmpty()); System.out.println(test.peek()); test.push(13); test.push(14); test.push(15); test.push(16); test.push(17); test.push(‘(‘); System.out.println(test.size()); System.out.println(test.peek().equals(‘(‘)); test.pop(); System.out.println(test.peek()); test.pop(); System.out.println(test.peek()); test.pop(); System.out.println(test.peek()); test.pop(); System.out.println(test.peek()); test.pop(); System.out.println(test.peek()); System.out.println(test.isEmpty()); test.pop(); System.out.println(test.peek()); test.pop(); System.out.println(test.isEmpty()); true false 12 7 true 17 16 15 14 13 false 12 true Что такое стек прекрасно расскажет Википедия. Реализация динамического стека. … Continue reading
АВЛ-дерево
Описание АВЛ-дерева вы можете прочитать в Википедии. Здесь представлен код реализации рекурсивного АВЛ-дерева. Отличается от обычно бинарного дерева тем, что у узлов есть высота и показатель балансировки. Балансировка может меняться при добавлении или удалении, и восстанавливается с помощью малого левого(правого), или большого левого(правого) поворотов. Как это выглядит можно увидеть в той же Википедии. Показатель балансировки … Continue reading
soundEx algorithm
Немного о фонетических алгоритмах Фонетические алгоритмы — алгоритмы, которые сопоставляют двум словам со схожим произношением одинаковые коды, что позволяет осуществлять сравнение и индексацию множества таких слов на основе их фонетического сходства. Существует достаточно много фонетических алгоритмов, например: NYSIIS, Metaphone, Double Metaphone, Caverphone и т.д. В данном отчёте я напишу об одном из фонетических алгоритмов, который … Continue reading
Обратная польская запись
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
// Символы во входном потоке следует вводить через пробел. import java.util.*; import java.lang.*; import java.io.*; class Ideone{ public static void main (String[] args) throws java.lang.Exception{ try{ BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String line; String a1=""; int st_len=0; Stack<String> st = new Stack(); while( (line = reader.readLine()) != null){ String[] a = line.split(" "); for(int i = 0 ; i < a.length ; i++){ if(!a[i].equals("+") && !a[i].equals("-") && !a[i].equals("*") && !a[i].equals("/") && !a[i].equals("(") && !a[i].equals(")")){ a1+=a[i]; } else{ if((a[i].equals("+") || a[i].equals("-")) && st_len>0){ for(int j=0; j<2;j++){ if(st_len>0){ if(!st.peek().equals("(")){ a1+=st.pop(); st_len--; } } } } if((a[i].equals("*") || a[i].equals("/")) && st_len>0){ for(int j=0; j<1;j++){ if(!st.peek().equals("(") && !st.peek().equals("+") && !st.peek().equals("-")){ a1+=st.pop(); st_len--; } } } if(a[i].equals(")") && st_len>0){ for(int j=0; j<=st_len+2;j++){ if(!st.peek().equals("(")){ a1+=st.pop(); st_len--; } } if(st_len!=0){ a1+=st.pop(); st_len--; } } st.push(a[i]); st_len++; } } for(int i = 0 ; i < st_len ; i++){ a1+=st.pop(); } for(int i = 0 ; i < a1.length() ; i++){ if(a1.charAt(i)!='(' && a1.charAt(i)!=')') System.out.print(a1.charAt(i)+" "); } } }catch(IOException ex){ System.err.println("Eror"); } } } |
Алгоритм: Пока строка содержит символы для чтения, читаем очередной символ. Далее рассматриваются варианты: 1) Если символ не является символом функции или скобкой, добавляем его к выходной строке. 2) Если встретили символ функции, помещаем его в стек. Если встретили символ функции и при этом стек не пустой, выталкиваем в выходную строку все символы функции, … Continue reading
Контрольная работа. Timus 2002
2002. Тестовое задание Условие Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread … Continue reading
Timus 2002
Ссылка на засчитанное решение. Идея решения состоит в том, чтобы использовать 2 ассоциативных массива, один из которых хранит в качестве ключа и значения логин и пароль пользователь, а второй — логин и состояние (онлайн/оффлайн). На С++ можно обойтись и одним ассоциативным массивом, если воспользоваться такой структурой: map<string, pair<string, bool> > m. Код программы (http://ideone.com/3Uqhuh):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) { Map<String, String> m = new HashMap<String, String>(); Map<String, Boolean> u = new HashMap<String, Boolean>(); Scanner in = new Scanner(System.in); int n = in.nextInt(); String s; for(int i = 0; i < n; i++) { s = in.next(); if (s.equals("register")) { String a, b; a = in.next(); b = in.next(); if (m.containsKey(a)) { System.out.println("fail: user already exists"); } else { m.put(a, b); u.put(a, false); System.out.println("success: new user added"); } } else if (s.equals("login")) { String a, b; a = in.next(); b = in.next(); if (!m.containsKey(a)) { System.out.println("fail: no such user"); } else if (!b.equals(m.get(a))) { System.out.println("fail: incorrect password"); } else { if (u.get(a) == false) { u.put(a, true); System.out.println("success: user logged in"); } else { System.out.println("fail: already logged in"); } } } else { String a; a = in.next(); if (!m.containsKey(a)) { System.out.println("fail: no such user"); } else { if (u.get(a) == true) { u.put(a, false); System.out.println("success: user logged out"); } else { System.out.println("fail: already logged out"); } } } } } } |