Темы
    Информатика(2656 задач)
---> 246 задач <---
Источники --> Командные олимпиады --> Московская командная олимпиада
    8 класс(18 задач)
    9-11 классы(228 задач)
Страница: << 23 24 25 26 27 28 29 >> Отображать по:
#2828
Подтасовка результатов
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В городе Н. олимпиада по информатике состоит из двух туров, каждый из которых оценивается из 400 баллов. Для удобства все её участники занумерованы числами от 1 до N.

Сразу после проведения олимпиады курьер принёс жюри пренеприятнейшее известие: «сверху» пришло указание о том, что некто Вася, выступавший в олимпиаде под номером 1, должен занять как можно более высокое место, то есть как можно меньше участников должны набрать по сумме двух туров больше баллов, чем Вася. При этом места, занятые школьниками в каждом из туров в отдельности, уже опубликованы, и их менять нельзя. Для каждого тура дан список номеров участников в порядке занятого места — перестановка чисел от 1 до N. Теперь работа жюри заключается в том, чтобы расставить целые баллы от 1 до 400 каждому участнику в первом и втором турах таким образом, чтобы в итоговой таблице Вася занял как можно более высокое место, а места участников в каждом из туров не изменились. При этом никакие два участника не должны получить в одном туре одинаковые баллы.

Ваша задача — проделать за жюри такую работу.

Считается, что участник по сумме двух туров занял место A, если ровно A - 1 участников набрали по сумме двух туров строго больше баллов.

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

Сначала вводится целое число N (1 ≤ N ≤ 200) — количество участников олимпиады. Во второй строке перечислены номера участников в порядке занятых мест в первом туре (от первого места до N-го). В третьей строке в таком же формате следует описание второго тура. Номера участников во второй и третьей строках разделены пробелами.

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

Сначала выведите N целых чисел от 1 до 400, соответствующих расстановке баллов участникам первого тура, где i-ое число — балл в первом туре участника, занявшего на нём i-е место, затем аналогично N целых чисел, соответствующих расстановке баллов во втором туре. Числа разделяйте пробелами или переводами строки. Никакие два участника не должны получить одинаковые баллы в одном и том же туре. Если существует несколько способов расставить баллы требуемым образом, выведите любой из них.

Примеры
Входные данные
3
2 1 3
3 1 2
Выходные данные
400 399 1 
400 399 1
Входные данные
3
2 3 1
3 1 2
Выходные данные
400 399 398 
400 399 1
#2829
Прямоугольники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Петя нарисовал на клетчатом листке бумаги красивый рисунок прямоугольной формы. Его младшему брату Васе тоже захотелось порисовать, поэтому он вырезал из того же листка бумаги другой прямоугольник. При этом он не делал лишних разрезов, то есть в результате в листке осталась прямоугольная дырка. Кроме того, линии разреза не проходили (даже частично) по границам рисунка Пети. Более того, по границам рисунка не проходили даже продолжения линий разреза.

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

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

Вам даны 8 целых чисел - x1, y1, x2, y2, x3, y3, x4, y4, где (x1, y1) - координаты левого нижнего угла рисунка Пети, (x2, y2) - координаты правого верхнего угла рисунка. Аналогично, (x3, y3) - координаты левого нижнего угла вырезанного Васей прямоугольника, (x4, y4) - координаты правого верхнего угла вырезанного прямоугольника. Гарантируется, что данные прямоугольники невырождены (x1 < x2, y1 < y2 и аналогичные неравенства для второго набора координат). Листок был не очень большим, поэтому каждое число по модулю не превосходит 104.

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

Выведите YES, если Вася испортил рисунок, и NO в противном случае.

Примеры
Входные данные
1 1 2 2 3 3 4 4
Выходные данные
NO
Входные данные
1 1 3 3 2 2 4 4
Выходные данные
YES
Входные данные
1 1 4 4 2 2 3 3
Выходные данные
YES
#2830
Словарь
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Однажды, разбирая старые книги на чердаке, школьник Вася нашёл англо-латинский словарь. Английский он к тому времени знал в совершенстве, и его мечтой было изучить латынь. Поэтому попавшийся словарь был как раз кстати.

К сожалению, для полноценного изучения языка недостаточно только одного словаря: кроме англо-латинского необходим латинско-английский. За неимением лучшего он решил сделать второй словарь из первого.

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

Помогите Васе выполнить работу по созданию латинско-английского словаря из англо-латинского.

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

В первой строке содержится единственное целое число N (1 ≤ N ≤ 100) — количество английских слов в словаре. Далее следует N описаний. В первой строке каждого описания содержится английское слово. В следующей строке записано единственное число K ≥ 1 — количество переводов. В следующих K строках приведены переводы текущего английского слова на латинский, по одному в каждой строке.

