Темы --> Информатика --> Язык программирования
    Процедуры и функции(96 задач)
    Массивы(232 задач)
    Типы данных(356 задач)
    Циклы(177 задач)
    Условный оператор (if)(164 задач)
    Python(260 задач)
    Standard Template Library(2 задач)
---> 952 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 173 174 175 176 177 178 179 >> Отображать по:
#111989
Телефон
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

У бизнесмена есть телефон, который он использует для связи с партнерами по бизнесу. Сегодня у предпринимателя запланировано n разговоров, про каждый из которых известно число Pi — сколько рублей прибыли получит бизнесмен, если i-й разговор состоится (Pi может быть равно 0 — в этом случае никакой выгоды от i-го разговора нет).

Телефон у бизнесмена сделан по новейшим технологиям, но иногда барахлит. Сегодня, например, телефон внезапно разрядился, поэтому он позволит бизнесмену провести только первые A0 разговоров, а затем выключится до конца дня. Однако телефон можно зарядить, пропустив несколько первых запланированных разговоров. Более формально, если предприниматель будет заряжать телефон вместо первых j разговоров (то есть разговоров с номерами от 1 до j), то он потом сможет провести ровно Aj разговоров (с номерами от j + 1 до min(n, j + Aj)), после чего телефон опять же перестанет работать до конца дня.

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

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

На вход программе дается целое число n — количество запланированных звонков (1 ≤ n ≤ 2·105). На следующей строке вводятся через пробел \(n\) целых чисел Pi, обозначающие прибыли от звонков (0 ≤ Pi ≤ 1 000). Затем вводятся \(n+1\) целых чисел Aj, обозначающие, сколько звонков можно будет провести после подзарядки (0 ≤ Aj ≤ 106).

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

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

Примеры тестов

Входные данные
5
1 2 0 4 1
2 0 8 3 5 6
Выходные данные
5 3

Примечание

Рассмотрим пример из условия: n = 5, P1 = 1, P2 = 2, P3 = 0, P4 = 4, P5 = 1, A0 = 2, A1 = 0, A2 = 8, A3 = 3, A4 = 5, A5 = 6.

Если бизнесмен не будет заряжать телефон, то результат будет равен P1 + P2 = 1 + 2 = 3 рубля. Если предприниматель будет заряжать телефон вместо первого звонка, то он не сможет позвонить ни разу, так как A1 = 0. Если вместо первых двух звонков, то результат составит P3 + P4 + P5 = 0 + 4 + 1 = 5 рублей. Если вместо первых трех, то P4 + P5 = 4 + 1 = 5. Если вместо четырёх звонков, то P5 = 1 рубль. Наконец, если бизнесмен будет заряжать телефон вместо всех n = 5 звонков, то он заведомо ничего не получит. Таким образом, два лучших варианта — это заряжать либо вместо 2 первых звонков, либо вместо 3, в обоих случаях получаем 5 рублей прибыли. По условию, из них мы выбираем выбираем вариант с 3 пропущенными звонками.

Тесты к этой задаче состоят из трех групп.

  • Тест 1 — тест из условия, оценивается в ноль баллов.
  • Тесты 2 – 19. В тестах этой группы 1 ≤ n ≤ 104. Эта группа оценивается в 50 баллов, баллы ставятся только при прохождении всех тестов группы.
  • Тесты 20 – 36. В тестах этой группы дополнительные ограничения отсутствуют. Группа оценивается в 50 баллов, баллы ставятся только при прохождении всех тестов этой и предыдущих групп.

#111990
Тетрадка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Формально, дана двухмерная таблица из нулей и единиц — часть тетрадки, которую видит Вася. Единицей обозначается закрашенный участок, а нулем — незакрашенный. Назовём вертикальной линией столбец таблицы, все элементы которого — единицы, а горизонтальной линией — строку таблицы, все элементы которой — единицы. Гарантируется, что каждая единица в таблице содержится в какой-либо линии.

Тетрадкой в клетку называется тетрадка, в которой содержатся вертикальные и горизонтальные линии. Тетрадкой в линейку называется тетрадка, в которой содержатся только горизонтальные линии. Тетрадкой в вертикальную линейку называется тетрадка, в которой содержатся только вертикальные линии.

Известно, что в целой тетрадке все расстояния между линиями одинаковы (то есть все клетки — квадраты, все линейки одинаковой ширины). Гарантируется, что линии не могут располагаться рядом (между ними всегда есть промежуток).

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

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

В первой строке входных данных даны целые числа n и m (1 ≤ n, m ≤ 1 000) — количество строк и столбцов в таблице. Следующие n строк по m чисел содержат целые числа ai, j (0 ≤ ai, j ≤ 1) — элементы таблицы, задающие видимую часть тетради.

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

Требуется вывести одну из строк:

  • «Square», если заданная тетрадка расчерчена в клетку;
  • «Line», если тетрадка расчерчена в линейку;
  • «Vertical line», если тетрадка расчерчена в вертикальную линейку;
  • «?», если невозможно однозначно определить, к какому типу относится данная тетрадь.

Примеры тестов

Входные данные
3 5
00100
11111
00100
Выходные данные
Square
Входные данные
4 5
11111
00000
11111
00000
Выходные данные
Line
Входные данные
5 5
00000
00000
11111
00000
00000
Выходные данные
?

Примечание

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

#112002
На краю доски
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Однажды на уроке биологии Петя решил заполнить таблицу n × m числами от 1 до mn по строкам (пример заполнения для n = 3 , m = 4 показан на рисунке). Когда он закончил свой труд, его сосед Коля заинтересовался, можно ли по числу X определить, записано оно на краю таблицы или нет. Помогите Коле.

Под фразой "на краю" имеется в виду, что число X стоит в первом столбце или в первой строке или в последнем столбце или в последней строке.

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

В первой строке даны два целых числа n и m ( n , m ≤ 20 ). Во второй строке дано одно целое число X ( 1 ≤ X ≤ nm ).

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

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

Примеры
Входные данные
3 4
8
Выходные данные
YES
Входные данные
3 4
6
Выходные данные
NO
#112015
Поле чудес
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Поле Чудес представляет из себя прямоугольную грядку размером n × m лунок, в каждую из которых можно закопать одну монету. Буратино зарыл на Поле Чудес все имевшиеся у него монеты, благоразумно составив карту посадок – звездочками он отмечал лунки, в которых лежат монеты, а точками — лунки без монет.

Теперь его интересует вопрос: а каких лунок больше – с монетами или без? Сколько было у него монет, он, к сожалению, не помнит.

Помогите Буратино справиться с этой задачей.

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

В первой строке даны два целых числа n и m – размеры грядки ( 1 ≤ n , m ≤ 20 ). В следующих n строках по m символов перечисляется содержимое грядки (точками отмечена пустая лунка, звездочкой – с монетой).

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

Выведите число 1, если лунок с монетами больше, чем пустых, число 2, если пустых лунок больше, чем полных и число 0, если их количества равны.

Примеры
Входные данные
3 3
**.
.**
*.*
Выходные данные
1
#112016
Игра
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Крокодил Гена с Чебурашкой играли в какую-то игру, выписывая числа в клетки квадратной таблицы n × n . Однако, когда таблица была заполнена целиком, выяснилось, что правила игры они забыли. Тогда Чебурашка предложил подсчитать числа на главной диагонали квадрата и на побочной диагонали, и если на главной диагонали сумма чисел больше, чем на побочной, то выигрывает Гена, если меньше, то Чебурашка, а если суммы равны, то объявляется ничья.

Таблица была большая и Чебурашка с Геной боятся ошибиться при подсчете. Помогите им определить, чем закончилась игра.

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

В первой строке дано одно целое число n – размер таблицы ( 1 ≤ n ≤ 20 ). Дальше идут n строк по n неотрицательных чисел в каждой – заполненная после окончания игры таблица. Все числа не превышают 100 .

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

Выведите 1, если выиграл Крокодил Гена, 2, если выиграл Чебурашка, и 0, если была ничья

Примеры
Входные данные
3
1 2 3
4 5 6
7 8 0
Выходные данные
2
Страница: << 173 174 175 176 177 178 179 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест