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

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

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

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

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

№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++

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

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

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

@petrole 2 / 2 / 0 Регистрация: 22.01.2012 Сообщений: 6
		1
	Олимпиадные задачи :/ 22.01.2012, 16:39. Показов 14598. Ответов 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, 20:44	21
	на то олимпиадная задача и является олимпиадной, что ее не решить в лоб из-за ограничений, которые наложены на память и время. вы же прекрасно все это понимаете, зачем это на форуме разводить. не дождетесь вы ответа от своей программы при большом n, ну что, разве не так? я знаю, что ваш код будет работать при любом n, я и не говорил что будет ошибка, я говорил, что он не пойдет для этой задачи. Сообщение от go Странно, что спрашиваете. что я спрашивал ?) 0

go 3646 / 1378 / 243 Регистрация: 16.04.2009 Сообщений: 4,526
	25.01.2012, 21:06	22
	Сообщение от neske я знаю, что ваш код мы говорим про алгоритм. Если отпираться от кода, то он будет работать при n < 20. Для увеличения n нужно использовать длинную арифметика, писать с ней у меня нет интереса. P.S. Алгоритм пишется без привязки к языку (в jawa, например, длинная арифметика есть по умолчанию). А чтобы решить задачу №1 особых знания языка не требуется. Добавлено через 2 минуты Сообщение от neske не дождетесь вы ответа от своей программы при большом n, ну что, разве не так? В моем понимании работать, это выдавать правильный результат. Сообщение от neske что он не пойдет для этой задачи. Код или алгоритм? 0

	25.01.2012, 21:29