Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 5.00/47: Рейтинг темы: голосов - 47, средняя оценка - 5.00
125 / 117 / 67
Регистрация: 07.11.2014
Сообщений: 788

Разбор задач второго этапа Республиканской олимпиады по информатике, 9-11 классы,РК I-II туры

09.12.2016, 11:02. Показов 9409. Ответов 27
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте. На днях(8-9 декабря) прошел районный этап Республиканской олимпиады по информатике в Казахстане. Всего в этапе было два тура. Задачи были не сложными, а скорее легкими. Но для школьников - то что надо. И так, условия задач:
Задача A

Дана последовательность чисел A длины N. Требуется вывести в обратном порядке.
Формат входных данных
Первая строка входного файла содержит целое число N (1 <= N <= 1 000 000) - длину последовательности. Вторая строка входного файла содержит N целых чисел - элементы последовательности A. Все элементы последовательности не превосходят 100000 по абсолютному значению.
Формат выходных данных
В единственной строке выходного файла выведите элементы последовательности A в обратном порядке. Для наглядности обратите внимание на примеры.
Примеры
A.in:
3
1 2 3
A.out:
3 2 1


Задача B

Две кошки загнали мышь в трубу. Первая кошка находится в точке с координатой x, вторая кошка находится в точке с координатой y, мышь находится в координате z. Определите, какая из кошек первой доберется до мыши, если кошки передвигаются с одинаковой скоростью. В случае если кошки одновременно добираются до мыши, то тогда кошки ссорятся из-за добычи, и мышь ускользает от них.
Формат входных данных
Единственная строка входного файла содержит три целых числа x,y,z(1<=x,y,z<=1000). Все числа различны.
Формат выходных данных
Если первая кошка доберется до мышки раньше второй выведите "1"(без кавычек). В случае если вторая кошка доберется до мыши раньше первой выведите "2"(без кавычек). В случае если мышка ускользает выведите "3"(без кавычек).
Примеры
B.in
1 5 2
B.out
1
B.in
5 1 2
B.out
2


Задача C
Даны целые числа a,b и n. Требуется найти количество целых чисел x таких, что 0<=x<=n-1 и число a*x при делении на n дает остаток b.
Формат входных данных
Единственная строка входного файла содержит три целых числа, разделенных пробелом: a,b и n (0<=n<=100000, 0<=a,b<100000).
Формат выходных данных
Выведите ответ к задаче
Примеры
C.in
3 0 6
C.out
3


Задача D
Даны 5 целых чисел. Посчитайте минимально возможную и максимально возможные суммы, выбрав ровно 4 числа из заданных изначально.
Формат входных данных
Единственная строка входного файла содержит 5 целых чисел. Все числа не превосходят 100 по абсолютному значению.
Формат выходных данных
Выведите минимально возможную и максимально возможную сумму, разделенные пробелом.
Примеры
D.in
1 2 3 4 5
D.out
10 14
D.in
1 1 1 1 2
D.out
4 5

Задача E
Батырхан любит числа, которые без остатка делятся на число 3. К сожалению, для очень больших чисел он не может проверить должен ли он любить его или нет. Помогите ему написав программу, которая поможет ему!Формат входных данных
Единственная строка входного файла содержит X - число, которое необходимо проверить (0<=X<=https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{1000})
Формат выходных данных
Выведите "YES" (без кавычек), если X без остатка делится на 3, иначе выведите "NO" (без кавычек).
Примеры
E.in
111
E.out
YES
E.in
5
E.out
NO

Задача F
Вам дан массив A длины n. Вы можете удалить некоторые элементы из него, при этом после всех удалении элементы должны стоять в строго возрастающем порядке. Выведите максимальную возможную длину массива после всех удалении.
Формат входных данных
Первая строка входного файла содержит целое число N (1 <= N <= 1 000 000) - длину последовательности. Вторая строка входного файла содержит N целых чисел - элементы последовательности A. Все элементы последовательности не превосходят 100 000 000 по абсолютному значению.
Формат выходных данных
Выведите ответ к задаче.
Примеры
F.in
4
4 1 2 3
F.out
3
Комментарий: Необходимо удалить 4, тогда результирующий массив будет 1 2 3

