Графы

Теория графов: Волновой алгоритм поиска кратчайшего пути. Центр онлайн-обучения «Фоксфорд»

Информатика. Разбор олимпиадных задач. Задача "Граф"

Олимпиадная информатика. Часть 2

Без повторений 8971 e-olimp

С заданного массива целых чисел нужно удалить все дублирования элементов. То есть из нескольких одинаковых элементов в массиве остается только элемент с наименьшим индексом.

Входные данные

В первой строке записано число N. В следующей строке записано N целых чисел. Все числа по модулю не превышают 100.

Выходные данные

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

from array import *

n=int(input())

a = [int(x) for x in input().split()]

a.reverse()

for i in range(n-1,0,-1):

if a.count(a[i])>1:

k=a.index(a[i])

k1=a.pop(k)

a.reverse()

for i in range(len(a)):

print(a[i],end=' ')

Модные элементы 8972

В заданном массиве целых чисел нужно вывести только элементы повторяющиеся несколько раз. То есть числа, которые встречаются один раз не выводятся вообще, а из нескольких одинаковых элементов в массиве выбираем один с наименьшим индексом. Если таких элементов нет необходимо вывести сообщение NO.

Входные данные

В первой строке записано число N. В следующей строке записано N целых чисел. Все числа по модулю не превышают 100.

Выходные данные

Вывести элементы массива, повторяющиеся в одной строке через пробел.

4538. Вася и шары

Недавно Вася узнал, что с шарами можно играть в очень занимательную игру. В этой игре требуется укладывать шары в виде различных геометрических фигур и тел. Пока Вася занимается укладкой шаров в виде равностороннего треугольника. Но вот незадача: иногда Васе не хватает наличных шаров, и он хочет знать, какова наибольшая сторона такого треугольника, для которого хватит Васиных шаров? Помогите Васе, напишите для него программу, которая будет вычислять n – длину стороны равностороннего треугольника для заданного количества шаров k.

Ниже приведён пример укладки шаров в виде равностороннего треугольника:

Вход. Натуральное число k (0 ≤ k ≤ 2 *10⁸) – имеющееся количество шаров.

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

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Если n – длина стороны треугольника, то для полной его укладки требуется 1 + 2 + … + n = n * (n + 1) / 2 шаров. В наличии имеется k шаров. Решим уравнение n * (n + 1) / 2 = k и округлим неотрицательный корень вниз до ближайшего целого.

Решим квадратное уравнение: n² + n – 2k = 0, d = 1 + 8k, n = .

import math

k=int(input())

n=(-1+math.sqrt(1+8*k))/2

print(int(n))

137. НОД

Найти НОД (наибольший общий делитель) n чисел.

Вход. Первая строка содержит количество чисел n (1 < n < 101). Во второй строке через пробел заданы n натуральных чисел, каждое из которых не превышает 30000.

Выход. НОД заданных чисел.

РЕШЕНИЕ

НОД

Анализ алгоритма

Известно, что

НОД (a₁, a₂, …, a_i) = НОД (НОД (a₁, a₂, …, a_{i - 1}) , a_i)

Будем последовательно вычислять наибольший общий делитель двух, трех, …, n чисел. Например, для четырех чисел имеет место равенство:

НОД (a₁, a₂, a₃, a₄) = НОД (НОД (НОД (НОД (0, a₁), a₂), a₃), a₄)

Реализация алгоритма

Функция gcd вычисляет Наибольший Общий Делитель.

import math

def ff(a,b):

k1=math.gcd(a,b)

return k1

k=int(input())

a = [int(x) for x in input().split()]

s=0

for i in range(len(a)):

s=ff(s,a[i])

print(s)

Число-палиндром 1608

Проверьте, или заданное число является палиндромом.

Число называется палиндромом, если оно читается слева направо и справа налево одинаково.

Входные данные

Одно неотрицательное целое 32-х разрядное число.

Выходные данные

Вывести "Yes" если число палиндром, в противном случае "No".

Удаление лишних пробелов 4737

Дана строка. Напишите программу, которая удалит из этой строки все лишние пробелы. Пробел будем считать лишним, если:

• • он находится в самом начале строки, до самого первого слова;

  • он находится в конце строки, после самого последнего слова;

  • несколько пробелов расположены между словами (проще говоря, если слова разделены более чем одним пробелом, тогда все пробелы, кроме одного, лишние).

Входные данные

Дана строка s (0 ≤ |s| ≤ 255). Строка содержит только латинские буквы и пробелы.

Выходные данные

Выведите строку без лишних пробелов.

import re

k=str(input())

k=k.strip()

print(re.sub('\s+',' ',k))

8240

Функция - 2

Реализуйте функцию sqrt(x) + 2 * x + sin(x), где sqrt - функция квадратного корня.

Входные данные

Каждая строка содержит одно действительное число x.

Выходные данные

Для каждого значения x вывести в отдельной строке значение функции f(x) с четырьмя десятичными знаками.

import math

with open('input.txt','r') as f:

for x in f:

x=float(x)

f1=open('output.txt','a')

f1.write(str('%.4f'%(math.sqrt(x)+2*x+math.sin(x))+'\n'))