Информатика

2 621 задачавместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Числа#21838

У Артура есть два натуральных числа — x и y (x < y). Помогите ему найти натуральное число z такое, что:

  • z > x;
  • z > y;
  • z не делится на x;
  • z не делится на y;
  • z делится на y - x;
  • z минимально.

Формат входных данных

В первой строке находятся числа x и y (x, y ≤ 106)

Формат выходных данных

Выведите число z или '0', если его не существует.

Ввод:
1 2

Вывод:
0

Разбор случаевреализация
✓ 56✗ 281700средняяВойти и решать
Z-функция#21824
Даны две строки - S и T. Ваша задача по запросам вывести колличество вхождений i-того префикса строки S в строку T.

Входные данные
В первой строке вводится k - количество запросов (\(k <= длина( S)\)), строка S и строка T. Далее вводится k запросов, запрос на количество вхождений i-го префикса строки S в строку T.

Выходные данные
Вывести k строк с ответами на запросы.

 

Примеры
№ Входные данные Выходные данные
1
2 ali balimali
3
0
 2
8
Z-функция. Префикс-функция
✓ 41✗ 148700средняяВойти и решать
Pref-функция#21823
Дана строка S. Найдите сумму значений префикс-функции для всех заданных позиций строки S. 

Входные данные
В первой строке входного файла записана строка S (\(1 <= |S| <= 150 000\)) и k (количество заданных позиций).
Далее идут k чисел - позиции, значения префикс-функции которых надо сложить.

Выходные данные
В выходной файл выведите одно число - сумму значений префикс-функции для всех заданных позиций строки S.
 

 

Примеры
№ Входные данные Выходные данные
1
abacaba 2
3
7
 4
Z-функция. Префикс-функция
✓ 68✗ 111400лёгкаяВойти и решать
HASH#21822
Программисту Васе не повезло - вместо отпуска его послали в командировку на научную конференцию. "Надо повышать уровень знаний", - сказал начальник, "Важная конференция по криптографии, проводится во Франции - а там шифровали еще во времена Ришелье и взламывали чужие шифры еще во времена Виета."
Вася быстро выяснил, что все луврские картины он уже где-то видел, вид Эйфелевой башни приелся ему еще раньше, чем мышка стерла его с коврика, а такие стеклянные пирамиды у нас делают надо всякими киосками и сомнительными забегаловками. Одним словом, смотреть в Париже оказалось просто не на что, рыбу половить негде, поэтому Васе пришлось посещать доклады на конференции.
Один из докладчиков, в очередной раз пытаясь разгадать шифры Бэкона, выдвинул гипотезу, что ключ к тайнам Бэкона можно подобрать, проанализировав все возможные подстроки произведений Бэкона. "Но их же слишком много!" - вслух удивился Вася. "Нет, не так уж и много!" - закричал докладчик, - "Подсчитайте, и вы сами убедитесь!"
Тем же вечером Вася нашел в интернете полное собрание сочинений Бэкона. Он написал программу, которая переработала тексты в одну длинную строку, выкинув из текстов все пробелы и знаки препинания. И вот теперь Вася весьма озадачен - а как же подсчитать количество различных подстрок этой строки? 

Входные данные
На входе дана непустая строка, полученная Васей. Строка состоит только из строчных латинских символов. Ее длина не превосходит 2000 символов. 

Выходные данные
Выведите количество различных подстрок этой строки.

 

Примеры
№ Входные данные Выходные данные
1 aaba 8
Хеш
✓ 39✗ 20700средняяВойти и решать
Dank numbers#21778
Число является dank number, если все его цифры идут в неубывающем порядке. Чтобы получить dank kush, Bonkisilver должен назвать все n-значные dank numbers. Вас не просят узнать все такие числа, Вам лишь нужно вывести их количество.

 
Входные данные
На вход подается число n (0 <= n <= 50).
 
Выходные данные
Выведите одно число - количество n-значных dank number. 
 
 
Примеры
№ Входные данные Выходные данные
1 9 24310
 
Динамическое программирование
✓ 105✗ 164700средняяВойти и решать
Запросы по Флойду#21777
Дан неориентированный взвешенный граф с отрицательными весами, необходимо выдавать информацию о кратчайшем пути между 2 вершинами.

Входные данные
В первой строчке дано целое число n - количество вершин в графе. Дальше на вход подается матрица смежности, в которой -1 означает отсутствие ребра между вершинами. После матрицы идет число k - количество запросов, в следующих k строках содержится по 2 числа, a и b - вершины в запросе.

Выходные данные
Выведите k чисел - расстояние между парой чисел из запроса в порядке их ввода, если нельзя добраться из вершины a в вершину b, следует вывести Imp. Каждое число выводится в отдельной строке.
 
Примеры
№ Входные данные Выходные данные
1
3
0 3 -1
3 0 4
-1 4 0
3
1 3
3 2
1 2
 7
4
3
Алгоритм Флойда
✓ 277✗ 465500лёгкаяВойти и решать
Дейкстра: Расстояние до всех вершин#21776
Дан неориентированный взвешенный граф, необходимо найти расстояние от вершины 1 до всех остальных, используя алгоритм Дейкстры.
 
Входные данные:
В 1 строке даны 2 целых числа n и m (n>=1, m >= 0), число вершин и ребер в графе соответсвенно. В следующих m строках дается по 3 числа a и b - вершины которые соединяет ребро и c - вес этого ребра .
 
Выходные данные:
Необходимо вывести n-1 число через пробел - расстояния от вершины 1 до всех остальных, если нет возможного пути из 1 в i вершину, то необходимо вывести Impossible.
 
Ввод Вывод
5 5
1 2 3
2 3 1
3 4 3
1 4 1
4 2 1
 2 3 1 Impossible
 
P.S. Внимательно проверяйте ограничения
Алгоритм Дейкстры
✓ 18✗ 42700средняяВойти и решать
Беллман#21775
Дан ориентированный взвешенный граф с отрицательными ребрами (без отрицательных циклов).
Дана стартовая и конечная вершина, определить минимальное расстояние между ними.
 
Входные данные:
Дано 4 числа n, m, s, f - количество вершин, количество ребер, стартовая и конечная вершина(начиная с 1) соответственно.
В следующих m строках содержится по 3 числа - вершина 1, вершина 2 и цена перехода между вершинами.
 
Выходные данные:
Требуется вывести одно число - ответ на поставленную задачу. Если ответа нет - следует вывести Inf.
 
Примеры
№ Входные данные Выходные данные
1
4 2 1 4    
1 2 100500
2 3 100500
 Inf 
Алгоритм Форда-Беллмана
✓ 89✗ 137400лёгкаяВойти и решать
Ленивый Вася и релиз Half-Life 3#21773
Свершилось чудо! Наконец-то вышел долгожданный Half-Life 3, о котором мечтали миллионы людей по всему миру! Вася тоже с нетерпением ждал продолжения легендарной серии, и даже не ел в школьной столовой целый месяц, чтобы ему хватило на покупку этого шедевра! Единственная проблема, которая стоит у него на пути - огромное домашнее задание по алгебре. В классе он прошёл новую тему - прямые, и теперь ему нужно сделать аж N задач на построение прямой через 2 точки. Но ведь так хочется поиграть, а на следующий день рассказывать друзьям, какой же там классный графон... Поэтому он попросил Вас, своего друга, помочь ему.
 
Входные данные
В первой строке вводятся координаты первой точки (X1, Y1), (\(-50 <= X_1, Y_1 <= 50\)).
Во второй строке вводятся координаты второй точки (X2, Y2), (\(-50 <= X_2, Y_2 <= 50\)).
 
Выходные данные
В единственной строке выведите подряд 3 целых числа: коэффициенты a, b, c уравнения прямой.
 
Примечание: если у вас не заходит задача, но вы уверены, что всё правильно - попробуйте умножить все коэффициенты на -1. Задача предполагает, что вы использовали формулы, взятые с лекции/теории.

 

Примеры
№ Входные данные Выходные данные
1
-1 -1
1 1
 -2 2 0
Вычислительная геометрия
✓ 71✗ 65600лёгкаяВойти и решать
Перевод часов#21772
В плоской стране наступила очередная зима, и нужно срочно переводиться на зимнее время! Проблема в том, что стрелка городских часов (единственная, кстати), находящихся в начале координат, очень-очень тяжёлая, и поэтому рабочие хотят узнать, в какую сторону крутить стрелку будет быстрее. Чтобы упростить вам задачу, они уже посчитали, куда указывает стрелка и куда она должна указывать. Помогите им!
 
Входные данные
В первой строке задаётся точка, куда указывает стрелка. Она задаётся координатами X1 и Y1 (\(-10 <= X_1, Y_1 <= 10\)).
Во второй строке задаётся точка, куда должна указывать стрелка. Она задаётся координатами X2 и Y2 (\(-10 <= X2, Y2 <= 10\)).
Координаты задаются вещественным типом.
 
Выходные данные
В единственной строке выведите "Clockwise", если стрелку нужно крутить по часовой стрелке, "Counter-clockwise", если её нужно крутить против часовой стрелки, и "Doesn't matter", если это займёт одинаковое время, в какую сторону её бы не крутили. Выводить фразы следует без кавычек.

 

Примеры
№ Входные данные Выходные данные
1
1 0
-1 1
 Counter-clockwise
Вычислительная геометрия
✓ 233✗ 652700средняяВойти и решать
Простые числа - 1#21768
Найти количество всех четырехзначных простых чисел, оканчивающиеся на цифру k.

Входные данные 
Число k.

Выходные данные 
Вывести число - количество простых чисел, удовлетворяющих условию задачи. Если таких чисел нет то вывести слово Absent.

Примеры
№ Входные данные Выходные данные
1 1 266
2 0 Absent
Простые числа и разложение на множители
✓ 794✗ 1 382400лёгкаяВойти и решать
Постулат Бертрана#21767

Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого \(n > 1\) найдется простое число p в интервале \(n < p < 2n\). Такая гипотеза была выдвинута в 1845 году французским математиком Джозефом Бертраном (проверившим ее до \(n=3000000\)) и доказана в 1850 году Пафнутием Чебышевым. Раманужан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.

Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала \(n < p < 2n\).

Напомним, что число называется простым, если оно делится только само на себя и на единицу

Входные данные
Целое число n (\(2 <= n <= 50000\)).

Выходные данные 
Выведите одно число – ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1 3000 353
Простые числа и разложение на множители
✓ 630✗ 1 075500лёгкаяВойти и решать
Максимальная цифра в восьмеричной СС#21763
Дано натуральное число N . Необходимо найти максимальную цифру данного числа при его записи в восьмеричной системе счисления.

Входные данные
На вход подается натуральное число N (\(N<=255\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры
№ Входные данные Выходные данные
1 255 7

 

Разные системы счисления
✓ 506✗ 350300лёгкаяВойти и решать
Количество единиц в двоичной СС#21762
Дано натуральное десятичное число N. Найдите количество единиц в двоичной записи данного числа. Ответ вывести в десятичной системе счисления.

Входные данные
На вход подается одно натуральное число N (\(N<=255\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Пример
№ Входные данные Выходные данные
1 100 3

 

Двоичная система счисления
✓ 588✗ 460300лёгкаяВойти и решать
Минимальное остовное дерево c с данным ребром#21748
Требуется найти в связном графе остовное дерево минимального веса в котором есть данное ребро.
 
Формат файла входных данных:
 
Первая строка входного файла содержит два натуральных числа N, M - количество вершин и ребер графа соответственно. Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами Bi, Ei, Wi номера концов ребра и его вес соответственно (1 <= Bi, Ei <= N, 0 <= Wi <= 2^32-1. N <= 10, M <= 10). В последней строке вводится данное ребро B, E, W.
 
Формат файла выходных данных:
 
Единственная строка выходного файла должна содержать одно натуральное число - вес минимального остовного дерева c данным ребром. 
 
Ввод:
 
4 4
1 2 1
2 3 2
3 4 5
4 1 4
1 4 7
 
Вывод:
10
Система непересекающихся множеств
✓ 25✗ 24700средняяВойти и решать
Сумма делителей#21723
Для данного натурального числа n вычислите сумму всех его натуральных делителей, включая 1 и само число. Решение оформите в виде РЕКУРСИВНОЙ функции с одним параметром. Основная программа должна содержать ввод исходных данных, вызов функции и вывод ответ
Запрещено использовать циклы в программе

Примеры
№ Входные данные Выходные данные
1 6 12
Рекурсия
✓ 384✗ 287500лёгкаяВойти и решать
Поделиться
Класснуть