Решение задачи A:
Нужно просто выводить массив от конца(i = N-1) до начала(i>=0):
Код
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int N; cin>>N;
int *array = new int[N];
for(int i = 0; i < N; i++) cin>>array[i];
for(int i = N-1; i >=0; i--) cout<<array[i]<<" ";
}

Решение задачи B:
Простая геометрия. Находим точку, которая будет иметь наименьшее расстояние до z.
Код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int x,y,z;
cin>>x>>y>>z;
if (abs(x-z)<abs(y-z)) //если первый кот ближе выводим 1
cout<<1; else
if (abs(x-z)>abs(y-z)) //если второй кот ближе выводим 2
cout<<2; else   //если ссорятся
cout<<3;
}

Решение задачи C:
Простой перебор, ибо 100000 операции за 2 секунды легко обрабатываются.
Код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int a,b,n;
cin>>a>>b>>n;
int count = 0;
for(int x = 0; x <= n-1; x++)
{
    if (a*x%n==b) count++;
}
cout<<count;
}

Решение задачи D:
Нужно получить 4 максимальных элемента. Для этого нужно сортировать наш массив по убыванию. Первые 4 элемента массива - это элементы, которые в сумме дадут сумму максимальных элементов. Последние 4 элемента - это элементы, которые в сумме дадут сумму минимальных элементов. Проще говоря, после сортировки выводим сумму первых четырех элементов, а затем последних четырех элементов.
Код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
vector<int>N(5);
int summin = 0, summax = 0;
for(int i = 0; i < 5; i++)
    cin>>N[i];
sort(N.rbegin(),N.rend());
for(int i = 0; i < 4; i++)
{
summax+=N[i];
summin+=N[i+1];}
cout<<summin<<" "<<summax;
}

Решение задачи E:
Нужно прочитать строку, каждый символ строки преобразовать в цифру, получить сумму цифр этого большого числа. Далее нужно просто проверить на кратность 3.
Код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
string str;
int summ = 0;
cin>>str;
for(int i = 0; i < str.length(); i++)
    summ+=(int)str[i]-48;
if (summ%3==0) cout<<"YES"; else cout<<"NO";
}

Решение задачи F:
Нужно посчитать количество элементов массива, которые портят возрастающую последовательность. В конце вывести N-count, где count - количество элементов массива, которые портят возрастающую последовательность.
Код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int count = 0;
int N; cin>>N;
vector<int>A(N);
for(int i = 0; i < N; i++)
    cin>>A[i];
for(int i = 0; i < N-1; i++)
{
    if (A[i]>A[i+1]) count++;
}
cout<<N-count;
}


Автор разбора: Мамбетниязов Аймурат
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
09.12.2016, 11:02
Ответы с готовыми решениями:

Олимпиады по информатике
Здравствуйте, не подскажите как сейчас еще действуют олимпиады по информатике, которые дают льготы при поступлении в ВУЗ Заранее спасибо!

Задачи с олимпиады по информатике
Помогите решить задачи

Подскажите олимпиады по информатике и программированию для студентов
Здравствуйте, кто может подсказать хорошие олимпиады по информатике и программированию для студентов на 2016 год. Желательно, что -...

27
Падаван С++
 Аватар для obivan
447 / 261 / 89
Регистрация: 11.11.2014
Сообщений: 916
09.12.2016, 11:54
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Aymurat Посмотреть сообщение
входные данные всегда корректны
тогда зачем отвлекать читателя задачи этими лишними условиями в тексте
0
 Аватар для Nishen
1359 / 857 / 366
Регистрация: 26.02.2015
Сообщений: 3,831
09.12.2016, 11:54
Просто мы, видимо, далеки от спортивного программирования, поэтому и не можем понять друг друга.
0
125 / 117 / 67
Регистрация: 07.11.2014
Сообщений: 788
09.12.2016, 11:56  [ТС]
obivan, то есть по вашему, лучше было бы умолчать насчет 1000 символов, которые не влезут даже в _Int64? Ограничения даются, чтобы знать наверняка, какие будут тесты
0
Падаван С++
 Аватар для obivan
