Школьная олимпиада

Автор: admin Опубликовано: Окт 31, 2011 В рубрике: Олимпиада

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

Задача №1.  Делители

Условие задачи:

Дано число n. Найти все его делители.

 

 

Задача №2. Круглые числа.

 

Будем называть числа круглыми, если они содержат в своей записи только цифры 0 и 5.

Составим последовательность круглых чисел в порядке возрастания: 0, 5, 50, 55, 500, 505 и так далее.

Написать программу, которая находит K-ое по порядку в этой последовательности круглое число.

 

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

Со стандартного потока ввода вводится натуральное число K — номер круглого числа в последовательности (0 < K < 500).

 

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

Выведите на экран требуемое круглое число.

Примеры

Ввод

Вывод

2
5
6
505

 

Задание3.   Скорость света.

 

Решить задачу, составив блок-схему.

Скорость света С приблизительно равна 3*108 м/с. Найти примерную длину светового года L, выразив ее в метрах Lm, футах Lph, милях Lml (1м = 3,28 фута, 1 миля = 1,61 км).

 

Задача 4 . «Цифры»

 

 

Запишем последовательно и без пробелов натуральные числа от 1 до N. Например, для N = 13 мы получим последовательность 12345678910111213. А теперь посчитаем, сколько раз каждая цифра входит в эту последовательность. Цифра 0 входит 1 раз, цифра 1 – 6 раз, цифра 2 – 2 раза и так далее.

Напишите программу, которая для заданного числа N будет находить количество вхождений в такую последовательность для всех цифр от 0 до 9.

 

Вход

Во входном файле записано натуральное число N (1 <= N <= 10000).

 

Выход

Запишите в выходной файл через пробел десять чисел – количество вхождений цифр 0, 1, …, 9 в получившуюся последовательность.

 

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

3

0 1 1 1 0 0 0 0 0 0

13

1 6 2 2 1 1 1 1 1 1

 

 

Задача 5.   «Последовательность»

 

Бесконечная последовательность натуральных чисел A1, A2, … строится следующим образом: A1 — любое натуральное число, Ai+1 = Ai * K mod B, где K и B – натуральные числа, одни и те же для всех членов последовательности, mod – остаток от деления.

Ваша задача – для  заданных чисел A1, K, B и n найти число An.

 

Вход

Во входном файле записаны четыре целых числа    A1,    K,    B,    n     (1 <= A1 <= 105, 1 <= K <= 104, 1 <= B <= 105, 1 <= n <= 109).

 

Выход

Запишите в выходной файл число An.

 

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

3 7 10 1

3

3 7 10 3

7

3 7 10 10

1

3 7 10 1000000000

9

 

Задача 6. Никифор — 2.(Автор — Д.О. Филимоненков)
Никифору в подарок досталось число x. Но оно ему не нужно, а нужно число y. Но Никифор не расстроился: он решил попробовать получить y, вычеркивая из числа x некоторые цифры. Но что-то не очень-то у него получается. Может быть, ему нужно правильно выбрать систему счисления, в которой это возможно?

Напишите программу, которая считывает два натуральных числа x и y и определяет минимальное основание системы счисления, в которой число y можно получить из числа x вычеркиванием некоторого набора цифр. Если это невозможно, программа должна выдавать сообщение «No solution«.

Вход: единственная строка входного файла содержит два числа x и y, разделенные пробелом. Известно, что 1 <= y < x <= 1000000.

Выход: Единственная строка выходного файла содержит либо сообщение "No solution", если необходимого основания системы счисления не существует, либо натуральное число, не меньшее 2, являющееся ответом задачи.

Пример входного файла 1:
127 16

Пример выходного файла 1:
3

Пример входного файла 2:
7 4

Пример выходного файла 2:
No solution

 

 

Задача7. «Олигархи»

 

Собрались как-то олигархи и стали хвастаться – у кого денег больше. Первый олигарх говорит – у меня одних долларов 100 миллиардов, а ещё евров 50 миллиардов, и рублей полно. Второй ему отвечает – подумаешь, кому сейчас твои доллары нужны, у меня вот британских фунтов стерлингов 76 миллиардов  с копейками, да тугрики монгольские, да динары алжирские… Тут все олигархи как закричат, как ногами затопают… и подрались, синяков друг другу наставили, а одному олигарху зуб выбили. А всё потому, что олигархи были глупые – надо было не кричать, и не драться, а спокойно пересчитать все их сбережения, непосильным трудом нажитые, в родные русские рубли, тогда сразу бы ясно стало, кто из них самый богатый.

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

 

Вход

В первой строке входного файла записаны натуральные числа N – количество олигархов и M  — количество разных валют, в которых они хранят свои сбережения (2 <= N <= 1000, 1 <= M <= 100). Во второй строке записано M вещественных чисел – курсы валют по отношению к рублю. В остальных N строках записано по M целых чисел в каждой. j-е число в i-ой из этих строк равно количеству миллиардов в j-ой валюте у i-го олигарха.

 

Выход

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

 

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

input.txt

output.txt

2 1

1.0

100

101

2

3 4

1.0 36.350 25.943 48.021

100 15 25 0

200 40 0 0

150 0 30 25

3

 

Задача 8.  Игра в города.

Условие задачи:

Всем известны правила игры «в города»: первый игрок называет произвольный город, следующий — город, название которого начинается на ту же букву, на которую заканчивается название предыдущего города, и т.д. Аналогичным образом можно играть не в названия городов, а, например, в названия животных. Задан список допустимых для описанной игры слов, слова в нём могут повторяться. Напишите программу, определяющую, в каком порядке в процессе игры должны быть названы слова из списка, чтобы каждое слово было использовано ровно столько раз, сколько оно в нём встречается.

 

