12 грудня 2010 р. ІІ етап Всеукраїнської учнівської олімпіади з інформатики для 8-11 класів Зернини



Скачати 90.84 Kb.
Дата конвертації23.01.2018
Розмір90.84 Kb.

12 грудня 2010 р.

ІІ етап Всеукраїнської учнівської олімпіади з інформатики

для 8-11 класів
1. Зернини
Ім'я вхідного файлу: Input.txt.

Ім'я вихідного файлу: Output.txt.
У банці знаходяться білі та чорні зернини. Кожного разу з банки виймають навмання дві зернини. Якщо вони однакового кольору, то їх викидають, а до банки кладуть чорну зернину (чорних зернин у достатній кількості). Якщо ж зернини різного кольору, то чорну викидають, а білу повертають до банки. Ці дії повторюють, доки не залишиться одна зернина.

Завдання Напишіть програму, яка за відомою кількістю чорних та білих зернин визначає колір останньої зернини.

Вхідні данні. У єдиному рядку записані два числа – кількість білих та чорних зернин.

Вихідні данні. Єдиний рядок вихідного текстового файлу має містити колір зернини, що залишилася: white – якщо зернина біла, black – якщо зернина чорна.

Приклад вхідних і вихідних даних:


Input.txt

Output.txt

4 3

black


2. Найбільший добуток
Ім'я вхідного файлу: Input.txt.

Ім'я вихідного файлу: Output.txt.

Максимальний час роботи на одному тесті: 5 секунд.
Дано N цілих чисел.

Завдання. Необхідно вибрати з N цілих чисел три таких числа, добуток яких максимальний.

Вхідні данні. Перший рядок вхідного файлу містить одне число N – кількість чисел у послідовності (3 N 106). У друго­му рядку записано саму послідовність: N цілих чисел, які за модулем не перевищують 30000.

Вихідні данні. У вихідний файл виведіть три шуканих числа в довільному порядку. Якщо існує декілька різних трійок чисел, які дають максимальний добуток, то виведіть довільну з них.

Приклад вхідних і вихідних даних:

Input.txt

Output.txt

9

9 10 9

3 5 1 7 9 0 9 –3 10




3

–5 30000 12

–5 30000 12




12 грудня 2010 р.

ІІ етап Всеукраїнської учнівської олімпіади з інформатики

для 8-11 класів

3. Купівля квитків
Ім'я вхідного файлу: Input.txt.

Ім'я вихідного файлу: Output.txt.

Максимальний час роботи на одному тесті: 5 секунд.

Максимальний об'єм використаної пам'яті: 4 Мбайти.
За квитками на прем'єру нового мюзиклу зібралася черга з N осіб, кожна з яких хоче купити 1 квиток. На всю чергу працювала тільки одна каса, тому продаж квитків просувався дуже повільно, від чого «клієнти» черги впадали у відчай. Найкмітливіші швидко примітили, що, як правило, декілька квитків у одні руки касир продає швидше, ніж коли ці ж квитки продаються по одному. Тому вони запропонували декільком людям, які стоять поряд, віддавати гроші першому з них, щоб він купив квитки на всіх.

Але для боротьби зі спекулянтами касир продавала не більше 3-х квитків в одні руки, тому домовитися таким чином між собою могли лише 2 або 3 особи, які стоять поряд.

Відомо, що на продаж і особі з черги одного квитка касир витра­чає Аі секунд, на продаж двох квитків – Ві секунд, трьох квитків – Сi секунд.

Завдання. Напишіть програму, яка визначить мінімальний час, за який можна було б обслужити всіх покупців.

Зверніть увагу, що квитки на групу людей, що об'єднались, завжди купує перший із них. Також ніхто з метою прискорення не купує зайвих квитків (тобто квитків, які нікому не потрібні).



Вхідні данні. Перший рядок вхідного файлу містить єдине число N – кількість покупців в черзі (1N5000). У кожному з наступних N рядків записано трійку натуральних чисел Аі, Bi, Сi. Кожне з цих чисел не перевищує 3600. Люди в черзі нумеруються, починаючи від каси.

Вихідні данні. Вихідний файл містить одне число – мінімальний час у секундах, за який можна було б обслужити всіх покупців.

Приклад вхідних і вихідних даних:


Input.txt

Output.txt

5

12

5 10 15




2 10 15




5 5 5




20 20 1




20 1 1




2

4

3 4 5




1 1 1






12 декабря 2010 г.

ІІ этап Всеукраинской ученической олимпиады по информатике

для 8-11 классов

1. Зернышки
Имя входного файла: Input.txt.

Имя выходного файла: Output.txt.
В банке находятся белые и черные зернышки. Каждый раз из банки вынимают наугад два зернышка. Если они одинакового цвета, то их выбрасывают, а в банку кладут черное зернышко (черных зернышек достаточное количество). Если же зернышки разного цвета, то черное зернышко выбрасывают, а белое возвращают в банку. Эти действия повторяют, пока не останется одно зернышко.

Задание. Напишите программу, которая по известному количеству черных и белых зернышек определяет цвет последнего зернышка.

Входные данные. В единственной строке записаны два числа – количество белых и черных зернышек.

Выходные данные. Единственная строка выходного текстового файла должна содержать цвет оставшегося зернышка: white – если зернышко белое, black – если зернышко черное.

Пример входных и выходных данных:


Input.txt

Output.txt

4 3

black


2. Наибольшее произведение
Имя входного файла: Input.txt.

Имя выходного файла: Output.txt.

Максимальное время работы на одном тесте: 5 секунд.

Дано N целых чисел.



Задание. Необходимо выбрать из N целых чисел три таких числа, произведение которых максимально.

Входные данные. Первая строка входного файла содержит одно число N – количество чисел в последовательности (3 N 106). Во второй строке записана сама последовательность: N целых чисел, которые по модулю не превышают 30000.

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

Пример входных и выходных данных

Input.txt

Output.txt

9

9 10 9

3 5 1 7 9 0 9 –3 10




3

–5 30000 12

–5 30000 12




12 декабря 2010 г.

ІІ этап Всеукраинской ученической олимпиады по информатике

для 8-11 классов

3. Покупка билетов
Имя входного файла: Input.txt.

Имя выходного файла: Output.txt.

Максимальное время работы на одном тесте: 5 секунд.

Максимальный объем использованной памяти: 4 Мбайты.
За билетами на премьеру нового мюзикла собралась очередь из N лиц, каждое из которых хочет купить 1 билет. На всю очередь работала только одна касса, потому продажа билетов продвигалась очень медленно, от чего «клиенты» очереди впадали в отчаяние. Самые сообразительные быстро приметили, что, как правило, несколько билетов в одни руки кассир продает быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким людям, которые стоят рядом, отдавать деньги первому из них, чтобы он купил билеты на всех.

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

Известно, что на продажу і лицу из очереди одного билета кассир тратит Аі секунд, на продажу двух билетов – Ві секунд, трёх билетов – Сi секунд.

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

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



Входные данные. Первая строка входного файла содержит единственное число N – количество покупателей в очереди (1N5000). В каждой из следующих N строк записана тройка натуральных чисел Аі, Bi, Сi. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы

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

Пример входных и выходных данных

Input.txt

Output.txt

5

12

5 10 15




2 10 15




5 5 5




20 20 1




20 1 1




2

4

3 4 5




1 1 1





Поділіться з Вашими друзьями:


База даних захищена авторським правом ©wishenko.org 2017
звернутися до адміністрації

    Головна сторінка