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

@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;
}

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

Новые блоги и статьи Все статьи Все блоги /
тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .	мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.	сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты	Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .	Вот представьте что вам дали бессмертие. kumehtar 24.07.2026 Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .

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

	Олимпиадные задачи :/ 22.01.2012, 16:39. Показов 18624. Ответов 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