Решение:

Очень простая идея. Это перебор 0 и 1 в n-значном числе. Т. е. если мы натыкаемся на 0, то данное слово мы не берём в последовательность, если 1, то берём. Получив некую последовательность проверяем на то, что есть ли такие слова, которые начинаются на ту букву, на которую некоторые заканчиваются. Затем ты записываем в двумерный массив в первый столбец количество слов, а затем в остальные столбцы последовательность слов.  Потом просто находим строчку с максимальным значением слов и выдаём эту последовательность.

while (true) do begin

   inc(p[1]);

   for i:=1 to n do

       if p[i]>1 then begin

             inc(p[i+1]);

             p[i]:=0;

         end;

   {—}

   if p[n+1]=1 then break;

end; — пример перебора нолей и единиц. Вместо {—} вставьте текст программы.

 

 

Задача9.  Левые повороты.

Условие задачи:

Маршрут движения автомобиля задан в виде координат вершин ломаной.
Необходимо определить количество левых поворотов (смежные участки ломаной не лежат на одной прямой). Автомобиль начинает движение с любой точки (!!!Здесь уточнение от меня — автомобиль начинает движение из первой вершины ломаной, а вот ее координаты любые!!!).
Формат входных данных:
Первая строка входного файла input.txt состоит из одного числа, количества звеньев ломаной; в последующих строках — пары натуральных чисел, координаты вершин ломаной.
Формат выходных данных:
Выходной файл output.txt содержит одно число — количество левых поворотов

Решение:

Итак, создадим два массива, в один из них будем записывать координату Х, а в другой - Y. Возможны 
несколько случаев:
1. Когда координата Х увеличилась и Y также. Тогда это поворот влево.
2. Когда координата X уменьшилась и Y увеличилась. Тогда это поворот влево.
3. Когда координата Х осталась неизменной, а Y увеличилась. Тогда это поворот влево.
Пояснение:

for i:=1 to n-1 do begin

      if  (x[i+1]>x[i]) and (y[i+1]>y[i]) then inc(k);

      if (x[i+1]<x[i]) and (y[i+1]>y[i]) then inc(k);

      if (x[i]=x[i+1]) and (y[i+1]>y[i[) then inc(k);

end;

Здесь: n-число звеньев ломанной, k-количество поворотов.

 

Задача 10.  Система счисления (автор-составитель — Брызгалов Е.В., оппонент — Еремин Е.А.)

Задан пример на сложение двух чисел, выполненный в позиционной системе счисления с основанием, не превосходящим 36. Запись примера имеет вид A + B = C, где A, B и C — числа, записанные в данной системе счисления.

Требуется написать программу, определяющую минимальное основание этой системы.

Технические замечания:
Цифры в системах, основание которых больше 10, обозначаются латинскими заглавными буквами: A — 10, B — 11, …, Z — 35.

Операнды и результат — натуральные числа, десятичная запись которых не превосходит 30000.

Формат входных данных:
одна строка, содержащая запись примера.

Формат выходных данных:
Одно число — минимальное основание системы счисления, при котором входное равенство является верным.

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

2+2=4

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

5

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

3A+2B=60

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

21

Задача 11.  Встреча исполнителей (автор-составитель — Еремин Е.А., оппонент — Брызгалов Е.В.)

На квадратном клетчатом поле 10 × 10 находятся два одинаковых исполнителя: исполнитель А — в левом нижнем углу с координатами (0, 0), и исполнитель В — в правом верхнем углу с координатами (9, 9).

Система команд исполнителей состоит из следующих команд:
R — сместиться на соседнюю клетку вправо;
L — сместиться на соседнюю клетку влево;
U — сместиться на соседнюю клетку вверх;
D — сместиться на соседнюю клетку вниз.

Для сокращения записи алгоритмов разрешается объединять одинаковые следующие друг за другом команды в виде NK, где 1 < N < 10 — число повторений команды, а K — повторяемая команда (например, запись 4U эквивалентна четырем командам U, т.е. UUUU).

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

Каждый исполнитель получает свою собственную программную строку (считать, что она не содержит синтаксических ошибок) и исполняет ее. Будем предполагать, что на каждом шаге алгоритма исполнители выполняют по одной команде. Тогда описанная процедура закончится одним из трех способов:
1) исполнители встретятся на одной клетке поля и остановятся: в этом случае необходимо напечатать номер шага алгоритма и координаты клетки встречи X и Y;
2) у обоих исполнителей закончатся строки с программами, но встреча не состоится: в этом случае необходимо вывести на экран слово «no» — нет решения;
3) любой исполнитель выйдет за пределы поля: в этой аварийной ситуации надо напечатать слово «error» — ошибка.

Технические замечания:
1. Длина каждой из двух вводимых строк с алгоритмами для исполнителей А и В не превышает 10 символов;
2. Строки не содержат никаких других символов, кроме цифр и букв R, L, U и D.

Формат входных данных:
2 строки, содержащие программы для исполнителей A и B.

Формат выходных данных:
Три числа — номер шага алгоритма, на котором произошла встреча и ее координаты, или сообщения no либо error.

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

9U9R
9L9U

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

9 0 9

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

U4U
D4D

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

no

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

U2U
D3U

 

 

 

 

Использованы материалы сайта

http://olimpzadachi.narod.ru/zadachi/001.htm

 

Вы можете обсудить этот пост комментариях или в нашем чате, который находится в верхнем правом углу сайта. Если вы не знаете как общаться в чате, то скорее жмите СЮДА! Приятного Вам общения :)

Прокомментировать

Copyright © 2018 Урок информатики All rights reserved.
Тема доработана интернет студией SMOpro, специализация которой реклама в блогах.