#include<iostream>#include <cstring>#include <cmath>using namespace std;
int n,a,b,i, ans;string s;
int main() { //freopen("abcode.in", "r", stdin); //freopen("abcode.out", "w", stdout); cin >> n; cin>>s; for ( i= 0; i <s.size(); i++) if(s[i] == 'B') b++; else a++; ans = b; i = 0; while (i < s.size()) if (s[i] == 'B') b--,i++; else break; ans = min(ans, b + 1); i = s.size() - 1; while (i >= 0) { if (s[i] == 'A') a--, i--; else break; } i = 0; ans = min(ans, a + 1); while (i < s.size()) if (s[i] == 'A') a--,i++; else break;
ans = min(ans, a + 1); cout << ans; system("pause"); return 0;}
Сначала найдем кратчайший путь от 1-ой вершины до последней. Обозначим длину как $len$. Ищем все пути от 1-ой вершины до последней (можно dfs-ом) с длиной $len$, затем еще раз ищем пути, но уже с длиной $len+1$, ..., и т.д. до того, как кол-во найденных путей стало больше или равно $l$. Затем сортируем пути и выводим первые $l$ из них.
#include<fstream>
#include<cmath>
using namespace std;
int main(){
ifstream cin("input.txt");
ofstream cout("output.txt");
double n,m,b;
cin>>n>>m;
b=pow(m,n);
if(pow(m,n)>1000000000)
cout<<0;
else
cout<<b;
return 0;
}
const fi=''; fo=''; mn=100000;var a: array[0..mn] of char; n,dd,db: integer; f,g: text; i: integer; begin dd:=0; db:=0; a[0]:='C'; assign(f,fi);reset(f); assign(g,fo);rewrite(g); readln(f,n); for i:=1 to n do begin read(f,a[i]); if a[i]<>a[i-1] then inc(dd); if a[i]='B' then inc(db); end; if a[n]='A' then dec(dd); if db<dd then dd:=db; write(g,dd); close(f); close(g); end.
#include<iostream>
using namespace std;
int main()
{
int n,i,c=0,a,b;
cin>>n;
for(i=1;i<=n;i++)
{
a=i/10%10;
b=i%10;
if(a*b>b+a)c=c+1;
}
cout<<c;
return 0;
}
Не сложная задача на динамическое программирование (На контесте мне так не показалось =) )
Тут нужно заметить две вещи:
1) Допустим в оптимальном ответе остаются ряды a1,a2,a3,...,ak, при чем ai < ai + 1, для 0 <= i < k, то удалять ряды между (a1,a2); (a2,a3); (a3,a4)... можно в любом порядки и они не влияют друг на друга.
2) Теперь нужно выяснить можно ли удалить все ряды между фиксированными двумя (l,r). Давайте поймем какой ряд был удален последним, это такой ряд что он либо ниже l,r, либо выше l,r. Переберем этот ряд среди всех от i = l + 1,r - 1. Теперь мы разбили нашу задачу, на две аналогичные, т.к удаление рядов между (l,i) и (i,r) не зависят друг от друга. Если мы не нашли такой ряд, что можно удалить все слева и справа значит (l,r) ряд нельзя освободить.
Теперь можно применить обычное ДП используя только те переходы, который мы посчитали выше, что то похожее на нахождение наибольшей возрастающей подпоследовательности.
Странная задача, в которой проходит почти все. Основная идея: если ЖКВД стоит в одном шаге от края, то стреляем в эту клетку(крайнюю), иначе, стреляйте куда хотите. Видимо, задача подразумевалась, как халява и на то, чтобы научиться решать интерактивы.
Сначало нам нужно минимизировать количество пройденных "-1", а потом сумму остальных штрафов. Заменим все "-1" на число $10^{10}$ и найдем минимальный путь из левой верхней в правую нижнюю Дийкстрой с кучей(все штрафы у нас неотрицательны). На сколько Вы знаете, Дийкстра с кучей работает за $O(M log N)$, а так как количество ребер у нас пропорционально количеству вершин, то все получится. У меня почему-то не проходило решение с std::set на Си++, потом зашло на std::priority_queue. Также можно попасть на ML. У меня он был и мне пришлось работать с неявным графом, у других может проходило и тупо.
Если присмотреться к условию, то нас просят найти максимальный поток минимальной стоимости в сети. На Си++ проходило решение за $O(n^3 m)$, но на Яве приходилось оптимизировать. Что здесь предполагали авторы, осталось для меня загадкой.
Для начала нужно считать всю информацию и как-то поладить с переменными, которые равны. То есть все переменные равные между собой сжимаем в одну переменную. Сделаем это любым способом, ограничения маленькие и позволяют все. Если переменные отношения которых нам нужно узнать ужались в одну вершину, то сразу выводим, что они равны и выходим. Иначе:
Теперь из оставшихся переменных построим орграф, в котором присуствует ребро A->B, если A>B;
Чтобы проверить, больше ли первая переменная второй, достаточно проверить существование путя от первой ко второй. Так попробуем найти путь из первой во вторую. Если нашли, то выведем "Больше", иначе попробуем найти путь из второй в первую. Если нашли, то выведем "Меньше". Иначе выведем, что тут ничего не понятно.
Можно придумать несколько формул(которые в итоге сводятся к одной).
Я рассуждал так: подсчитаем вероятность того, что наша песня еще не играла. Потом эту вероятность можно будет отнять от 1 и получить ответ. Мы знаем, что было K проигрываний и из N песен могла прозвучать любая, кроме нашей, то есть N-1. Таких различных вариантов $(N-1)^K$, а всего вариантов $N^K$, то есть ответ $1-(\frac{N-1}{N})^K$. И не забываем умножить на сто, чтобы получить проценты.
Когда я увидел эту задачу, то мне сразу пришло решение с MinCost-MaxFlow алгоритмом. Возможно есть и проще, но этот разбор использует именно идею минимального по весу максимального паросочетания.
Давайте подсчитаем, сколько каких букв в первой и во второй строке. Создадим сеть, где кроме стока и исктока будут две доли вершин - для первой строки и второй. Проведем пропускную способность из истока к буквам первой доли такую, сколько раз эта буква встречается в нашей первой строке. Аналогично по второй строке проведем ребра из второй доли к стоку. Цена таких ребер равна нулю.
Далее будем делать ребра из первой доли во вторую, неограниченные пропускной способностью для ребер, которые нам даны во входных данных(других просто нет). Цена таких ребер берется из входных данных, но тут есть одно "но". Возможно выгодно для получения буквы "Б" из буквы "А", предворительно обменять ее на букву "В". Поэтому флойд по ценам в начале не помешает. И таким образом у нас получится матрица расстояний из которой надо перенести все ребра у которых цена не бесконечность в сеть, между первой и второй долей. Не забудьте, что g[i][i] = 0;
Когда мы построили сеть, найдем Макс.Поток-Мин.Строимости в сети. Если поток не равен длине второй строки, то ответ "Impossible". Иначе выводим стоимость.
Время рабты алгоритма: время работы алгоритма нахождения потока минимальной стоимости + время Флоида. При реализации потока ФордБеллманом выйдет что-то типа $O(n^2m^2 + n^3)$, а n у нас порядка 26*2, ребер (26*2)^2. Но это оценка сверху и все прекрасно проходит.
В силу небольших ограничений на длину строк мы можем перебрать всевозможные варианты соединений, которые могут быть получены из данных имен. Сделаем это следующим образом: будем убирать по одному символу справа из первого имени и приписывать к нему второе, при этом каждый раз будем проверять: начинается ли образующаяся таким образом строка с первого имени, если это так, то данная строка удовлетворяет необходимому условию (заканчиваться она будет вторым имененем по построению). При встрече очередной строки, начинающейся и заканчивающейся нашими именами, будем сравнивать ее с ранее найденной, на текущий момент самой короткой. Если текущая окажется короче, то ее следует запомнить. После перебора всех вариантов сокращения первой строки следует поменять строки местами, для чего удобно описать отдельную функцию search(a,b) , которая будет сокращать первую строку, припысывая вторую. Следует так же отметить, что в процессе сравнения нужно преобразовывать все символы либо в верхний, либо в нижний регистр. В начале в качестве самой короткой строки можно считать строку, состоящую из суммы исходных имен, которая очевидно обладает необходимым свойством. По завершению поиска в качестве ответа просто останется вывести ту строку, в которой мы хранили текущий наикратчайший вариант.
Алгоритмическая реализация вышеописанной идеи:
String a,b,m,s;
void search(a,b){
for i=len(a)..0{
s = a[1..i]+b;
if ((len(lm)>len(ls) or len(lm)=len(ls) and m>s) and lower(a)=lower(left(s,len(a)))) m=s;
}
}
read(a,b);
m=a+b;
search(a,b);
search(b,a);
write(m);
U hleba 2 storony i v skovorodu pomewaetsya 2 kuska. Teper prosto pereberem slu4ai i sostavim algoritm (hotya eto slojno nazvat' algoritmom ^^ ). N=1: 1 minuta na 1 storonu, i togo 1+1=2 minuty.
N=2: eto 2 minuty (dumau vse dogadalis' po4emu). N=3: polojim 2 kuska (1min), dalwe perevernem 1 iz nih i lojim druguyu (1min), i pod konec perevernem 1 i polojim tu, kotoraya nedojarilas' (1min), v summe 3 minuty. N=4: lojim 2 raza po 2, i togo 4 minuty. N=5: dojarivaem 2 kuska (2 min), ostalos 3 (kogda N=3 > vremya 3min) i togo 2+3=5 minut.
Polu4aetsya kogda N=1 otvet 2. a v ostalnyh slu4ayah otvet raven samomu N.