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

Автор removed1, 17 лет назад, По-русски

Задача А. В условии пропущен (UPD: добавлен) пункт, что стороны плитки должны быть параллельны сторонам площади. Это условие делает задачу тривиальной: координаты разделяются, и ответ равен произведению количества плиток, необходимых для закрытия по вертикали, на количество плиток, необходимых по горизонтали.

т.е. answer = ceil (m/a) * ceil (n/a)

где ceil - наименьшее целое, большее или равное аргументу. В целых числах обычно ceil(a/b) заменяется на ((a+b-1)/b) -- внешние скобки нужны для задания порядка операций.

Неприятности в этой задаче заключались в основном с типизацией и приоритетом вычислений, что очень сильно зависит от стиля кодирования и языка.


Задача B.

Отождестим буквенную запись столбца с числом в системе счисления с основанием 26. ('A' = 0, 'B'=1, 'Z' = 25). Тогда при переводе из буквенного обозначения в цифровое нужно к значению дополнительно добавить количество всех вариантов, имеющих меньшую длину, плюс один (ради формализма можно считать, что вариантов нулевой длины -- один, и отказаться от добавления единицы).

При переводе из цифрового обозначения в буквенное нужно сначала найти, сколько знаков понадобится и из числа вычесть количество обозначений меньшей длины (для чего последовательно вычитаем из числа количество обозначений, имеющих длину 0, потом количество имеющих длину 1, 2, и т.п., пока число не станет меньше, чем количество обозначений, имеющих текущую длину и следующее вычитание привело бы к появлению отрицательного числа), переводим в систему счисления 'A'..'Z'.

Возможна интерпретация, реализуемая более компактно, но там сложнее не допустить ошибку при реализации.

Задача C.

Можно разбить на две подзадачи: найти центр правильного многоугольника и найти число углов.

Центр многоугольника обязан быть на одинаковом расстоянии от трех вершин. Можно воспользоваться обычным методом нахождения центра окружности, построенной по трем точкам. Напишу метод, которым воспользовался я. Для двух отрезков (x1,y1 - x2,y2) , (x2,y2 - x3,y3) находим среднюю точку, строим перпендикуляры, пересечение их даст искомый центр. Из подводные камни здесь: некоторые формулы в некоторых частных случаях дают деление на ноль. Лежать на одной прямой три точки из условия не могут (т.к. гарантируется корректность входных данных), а оставшийся плохой случаи можно устранить поворотом всей системы (т.е. всех трех точек) на случайно выбранный угол.

Нахождение числа углов

Поскольку при равном расстоянии от центра до вершины площадь правильного многоугольника возрастает монотонно с ростом N, можно просто перебирать все N, начиная с 3, и при нахождении первого подходящего печатать ответ и прекращать работу. Нужно, следовательно, для данного N уметь определять, могут ли данные вершины быть вершинами N-угольника -- критерий прост: углы между отрезками от центра до вершин должны быть кратны 2*pi/N. Воспользуемся свойством синуса: sin(x)=0, если аргумент кратен пи. Условие кратности угла между двумя отрезками заменяется при этом на следующее:

sin( N * (a[i]-a[j]) /2 )=0

т.к. имеем дело с арифметикой конечной точности, то:

fabs( sin( N * (a[i]-a[j]) /2 ) ) < eps

a[i]  посчитаем просто: atan2( y[i] - ycenter, x[i] - xcenter)

[/cut]

Разбор задач Codeforces Beta Round 1
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

17 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Вместо описанной конструкции (a+b-1)/b для нахождения ответа я использовал куда более очевидную (на мой взгляд) , но более длиную конструкцию:

long res = a/b;

if (a%b>0){

res++;

}

Ваш вариант тоже приму на заметку. Спасибо за разбор.

