Школьные олимпиадные задачи (Прошу помощи в некоторых задачах)

[Assuri]

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

Вот одна из этих задач:

Объем пирамиды
Васе подарили игрушку в виде пирамиды с треугольником в основании. Он захотел найти объем этой
пирамиды. Для этого он измерил длины всех шести ребер пирамиды в следующем порядке: AB, AC, AD, BC,
BD, CD, они все оказались целыми числами.
Помогите Васе и напишите программу, которая по этим данным, вычисляет объем пирамиды.
Входные данные
Входной файл содержит шесть положительных целых чисел AB, AC, AD, BC, BD и CD, каждое из которых
не превышает 1000.
Выходные данные
В выходной файл необходимо вывести одно вещественное число, равное объему пирамиды с точностью до
четырех десятичных знаков после запятой без округления.
Пример

Код: Выделить всё

input.txt                                     output.txt
1 1 1 1 1 1                                  0.1179

По формуле объем пирамиды равен "1/3*Sоснования*высоту". Площадь основания по формуле Герона нет проблем найти, но как найти высоту пирамиды(не обязательно правильной)?

[KiWi]

Особо не проверяя правильности и не ищя простых путей: в треугольнике ABC опускаем вусоту AM, потом опускаем высоту AN в треугольнике AMD. Оно вроде и искомое.

Ещё вариант: Объём пирамиды равен 1/6 площади параллелепипеда, что в свою очередь есть смешанное произведение векторов(см. определители). Остается лишь посчитать координаты 3х векторов.

Векторы:
AB: (0;0;0) -> (AB;0;0)
AC: (0;0;0) -> (x1;x2;0) -- 2 уравнения, 2 неизвестных (расстояния до A, B)
AD: (0;0;0) -> (y1;y2;y3) -- 3 уравнения, 3 неизвестных (расстояние до A, B, C)

[MUTOgen]

Особо не проверяя правильности и не ищя простых путей: в треугольнике ABC опускаем вусоту AM, потом опускаем высоту AN в треугольнике AMD. Оно вроде и искомое.

а по-моему не факт что она будет лежать в плоскости AMD... пример - представим пирамиду где в основании ABC а вершина D висит вообще не над треугольником ABC. получаем высоту вообще за пределами пирамиды...

[KiWi]

Особо не проверяя правильности и не ищя простых путей: в треугольнике ABC опускаем вусоту AM, потом опускаем высоту AN в треугольнике AMD. Оно вроде и искомое.

а по-моему не факт что она будет лежать в плоскости AMD... пример - представим пирамиду где в основании ABC а вершина D висит вообще не над треугольником ABC. получаем высоту вообще за пределами пирамиды...

Собсна, я там вижу только 1 проблему -- поиск 2ой высоты.

P.S.: если бы и реализовывал, то второй вариант.

[/dev/random]

Особо не проверяя правильности и не ищя простых путей: в треугольнике ABC опускаем вусоту AM, потом опускаем высоту AN в треугольнике AMD. Оно вроде и искомое.

а по-моему не факт что она будет лежать в плоскости AMD... пример - представим пирамиду где в основании ABC а вершина D висит вообще не над треугольником ABC. получаем высоту вообще за пределами пирамиды...

Собсна, я там вижу только 1 проблему -- поиск 2ой высоты.

Вообще-то, есть более серьёзная проблема. Ваше решение исходит из ошибочной предпосылки, что AM, AD и высота пирамиды обязательно лежат в одной плоскости.

[Assuri]

Всем спасибо, с трудом, но задачу таки решили.
Вот как я её реализовал:

Код:

#include <iostream> #include <fstream> #include <cmath> using namespace std; template<class T> T sqr(T number) { return number * number; } int main() { int AB,AC,AD,BC,BD,CD; ifstream input("input.txt"); input >> AB >> AC >> AD >> BC >> BD >> CD; // Height from top D to rib BC double DK = 0.0; DK = sqrt(CD*CD*(1.0 - sqr((double)(CD*CD+BC*BC-BD*BD)/(2*CD*BC)))); double CK = 0.0; CK = sqrt(sqr(CD)-sqr(DK)); double AK = 0.0; double cosBCA = (double)(sqr(BC)+sqr(AC)-sqr(AC))/(2*BC*AC); AK = sqrt(sqr(CK)+sqr(AC)-2*CK*AC*cosBCA); double height = 0.0; height = AD*sqrt(1.0 - sqr((double)(sqr(AK) + sqr(AD) - sqr(DK))/(2*AK*AD))); double halfRootPerimeter = AB + BC + AC; halfRootPerimeter /= 2.0; double S_root = sqrt((double)halfRootPerimeter*(halfRootPerimeter-AB)*(halfRootPerimeter-BC)*(halfRootPerimeter-AC)); ofstream output("output.txt"); output << round(10000*(double)1/3*S_root*height)/10000; }

Чистая стереометрия, а не программирование.

[Assuri]

Во многих задачах необходимо записывать большие числа в файл, но ofstream записывает в файл большие числа примерно так: 2e+08. Что это такое я понимаю, но какой манипулятор или что ещё использовать для записи большого числа без всяких сокращений?

Решил проблему так:

Код: Выделить всё

ofstream output("output.txt");
output.setf(ios_base::fixed,ios_base::floatfield);
output.precision(0);

[Assuri]

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

Максимальное время работы на одном тесте:1 секунда

Петя и Вася играют в следующую игру. Они по очереди называют числа. Один называет число, а другой игрок при помощи операций "прибавить к текущему числу 3" и "умножить текущее число на 2" должен получить из числа 1 названное число. Все шло хорошо, пока Петя не застопорился на одном из чисел, названным Васей. Пете никак не удается получить это число из 1, и ему кажется, что Вася специально дал такое число, которое нельзя получить указанными операциями. Однако сдаваться он не хочет и обращается к Вам за помощью. Напишите программу, которая по заданному числу N выдаст последовательность операций, с помощью которых можно получить это число.
Входные данные
Во входном файле задано одно число N (1 ≤ N ≤ 1018) — число, загаданное Васей.
Выходные данные
В выходной файл необходимо выдать требуемую последовательность операций в следующем формате:
N=1-операции-
-операции- — это последовательность операций вида +3 и *2, в результате выполнения которых слева направо получается число N. Заметим, что умножение не имеет приоритета над сложением. Если же получить число N действительно невозможно, выходной файл должен содержать единственное слово impossible. Если последовательность операций существует, вы должны будете найти и выдать такую последовательность, которая содержит не более 200 операций, так как слишком длинный ответ Васе проверять будет трудно. Гарантируется, что в этом случае такая короткая последовательность обязательно существует. Если существует несколько последовательностей, удовлетворяющих условию, достаточно выдать любую.
Выходной файл не должен содержать символов пробелов и табуляций.
Примеры
input.txt - output.txt
1 - 1=1
10 - 10=1*2+3*2
3 - impossible

--------------------------------
Никакого конкретного алгоритма я придумать не могу. Лишь только перебор вариантов как можно найти эту последовательность, то-есть сначало проверяем получится ли это число если действие +3 и *2 будет чередоваться, потом проверим если все действия - "+3", потом если все действия - "*2" и т.д. пока не закончатся варианты или не будет найдена последовательность. Данный вариант, конечно, ужасен, но другого придумать не могу.

Заранее спасибо за помощь!

[Portnov]

Идея такая. Если данное число чётное - делим его на два (и записываем это), если нечётное - вычитаем 3. И так до тех пор, пока не получим 1 или 0. Если получился 0 - значит, данное число из 1 получить нельзя, а если 1 - то выводим последовательность операций, которые мы проделали (в обратном порядке, конечно).

[drBatty]

Никакого конкретного алгоритма я придумать не могу.

алгоритм писать лень.
видимо с конца надо начать:
если число чётное - делим на 2
иначе вычитаем 3
ну вобщем то и всё

[Assuri]

Огромное вам спасибо за ответ! Прошу прощения за мою глупость - надо было самому додуматься...

Завтра олимпиада и сейчас я готовлюсь, поэтому позволю себе задать два вопроса в один день. Чтобы вам было удобно читать, приаттачу все задачи олимпиады. по которой я готовлюсь. Меня интересует задача номер 6 "Классики". Формат .doc, так как придумыватели задач у нас виндузятники, не моя вина. Спасибо.

[Assuri]

Здраствуйте. Помогите, пожалуйста, решить вот эту задачу:

Сегодня Васе и Пете пришла в голову мысль, что они обязательно должны стать архитекторами. Первый свой проект они выбрали в своем городе – на центральной площади располагается триумфальная арка. Основная идея проекта – заделать внутренность арки кирпичами. Но прежде, чем приступить к выполнению проекта, ребята решили провести соответствующие расчеты. На клетчатом листе бумаги внутренность арки была изображена, как внутренняя область пересечения кривой y = x2 и прямой y = h (длина единичного отрезка совпадает с длиной стороны клетки на бумаге). Кирпичи занимают ровно две горизонтальные клетки на бумаге. Ребята не могут понять, какое максимальное количество кирпичей они могут использовать, чтобы заделать арку. Помогите им решить эту задачу.
Входные данные
В первой строке входного файла содержится целое число h — высота арки в клеточках (0 < h < 1000).
Выходные данные
В выходной файл требуется вывести единственное число – максимальное количество кирпичей, которое им удастся использовать для своего первого проекта. Помните, что кирпичи можно класть только горизонтально, стороны кирпичей должны совпадать с линиями сетки на бумаге.
Примеры
input.txt - output.txt
2 - 1
4 - 3

Желательно как можно быстрее. Понимаю, что это наглая просьба, но выбора нет

[Portnov]

Видимо, надо взять за основу тот факт, что между высотами n^2 и (n+1)^2 в ширину можно положить ровно n кирпичей (нарисуйте себе эту параболу с кирпичами для ясности). Ну отсюда можно вывести ответ...

[Assuri]

Видимо, надо взять за основу тот факт, что между высотами n^2 и (n+1)^2 в ширину можно положить ровно n кирпичей (нарисуйте себе эту параболу с кирпичами для ясности). Ну отсюда можно вывести ответ...

Да, Вы правы, я так и сделал, спасибо!