Олимпиадное программирование java задачи

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

kenthex/olympiad-task

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Solution of the olympiad task in Java language 

Task question. Help the mayor build the minimum number of depots so that in case of a house fire at any crossroad, a fire car from one of the depots can reach this crossroad (possibly against traffic), and then she could return to her depot (already moving only in the direction of the roads). In the first line, n and m (1 ≤ N ≤ 20,000, 1 ≤ M ≤ 200,000) — the number of crossroads and streets. Starting from the second line, there is a listing of the starting and ending street numbers. Need to print a number showing the minimum number of depot to be built.

Short description of the task solution. First we need to find SCC (Strongly Connected Components), in the program it was implemented by Kosaraju algorithm. After that, we need to check connections between SCC: if we can reach a vertex located in one SCC from vertex located in another SCC, we add the vertex we reached in preliminary list of depot. In case we can’t reach both of vertices, we add both vertices in preliminary list of depot. And the last action is to check reachability between vertices in preliminary list of depot. If we can reach from one to another, we delete the vertex from which we left, and the final list will be list of depot.

Working input data examples:
Example 1.
Number of vertices (crossroads): 6
Number of edges (roads): 7
Connections of vertices:
1 5
1 4
1 2
2 3
3 1
4 6
6 4

Example 2.
Number of vertices (crossroads): 8
Number of edges (roads): 13
Connections of vertices:
1 2
2 3
3 4
4 3
4 8
8 4
8 7
7 6
6 7
3 7
5 1
5 6
2 5

WARNING: the program may not work correctly with different parameters.

Решение олимпиадной задачи по программированию на языке Java 

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

Рабочие примеры входных данных:
Пример 1.
Количество вершин (перекрестков): 6
Количество ребер (дорог): 7
Связи между вершинами:
1 5
1 4
1 2
2 3
3 1
4 6
6 4

Пример 2.
Количество вершин (перекрестков): 8
Количество ребер (дорог): 13
Связи между вершинами:
1 2
2 3
3 4
4 3
4 8
8 4
8 7
7 6
6 7
3 7
5 1
5 6
2 5

ВНИМАНИЕ: с другими параметрами программа может работать некорректно.

Источник

Как я олимпиаду на Java писал или почему лучше не пользоваться Scanner

Вчера завершился Региональный этап Всероссийской олимпиады школьников. Я участвовал в нем и выбрал для этого язык Java. Основной причиной, почему я решил писать олимпиаду именно на Java заключался в том, что на тот момент я довольно хорошо ее знал и понимал то, как в ней реализовано большинство основных структур данных и функций. Также IntellijIDEA очень сильно способствовала плодотворному кодингу, в ситуациях, когда время является решающим фактором. Да, среды разработки от JetBrains есть и для многих других языков, но среди этих языков нет тех, что обычно используются в спортивном программировании, не считая Python, но использовать здесь его я побаивался из-за того, что этот язык известен прожорливостью.

Однако наш друг, носящий имя индонезийского острова, оказался в некоторых ситуациях еще медленнее, чем прожорливый змей.

Не буду сильно вникать в условия задачи, в решении которой я столкнулся с тем, что программа не успевает справится с задачей за предоставленное время, но отмечу один факт: то решение, которое я написал, являлось эталонным (то есть судьи в пакете с тестами предоставили идентичное решение, но на C), не имело бесконечных циклов и прочего, а его сложность была O(n).

И по итогу можно с точностью сказать, что виновником являлся Scanner и его функция nextInt() .

А теперь более подробно разберемся с тем, как же эта функция работает.

Сама функция состоит всего из одной строчки return nextInt(defaultRadix); .
А вот то, что творится уже внутри этой функции нам гораздо интереснее.

Первым делом идет проверка if ((typeCache != null) && (typeCache instanceof Integer)
&& this.radix == radix) и здесь очень важно понять, чем же является typeCache и откуда он берется. И тут все вполне просто. Он является ничем иным, как строкой нашей консоли, записанной в форме Object и если этот объект (читать как строка, которую мы ввели) является инстансом Integer , то Scanner делает вывод о том, что введенная строка это и есть искомое число и возвращает его.
Тут все хорошо и сложность этой операции О(1). Отсюда можно заключить, что вводя в строчку только одно число мы практически не тратим время на преобразование ввода в число.
Значит едем дальше.

А вот тут-то и появляется виновник торжества.

Если в строке, которую получил Scanner не int или же если там несколько таковых, то вызывается вот такая строка кода:

String s = next(integerPattern());

public String next(Pattern pattern) < ensureOpen(); if (pattern == null) throw new NullPointerException(); // Did we already find this pattern? if (hasNextPattern == pattern) return getCachedResult(); clearCaches(); // Search for the pattern while (true) < String token = getCompleteTokenInBuffer(pattern); if (token != null) < matchValid = true; skipped = false; return token; >if (needInput) readInput(); else throwFor(); > >

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

Первые три строчки это просто защита от дурака.

А дальше, как нам подсказывают комментарии тех, кто писал этот код идет проверка «а мы случаем не нашли уже такой паттерн?», но в нашем случае эта проверка всегда будет возвращать ложь, поскольку мы на прошлом этапе уже проверили, что полученная нами строка не int.

И что мы видим в конце? Понимая, что быстрых способов поиска больше нет, Scanner сдается и запускает бесконечный цикл который завершится только, если перебором будет найдено что-то, что нам подходит.

А какая у нас сложность у такого перебора? Там вроде бы используется конечно метод двух указателей или что-то на него похожее, но это в любом случае не спасает от множества проверок.

