I. Новорічні іграшки

Задача с SEERC 2015, [latex]\frac {1}{8}[/latex] финала.

Формулировка

«У кожного свята є один недолік – рано чи пізно, але воно закінчується. Ось і новорічні свята завершились і малому Дмитрику необхідно скласти іграшки у коробки. Частину іграшок він склав у одну коробку, а частину у іншу. Старший брат Дмитрика Петрик навчається в математичному класі. І його цікавить чи можна перекласти всі іграшки у одну з коробок (кожна коробка вміщує усі іграшки), якщо з одної коробки у іншу можна перекладати стільки іграшок, скільки у іншій коробці.

Вхідні дані:
Два числа N і M — кількість іграшок у першій та другій коробці (1 ≤ N, М ≤ 2000000000).
Вихідні дані:
Bиведіть 1 – якщо можна перекласти іграшки у одну коробку, або 0 – якщо такої можливості немає.»

Алгоритм

Ограничение на входные данные.
Предположим, что при некоторых [latex]N[/latex], [latex]M[/latex] ответ положительный. Пусть [latex]c = N + M[/latex].
Будем выстраивать последовательность шагов от конца к началу. Стартовая позиция — [latex]\left(c \quad 0 \right)[/latex](подарков в коробках). Очевидно, что прийти в неё можно только из [latex]\left( \frac {c}{2} \quad \frac {c}{2} \right)[/latex]. Определим вид предыдущей позиции: [latex]\begin{cases} a+b=c, \\ a-b=\frac { c }{ 2 } ; \end{cases}\sim \begin{cases} 2a=c+\frac { c }{ 4 } , \\ b=a-\frac { c }{ 2 } ; \end{cases}\sim \begin{cases} a=\frac { 3c }{ 4 } , \\ b=\frac { c }{ 4 } ; \end{cases}[/latex]. Принципиально важно, что показатель знаменателя на каждом шаге монотонно возрастает. В силу конечности [latex]c[/latex], процесс конечен. Меньший член пары имеет общий вид [latex]\frac {c}{2^{n}}[/latex], следовательно, [latex]c = N + M = 2k[/latex] (здесь и далее предполагается, что все переменные — некоторые натуральные числа).
Заметим, что постоянный множитель [latex]k[/latex] не влияет на сходимость. Следовательно, на него можно сократить и суммы [latex]N + M[/latex]. Максимальный из таких [latex]k[/latex] будет [latex]gcd \left(N, M \right)[/latex].
Полученный результат позволяет сформулировать необходимое условие: если решение есть, то сумма чисел [latex]N[/latex] и [latex]M[/latex] равна некоторой степени двойки с точностью до НОД([latex]N, M[/latex]).
Достаточно условие сходимости.
Пусть [latex]N, M[/latex] — некоторые числа, удовлетворяющие необходимому условию. Тогда [latex]\exists n: N=2^{ n }-M[/latex].
Рассмотрим следующий шаг, предполагая, что [latex]N \ge M[/latex]: [latex]\left(2N \quad 2^{n}-2N\right) \sim \left(N \quad 2^{n-1}-N \right)[/latex]) — задачу удалось свести к подзадаче. Повторяя аналогичную процедуру, на [latex]n[/latex]-м шаге придём в позицию, эквивалентную [latex]\left(1 \quad 2^{0}-1 \right) \sim \left(1 \quad 0 \right)[/latex], т.е. последнему шагу. Следовательно, для любого набора данных, удовлетворяющих необходимому условию, решение существует. Следовательно, условие является необходимым и достаточным, с поправкой на тривиальный случай [latex]N = M[/latex].

Реализация

ideone: http://ideone.com/OxWVLi

#include <cstdio>
inline int gcd(int a, int b){
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}
int main()
{
    int a, b, c;
    scanf("%d %d", &a, &b);
    c = (a + b)/gcd(a, b);
    printf("%d\n", (a == b || c == (c & (-c))));
    return 0;
}

#include <cstdio>

inline int gcd(int a, int b){

while(b) b ^= a ^= b ^= a %= b;

return a;

}

int main()

{

int a, b, c;

scanf("%d %d", &a, &b);

c = (a + b)/gcd(a, b);

printf("%d\n", (a == b || c == (c & (-c))));

return 0;

}

ideone: http://ideone.com/Xnupjz

import java.util.*;
import java.io.*;
import java.math.*;
 
class Ideone { 
    public static int gcd(int a, int b){
        while(b != 0) b ^= a ^= b ^= a %= b;
        return a;
    }
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt(); int b = in.nextInt();
        int c = (a + b)/gcd(a, b);
        System.out.println((a == b || c == (c & (-c))) ? 1 : 0);
    }
}

import java.util.*;

import java.io.*;

import java.math.*;

class Ideone {

public static int gcd(int a, int b){

while(b != 0) b ^= a ^= b ^= a %= b;

return a;

}

public static void main(String args[]) {

Scanner in = new Scanner(System.in);

int a = in.nextInt(); int b = in.nextInt();

int c = (a + b)/gcd(a, b);

System.out.println((a == b || c == (c & (-c))) ? 1 : 0);

}

Детали реализации

Задачи тура подразумевали лаконичные реализации решений. Использование битовых операций позволяет легко ответить на вопрос, является ли сумма чисел некоторой степенью двойки, а также вычислить НОД двух чисел методом приведения в смятение, для чего используется, на мой взгляд, весьма красивое наблюдение о свойствах функции XOR.

Related Images:

Похожее

3 thoughts on “I. Новорічні іграшки”

Мазурок Игорь Евгеньевич says: 10/05/2015 at 14:55

Отлично. Зачтено.
Только укажите в начале текста откуда взята задача.

Войдите, чтобы ответить
- Іванов Вячеслав Володимирович says: 17/06/2015 at 15:37
  
  Указал источник перед текстом.
Антоненко Александр Сергеевич says: 23/12/2015 at 01:06

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

Войдите, чтобы ответить