Все слова состоят только из маленьких латинских букв. Общее количество слов на входе не превышает 100. Длина каждого слова не превосходит 15 символов.

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

Выведите соответствующий данному латинско-английский словарь в следующем формате. В первую строку запишите единственное целое число N — количество латинских слов в словаре. Далее выведите N описаний, каждое описание в отдельной строке: сначала латинское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого латинского слова на английский.

При этом порядок английских слов внутри перевода одного латинского может быть каким угодно. Кроме того, порядок следования латинских слов для перевода в словаре также не важен.

Примеры
Входные данные
3
apple
3
malum
pomum
popula
fruit
3
baca
bacca
popum
punishment
2
malum
multa
Выходные данные
7
baca - fruit
bacca - fruit
malum - apple, punishment
multa - punishment
pomum - apple
popula - apple
popum - fruit
#2831
Пешки
  
Темы: [Потоки]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-наверх и вправо-наверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. Поэтому он придумал свой вариант шахмат.

Игра идёт на доске с N строками и M столбцами (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) по следующим правилам. В нижней строке, имеющей номер 1, стоит P белых пешек, белых фигур на доске больше нет. На остальной части доски стоят разные чёрные фигуры (их названия Глеб не знает). Ходят только белые, цель — достичь хотя бы одной пешкой самой верхней строки, имеющей номер N (Глеб слышал, что в этой ситуации из пешки можно сделать ферзя, а с такой силой он безусловно сможет побить все остальные чёрные фигуры).

Как и в настоящих шахматах, если пешка Глеба бьёт чёрную фигуру, то она становится на её место, а побитая фигура убирается с доски. Считается, что Глеб выиграл, если он сумел достичь хотя бы одной пешкой самой верхней строки, в противном случае он проиграл. Помогите ему по заданной конфигурации всех фигур определить, сможет ли он выиграть.

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

Сначала вводятся четыре целых числа N, M, P, K (1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ P ≤ M, 1 ≤ K ≤ (N - 1)M. Далее записано P различных чисел — номера столбцов pj (1 ≤ pj ≤ M), в которых стоят белые пешки. Далее идут K различных пар целых чисел — номера строк и столбцов чёрных фигур ri, ci (2 ≤ ri ≤ N, 1 ≤ ci ≤ M).

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

Если хотя бы одна пешка сможет достичь последнего ряда, выведите YES, в противном случае выведите NO.

Примеры
Входные данные
3 3 2 3
1 3
2 2
3 1
3 3
Выходные данные
YES
Входные данные
4 4 2 4
1 4
3 1
3 2
4 2
4 4
Выходные данные
NO
#3577
Домино
  

Проводя генеральную уборку на дачном чердаке, Саша нашел в комоде кучу доминошек из разных наборов. Каждая доминошка представляет собой прямоугольник, разделенный на две половинки. На каждой из половинок нарисовано от 0 до 6 точек. Ориентации доминошки не имеют — их можно как угодно поворачивать.

В совсем раннем детстве Саша видел, как играют в домино: суть игры заключается в том, что надо брать доминошку и как можно громче колотить ею об стол, крича при этом «рыба!». Услышав доносящийся с чердака грохот, наверх поднялся Сашин дедушка. Он смог объяснить Саше настоящие правила игры в домино: игроки составляют длинную цепочку, в которой соседние доминошки касаются половинками с одинаковым числом точек.

Саше решил называть «дружными доминошками» пару доминошек, которые можно поставить в игре рядом (т.е. доминошки в паре соприкасаются половинками с равными числами) в том или ином порядке. Играть в домино ему не с кем, поэтому Саша развлекается тем, что всевозможными способами составляет пары и считает количество «дружных доминошек».

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

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

В первой строке входного файла содержится натуральное число N — количество доминошек (1 ≤ N ≤ 100 000).

В каждой из последующих строк содержится описание доминошки: два целых числа X и Y (0 ≤ X, Y ≤ 6) — количество точек на каждой из половинок доминошки.

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

Выведите одно число — количество пар «дружных доминошек».

Примечание

Во втором тесте дружными являются следующие пары:

1-2 2-3, 1-2 3-1, 2-3 3-1, 2-3 4-3, 2-3 4-3, 3-1 4-3, 3-1 4-3, 4-3 4-3

В этой задаче для хранения ответа необходим 64-битный тип данных (int64 на языке Pascal и long long на языках C/C++).

Примеры
Входные данные
2
1 2
2 1
Выходные данные
1
Входные данные
5
1 2
2 3
3 1
4 3
4 3
Выходные данные
8
Страница: << 23 24 25 26 27 28 29 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест