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

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

Задача А. В условии пропущен (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
  • Проголосовать: не нравится

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

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

long res = a/b;

if (a%b>0){

res++;

}

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

14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
В задаче C проще обойтись без нахождения центра окружности. Угол, под которым хорда видна из центра в 2 раза больше, чем угол, под которым она видна из точки на окружности. (Если угол тупой, то надо его вычесть из Pi, а потом только домножать на 2). Радиус окружности тоже находится по формуле.
14 лет назад, # |
  Проголосовать: нравится +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));
}
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
К автору. 

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

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


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

>нужно к значению дополнительно добавить количество
>всех вариантов, имеющих меньшую длину
то есть к значению которое мы нашли, добавить длину найденного значения? 
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нет, длину добавлять не надо.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I think A=1,B=2 and there is no '0'
    so we should subtract 64 from the char, not 65
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It is conventional to use positional systems where the least digit means zero, not one -- it is more logically consistent.

      I do not understand your reference to 64/65 at all.

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        65 is ASCII code for 'A'. So we can get ordinal number of the letter by subtracting it from the char variable.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Ah, I see. This is technical issue, dependant on language being used. BTW, here, 65 is magical number (which should be avoided).

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Коордианты центра окружности можно ещё найти заглянув в википедию
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По-мойму эти формулы нереально запомнить. А во время контеста не стоит смотреть вики
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Почему бы и не посмотреть ?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Думаю это читерство http://codeforces.com/blog/entry/80
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          по ссылке не утверждается что это должно считаться читерством,  правил то пока нету, а здравый смысл подсказывает, что такие вещи(стандартные формулы)имеет смысл смотреть в википедии.
          По моему это такое же 'читерство' как использование класса complex или реализaции map из stl.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
You can use TeX for the mathematical formulas.
14 лет назад, # |
  Проголосовать: нравится 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
?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

»
11 лет назад, # |
  Проголосовать: нравится +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?

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

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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);

»
10 лет назад, # |
  Проголосовать: нравится 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

»
10 лет назад, # |
  Проголосовать: нравится 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.

»
10 лет назад, # |
  Проголосовать: нравится 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.

»
9 лет назад, # |
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

  • »
    »
    9 лет назад, # ^ |
    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'

»
9 лет назад, # |
  Проголосовать: нравится +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.

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

    Tip: Solve the problem first in one dimension. Look for an analytical solution of the problem, no advanced data structures are needed.

»
8 лет назад, # |
  Проголосовать: нравится +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

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

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

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

      i try to multiplicate 1000000000X1000000000 and i want that the result was 10000000000000000000, but when i try do this operation in java, the answer of the multiplication give me how result this number -1486618624 whit datatype long and int and BigInteger.

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

        You have to store 1000000000 in a long also, if you want to make operations on it which makes it become a long. You can cast it meanwhile operation too, so you can do ((long) 10000000000)*10000000000, and it will give correct result.

        Long can handle numbers up to 9*10^18, for numbers bigger than that you need to use BigInteger.

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

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

»
6 лет назад, # |
  Проголосовать: нравится 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??

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

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

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

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

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

hi