3-этап республиканской олимпиады по информатике (Республика Казахстан)

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

Лично я разбил n на простые множители, а затем для каждого простого множителя находил k! и из них брал максимальный(если было несколько одинаковых простых множителей, то считал что то навроде ans=max(ans,минимальный к, чтобы k!/x+k!/x*x+k!/x*x*x была >= количеству одинаковых простых множителей)).

→ Ответить

vogel

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

И сколько в итоге получили баллов?

→ Ответить

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

← Rev. 3 →

Незнаю скоро выйдут резы(поидее я как то убито объяснил свое решение)
По А 100

→ Ответить

fiter

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

← Rev. 4 →

ошибка( написал неправильный алгоритм

→ Ответить

Anuar

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

Ммм что!?

→ Ответить

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

Для каждого простого делителя N сравниваем степень этого простого в N со степенью этого простого в K!.

А степень простого в K! находится так:

int calc(int K, int P) {
  int res = 0;
  while (K >= P) K /= P, res += K;
  return res;
}

→ Ответить

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

B примерно за O(8*N) (тама 8 различных случаев и каждый перебираем за n).
C — находил для каждой X-axis точки максимальный рост(который равняеться h+0.5 или же если пересекаются то h+0.75) и суммировал их.Где то за O(N*H+X).

→ Ответить

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

← Rev. 3 →

C. Тоже самое. Решение работает в худшем случаи за 2 * 10^8 при TL 2 секунды :(.

→ Ответить

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

я добавил break; когда он хоть раз пересекаеться(надеюсь затащит:D)

→ Ответить

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

← Rev. 2 →

У меня макстест работал у себя за 1.7. Но прошло не на full (86), пока не знаю почему.

UPD. WA оказывается. Тупая ошибка. Проверял до 10^6 надо до 10^6+10^4. :(

→ Ответить

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

в С можно по точкам ходить, отсортировав(для треугольника p[i], l[i], r[i]).

Надо не забыть только убрать все внутренние треугольники за N^2(я забыл)

→ Ответить

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

Надо еще с -10^4

→ Ответить

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

Это я не забыл, потому что в сэмпле есть :)

→ Ответить

Ximera

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

А можно сканлайном вот так:

Добавим в вектор для каждой верхней вершины треугольника (x, y) данный (x — 1, 1) и (x + 1, 1). Проходим по всем высотам i сверху вниз, и по вектору слева направо, поддерживая сканлайн и несколько случаев, когда мы добавляем sqrt(2), 3sqrt(2) / 2 или 2. Сложность O(2NH), и че-то все задачи решаются за 10^8, может это нормально для ваших серверов?

→ Ответить

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

У нас в каждом регионе по-другому и еще нету feedback-а.

→ Ответить

Anuar

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

+15

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

UPD: Они катают отсюда походу

→ Ответить

Zharaskhan

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

Чалил?

→ Ответить

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

"Чалил"

→ Ответить

chrome

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

çalıştı

→ Ответить

EeOneGuy

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

← Rev. 10 →

dASdasdasda asdf MInus give

→ Ответить

kshj78

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

лол :)

→ Ответить

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

Вы Б — шку как написали(не квадрат)

→ Ответить

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

← Rev. 2 →

У нас есть 8 случаев
насчет х(x1>=x2 или же x1<x2), y(y1>=y2 и y1<y2), z(аналогично).
2 случая * 2 * 2 = 8 случаев.
Каждый случай за O(N) находим максимум и минимум и его разницу берем. И из всех разниц берем максимальный.
Итоговая асимптотика O(8*n).

→ Ответить

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

блин) я так подумал но не смог доказать) завтра сюда резы скинте

→ Ответить

alibi

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

Скорее всего завтра будет игра, граф и строки. Всем удачи!

→ Ответить

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

игра и граф не будут отвечаю) геометрия,динамика и строки будут отвечаю) ну все равно удачи всем)

→ Ответить

alibi

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

Как на счет прошлой области???

→ Ответить

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

Ахах, ни игры, ни строк, ни динамики и ни графов не было

→ Ответить

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

зато геометрия была и F — ку можно двухмерной динамикой решить:D

→ Ответить

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

Не знаю как вы, а я прочитав условия, увидел первые 2 задачи как: напишите бинпоиск по ответу.

А геома халява по идее

→ Ответить

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

Увидел в B: решите это уравнение и там всё будет :)

→ Ответить

EeOneGuy

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

Задачи второго тура как решать?

→ Ответить

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

← Rev. 3 →

F можно за N, я написал за NlogN что то вроде этого:

solve(l, r) {
  int pos = rmq(l, r); // min element
  ans = max(ans, (r - l + 1) * a[pos]);
  solve(l, pos - 1);
  solve(pos + 1, r);
}

Вроде должно проходить.

→ Ответить

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

В D я написал жадное решение, сортируя девушек по росту, ищу для них минимальную пару.

→ Ответить

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

Можно диницу было пустить за N*sqrt(N) :)

Сколько баллов по второму кстати?

→ Ответить

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

Еще не проверили. Но не фулл. Я перебирал (p-a) тоже.)

→ Ответить

kshj78

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

Прошел 2-тур, может кто-то сделать разбор задач?

→ Ответить