Сайт підготовки до олімпіади з інформатики

Теорія графів (скачати)

Codeforces  (http://codeforces.com/)

http://codeforces.com/problemset/problem/550/A

Два підрядка

Дано рядок s. Потрібно визначити, чи існують в цьому рядку s два  підрядка, які не перетинаються "AB" і "BA" (ланцюжків можуть йти в будь-якому порядку).

Вхідні дані

На вхід подається рядок s довжиною від 1 до 10⁵ символів, що складається з великих літер латинського алфавіту.

Вихідні дані

Виведіть "YES" (без лапок), якщо рядок s містить дві непересічні підрядка "AB" і "BA", і "NO" інакше

$11.      Турнір http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=11

Задачі А

Неуважність

Степан вдало пройшов співбесіду і ось уже як чотири місяці працює на одній із самих престижних ІТ компаній. Прийшов час здавати проект менеджеру і Степан, як істинний студент, все виконує у останню ніч перед здачею. Набирає текст Степан звичайно дуже швидко, але неуважно. От і цього разу останню частину тексту він набрав не звернувши уваги, що випадково натиснув клавішу caps lock. Таким чином великі букви були набрані маленькими, а маленькі великими. Інші символи він набрав вірно. Степан настільки стомився, що немає сил виправити помилки, і він вирішив кілька годин поспати. Допоможіть Степану, доки він спить, напишіть програму, яка виправляє неуважно набраний текст.

Input format

перший рядок вхідного файлу містить неуважно набраний Степаном текст, який містить не більше 500 символів.

Output format

вихідний файл має містити виправлений текст.

Examples

Задача F

Арифметика

Молодший брат Степана Мишко навчається у першому класі. Він дуже допитливий і постійно дістає Степана запитаннями: А скільки? А чому? Сьогоднішній день не виключення. Мишко каліграфічно виписує цифри в ряд і запитує: А скільки різних цифр у записі цього числа. На перші приклади Степан швидко знаходив відповідь. Але Мишко чим далі, тим більші числа записував. Це стало для Степана проблемою. Допоможіть Степану, напишіть програму, яка визначає, кількість різних цифр у числі Мишка.

Input format

перший рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 10¹⁰⁰⁰), записане Мишком.

Output format

вихідний файл має містити одне число – кількість різних цифр у числі.

Examples

Теорія графів

Основні алгоритми роботи з графами:

http://www.e-olymp.com/uk/problems/4764 - Матриця суміжності, степінь вершин

http://www.e-olymp.com/uk/problems/4763 - Від списку ребер до матриці суміжності

http://www.e-olymp.com/uk/problems/625 - Пошук в глибину на графах

http://www.e-olymp.com/uk/problems/975  - Флойд (зчитування матриці)

http://www.e-olymp.com/uk/problems/983 - Флойд (створення матриці)

http://www.e-olymp.com/uk/problems/2968 -  Флойд (Форд)

http://www.e-olymp.com/uk/problems/1365 -  Дейкстри

http://www.e-olymp.com/uk/problems/2965 -   Дейкстра

http://www.e-olymp.com/uk/problems/981 - мінмальне остове дерево (алгоритм Прима)

http://www.e-olymp.com/uk/problems/964 - Матриця інцендентності