Programming contests

ACM ICPC programozó csapatverseny, házi forduló, 2014. október 22.

October 22, 2014 10:05 AM – October 22, 2014 3:05 PM

Say NO to Memorization

Kamran is preparing for his term final examinations. He understands all the algorithms in the syllabus and expects a creative question in the examination hall. But when he looks at a question paper of previous year, he realizes that he is expecting too much. It is full of questions like “Write the pseudocode of Matrix Chain Multiplication Algorithm.”, “Write the pseudocode of BFS algorithm.”, all of which can be answered with the help of memorization (not memoization). In almost all his courses, “Commit to Memory and Vomit to Exam Sheet” is the ultimate method of getting good marks. The fact is clear and simple that one cannot expect creative questions from people who are not creative at all. This lack of creativity is evident in his country’s poor status in Science & Technology field. His mind gets lost for some time in the past when he dreamt of learning wonderful things while studying in the so-called best science & technology university of his country, and then he comes back again to the bitter present, lost in his clerical study materials.

Kamran has a very simple but uncommon (I mean cannot just be copied from pages of your book) problem for you. Can you prove by solving it that you are not one of those who only memorize pseudocodes before algorithm exam? The problem is stated below:

A general equation of second degree with two variables is ax2 + by2 + cxy + dx + ey + f = 0. You can see that it has six terms on the left hand side (LHS). A general equation of second degree with two variables and with only terms of even degree is ax2 + by2 + cxy + d = 0, which has only four terms in LHS. A general equation of third degree with two variables with only terms of odd degree is ax3 + by3 + cx2y + dxy2 + ex + fy = 0, which has only six terms in LHS. Given the degree (n) and number of variables (v), your job is the following:

  1. If n is even, you should determine the number of terms in a general equation of n-degree with v variables and only with terms of even degree.
  2. If n is odd, you should determine the number of terms in a general equation of n-degree with v variables and only with terms of odd degree.

Input Specification

The input contains at most 5000 lines of input. Each line contains two integers n (0 ≤ n ≤ 1000) and v (0 < v ≤ 1000). The input is terminated by a case whose value of n and v is zero. This case must not be processed. The meaning of n and v is given in the problem statement.

Output Specification

For each line of input, produce one line of output. This line contains one integer T that indicates the number of terms on the left hand side of a general equation of degree n, v variables and only of odd degree terms when n is odd or only of even degree terms when n is even. You can assume that the input will be such that output will always fit in a 64-bit signed integer.

Sample Input

  1. 2 2
  2. 4 2
  3. 20 10
  4. 0 0
download as text file

Output for Sample Input

  1. 4
  2. 9
  3. 17978389
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019