17 лет назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится
В задаче C проще обойтись без нахождения центра окружности. Угол, под которым хорда видна из центра в 2 раза больше, чем угол, под которым она видна из точки на окружности. (Если угол тупой, то надо его вычесть из Pi, а потом только домножать на 2). Радиус окружности тоже находится по формуле.
17 лет назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится
В задаче C после нахождения центра окружности и вычисления полярных углов можно найти угол α, равный 2π/N, как наибольший угол, который делит 2π, |a[0]-a[1]| и |a[1] - a[2]|. Это делается при помощи алгоритма Евклида:
double gcd(double x, double y)
{
    if (fabs(y) < EPS) return x;
    return gcd(y, fmod(x, y));
}
17 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
К автору. 

Хорошо бы перевести разбор на английский. Я бы хотел поместить его на главную и, как я уже писал, в прошедших контестах будет ссылка на разборы - я бы его поместил и туда.
17 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
>где ceil - наименьшее целое, не превосходящее аргумента.

по-моему тут опечатка) должно быть примерно так:
ceil(x) - наименьшее целое, не меньше x.


17 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
>'A' = 0, 'B'=2,
еще опечатка.

>нужно к значению дополнительно добавить количество
>всех вариантов, имеющих меньшую длину
то есть к значению которое мы нашли, добавить длину найденного значения? 
17 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Коордианты центра окружности можно ещё найти заглянув в википедию
17 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Я искал центр описанной окружности двумя вложенными тернарными поисками.

17 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

fabs( sin( N * (a[i]-a[j]) /2 ) ) < eps

а сколько лучше взять eps?

17 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
You can use TeX for the mathematical formulas.
17 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Problem B.
I can't pass Test case 6.
I don't konw why? Isn't there a test case like:
Input: R001C001
Ouput: 00A001
?
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Спасибо за разбор. Добавлю свои 5 копеек, надеюсь, что помогут кому-нибудь.

В задаче B не думал про системы счисления, а реализовывал восстановление размещения по номеру. В этом случае даже о количестве символов задумываться не приходится, все само собой получается (хотя это само собой получается). То есть количество символов при переводе можно не считать, это упрощение.

А вот по задаче С могу немного больше сказать. Действительно, центр можно не искать, ведь радиус мы можем найти из данных трех точек как окружности, описанной вокруг треугольника (действительно, если точки треугольника лежат на многоугольнике, то их описанные окружности совпадают). R = abc/4S. Площадь находится из векторного произведения. Тут в разборе предлагалось искать какие-то тангенсы и про какие-то деления на 0 говорилось, но можно без этого. Нам даны три хорды и если мы соединим концы хорды с центром, то получим равнобедренный треугольник. И у нас 3 таких треугольника и углы (из центра) нам нужно проверить, что кратны 2pi/n. Поскольку угол может быть тупой, то синус не знает как себя вести, поэтому можно схитрить и поделить этот угол на 2. И тогда все снова немного упростится, а синус этого половинного угла можно легко найти как d/2r, где d - противолежащая хорда. Не примите за хвастовство, но реализацию этого на С++ можете найти в списке решений этой задачи, если упорядочите их по размеру кода: первое решение.

Вот, надеюсь, что кому-то это пригодится :)

16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Who can give me the data on test 6?
Why I always get WA、 
»
14 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

B: what about "R1C204152" answer:"KOYZ169801"

»
14 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

When I use ceil((float)N/A) for problem 1A, it gives wrong answer while it gives a correct answer when I use ((N+A-1)/A). What is the catch behind it?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

Hello :) How do I represent 10^9 integers and input integers separated by space in a single line in C language?

  • »
    »
    13 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    For integers up to 10^9, you can use the 32-bit integral type long int. But if you multiply them, you have to use a 64-bit type, like long long int, otherwise the multiplication will overflow.

    As for input, the proper way to input a 32-bit integer on Codeforces is

    scanf ("%ld", & integer);

    and for a 64-bit integer

    scanf ("%I64d", & integer);

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone help me in problem 1B ? 1B - Spreadsheet

except this one "R1C204152" answer:"KOYZ169801", all the test cases which users gave in comments run on my machine. Help me please

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I have been trying 1B. But getting Runtime error. Here other people also have said same but no reason mentioned. Please suggest me what's wrong.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Problem B. My submission: here WA on test 6, but I can't trace this big test case. Can anyone help me with a one that can be traced and hacks my code? Thanks in advance.

»
11 лет назад, скрыть # |
← Rev. 7  
Проголосовать: нравится +8 Проголосовать: не нравится

Не могу понять в чем ошибка седьмого теста задания В (

И еще, в этом же задании, если компилировать код так:

int num = 0;
#define ALPHACOUNT 26
int j = 1;
string str1 = "BC";
ii = 0;
//.........
num += pow(ALPHACOUNT, j) * (str1[ii] - 'A' + 1);

num получит ожидаемое значение 52, если последнюю строку записать иначе, поменяв лишь местами функцию и выражение в скобках:

num += (str1[ii] - 'A' + 1) * pow(ALPHACOUNT, j);

в результате получаю 51 ??? О_о

С этим я так и не разобрался т.к. по другому ведь работает, но это ведь не вариант. На моем компе работают оба варианта, не работает только на сервисе. Ubutu Linux x86_64, g++ (Ubuntu 4.9.2-10ubuntu13) 4.9.2

  • »
    »
    11 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    У вас в вычислении длины ответа была нестыковка:

    В первом цикле вы просто делили num на ALPHACOUNT,

        do {
            if(num == ALPHACOUNT){
                length ++;
                break;
            }
            num /= ALPHACOUNT;
            length++;
        } while (num != 0);
    

    а во втором добавили корректировку числа по нулевому остатку:

        do {
            ostacha = num % ALPHACOUNT;
            num /= ALPHACOUNT;
            if(ostacha == 0){
                ostacha = ALPHACOUNT;
                num --;
            }
            ret[--length] = 'A' + ostacha - 1;
            
        } while (num != 0);
    

    Если перенести логику переходов в цикл вычисления длины, то получаем верное решение:

        do {
            ostacha = num % ALPHACOUNT;
            num /= ALPHACOUNT;
            if(ostacha == 0){
                ostacha = ALPHACOUNT;
                num --;
            }
            length++;
        } while (num != 0);
    

    Насчет использования pow — это все-таки вещественная функция, поэтому при приведении к целочисленному типу вы могли получить что-то наподобие (int)51.999999999 -> 51, а в другом случае (int)52.00000001 -> 52. Используйте лучше целочисленное возведение в степень, например:

        int binpow(int a, int n)
        {
            if (n == 0) return 1;
            if ((n & 1) == 0) 
            {
                int b = binpow(a, n >> 1);
                return (b * b);
            }
            else 
                return binpow(a, n - 1) * a;
        }
    

    P.S. У вас некорректно переводился тест R127686C474738 (можно открыть свою посылку и в информации к тесту увидеть данное сообщение):

    wrong answer 3223rd words differ — expected: 'ZZGD127686', found: '(ZZGD127686'

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

I can't solve problem A, please help me. I was using a 2D-Segment Tree to simulate the squares, but I got WA. I need help. If you help me, I'll give you a big hug.

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Please help: Why I'm getting a different output on different systems for Problem B sample test cases?

On my system:

On CF system:

My submission: 16392041

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

what datatype can i use to this big number in java? numbre: 1000000000000000000

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I found another solution for B here is my code: 33646284

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

can someone help me with the concept of epsilon in finding the gcd. Why do most of the accepted answers have it as 10^-4 . when i reduce it to 10^-5 , i get incorrect answer. Can someone tell me how did we decide this value because i think that lesser the value of eps meant a more precise answer??

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

can anyone explain me why my code is not passing testcase 6. https://codeforces.me/contest/1/submission/58648097

»
3 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

it was a nice contest....it was a og.

»
17 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Problem C is a really well-thought-out problem that blends classical geometry and trigonometry. I’m not necessarily a geometry fan, but I found this problem genuinely beautiful. The solutions I’ve seen are truly elegant, and it’s a bit sad that not many people have discussed it in this blog. The concepts used in the problem were things I learned in school but never expected to use in the context of competitive programming. I know this contest is quite old, and because of that, no one might read this, but if you do, I sincerely encourage you to give Problem C a try.

»
10 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

If you encounter a 1B issue, you can try special boundary value examples such as R23, R2, R1C, R2600,R288C494,R1C204152, and R457002, This may be effective.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

考古