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

Solutions for April Fools Day Contest 2023 in one line (Collection)
Автор thanhchauns2, история, 13 месяцев назад, По-английски

Hi, I collected the solutions for the problems of April Fools Day Contest 2023. Before the official editorial being posted, we can discuss about the problems here.

P/s: The editorial was published.

1812A - Вы робот?

Solution

1812B - Was it rated?

Solution

1812C - Цифры

Solution

1812D - Тривиальная гипотеза

Solution

1812E - Не задача по геометрии

Solution

1812F - Факторизация

Solution

1812G - Цветовое зрение

Solution

1812H - Ожидаемое твист

Solution

1812I - Скалолаз

Solution

1812J - Не-загадочный язык

Solution
  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

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

After about 300 — 400 steps, a positive number will be decreased down to 1.

Where did you get those numbers from? the conjecture asks whether every positive integer will eventually get to 1 by applying the operation however many times you'd like.

The biggest answer allowed (103 digits) will take more than 3,000 operations to reach 1, but it might take millions, or never reach 1 (proving the conjecture false), which means that the [REDACTED] part must be pretty small, or the grader wouldn't be able to evaluate a very large submission definitively.

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

    Here. Or I could remember the wrong number, I watched it a long time ago.

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

      I think it is around $$$350$$$:

      void solve(){
	int mx = 0;
	for (int n1 = 1; n1 < 100000; n1++){
		int steps = 0;
		for (int n = n1; n != 1; steps++){
			if (n & 1) n = 3 * n + 1;
			else n /= 2;
		}
		mx = max(mx, steps);
	}
	cout << mx << '\n';
}
      → Ответить
  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I believe the grader can just simulate $$$10^5$$$ ish steps to check if an answer is valid or not. In testing, the best number I could find was around $$$2.5 \cdot 10^4$$$ steps by just randomly generating $$$1000$$$ digit numbers and running them. In any event, it is probably impossible to find a positive integer that could work on the given constraints, and if you could, you could probably write a paper on it!

    → Ответить