e-olymp 1108. Червячные дыры

Ссылка на оригинальную статью

Ссылка на Try Haxe!

Условие задачи

В 2163 году были обнаружены червячные дыры. Червячная дыра представляет собой тоннель сквозь пространство и время, соединяющий две звездные системы. Эти дыры имеют следующие свойства:

  • Червячные дыры являются односторонними.
  • Время путешествия по любому тоннелю равно нулю.
  • Червячная дыра имеет два конца, каждый из которых находится в звездной системе.
  • Звездная система в своих границах может иметь несколько концов червячных дыр.
  • По некоторой неизвестной причине начиная с нашей Солнечной системы всегда можно достигнуть любую другу звездную систему перемещаясь некоторой последовательностью червячных дыр (возможно, это потому что Земля является центром универсума).
  • Между любой парой звездных систем существует не более одной червячной дыры в любом из направлений.
  • Оба конца червячной дыры не могут находиться в одной звездной системе.
  • Каждая червячная дыра перемещает путешественника на определенное константное количество лет вперед или назад. Например, одна дыра может переместить на 15 лет в будущее, а другая на 42 года в прошлое.

Известный физик, живущий на Земле, хочет использовать червячные дыры для исследования теории Большого Взрыва. Поскольку двигатель искривления пространства еще не изобретен, невозможно напрямую путешествовать между звездными системами. Однако это можно делать при помощи червячных дыр.

Ученый хочет достигнуть цикла червячных дыр, который поможет ему попасть в прошлое. Двигаясь по этому циклу несколько раз, можно прийти ко времени, когда имел место Большой Взрыв и наблюдать его собственными глазами. Напишите программу, которая определяет существование такого цикла.

 

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

Первая строка содержит количество звездных систем $n (1 ≤ n ≤ 1000)$ и количество червячных дыр $m (0 ≤ m ≤ 2000)$. Звездные системы пронумерованы от 0 (наша солнечная система) до n — 1. Каждая червячная дыра описывается в отдельной строке и содержит три целых числа x, y и t. Эти числа указывают на возможность передвижения из звездной системы с номером x в звездную систему с номером y, при этом время изменяется на $t (-1000 ≤ t ≤ 1000)$ лет.

 

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

Cтрока содержит информацию, возможно ли в заданном множестве систем попасть в минус бесконечность во времени используя червячные дыры. Выводить следует строку «possible» или «not possible».

 

Тесты

Входные данные Выходные данные
3 3
0 1 1000
1 2 15
2 1 -42
possible
4 4
0 1 10
1 2 20
2 3 30
3 0 -60
not possible
4 4
0 1 10
1 2 20
2 3 30
3 0 -61
possible
3 3
0 1 -100
1 2 1
2 1 0
not possible

 

Код

Ход решения

Решение данной задачи сводится к нахождению отрицательного цикла в ориентированном графе. Необходимо воспользоваться алгоритмом Форда-Беллмана. Создадим вектор на n элементов и заполним его нулями. Алгоритм основан на том, что если в графе размерностью n элементов нет отрицательных циклов, то после n1 прохождения, изменения в массива кратчайших расстояний не будет. Поэтому, будем выполнять следующее n раз:

  1. Возьмем первое ребро из вектора canals, и проведем сравнение: если исходная длина пути конца данного ребра из исходного вектора distance больше, чем сумма длины пути начала вектора и стоимости прохода по данному ребру canals[].t, то изменим в векторе distance элемент с номером конца исходного ребра, и изменим индикатор изменений х, чтобы показать, что в ходе данного прохода были внесены изменения.
  2. Переходим к следующему ребру.

Если после во время последнего прохода ни разу не была изменена переменная x, то это значит, что в графе нет циклов отрицательной длины, и тогда выводим «not possible». Иначе, выводим «possible».

e-olymp 1077. Java против C++

Ссылка на выполнение кода

Условие задачи

