Различия между версиями 3 и 5 (по 2 версиям)
Версия 3 от 2012-04-22 11:45:21
Размер: 2415
Редактор: Ray
Комментарий:
Версия 5 от 2012-04-22 13:31:40
Размер: 6675
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 18: Строка 18:
  1. ([[http://codeforces.ru/contest/180/problem/C|Письмо]]): Сообщение является красивым, если любая прописная буква стоит левее любой строчной. Найти наименьшее число действий, необходимое, чтобы письмо стало красивым. Длина строки не превосходит 10**5
  1. ([[http://codeforces.ru/contest/180/problem/F|Задача про матанализ]]): Заданы две последовательности, описывающие ситуацию на третий и четвертый день подготовки. Определить, кто является чьим лучшим другом.
  1. ([[http://codeforces.ru/contest/180/problem/C|Письмо]]): По мнению Петра, сообщение является красивым, если любая прописная буква стоит левее любой строчной. Иными словами это правило описывает строки, в которых сначала идет ноль или более прописных букв, а затем — ноль или более строчных. Для приведения письма в красивый вид Петр может замазать некоторую букву и записать эту же букву в этом же месте в противоположном регистре (строчную букву заменить на прописную и наоборот). Петр заинтересовался вопросом — какое наименьшее число действий необходимо, чтобы привести письмо в красивый вид. Одним действием будет считать смену регистра буквы в письме. Никаких других действий Петр совершать не может.
Строка 21: Строка 20:
  '''Входные данные'''. В единственной строке входных данных содержится непустая строка из строчных и прописных латинских букв. Длина строки не превосходит 105.

  '''Выходные данные'''. Выведите единственное число — наименьшее число действий, необходимое, чтобы письмо стало красивым.
  1. ([[http://codeforces.ru/contest/180/problem/F|Задача про матанализ]]): Будем считать, что студенты группы пронумерованы от 1 до n, а у каждого студента i (1 ≤ i ≤ n) есть его лучший друг p[i] (1 ≤ p[i] ≤ n). Так получилось, что каждый из студентов является лучшим другом ровно одного студента, иными словами все p[i] — различны. Возможно, в группе присутствуют такие «оригиналы», для которых i = p[i].
   * В первый день подготовки каждый студент учит матанализ по своим лекциям,
   * утром каждого следующего дня каждый студент передает тетрадку с лекциями своему лучшему другу, но получает тетрадку от студента, чьим лучшим другом он является.
  Так, во второй день тетрадка i-го студента находится у студента p[i] (1 ≤ i ≤ n), в третий день у студента p[p[i]] и так далее. В силу особенностей того, как дружат ребята (см. первый абзац), каждый день у каждого студента есть ровно одна тетрадь с лекциями.
  
  Вам заданы две последовательности, описывающие ситуацию на третий и четвертый день подготовки:
   * a1, a2, ..., an, где ai обозначает студента, у кого в третий день подготовки находится тетрадь i-го студента;
   * b1, b2, ..., bn, где bi обозначает студента, у кого в четвертый день подготовки находится тетрадь i-го студента.
  Вам неизвестен массив p, то есть неизвестно, кто является чьим лучшим другом. Напишите программу, которая по заданным последовательностям a и b находит p.

  '''Входные данные'''. В первой строке записано целое число n (1 ≤ n ≤ 105) — количество студентов в группе. Вторая строка содержит последовательность различных целых чисел a1, a2, ..., an (1 ≤ ai ≤ n). Третья строка последовательность различных целых чисел b1, b2, ..., bn (1 ≤ bi ≤ n).

  '''Выходные данные'''. Выведите последовательность n различных целых p[1], p[2], ..., p[n] (1 ≤ p[i] ≤ n). Гарантируется, что решение существует и оно единственно.

Анализ эффективности программ на Python

  • Неэффективность высокоуровневых операторов Python
    • Использование итераций вместо циклов
  • Списки вместо массивов — логарифмическая сложность вместо константы
    • Использование «настоящих» массивов из проекта NumPy

  • Анализ неэффективности реализации кодировщика в алгоритме преобразованиея Барроуза — Уилера:

Домашнее задание

Просто олимпиадные задачки.

  1. (Письмо): По мнению Петра, сообщение является красивым, если любая прописная буква стоит левее любой строчной. Иными словами это правило описывает строки, в которых сначала идет ноль или более прописных букв, а затем — ноль или более строчных. Для приведения письма в красивый вид Петр может замазать некоторую букву и записать эту же букву в этом же месте в противоположном регистре (строчную букву заменить на прописную и наоборот). Петр заинтересовался вопросом — какое наименьшее число действий необходимо, чтобы привести письмо в красивый вид. Одним действием будет считать смену регистра буквы в письме. Никаких других действий Петр совершать не может.

    Входные данные. В единственной строке входных данных содержится непустая строка из строчных и прописных латинских букв. Длина строки не превосходит 105.

    Выходные данные. Выведите единственное число — наименьшее число действий, необходимое, чтобы письмо стало красивым.

  2. (Задача про матанализ): Будем считать, что студенты группы пронумерованы от 1 до n, а у каждого студента i (1 ≤ i ≤ n) есть его лучший друг p[i] (1 ≤ p[i] ≤ n). Так получилось, что каждый из студентов является лучшим другом ровно одного студента, иными словами все p[i] — различны. Возможно, в группе присутствуют такие «оригиналы», для которых i = p[i].

    • В первый день подготовки каждый студент учит матанализ по своим лекциям,
    • утром каждого следующего дня каждый студент передает тетрадку с лекциями своему лучшему другу, но получает тетрадку от студента, чьим лучшим другом он является.
    Так, во второй день тетрадка i-го студента находится у студента p[i] (1 ≤ i ≤ n), в третий день у студента p[p[i]] и так далее. В силу особенностей того, как дружат ребята (см. первый абзац), каждый день у каждого студента есть ровно одна тетрадь с лекциями. Вам заданы две последовательности, описывающие ситуацию на третий и четвертый день подготовки:
    • a1, a2, ..., an, где ai обозначает студента, у кого в третий день подготовки находится тетрадь i-го студента;
    • b1, b2, ..., bn, где bi обозначает студента, у кого в четвертый день подготовки находится тетрадь i-го студента.
    Вам неизвестен массив p, то есть неизвестно, кто является чьим лучшим другом. Напишите программу, которая по заданным последовательностям a и b находит p.

    Входные данные. В первой строке записано целое число n (1 ≤ n ≤ 105) — количество студентов в группе. Вторая строка содержит последовательность различных целых чисел a1, a2, ..., an (1 ≤ ai ≤ n). Третья строка последовательность различных целых чисел b1, b2, ..., bn (1 ≤ bi ≤ n).

    Выходные данные. Выведите последовательность n различных целых p[1], p[2], ..., p[n] (1 ≤ p[i] ≤ n). Гарантируется, что решение существует и оно единственно.

Условные обозначения

  • {o} — тема по Linux

  • <!> ­— необязательная тема

  • {i} — теоретическое задание

  • {*} — тема для самостоятельного изучения


CategoryClass CategoryVmsh

LecturesVMSH/2012-04-18 (последним исправлял пользователь FrBrGeorge 2012-04-27 23:26:41)