Как я решал задачу А и пытал В,С

№	Пользователь	Рейтинг
1	tourist	3880
2	jiangly	3669
3	ecnerwala	3654
4	Benq	3627
5	orzdevinwang	3612
6	Geothermal	3569
6	cnnfls_csy	3569
8	jqdai0815	3532
9	Radewoosh	3522
10	gyh20	3447

№	Пользователь	Вклад
1	awoo	161
1	maomao90	161
3	adamant	156
4	maroonrk	153
5	atcoder_official	149
6	-is-this-fft-	148
6	SecondThread	148
8	Petr	147
9	nor	144
10	TheScrasse	143

Задача А. STL + немного мозгов.

map<string,int> M_pair; // считал входные данные в M_pair;
map<string,vector<pair<int,int> > > M_step; // сюда записывал ходы, игрока;
vector<pair<int,string> > Res; // а сюда скинул, ключ - выигрыш игрока, и имя игрока ;
sort(Res.being(),Res.end(),predicat); // создал предикат по которому происходила сортировка Res, игроков;
predicat //если выигрыш одинаковый, тогда смотрим в M_step хронологию событий когда игрок впервые заработал, сумму m;

решение: http://ideone.com/xLNBhopu accepted.

Задача В. Почти ни каких соображений нету((

сначала предположил избегать чисел 2,5,10 то есть тех которые создают нули, но увидев тест понял что это не правильно.

решение: http://ideone.com/o5wvzGpT wrons answer on test 13, спасибо тем кто помог.

Задача С. Вообще я ее правильно понял???

Три круга на поле и нужно, найти точку равноудаленную от трех окружностей?

Мнение:

Хоть я и решал задачу А два часа, мне понравился этот процесс=)

Комментарии (45)

Показать архивные | Написать комментарий?

Jokser

14 лет назад, # |

По задаче B. Для каждого числа в таблице посчитал кол-во двоек и пятерок. Именно числа 2 и 5 создают нули. Кол-во нулей будет min(двойки, пятерки).

Далее идет простая динамика, как если бы мы искали минимальный путь в таблице. Формула:

a[i][j]=a[i][j]+min(a[i-1][j],[i][j-1]).

Пытаемся найти один путь с мин. кол-вом двоек и второй путь с мин. кол-вом пятерок. Далее сравниваем, в каком из двух случаев получилось меньше нулей.

Отдельно нужно рассмотреть случай, когда в таблице есть просто 0. Тогда у нас уже есть ответ - 1. Плюс строим по нему любой путь, который включает в себя клетку с нулем.

→ Ответить

14 лет назад, # ^ |

двойки и пятерки - множители числа. их кол-во.

Salat

ага все таки был где то рядом)

спасибо, решение почти написал, завтра проверю.

интересно тут можно иходники выкладывать?

it4.kp

Сразу оговорюсь, что С я не сдал и пробовать неохото ))
Но вот мои мысли по ее поводу (возможно они вообще мимо кассы):

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

ivan.popelyshev

Множество точек у которых отношение расстояний до точки A и B одинаковое это либо прямая - серед. перпендикуляр AB (если отношение единица) либо окружность с центром в A или B. окружность определяется по двум подходящим точкам лежащим на AB.

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

среди таких точек берём наиболее близкую к любому из стадионов.

removed1

Какая окружность нафиг? Эллипс с фокусом в точке (в нашей задаче той, где стадион меньше).

Друг, ты ошибся. Множество точек C таких что AC-BC = const это эллипс.
Множество точек C таких что AC/BC = const>1 это окружность с центром в B.

Пусть R - расстояние от точки до какого-либо стадиона радиуса r. тогда r/R это косинус половины угла под которым виден стадион.

Так что нам нужно именно отношение.

*чего-то меня глючит. Не с центром в A или B а с центром лежащим на AB.

Центр сдвинут по прямой AB на |AB| *R1^2/(R2^2 - R1^2), верно?

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

все в порядке, ты считал от А, я считал от B : - )

ещё одна бага:
эллипс с фокусами в A, B это AC+BC=const.

Мои извинения

AndreySiunov

Ну догадки насчёт 10-ок это не то.. но вот если возникли догадки насчёт 2 и 5 то следующий шаг - это то, какая именно динама нужна... тут мне помог на мой взгляд хороший тест:

1 4 100

25 5 8

7 8 9

Кстати.. начёт возможного нуля в таблице я чуть не согласен :) всё-таки у нуля на мой взгяд круглость не 1 :) мне кажется число 0 - это совершенно круглое число :)

xdumlex

У нуля круглость один, потому как круглость - это количество нулей в конце числа.
Поэтому 2 динамики надо пробежать, потом взглянуть на ответ, если меньше 1, то ответ из динамики берем, если больше, то просто путь делаем, чтобы 0 содержал. Ну и конечно когда таблицу составляем для динамик надо не забыть в клетке где ноль сделать очень много двоек и пятерок ;)
3 задача - бинпоиск по углу. Можно попытаться системку сделать, но руки пока не дошли.

Я так и пробил вторую... только вот я не делал "Ну и конечно когда таблицу составляем для динамик надо не забыть в клетке где ноль сделать очень много двоек и пятерок ;) "

я просто отдельным случаем проверил есть ли ноль :) а в функцию вычисления количества 2 и 5 в составе числа довил условие что если 0 то вернуть 0.

Почему "вернуть 0" как раз таки далеко не ноль.
Вот тест, все поймете:
5
1 1 1 1 1
1 1 1 1 1
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1
Поясню:
если идти через ноль, то в итоге произведение = 0 и круглость 1, если же идти по единицам только, то произведение = 1 и круглость 0.

да вот щас тоже сижу и думаю почему у меня вернуть ноль прокатило :)

ОМГ! Я сделал тест на котором валится моя прога :-D

5
1 1 1 1 1
1 1 1 1 1
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1

этот не катит, потому что у меня по алгоритму вначале идёт вниз...

1 1 1 1 1

0 1 1 1 1

а вот этот валит :)

maslowmw

Странный алгоритм если идет сначала вниз а потом еще куда то.. хм

Не.. это, естественно, образно сказано! Просто суть в том что мы выбираем первым при равенстве случаев - верхний от текущего элемент или левый.. ну в моём алгоритме верхний

Обшибся.. наоборот левый...

Кстати! Сорь если слишком обильное число сообщений

Что насчёт глобального ретеста уже после окончания контеста? :-D

Не.. ну это никак нельзя допустить :) это же не солидно :-D

З.Ы. Данное сообщение написано по большей части не из-за фразы "это же не солидно :-D ", никоим образом не хочу поставить уважаемого Михаила в неудобное положение, а скорее из-за "Не.. ну это никак нельзя допустить :) " так так у меня ас :)

сделал как Вы писали, на 13 тесте получил wrong answer :( problem B

#include <iostream>

#include <vector>

using namespace std;

int get_count_of_div(int c,int div)

{

int i = 0;

while(c % div == 0){ i++; c /= div;}

return i;

}

vector<char> dinamic(vector<vector<int> > a,int n,int &res)

for(int i = 1; i < n; i++)

a[i][0] += a[i - 1][0];

for(int j = 1; j < n; j++)

a[0][j] += a[0][j - 1];

a[i][j] += min(a[i - 1][j],a[i][j - 1]);

vector<char> path;

int x = n - 1,y = n - 1;

while(x > 0 && y > 0)

if(a[x][y - 1] < a[x - 1][y])

{path.push_back('R');y--;}

else

{ path.push_back('D');x--;}

if(y != 0)while(y > 0){path.push_back('R'); y--;}

if(x != 0)while(x > 0){path.push_back('D'); x--;}

res = a[n - 1][n - 1];

return path;

vector<char> get_ans(int x,int y,int n)

vector<char> res;

for(int i = 0; i < x; i++) res.push_back('D');

for(int i = 0; i < y; i++) res.push_back('R');

for(int i = x + 1; i < n; i++) res.push_back('D');

for(int i = y + 1; i < n; i++) res.push_back('R');

return res;

int main()

int n;

scanf("%d",&n);

vector<vector<int> > a(n,vector<int>(n,0));

vector<vector<int> > dinam_two(n,vector<int>(n,0));

vector<vector<int> > dinam_five(n,vector<int>(n,0));

bool label_null = false;

vector<char> ans_if_null;

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

scanf("%d",&a[i][j]);

if(a[i][j] == 0)

label_null = true;

a[i][j] = 2000000000;

ans_if_null = get_ans(i,j,n);

dinam_two[i][j] = get_count_of_div(a[i][j],2);

dinam_five[i][j] = get_count_of_div(a[i][j],5);

int s_two = 0,s_five = 0;

vector<char> path_two = dinamic(dinam_two,n,s_two);

vector<char> path_five = dinamic(dinam_five,n,s_five);

if(label_null && min(s_two,s_five) > 1)

printf("1\n");

copy(ans_if_null.rbegin(),ans_if_null.rend(),ostream_iterator<char>(cout,""));

printf("%d\n",min(s_two,s_five));

if(s_two < s_five)copy(path_two.rbegin(),path_two.rend(),ostream_iterator<char>(cout,""));

elsecopy(path_five.rbegin(),path_five.rend(),ostream_iterator<char>(cout,""));

return 0;

О_о че с кодом стало УЖАС.

ВОТ СЮДА ЗАЛИЛ http://ideone.com/o5wvzGpT

по-хорошему надо подобный сервис тут сделать.

мне кажется косяк тут

78: a[i][j] = 2000000000;

это что то вроде много 2 и 5, но щас поправил сделал так:

if(a[i][j] == 0){

dinam_five[i][j] = 1000; //много петерок

dinam_two[i][j] = 1000; //много двое

esle

{//иначе считаем сколько их на самом деле

все равно 13 тест не проходит

2000 - макс длина пути, на каждом возможно до 9-ти пятёрок... т.е. 1000 слишком мало

нужно условие

if(a[i][j] == 0)
{
label_null = true;
a[i][j] = 2000000000;
ans_if_null = get_ans(i,j,n);
}

поставить после
dinam_two[i][j] = get_count_of_div(a[i][j],2);
dinam_five[i][j] = get_count_of_div(a[i][j],5);

поправив в условии то, что нужно менять значения dinam_two[i][j] и dinam_five[i][j] на очень много

соответственно адаптировать get_count_of_div под 0.

сделал, но валится по прежнему(( видимо я где то в реализации допустил еле заметную ошибку.

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

как можно комент удалить?

может у кого есть хитрый тест? ату я уже их кучу на генерировал, а толку нуль.

4
1 625 1 1
1000 1 8 8
1000 1 8 2

1000 1 8 1

Там путь генерируется неправильно. Ошибка в push_back. Вообще там много использования STL не к месту.

dinamic(vector<vector<int> > a -- передача вектора по значению (надо по константой ссылке).

dynamic(const vector<vector<int> > &a

4
100 100 0 100
100 100 100 100
100 100 100 100
100 100 100 100

поменять местами две верхние с двумя нижними

for(int i = 0; i < y; i++) res.push_back('R');
for(int i = x + 1; i < n; i++) res.push_back('D');
for(int i = y + 1; i < n; i++) res.push_back('R');

В общем не надо было так делать, чтобы в результате лежала строка задом наперед и обращать ее только перед выводом в файл

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

Копипаст это антипаттерн номер один

ldyllic

2 года назад, # |

-11

Wondering a lot why such posts appear in my "Recent actions"...

Блог пользователя Salat