Сторонники языков Java и C++ часто спорят о том, какой язык лучше для решения олимпиадных задач. Одни говорят, что в Java есть масса полезных библиотек для работы со строками, хорошо реализованы механизмы чтения и вывода данных, а так же радует встроенные возможности для реализации длинной арифметики. С другой стороны, С++ является классическим языком, скорость выполнения программ благодаря существующим компиляторам (например, Intel Compiler 10.0) гораздо выше, чем у Java.

Но сейчас нас интересует лишь небольшие отличия, а именно соглашения, которыми пользуются программисты при описании имен переменных в Java и C++. Известно, что для понимания значений переменных часто используют английские слова или даже целые предложения, описывающие суть переменных, содержащих те или иные значения. Приведем ниже правила описания переменных, которыми руководствуются программисты, реализующие программы на Java и C++.

В языке Java принято первое слово, входящее в название переменной записывать с маленькой латинской буквы, следующее слово идет с большой буквы (только первая буква слова большая), слова не имеют разделителей и состоят только из латинских букв. Например, правильные записи переменных в Java могут выглядеть следующим образом: javaIdentifier, longAndMnemonicIdentifier, name, nEERC.

В языке C++ для описания переменных используются только маленькие латинские символы и символ «_», который отделяет непустые слова друг от друга. Примеры: java_identifier, long_and_mnemonic_identifier, name, n_e_e_r_c.

Вам требуется написать программу, которая преобразует переменную, записанную на одном языке в формат другого языка.

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

Во входном потоке задано наименование переменной длиной не более 100 символов.

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

В выходной поток требуется вывести аналог имени переменной в другом языке. Т.е. если переменная представлена в формате Java, то следует перевести в формат C++ и наоборот. В том случае, когда имя переменной не соответствует ни одному из вышеописанных языков, следует вывести «Error!».

Задача взята с сайта e-olymp.

Тесты:

Ввод Вывод
java_word javaWord
cppWorD cpp_wor_d
simpleword simpleword
two__underscores Error
underscore_in_the_end_ Error
UppercaseInTheBeginning Error
mixed_Style Error

Код:

Ход решения:

Со входного потока считывается название переменной, которая помещается в переменную $varName$. Затем вызывается вспомогательная функция $parseLanguage$, которая возвращает одно из значений enum: относится ли переменная к языку С++, Java, универсальная ли она или же, если ничего из вышеперечисленного не подошло, возвращает ошибку. Далее, проанализировав значение, которое нам вернула функция, решается, что делать с переменной: либо конвертировать её в переменную C++, либо в переменную Java, либо оставить её, как есть (универсальная переменная). В ином случае это ошибка, что тоже выводится. Функции $toCPP$ и $toJava$ также являются вспомогательными, которые «переводят» переменную из одного языка в другой.

A711a

Задача.

Дана матрица $A$ размера $m\times m$. Получить матрицу $AA^{*}$ (ее размер $m\times m$).
Размер матрицы:

m 4

Матрица:

1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6

Результирующая матрица:

30 70 20 50
70 174 68 122
20 68 86 44
50 122 44 86

Ход решения:

На входе считываем $m$ — размер матрицы. После этого создаем два вложенных массива — $A$ для хранения вводимых значений и вычислений, $result$ — для результатов вычислений. Переменная $sum$ нужна для хранения временного результата суммы произведений $A[i,k]A[j,k]$.

Код:

Ю 4.24

Ссылка оригинальную статью

Ссылка Try Haxe!

 

Условие задачи:

В массиве $А(n)$ каждый элемент, кроме первого, заменить суммой всех предыдущих элементов.

Тесты:

Ввод Вывод
1 1 1 1 1 1 1 1 2 3 4 5
3 5 2 9 0 4 65 156 1 3 3 8 10 19 19 23 88 244
2 -7 3 8 -4 5 -2 4 2 2 2 -5 -2 6 2 7 5 9

Код:

Ход решения:

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

А 136к

Задача:

Даны натуральное число $n$, действительные числа  [latex]a_{1}\ldots a_{n}[/latex].

Вычислить:  $ 2\left(a_{1}+\ldots+a_{n} \right)^2 $.

Тесты:

n введенные результат
3 1 2 3 72
4 0 0 0 0 0
4 -5 -7 -3 -1 512

Код:

Ход решения:

Заводим переменную [latex]result[/latex] и присваиваем ей значение 0 . Далее, в цикле от 0 до [latex]n[/latex] увеличиваем значение текущего значения [latex]result[/latex]. По окончании цикла возводим [latex]result[/latex] в квадрат и умножаем на 2.

e-olymp 1154. Кружок хорового пения

Условие задачи:

В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex] -й для распевки поёт гамму.

Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]M[/latex] и [latex]N[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.

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

Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]M[/latex] и [latex]N[/latex].

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

Для каждого тестового случая в отдельной строке выведите «Yes», если в разминке примут участие все участники хора, в противном случае выведите «No».

Тесты:

n m answer
 4   1  Yes
 6   3  No

Код:

Ход решения:

Для начала нам надо найти наибольший общий делитель (НОД). Для этого хорошо подойдет алгоритм Евклида и если НОД равен единице, то все ученики распоются и на выходе подаётся «Yes», иначе «No».

Mif 17.18

Условие:

Принадлежит ли точка ([latex]x;y[/latex]) фигуре на рисунке?

Image

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

Два числа — координаты точки.

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

Слово «Yes», если точка принадлежит фигуре, в противном случае -«No».

Код:

Ход решения:

Точка будет принадлежит фигуре тогда и только тогда, когда будет выполняться одно из условий:

  • Оба числа не отрицательные и их сумма не превышает 6;
  • Оба числа не положительные, и их сумма не меньше 6.

Если одно из этих условий выполняется, то на выходе имеем «Yes», иначе — «No».

e-olymp 57. Бабочка-санитар

Задача взята с сайта e-olymp.com.
Решение на с++

Условие

Школьники, идя из дому в школу или наоборот — со школы домой, любят кушать конфеты. Но, как всегда, это приятное дело иногда имеет неприятные последствия – детки часто выбрасывают обертки на школьном дворе.

Мурзик всегда следил за чистотой школьного двора и ему в этом с радостью помогали бабочки, благодарные за прекрасные фотографии, сделанные им. Бабочки могли использовать собственные крылышки как линзы, причем они могли изменять их фокусное расстояние. Заметив обертку от конфетки, лежавшую на школьном дворе в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], бабочка перелетала в точку с координатами [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex], расположенную на пути солнечных лучей к обертке и, изменяя фокусное расстояние своих крылышек-линз, сжигали обертку от конфеты.

Какую оптическую силу [latex]D[/latex] имели крылышки-линзы бабочки в этот момент?

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

В первой строке 2 числа: координаты [latex]X_1[/latex], [latex]Y_1[/latex] обертки от конфетки. Во второй – 3 числа: координаты [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex] бабочки в момент сжигания обертки.

Все входные данные целые числа, не превышающие по модулю 1000.

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

Единственное число – оптическая сила крылышек-линз [latex]D[/latex].

Код

Ход решения:

Вычисляем оптическую силу линзы [latex]D[/latex] по формуле [latex]D=\frac{1}{f}
[/latex], где [latex]f[/latex] — расстояние между бабочкой и обёрткой. Вычисляем его по формуле: [latex]f =
\sqrt{(X_2-X_1)^2+(Y_2-Y_1)^2+Z_2^2}[/latex].

2.7.1 Динамический тип данных с типовым параметром

Ссылка на статью

Динамический тип — это специальный тип данных, потому как он допускает объявление переменной с и без строгой типизации. Если переменная строго типизирована, то семантика, описанная в динамическом типе, накладывает ограничения по всем свойствам, чтобы они были совместимы с заданным типом. Например, на следующем коде видно поведение Dynamic при строгой типизации String: