Олимпиадные задачи :/

@petrole · Регистрация: 22.01.2012

Студворк — интернет-сервис помощи студентам

Здравствуйте!

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

№1

Среди всех комбинация из N цифр найти те, сумма которых равно числу K.

Формат входных данных:
Вводятся два целых числа через пробел – количество цифр N (1 ≤ N ≤ 100) в номере и сумма его цифр K (0 ≤ S ≤ 9•N).

Формат выходных данных:
Вывести количество номеров, состоящих ровно из N цифр, сумма цифр в которых равна заданному K.

Пример входных - выходных данных:
input:
2 7
output:
8

№2

Учитель информатики Олег Петрович задумал натуральное составное число, нашел все его делители, исключая само число, и сообщил ученикам сумму двух наибольших из этих делителей.
Напишите программу, которая по значению суммы найдет число, задуманное Олегом Петровичем.

Формат входных данных (input.txt)
В первой строке входного файла содержится одно целое число S (3 ≤ S ≤ 1000) – сумма делителей.

Формат результата (output.txt)
В выходной файл вывести в порядке возрастания по одному числу на строке все числа, у которых сумма двух наибольших делителей, исключая само число, равна заданному S.

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

Пример результата
16
27
35
121

№3
В центре городского парка, имеющего форму круга радиусом R2, находится круглый фонтан радиусом R1. Деревья в парке растут в узлах координатной сетки, начало которой находится в центре фонтана. Шаг координатной сетки равен 1. На границах парка и фонтана деревья не растут. Подсчитайте количество деревьев в парке.

Формат входных данных (input.txt)
Вводятся два целых числа R1 и R2 через пробел (1 ≤ R1 < R2 ≤ 10000).
Формат результата (output.txt)
Вывести количество деревьев.
Пример входных данных
1 3
Пример результата
20

@neske · 25.01.2012, 20:44

на то олимпиадная задача и является олимпиадной, что ее не решить в лоб из-за ограничений, которые наложены на память и время. вы же прекрасно все это понимаете, зачем это на форуме разводить.
не дождетесь вы ответа от своей программы при большом n, ну что, разве не так?
я знаю, что ваш код будет работать при любом n, я и не говорил что будет ошибка, я говорил, что он не пойдет для этой задачи.

Сообщение от go

Странно, что спрашиваете.

что я спрашивал ?)

go · 25.01.2012, 21:06

Сообщение от neske

я знаю, что ваш код

мы говорим про алгоритм. Если отпираться от кода, то он будет работать при n < 20. Для увеличения n нужно использовать длинную арифметика, писать с ней у меня нет интереса.
P.S. Алгоритм пишется без привязки к языку (в jawa, например, длинная арифметика есть по умолчанию). А чтобы решить задачу №1 особых знания языка не требуется.

Добавлено через 2 минуты

Сообщение от neske

не дождетесь вы ответа от своей программы при большом n, ну что, разве не так?

В моем понимании работать, это выдавать правильный результат.

Сообщение от neske

что он не пойдет для этой задачи.

Код или алгоритм?

@neske · 25.01.2012, 21:13

ваш алгоритм не подойдет для этой задачи (даже на jaWa, например, где длинная арифметика есть по умолчанию) из-за ограничений, он просто по времени не уложится - time limit будет.

Не по теме:

при n = 100, ваш алгоритм будет перебирать чисел больше, чем частиц в нашей вселенной, говорит нам википедия)

go · 25.01.2012, 21:29

Сообщение от neske

go, вы знаете, при n = 100, ваш алгоритм будет перебирать чисел больше, чем частиц частиц в нашей вселенной, говорит в википедия, ну это так, просто интересный факт.

Мда. Набросал вот такой код

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream> 
#include <limits> 
 
typedef unsigned long long T_my;
 
int main() 
{ 
   T_my max = std::numeric_limits<T_my>::max();
   int i;
   T_my j;
   for ( i = 0, j = 0 ; i < 3 ; ++j ) 
      if ( j == max ) 
      {
         ++i;
         j = 0;
      }  
   std::cout << "OK" << std::endl;    
   return 0;
}

и понял, что простым перебором здесь не обойтись.

Новые блоги и статьи Все статьи Все блоги /
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .	Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .
Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .	Почему SEO не начинается с ключевых слов: что проверить до написания текстов Neotwalker 01.08.2026 Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .	Знание — сила: Доктрина интенциональности знаний, углубление в формулу Hrethgir 01.08.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .	SUNO Ai - Река Без Дна zorxor 31.07.2026 Автор стихотворения - астрофизик Марина Катыс Ссылка на сгенерированную музыкальную композицию: https:/ / suno. com/ song/ 6f6e5464-b290-4650-be6c-44c85f8d8013 Я говорю, что Время- как вода течет. . .

@petrole 2 / 2 / 0 Регистрация: 22.01.2012 Сообщений: 6

	Олимпиадные задачи :/ 22.01.2012, 16:39. Показов 18646. Ответов 23 Метки нет (Все метки) Здравствуйте! Недавно прошёл очередной тур олимпиады по программированию и мне стало интересно, как следовало решать задачи (авторских решений или тестов для ввода-вывода выложено не было). №1 Среди всех комбинация из N цифр найти те, сумма которых равно числу K. Формат входных данных: Вводятся два целых числа через пробел – количество цифр N (1 ≤ N ≤ 100) в номере и сумма его цифр K (0 ≤ S ≤ 9•N). Формат выходных данных: Вывести количество номеров, состоящих ровно из N цифр, сумма цифр в которых равна заданному K. Пример входных - выходных данных: input: 2 7 output: 8 №2 Учитель информатики Олег Петрович задумал натуральное составное число, нашел все его делители, исключая само число, и сообщил ученикам сумму двух наибольших из этих делителей. Напишите программу, которая по значению суммы найдет число, задуманное Олегом Петровичем. Формат входных данных (input.txt) В первой строке входного файла содержится одно целое число S (3 ≤ S ≤ 1000) – сумма делителей. Формат результата (output.txt) В выходной файл вывести в порядке возрастания по одному числу на строке все числа, у которых сумма двух наибольших делителей, исключая само число, равна заданному S. Пример входных данных 12 Пример результата 16 27 35 121 №3 В центре городского парка, имеющего форму круга радиусом R2, находится круглый фонтан радиусом R1. Деревья в парке растут в узлах координатной сетки, начало которой находится в центре фонтана. Шаг координатной сетки равен 1. На границах парка и фонтана деревья не растут. Подсчитайте количество деревьев в парке. Формат входных данных (input.txt) Вводятся два целых числа R1 и R2 через пробел (1 ≤ R1 < R2 ≤ 10000). Формат результата (output.txt) Вывести количество деревьев. Пример входных данных 1 3 Пример результата 20 1

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	25.01.2012, 21:13
	ваш алгоритм не подойдет для этой задачи (даже на jaWa, например, где длинная арифметика есть по умолчанию) из-за ограничений, он просто по времени не уложится - time limit будет. Не по теме: при n = 100, ваш алгоритм будет перебирать чисел больше, чем частиц в нашей вселенной, говорит нам википедия) 0

Опции темы