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

@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

@Ilyawow · 22.01.2012, 16:43

это облостная 2 тур?

@petrole · 22.01.2012, 16:44 **[ТС]**

Областная 1 (заочный) тур.

@x1Mike7x · 22.01.2012, 17:01

3я решается перебором х/у для Р2 и Р1, результат: Р2 - Р1.
Рассмотрим все х, которые лежат в диапазоне [ 0; R ]. Для каждого х найде соответсвующий у, который является максимальным, при этом находящимся в круге, этот игрик есть число точек в круге для выбранного х ( точнее не в круге, а в 1/4 круга - если нарисовать на листочке, то станет ясно почему ).
Найдём количество у для Р2 ( все точки для заданого х от центра парка до его границы ), а также количесвто у для Р1 ( все точки для х от центра фонтана до границы фонтана ), прибавим разницу к результату.
+ еще проверяем, есть ли точка на границе, если так, то просто инкрементируем у.
В конце умножим результат на 4, потому что мы нашли число деревьев (точек) только в 1,4 круга.
Примерно так:

C++

cin >> R1 >> R2;
for ( x = 0; x < R2; ++x )
{
    y2 = ( int )( sqrt( R2 * R2 - x * x ) + eps );
    y1 = ( int )( sqrt( R1 * R1 - x * x ) + eps );
 
    y2 -= ( R2 * R2 == x * x + y2 * y2 );
    y1 -= ( R1 * R1 == x * x + y1 * y1 );
 
    Result += y2 - y1;
}
Result *= 4;

@petrole · 22.01.2012, 17:07 **[ТС]**

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

eps

Что есть эта переменная?

@x1Mike7x · 22.01.2012, 17:22

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

Что есть эта переменная?

Допустимая погрешность при выичслении чисел с плавающей запятой.

C++

1	const double eps = 1e-9;

@Teravisor · 22.01.2012, 18:01

Первая задача:
переформулируем. Дан массив A из N элементов, изначально 0, не могут превышать 9
Дано число K
Надо найти число комбинаций распределения K вещей по N местам.
Решение:
пусть есть функция, которая распределяет T элементов по всем массивам начиная с номера U.
запускаем цикл. Начало рекурсии: U=0,T=K
функция F(T,U):
Для каждого A[U] 0<=i<=min(9,T) делаем F(T-i,U+1); Считаем сумму всех F(T-i,U+1) которые мы запускали и возвращаем.
Каждый запуск функции при Т=0 - это один из вариантов. Значит возвращаем 1 ничего не запуская. Конец рекурсии.

Если после последнего цикла T(T,N) - возвращаем 0 при T>9. Иначе 1. Второй конец рекурсии.

Написать на С++ не проблема по этому алгоритму. Кому не лень.

Edit: опечатки.

Добавлено через 21 минуту
По сути в прошлом A[U] нужен только для виду. в программе его не будет.

Вторая задача:
Дан К - сумма двух наибольших делителей.
Переформулируем:
перебрать все варианты разложения К вещей по двум полкам A[0] и A[1], так чтобы
A[0]*A[1]%B >0 для любого B больше A[0] или A[1] и меньшего K
A[0]+A[1]==K

Т.е. банально три вложенных цикла, которые ищут два числа, удовлетворяющие этим условиям. Плюс третий вложенный в них цикл по поиску B, которое бы удовлетворяло A[0]*A[1]%B==0. Ответом будет их сумма. Это если писать на скорость.
Даже распишу:

C++

int Function(int K)
{
   int A0=0;
   int A1=0;
   for(A0=K;A0>0;A0--)
       for(A1=K;A1>0;A1--)
       {
//Тут мы не будем использовать math::min или другие библиотеки. Поэтому так.
          if(A0==A1)continue;
          for(int B=K;a>0;a--)
          {
              if((A0*A1%B)==0)break;
              if((B<A0)&&(B<A1))return A[0]+A[1];
          }
       }
//Такого числа нет.
   return -1
}

Вроде так.

З.Ы. можно сделать циклы A0 и A1 >1 т.к. если одно из них равно 1, то строка 12 всегда сработает. Можно еще 14й строкой вставить else break;
Увеличит производительность, но для олимпиадных оно не требуется вроде?

@neske · 22.01.2012, 19:59

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

Увеличит производительность, но для олимпиадных оно не требуется вроде?

наоборот, один из самый важный факторов 8) там же везде ограничения на время и память.

Добавлено через 2 минуты
Teravisor, во второй задачи вы намудрили, как минимум из за того, что ответов может быть несколько.

@Vergil111 · 23.01.2012, 00:33

Имхо, все намного проще насчет первой задачи. Первое условие вам дает количество возможных перестановок цифр в числе, то есть в указанном вами примере это будет 2! Второе условие дает количество уникальных вариантов, равное [k/2]+1, где скобки обозначают нацело.То есть опять-таки согласно вашему примеру получается так. Выписываем "уникальные" числа
0 7
1 6
2 5
3 4
Далее они начинают просто меняться местами. Получилось 4 варианта, то есть как раз [7/2]+1=4
Далее просто умножаем одно на другое и получаем наш ответ.
Правда вот если количество цифр равно 1, то метод не работает=)
А для трехразрядных чисел мне было лень проверять

@neske · 23.01.2012, 00:42

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

Второе условие дает количество уникальных вариантов, равное [k/2]+1

будет работать только для n = 2

@Vergil111 · 23.01.2012, 00:46

neske, ты прав, да и вообще количество уникальных вариантов неверное, если подставить сумму, равную 10 в условие. Хм, буду дальше думать над нахождением количества уникальных элементов=/

@~~alkagolik~~ · 23.01.2012, 01:33

Vergil111, верно начал и неверно кончил. Правильный ответ $https://www.cyberforum.ru/cgi-bin/latex.cgi?$K + 1$^{N - 1}$ . Какие-то номера в условии, кто его составлял, это условие... сложность в том что N (1 ≤ N ≤ 100) ,а это длинная арифметика.

@Vergil111 · 23.01.2012, 10:07

alkagolik, я знал, что должно быть короткое решение) Чуть-чуть не хватило, спать хотелось) спасибо)

go · 25.01.2012, 19:50

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

№1

На самом деле очень легкая задача для олимпиадной. Делается очень просто. Вот

C++

#include <iostream>
#include <cmath>
 
typedef unsigned long long T_my;
 
size_t dig_sum(T_my val)
{
   size_t sum = 0;
   
   do
   {
      sum += val % 10;
   }
   while ( val /= 10 );
   return sum;
}
 
int main()
{
   int k = 7, n = 2;
   T_my max = static_cast<T_my> (pow( 10., n));
   T_my i;
   T_my cnt = 0;
   
   for ( i = 0; i < max ; ++i )
      if ( dig_sum(i) == k )
         ++cnt;
   std::cout << cnt << std::endl;
   return 0;
}

http://liveworkspace.org/code/... 63727ff9f0

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

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

Дан массив A из N элементов,

Все намного проще...

@neske · 25.01.2012, 20:05

go, вы на ограничения смотрели? 10^100 чисел перебирать будете?

go · 25.01.2012, 20:13

neske, а длинная арифметика??? Про нее то забыли, алгоритм решения я предложил.

@neske · 25.01.2012, 20:19

да не пойдет этот алгоритм, на n > 15 уже вечность работать будет.

Добавлено через 1 минуту
это ж кстати 1 гугол, 10^100

go · 25.01.2012, 20:30

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

это ж кстати 1 гугол, 10^100

Что?
Специально для вас набросал http://liveworkspace.org/code/... fb9742b3fb

@neske · 25.01.2012, 20:35

спасибо, но писать длинную арифметику я вроде и сам умею.
лучше проверьте свою программу, хотя бы для n > 10, и убедитесь, что такой алгоритм при данных ограничениях не подойдет.

go · 25.01.2012, 20:38

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

лучше проверьте свою программу, хотя бы для n > 10, и убедитесь, что такой алгоритм при данных ограничениях не подойдет.

Алгоритм работает для любого кол-во цифр. Данный код работает для n < 20. Но использую длинную арифметику, можно увеличить и до 100 (как в задании). Писать это за Вас я не собираюсь.

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

я вроде и сам умею.

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

@petrole 2 / 2 / 0 Регистрация: 22.01.2012 Сообщений: 6
		1
	Олимпиадные задачи :/ 22.01.2012, 16:39. Показов 14597. Ответов 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

@Ilyawow 26 / 26 / 7 Регистрация: 18.11.2011 Сообщений: 266
	22.01.2012, 16:43	2
	это облостная 2 тур? 0

@petrole 2 / 2 / 0 Регистрация: 22.01.2012 Сообщений: 6
	22.01.2012, 16:44 [ТС]	3
	Областная 1 (заочный) тур. 0

@petrole 2 / 2 / 0 Регистрация: 22.01.2012 Сообщений: 6
	22.01.2012, 17:07 [ТС]	5
	Сообщение от x1Mike7x eps Что есть эта переменная? 0

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	22.01.2012, 19:59	8
	Сообщение от Teravisor Увеличит производительность, но для олимпиадных оно не требуется вроде? наоборот, один из самый важный факторов 8) там же везде ограничения на время и память. Добавлено через 2 минуты Teravisor, во второй задачи вы намудрили, как минимум из за того, что ответов может быть несколько. 0

@Vergil111 31 / 31 / 16 Регистрация: 30.11.2010 Сообщений: 81
	23.01.2012, 00:33	9
	Имхо, все намного проще насчет первой задачи. Первое условие вам дает количество возможных перестановок цифр в числе, то есть в указанном вами примере это будет 2! Второе условие дает количество уникальных вариантов, равное [k/2]+1, где скобки обозначают нацело.То есть опять-таки согласно вашему примеру получается так. Выписываем "уникальные" числа 0 7 1 6 2 5 3 4 Далее они начинают просто меняться местами. Получилось 4 варианта, то есть как раз [7/2]+1=4 Далее просто умножаем одно на другое и получаем наш ответ. Правда вот если количество цифр равно 1, то метод не работает=) А для трехразрядных чисел мне было лень проверять 0

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	23.01.2012, 00:42	10
	Сообщение от Vergil111 Второе условие дает количество уникальных вариантов, равное [k/2]+1 будет работать только для n = 2 0

@Vergil111 31 / 31 / 16 Регистрация: 30.11.2010 Сообщений: 81
	23.01.2012, 00:46	11
	neske, ты прав, да и вообще количество уникальных вариантов неверное, если подставить сумму, равную 10 в условие. Хм, буду дальше думать над нахождением количества уникальных элементов=/ 0

@~~alkagolik~~ Заблокирован
	23.01.2012, 01:33	12
	Vergil111, верно начал и неверно кончил. Правильный ответ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\(K + 1\)^{N - 1}$ . Какие-то номера в условии, кто его составлял, это условие... сложность в том что N (1 ≤ N ≤ 100) ,а это длинная арифметика. 2

@Vergil111 31 / 31 / 16 Регистрация: 30.11.2010 Сообщений: 81
	23.01.2012, 10:07	13
	alkagolik, я знал, что должно быть короткое решение) Чуть-чуть не хватило, спать хотелось) спасибо) 0

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	25.01.2012, 20:05	15
	go, вы на ограничения смотрели? 10^100 чисел перебирать будете? 0

go 3646 / 1378 / 243 Регистрация: 16.04.2009 Сообщений: 4,526
	25.01.2012, 20:13	16
	neske, а длинная арифметика??? Про нее то забыли, алгоритм решения я предложил. 0

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	25.01.2012, 20:19	17
	да не пойдет этот алгоритм, на n > 15 уже вечность работать будет. Добавлено через 1 минуту это ж кстати 1 гугол, 10^100 0

go 3646 / 1378 / 243 Регистрация: 16.04.2009 Сообщений: 4,526
	25.01.2012, 20:30	18
	Сообщение от neske это ж кстати 1 гугол, 10^100 Что? Специально для вас набросал http://liveworkspace.org/code/... fb9742b3fb 0

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	25.01.2012, 20:35	19
	спасибо, но писать длинную арифметику я вроде и сам умею. лучше проверьте свою программу, хотя бы для n > 10, и убедитесь, что такой алгоритм при данных ограничениях не подойдет. 0

go 3646 / 1378 / 243 Регистрация: 16.04.2009 Сообщений: 4,526
	25.01.2012, 20:38	20
	Сообщение от neske лучше проверьте свою программу, хотя бы для n > 10, и убедитесь, что такой алгоритм при данных ограничениях не подойдет. Алгоритм работает для любого кол-во цифр. Данный код работает для n < 20. Но использую длинную арифметику, можно увеличить и до 100 (как в задании). Писать это за Вас я не собираюсь. Сообщение от neske я вроде и сам умею. Странно, что спрашиваете. 0