447 / 261 / 89
Регистрация: 11.11.2014
Сообщений: 916
09.12.2016, 11:59
если память чистить не надо, зачем тогда в D мы используем вектор, он то в деструкторе будет чистить, т.е мы задерживаем программу, в чем проблемма написать свою быструю сортировку ? Если вы только брали вектор, чтобы сорт использовать, да и на сколько я помню на малых колличествах элементов помойму, сортировка вставками быстрее быстрой работает

Добавлено через 1 минуту
понимаете в чем проблемма, скорость выполнения, зависит от машины, это во первых и я в условиях не вижу ну минимальный порог по скорости чтобы набрать 100 баллов
0
125 / 117 / 67
Регистрация: 07.11.2014
Сообщений: 788
09.12.2016, 11:59  [ТС]
obivan, я еще мог бы поставить таймер, подождать секунду, а потом выполнять. Не оптимально, но в рамки ограничении влезает.
0
Падаван С++
 Аватар для obivan
447 / 261 / 89
Регистрация: 11.11.2014
Сообщений: 916
09.12.2016, 12:03
Aymurat, ну честно сказать я от олимпиад далек, учавствовал когда еще в школе был 1 раз и на 1ом курсе универа и все, не буду спорить, может что то там и действительно позволительно, касательно памяти и тд., но нехватает временных рамок, если бы они были, то в некоторых местах можно было бы еще быстрее сделать, но может и не стоит потому что ваш пример может проходить по условиям, а вообще как по мне, 100 баллов должен набирать код который отработал быстрее всех, а не просто вошел в минимальный порог
0
125 / 117 / 67
Регистрация: 07.11.2014
Сообщений: 788
09.12.2016, 12:07  [ТС]
obivan, во втором этапе щедро выделяют время, можно побаловаться. Но в третьем и четвертом этапах уже не до развлечении. Баллы дают за прошедшие тесты. Насиловать код, когда он уже влезает в рамки, не имеет смысла.
0
 Аватар для Nosey
1379 / 406 / 144
Регистрация: 22.10.2014
Сообщений: 872
09.12.2016, 12:37
Цитата Сообщение от Aymurat Посмотреть сообщение
Решение задачи D:
Нужно получить 4 максимальных элемента. Для этого нужно сортировать наш массив по убыванию.
Не нужно сортировать, нужно за один проход найти сумму всех элементов, минимальный элемент, максимальный элемент. И вывести разницу общей суммы и минимального и максимального элементов.

Цитата Сообщение от Aymurat Посмотреть сообщение
Нужно посчитать количество элементов массива, которые портят возрастающую последовательность. В конце вывести N-count, где count - количество элементов массива, которые портят возрастающую последовательность.
Неа, вот пример:
Code
1
2
6
1 2 3 1 2 3
Я точно не знаю как правильно такие задачи решать, но я бы попробовал найти все возрастающие последовательности и уже от них плясать, потом возможно заинлайнится алгоритм в сам поиск этих последовательностей.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
09.12.2016, 12:37

C++ vs C# для олимпиады. Примеры задач
Здравствуйте. На информатике в школе, говорят что я 1 из самых знающий в области программирования в школе. Это учитывая, что ничего...

Вычислить сумму и число положительных элементов матрицы, находящихся над главной диагональю
Вычислить сумму и число положительных элементов массива 6х6, находящихся над главной диагональю. Массив задан случайным образом из...

Разбор задач
Гугление тут практически не помогает. Нужен совет мастера-синусоидника-переменщика) 1 Рисунок - Как вообще читать такие векторные...

Классы - разбор кода
в коде на шарпе встретил такую конструкцию .... 1)public Transform target; Потом через пару инструкций встретил target.position ...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
28
Ответ Создать тему
Новые блоги и статьи
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ"
Adler 06.10.2026
Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .
ИИ не может найти нужный язык в списке
Supersumestria 05.10.2026
Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO
zorxor 05.10.2026
Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
Мобильное приложение ColorStep
pavlinmavlin 17.09.2026
Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru