Задачи второго этапа республиканской олимпиады по информатике прошлых лет, при решении которых используются массивы
Задача 1 (2010 г). На чемпионате по фигурному катанию оценки выставляют N (3≤N≤10) судей из разных стран. Оценка представляет собой число с одним десятичным знаком после запятой. Все оценки выставляются в диапазоне от 0.0 до 10.0. При подсчете результата, для обеспечения честности судейства, откидывается одна самая большая оценка и одна самая маленькая оценка (если самых больших оценок несколько, то откидывается только одна из них, то же правило действует в отношении самых маленьких оценок). Среди оставшихся оценок высчитывается среднее арифметическое значение, которое округляется по правилам округления до одного знака после запятой. Получившееся число является итоговой оценкой фигуриста. Требуется по имеющимся оценкам судей определить итоговую оценку фигуриста.Примечание:
Округление можно произвести таким образом:
#include <cmath> // подключить библиотеку для round
double value = 4.64459675;
// Положительные числа
cout << round(value*10)/10 << endl; // Округление до первого знака
cout << round(value*100)/100 << endl; // второго
cout << round(value*1000)/1000 << endl; // третьего
cout << round(value*10000)/10000 << endl; // четвертого
// Отрицательные числа
cout << round(-value*10)/10 << endl; // Округление до первого знака
cout << round(-value*100)/100 << endl; // второго
cout << round(-value*1000)/1000 << endl; // третьего
cout << round(-value*10000)/10000 << endl; // четвертого
Результат:
Результат:
4.6
4.64
4.645
4.6446
-4.6
-4.64
-4.645
-4.6446
Формат ввода:
В первой строке ввода находится единственное число N (3≤N≤10) – число судей.
Во второй строке вводится N чисел через пробелы – баллы, которые выставили судьи.
Формат вывода:
Вывести число – итоговую оценку фигуриста.
Примеры:
Задача 2 (2010 г). Вы решили купить торт цилиндрической формы с радиусом основания R (1≤R≤100). Конечно же, торт нужно упаковать. Для упаковки торта предлагается выбрать одну из N (1≤N≤1000) коробок, о которых известно следующее:
1) коробки имеют стандартную высоту, которая подходит для упаковки вашего торта;
2) основания коробок - прямоугольники, с длинами сторон А: (1≤А≤100) см и В: (1≤В≤100) см;
3) стоимость коробки зависит от площади основания коробки и равна С (1 ≤С ≤100) рублей за см² площади основания.
Выберите подходящую для упаковки торта коробку наименьшей стоимости.
Формат ввода:
В первой строке ввода находятся три числа через пробел R (1≤R≤100) – радиус основания торта, N (1≤N≤1000) – число коробок, С (1 ≤С ≤100) – стоимость за 1 см² основания коробки.
Далее идет N строк, в каждой указаны два числа – длины сторон i-той коробки.
Формат вывода:
В первой строке вывести число – номер коробки.
Во второй строке вывести число – стоимость коробки в рублях.
Примеры:
Задача 3 (2011 г)
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Ввод: с клавиатуры
Вывод: на экран
Одна очень не знаменитая (пока не знаменитая) компания «Brain Coders» решила выпустить новую операционную систему «Winux».
Перед менеджером проекта стало очень много вопросов. Каким образом реализовать взаимодействие пользователя с новой операционной системой? Использовать ли мышку? Может сделать так, чтобы курсор можно было бы передвигать усилием мысли? Всё потому, что у этой компании есть аппарат, который может анализировать мозговые импульсы.
Эти вопросы мучали менеджера очень долго. И он решил: пусть ответ на него даст его любимая монетка. Если выпадает «орёл», то в новой операционной системе будет использоваться мышка, если выпадает «решка», то нет.
Но вот незадача: менеджер кинул монетку, а она закатилась под диван, где было очень-очень много других монеток. Как теперь узнать, что выпало? Однако менеджер точно помнил вес своей любимой монеты. Он узнал веса всех остальных и теперь хочет найти его любимую. Вам, как ведущему программисту, доверена ответственная задача – помочь своему менеджеру.
Формат ввода:
Формат вывода:
В единственной строке вывода должно содержаться единственное число – номер любимой монетки менеджера, вес которой равен m.
Тесты Посмотреть решение
Задача 5. Апокалипсис (2014 г.)
Ограничение по времени: 2 секунды
Формат ввода:
В первой строке ввода находится единственное число N (3≤N≤10) – число судей.
Во второй строке вводится N чисел через пробелы – баллы, которые выставили судьи.
Формат вывода:
Вывести число – итоговую оценку фигуриста.
Примеры:
Ввод
|
Вывод
|
4
5.4 6.5 5.7 2.3
|
5.6
|
Задача 2 (2010 г). Вы решили купить торт цилиндрической формы с радиусом основания R (1≤R≤100). Конечно же, торт нужно упаковать. Для упаковки торта предлагается выбрать одну из N (1≤N≤1000) коробок, о которых известно следующее:
1) коробки имеют стандартную высоту, которая подходит для упаковки вашего торта;
2) основания коробок - прямоугольники, с длинами сторон А: (1≤А≤100) см и В: (1≤В≤100) см;
3) стоимость коробки зависит от площади основания коробки и равна С (1 ≤С ≤100) рублей за см² площади основания.
Выберите подходящую для упаковки торта коробку наименьшей стоимости.
Формат ввода:
В первой строке ввода находятся три числа через пробел R (1≤R≤100) – радиус основания торта, N (1≤N≤1000) – число коробок, С (1 ≤С ≤100) – стоимость за 1 см² основания коробки.
Далее идет N строк, в каждой указаны два числа – длины сторон i-той коробки.
Формат вывода:
В первой строке вывести число – номер коробки.
Во второй строке вывести число – стоимость коробки в рублях.
Примеры:
Ввод
|
Вывод
|
1 3 4
2 1
2 3
4 3
|
2
24
|
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Ввод: с клавиатуры
Вывод: на экран
Одна очень не знаменитая (пока не знаменитая) компания «Brain Coders» решила выпустить новую операционную систему «Winux».
Перед менеджером проекта стало очень много вопросов. Каким образом реализовать взаимодействие пользователя с новой операционной системой? Использовать ли мышку? Может сделать так, чтобы курсор можно было бы передвигать усилием мысли? Всё потому, что у этой компании есть аппарат, который может анализировать мозговые импульсы.
Эти вопросы мучали менеджера очень долго. И он решил: пусть ответ на него даст его любимая монетка. Если выпадает «орёл», то в новой операционной системе будет использоваться мышка, если выпадает «решка», то нет.
Но вот незадача: менеджер кинул монетку, а она закатилась под диван, где было очень-очень много других монеток. Как теперь узнать, что выпало? Однако менеджер точно помнил вес своей любимой монеты. Он узнал веса всех остальных и теперь хочет найти его любимую. Вам, как ведущему программисту, доверена ответственная задача – помочь своему менеджеру.
Формат ввода:
В первой строке находятся числа N, m (1 ≤ N, m ≤ 100) – количество взвешенных монеток и вес любимой монетки менеджера соответственно.
Во второй строке находится N чисел (a1, a2, a3, … , aN) – вес каждой монеты. Известно, что вес – натуральное число, не превышающие 100 (1 ≤ ai ≤ 100, где ai – вес i-ой монетки).
Гарантируется, что на вводе будет монетка, вес которой равен m, причём только одна.Во второй строке находится N чисел (a1, a2, a3, … , aN) – вес каждой монеты. Известно, что вес – натуральное число, не превышающие 100 (1 ≤ ai ≤ 100, где ai – вес i-ой монетки).
Формат вывода:
В единственной строке вывода должно содержаться единственное число – номер любимой монетки менеджера, вес которой равен m.
Задача 4 (2012 г)
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Ввод: с клавиатуры
Вывод: на экран
Питер и Мика хорошие друзья и коллеги по работе, очень сложной, ответственной и к тому ещё засекреченной работе, о которой нам, увы, нельзя ничего говорить в целях защиты серьёзного дела, которым они занимаются.
Однажды они собрались, чтобы сыграть в одну очень интересную игру.
На столе лежит N карточек в ряд, на каждой написано некоторое число. Питер и Мика по очереди их вытягивают, начиная с самой левой карты и заканчивая самой правой. Первой начинает Мика. Достав определённую карточку, Мика записывает число на ней (умноженное на 2) себе на листик. Затем карточку тянет Питер и записывает вытянутое число в свой листик только уже умноженное на 3. После Питера, карточку опять тянет Мика, дописав новое число, умноженное на 4, в свой листок и так далее, пока не закончатся все карточки, находящиеся на столе.
После, каждый игрок подсчитывает сумму чисел, которую он получил. Выигрывает тот, у кого она больше. Питер и Мика очень занятые люди и они не хотят терять время понапрасну, например, на подсчёты заработанных очков. Поэтому они обратились к вам за помощью.
Формат ввода:
В первой строке находится целое число N (1 ≤ N ≤ 100) – количество карточек, выложенных на столе.
Во второй строке находятся N чисел (a1, a2, a3, … , aN)
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Ввод: с клавиатуры
Вывод: на экран
Питер и Мика хорошие друзья и коллеги по работе, очень сложной, ответственной и к тому ещё засекреченной работе, о которой нам, увы, нельзя ничего говорить в целях защиты серьёзного дела, которым они занимаются.
Однажды они собрались, чтобы сыграть в одну очень интересную игру.
На столе лежит N карточек в ряд, на каждой написано некоторое число. Питер и Мика по очереди их вытягивают, начиная с самой левой карты и заканчивая самой правой. Первой начинает Мика. Достав определённую карточку, Мика записывает число на ней (умноженное на 2) себе на листик. Затем карточку тянет Питер и записывает вытянутое число в свой листик только уже умноженное на 3. После Питера, карточку опять тянет Мика, дописав новое число, умноженное на 4, в свой листок и так далее, пока не закончатся все карточки, находящиеся на столе.
После, каждый игрок подсчитывает сумму чисел, которую он получил. Выигрывает тот, у кого она больше. Питер и Мика очень занятые люди и они не хотят терять время понапрасну, например, на подсчёты заработанных очков. Поэтому они обратились к вам за помощью.
Формат ввода:
В первой строке находится целое число N (1 ≤ N ≤ 100) – количество карточек, выложенных на столе.
Во второй строке находятся N чисел (a1, a2, a3, … , aN)
Формат вывода:
В единственной строке вывода должно содержаться одно слово: “Won”, если выиграл Питер или “Lost”, если выиграла Мика. В случае одинакового количества набранных баллов выведите символ “?”.
В единственной строке вывода должно содержаться одно слово: “Won”, если выиграл Питер или “Lost”, если выиграла Мика. В случае одинакового количества набранных баллов выведите символ “?”.
Задача 5. Апокалипсис (2014 г.)
Ограничение по времени: 2 секунды
Ограничение по памяти: 32 мегабайта
Ввод: с клавиатуры
Вывод: на экран
Во время апокалипсиса, когда перестают работать все магазины, улицы пусты, привычные нам удобства жизни уже недоступны, а о существовании государства говорить бессмысленно, самыми ценными вещами стали банки тушёнки и спички для того, чтобы постоянно поддерживать огонь, греясь холодными ночами и утолять голод в столь сложное время.
Дмитрий всю жизнь проработал на предприятии специализировавшимся на производстве тушёнки. Когда дела во всём мире пошли плохо, зарплату работникам начали выдавать банками тушёнки. Теперь Диме долгое время нет нужды сильно заботится о пропитании. Однако спички у него уже закончились.
Дима знает о том, что несколько людей могут обменять тушёнку на спички, однако у каждого свои условия: он готов поменять В банок тушёнки на S штук спичек. Дима хочет обменять тушёнку на 1000 спичек и по самому выгодному тарифу. В это тяжелое время даже грамм тушёнки весьма ценится, поэтому люди могут обмениваться неполными банками тушёнки. Помогите Диме определить какое минимальное количество банок тушёнки ему нужно отдать, чтобы получить желаемые 1000 штук спичек.
Формат ввода
В первой строке ввода содержится целое число N - общее количество людей, предлагающих обмен тушёнки на спички (1 <= N <= 100).
В следующих N строках содержатся пары чисел Bi и Si (1 <= Bi <= 100, 1 <= Si <= 1000), где i=1..N, Bi - количество банок тушёнки, которое обменьщик ожидает за Si штук спичек.
Формат вывода
Выведите минимальное количество банок тушёнки, необходимое для обмена на 1000 штук спичек с точностью до двух знаков после запятой (у Димы нет более точных весов для замера веса неполных банок).
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Формат ввода:
Первая строка ввода содержит два целых числа N и M
(3 ≤ N ≤ 100, 5 ≤ M ≤ 500 000).
В следующей строке записаны N целых чисел через пробел: ai – количество килограмм в i-ом ящике. Все числа положительные, не превосходящие 100 000.
Гарантируется, что всегда можно выбрать три ящика, чтобы суммарный вес вещей, лежащих в них, не превысил вместимость чемодана.
Формат вывода:
Выведите единственное число – максимально возможное количество килограмм, которыми можно наполнить чемодан Хелены с помощью трёх ящиков.
Примеры:
Задача 2 (2009 г)
Метрополитен города Глупова состоит из единственной одноколейной линии. В нулевой момент времени с начальной и конечной станции этой линии навстречу друг другу начинают двигаться два поезда. Поезда останавливаются на всех промежуточных станциях. На каждой станции поезда стоят одно и то же фиксированное время. Между станциями поезда движутся с одной и той же фиксированной скоростью. Требуется определить, где и когда поезда столкнутся.
Входные данные:
В первой строке содержится целое число N (2≤N≤100) - количество станций на линии. Во второй строке содержится N-1 вещественное число - расстояние от начальной станции до второй, от начальной до третьей и т.д., от начальной до N-ой станции.
В третьей строке содержится два вещественных числа - скорость движения поездов и время пребывания поездов на станции.
Выходные данные:
В первой строке вывести с точностью до двух знаков после десятичной точки расстояние от начальной станции до места столкновения. Во второй строке вывести время с точностью до двух знаков после десятичной точки.
Пример:
Во время апокалипсиса, когда перестают работать все магазины, улицы пусты, привычные нам удобства жизни уже недоступны, а о существовании государства говорить бессмысленно, самыми ценными вещами стали банки тушёнки и спички для того, чтобы постоянно поддерживать огонь, греясь холодными ночами и утолять голод в столь сложное время.
Дмитрий всю жизнь проработал на предприятии специализировавшимся на производстве тушёнки. Когда дела во всём мире пошли плохо, зарплату работникам начали выдавать банками тушёнки. Теперь Диме долгое время нет нужды сильно заботится о пропитании. Однако спички у него уже закончились.
Дима знает о том, что несколько людей могут обменять тушёнку на спички, однако у каждого свои условия: он готов поменять В банок тушёнки на S штук спичек. Дима хочет обменять тушёнку на 1000 спичек и по самому выгодному тарифу. В это тяжелое время даже грамм тушёнки весьма ценится, поэтому люди могут обмениваться неполными банками тушёнки. Помогите Диме определить какое минимальное количество банок тушёнки ему нужно отдать, чтобы получить желаемые 1000 штук спичек.
Формат ввода
В первой строке ввода содержится целое число N - общее количество людей, предлагающих обмен тушёнки на спички (1 <= N <= 100).
В следующих N строках содержатся пары чисел Bi и Si (1 <= Bi <= 100, 1 <= Si <= 1000), где i=1..N, Bi - количество банок тушёнки, которое обменьщик ожидает за Si штук спичек.
Формат вывода
Выведите минимальное количество банок тушёнки, необходимое для обмена на 1000 штук спичек с точностью до двух знаков после запятой (у Димы нет более точных весов для замера веса неполных банок).
Задания для самостоятельной работы
Задача 1 (2012 г.)Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Ввод: с клавиатуры
Вывод: на экран
Близкая подруга Мики – Хелена собирается переезжать со своей старой квартиры в новый роскошный дом, который находится в городе Ататата. Поэтому ей необходимо перевезти свои вещи из N ящиков старой квартиры, где она жила.
У Хелены есть чемодан вместимостью M килограмм. В каждом из N ящиков находятся вещи весом ai килограмм. Хелена хочет освободить полностью три ящика, выгрузив вещи из них в свой чемодан. Понятно, что он может оказаться неполным, поэтому Хелена хочет выбрать три таких ящика, чтобы минимизировать оставшееся свободное место в чемодане. Помогите ей в этом.
Вывод: на экран
Близкая подруга Мики – Хелена собирается переезжать со своей старой квартиры в новый роскошный дом, который находится в городе Ататата. Поэтому ей необходимо перевезти свои вещи из N ящиков старой квартиры, где она жила.
У Хелены есть чемодан вместимостью M килограмм. В каждом из N ящиков находятся вещи весом ai килограмм. Хелена хочет освободить полностью три ящика, выгрузив вещи из них в свой чемодан. Понятно, что он может оказаться неполным, поэтому Хелена хочет выбрать три таких ящика, чтобы минимизировать оставшееся свободное место в чемодане. Помогите ей в этом.
Формат ввода:
Первая строка ввода содержит два целых числа N и M
(3 ≤ N ≤ 100, 5 ≤ M ≤ 500 000).
В следующей строке записаны N целых чисел через пробел: ai – количество килограмм в i-ом ящике. Все числа положительные, не превосходящие 100 000.
Гарантируется, что всегда можно выбрать три ящика, чтобы суммарный вес вещей, лежащих в них, не превысил вместимость чемодана.
Формат вывода:
Выведите единственное число – максимально возможное количество килограмм, которыми можно наполнить чемодан Хелены с помощью трёх ящиков.
Примеры:
Ввод
|
Вывод
|
4 10
5 1 1 4
|
10
|
4 8
1 20 3 3
|
7
|
Задача 2 (2009 г)
Метрополитен города Глупова состоит из единственной одноколейной линии. В нулевой момент времени с начальной и конечной станции этой линии навстречу друг другу начинают двигаться два поезда. Поезда останавливаются на всех промежуточных станциях. На каждой станции поезда стоят одно и то же фиксированное время. Между станциями поезда движутся с одной и той же фиксированной скоростью. Требуется определить, где и когда поезда столкнутся.
Входные данные:
В первой строке содержится целое число N (2≤N≤100) - количество станций на линии. Во второй строке содержится N-1 вещественное число - расстояние от начальной станции до второй, от начальной до третьей и т.д., от начальной до N-ой станции.
В третьей строке содержится два вещественных числа - скорость движения поездов и время пребывания поездов на станции.
Выходные данные:
В первой строке вывести с точностью до двух знаков после десятичной точки расстояние от начальной станции до места столкновения. Во второй строке вывести время с точностью до двух знаков после десятичной точки.
Пример:
Входные данные: Выходные данные:
3 0.63
0.25 2.25 1.63
1 1 