Можете меня поправить, но я вижу там О(n^2), поскольку иначе я не могу объяснить куда могло уйти столько времени.

Итог: в случае, когда вам нужно, чтобы программа действительно быстро считала целые числа из консоли, не доверяйте это дело Scanner.nextInt() . Даже банальное Scanner.nextLine и разбиение String в String[] и превращение каждого из членов данного массива в int окажется значительно быстрее.

Источник

Решение олимпиадной задачи

После затянувшегося совещания директор фирмы решил заказать такси,чтобы развезти сотрудников по домам. Он заказал N машин —ровно столько, сколь у него сотрудников.Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.

Директор знает, какому сотруднику сколько километров от работы до дома (к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине). Теперь директор хочет определить, сколько придется заплатить за перевозку всех сотрудников. Естественно, директор хочет заплатить как можно меньшую сумму.

Входные данные
В первой строке записаны N чисел через пробел, задающих расстояния в километрах от работы до домов сотрудников компании. Во второй строке записаны N чисел — тарифы за проезд одного километра в такси.

Выходные данные
Выведите одно целое число — наименьшую сумму, которую придется заплатить за доставку всех сотрудников.

Решение олимпиадной задачи (ч.2)
i:= 1 j:= 257 Цикл i:= i + x; j:= j — x; x:= x — 1 выполнили 25 раз и стало i= j. .

Решение олимпиадной задачи
Доброй ночи! У меня возникла проблема с онлайн проверкой задачи. ссылка на условие мое.

Решение олимпиадной задачи
Условие: Антон, Борис и Василий решили переплыть с одного берега озера на противоположный.

Решение олимпиадной задачи
Есть задача, никак не могу решить не то что решить, но и до конца осознать условие. Буду рад любой.

Qox, создайте два массива: расстояние (отсортировать по возрастанию) и цена (отсортировать по убыванию), перемножьте одинаковые элементы и сложите произведения.

Самому «удаленному» сотруднику предоставляем такси с самым дешевым тарифом. И далее, по убыванию расстояния от дома, увеличиваем стоимость тарифа.

Qox, я не силен в Java, но у меня получилось как-то так, с учетом советов выше. Если есть замечания, пишите, мне только на пользу)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

import java.util.Arrays; import java.util.Collections; import java.util.Scanner; public class Zadanie3 { public static void main(String args[]) { int i,j,k; int sum = 0; Scanner in = new Scanner(System.in); System.out.print("Введите расстояние от офиса до дома: "); int [] S = new int [5]; for (i=0;iS.length;i++) { S[i]=in.nextInt(); } System.out.print("Введите тариф: "); Integer[] T = new Integer [5]; for (j=0;jT.length;j++) { T[j]=in.nextInt(); } System.out.print("Расстояния от офиса до дома (S): "); for(i=0;iS.length;i++) { System.out.print(S[i] + " "); } System.out.println(); System.out.print("Тариф за 1 км (T): "); for (j=0;jT.length;j++) { System.out.print(T[j] + " "); } System.out.println(); System.out.print("Отсортированный массив S: "); Arrays.sort(S); for (i=0; iS.length;i++) { System.out.print(S[i] + " "); } Arrays.sort(T, Collections.reverseOrder()); System.out.println(); System.out.print("Отсортированный массив T: "); for (j=0; jS.length;j++) { System.out.print(T[j] + " "); } System.out.println(); int [] P = new int [5]; for (k=0; kP.length;k++) { P[k] = T[k] * S[k]; sum = sum + P[k]; } System.out.print("Сумма для доставки сотрудников: " + sum); } }

Источник

Олимпиадное программирование java задачи

Войдите, чтобы использовать все возможности RUTUBE

Войдите, чтобы использовать все возможности RUTUBE

Источник

12. Решение задач на условный оператор | Олимпиадное программирование с нуля на Java

Занятие 12. Тема: решение задач на условный оператор. 01:24 Разбор и решение задачи 61 acmp.ru Баскетбол — https://acmp.ru/?main=task&id_task=61 09:22 Разбор и решение задачи 8 acmp.ru Арифметика — https://acmp.ru/?main=task&id_task=8 13:25 Разбор и решение задачи 539 acmp.ru Торт — https://acmp.ru/?main=task&id_task=539 21:14 Разбор и решение задачи 597 acmp.ru Внеземные гости — https://acmp.ru/?main=task&id_task=597 28:12 Разбор и решение задачи 324 acmp.ru Четырехзначный палиндром — https://acmp.ru/?main=task&id_task=324 31:22 Разбор и решение задачи 52 acmp.ru Счастливый билет — https://acmp.ru/?main=task&id_task=52 35:14 Разбор и решение задачи 504 acmp.ru Цветочки — https://acmp.ru/?main=task&id_task=504 42:58 Разбор и решение задачи 26 acmp.ru Две окружности — https://acmp.ru/?main=task&id_task=26 Домашнее задание (постарайтесь не использовать вещественные числа, циклы, массивы): 677 Количество участников олимпиады — https://acmp.ru/?main=task&id_task=677 606 Треугольник — 3 — https://acmp.ru/?main=task&id_task=606 340 Коробки — https://acmp.ru/?main=task&id_task=340 511 Очередь — https://acmp.ru/?main=task&id_task=511 94 Принц и дракон — https://acmp.ru/?main=task&id_task=94 499 Турист — https://acmp.ru/?main=task&id_task=499 667 Автобусы — 2 — https://acmp.ru/?main=task&id_task=667

Источник