Две задачки с ЕГЭ
...или откуда там они? Не уверен в написанном, и ввод не с консоли, а просто через оператор "=", так как написал в спешке и скинул, а сейчас вот попалось на глаза.
Похоже, вместо нормальной алгоритмизации и комбинаторики нынче в моде безумные стратегии. Как и во всём остальном. У меня больше тестов нет, а тест из условия даёт min(a,b)==3, max(a,b)==6, само же условие первой задачи аж вот такое:
Миссия простая: нужно либо накопить c кредитов (читайте: единиц вымышленной валюты), либо сокрушить врага в этом регионе. Миссия проходная и не интересная (даже никаких юнитов кроме пехоты), так что надо её закрыть побыстрее.
Изначально у нас нет ни одного кредита и ни одного отряда пехоты. Но есть база и гарантия того, что враг нас не обнаружит, пока мы на него не нападём.
На нашей базе можно хранить не более x кредитов. Чтобы хранить больше, нужно строить хранилища: каждое стоит y (y≤x) кредитов и в каждом можно будет хранить дополнительно по максимум z кредитов. Строительство моментально (а вы что, реализма ожидали?).
Через каждые m минут нам привозят добычу на s кредитов. Добыча моментально конвертируется в кредиты и мы перераспределяем новые s кредитов и кредиты, имеющиеся на базе, по трём направлениям: строительство хранилищ, наём отрядов пехоты, хранение на базе. Количество кредитов, отданных на строительство хранилищ, должно быть кратно стоимости постройки одного хранилища. Количество кредитов, отданных на наём отрядов пехоты, должно быть кратно стоимости наёма одного отряда пехоты. Если мы отдаём на хранение больше кредитов, чем может храниться на базе (хранилища, на строительство которых мы только что отдали кредиты, тоже учитываются), то излишки кредитов исчезают.
Если после очередного описанного выше распределения на базе будет храниться хотя бы c кредитов, то считается, что мы накопили cc кредитов, и миссия считается пройденной. Один отряд пехоты стоит f (f≤x) кредитов. Сразу после оплаты, которая тоже моментальна, отряд будет ждать приказаний на нашей базе.
Проще и быстрее всего избавиться от врага в этом регионе – заставить его капитулировать. Для этого нужно привести к стенам вражеской базы больше отрядов пехоты, чем есть на вражеской базе.
По данным разведки, на вражеской базе e отрядов, а добраться до вражеской базы наши отряды пехоты смогут за t минут (все отряды, независимо от их количества, могут идти вместе). За сколько в лучшем случае мы завершим миссию?
Формат входных данных
Единственная строка содержит 9 целых чисел c,x,y,z,m,s,f,e,t (1≤c,x,y,z,m,s,f,e,t≤100;f,y≤x)
Формат выходных данных
Выведите одно целое число – искомое количество минут.
Пояснение к примеру
Чтобы максимально быстро накопить 2700 кредитов, мы можем построить 2 хранилища через 3 минуты после начала (в этот момент у нас появятся первые кредиты) и далее просто складировать все кредиты на базе. Тогда через 9 минут после начала на базе накопится необходимая сумма.
Чтобы заставить врага сдаться, мы можем через 3 минуты после начала нанять 10 отрядов пехоты и сразу же пойти на вражескую базу. Тогда через 6 минут после начала враги сдадутся. Несмотря на то, что пример не удовлетворяет ограничениям на входные данные в данной подзадаче, для получения баллов за текущую подзадачу необходимо, чтобы ваша программа выдавала правильный ответ на пример.
Sample Input:
2700 1000 150 1000 3 1000 100 7 3
Sample Output:
6
Напишите программу. Тестируется через stdin / stdout
Программка из консоли Visual Studio 2015:
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
int c, x, y, z, m, s, f, e, t, n;
c = 2700; x = 1000; y = 150; z = 1000; m = 3;
s = 1000; f = 100; e = 7; t = 3;
int a = ceil((e + 1) * f / s) * m + t;
if (c > x) n = ceil((c - x) / z);
else n = 0;
int b = ceil((c + n * y) / s) * m;
cout << min(a, b);
cin.get();
return 0;
}
В задаче про строку:
Задача E1. Циклические сдвиги vs разворот строки (4 балла)
На этой неделе на уроках информатики Васе рассказывают про строки.
Вчера Вася узнал, что такое циклический сдвиг:
k-й циклический сдвиг строки – это строка, полученная перестановкой первых k символов строки в её конец. В частности, 0-й циклический сдвиг строки – это сама строка.
И он написал программу, которая умеет перемещать первый символ строки в её конец k раз, получая таким образом k-й циклический сдвиг строки.
Сегодня Васе нужно реализовать разворот строки. Но у Васи тренировка. Ему некогда писать новые сложные программы. Поэтому он задался вопросом:
Можно ли циклическими сдвигами развернуть строку?
Благодаря своим друзьям Вася узнал, на какой строке (да, всего одной) будет тестировать его программу учитель, у которого нет времени рецензировать код каждого ученика. Поэтому вопрос упростился:
Можно ли циклическими сдвигами развернуть строку ss?
Помогите ему ответить на этот вопрос.
Формат входных данных
Первая строка содержит одно целое число n (1≤n≤10) – длина строки s.
Во второй строке – сама строка s, на которой будет тестировать программу Васи учитель. Состоит строка s только из строчных латинских букв.
Формат выходных данных
Если строку нельзя развернуть циклическими сдвигами, то выведите число −1. В противном
случае выведите такое целое число k (0≤k<n), что k-й циклический сдвиг строки s равен развёрнутой строке s. Если таких k несколько, выведите любое из них.
Пояснение к примеру
0-й циклический сдвиг строки s равен abac.
1-й циклический сдвиг строки s равен baca.
2-й циклический сдвиг строки s равен acab.
3-й циклический сдвиг строки s равен caba.
Развёрнутая строка s равна caba.
Единственное подходящее k равно трём.
Sample Input:
4
abac
Sample Output:
3
Напишите программу. Тестируется через stdin / stdout
- надо ли вообще реализовывать перестановки, а не просто считать, что ответ = да, если строка состоит из 2 палиндромов или сама есть палиндром? Тоже нужно больше тестов.
#include <iostream>
#include <string>
using namespace std;
int main() {
int n = 4;
string s("abac");
string d(s.rbegin(), s.rend());
s += s;
size_t found = s.find(d);
if (found == string::npos) cout << -1;
else cout << found;
cin.get();
return(0);
}
24.10.2019, 12:28 [1602 просмотра]