Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1532
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1532
Throwing Balls
By Cristhian Bonilha, UTFPR 
Brazil
Timelimit: 1
Your friends invented a new competition: Throwing Balls. The goal is simple, just throw a ball in a way that it falls into a hole N meters ahead.
When the ball is thrown, let's say that at an integer speed V, it stays in the air for V meters and then touches the ground. It repeats this process V times. After it touches the ground V times, it changes its speed to V-1, and the previous process repeats, until the speed is equal to 0.
For example, if the ball is thrown at a speed equal to 3, it will touch the ground at the following points: 3, 6, 9, 11, 13, 14; as it can be seen in the picture below.
You can throw a ball at an integer speed less than or equal to V. Given the distance of the hole, say if it's possible for you to throw the ball and that it falls exactly into the hole.
Input
There will be several test cases. Each test case contains two integers, N and V (1 ≤ N ≤ 1000, 1 ≤ V ≤ 30), representing the distance of the hole, and the maximum speed that you can throw the ball.
The last test case is indicated when N = V = 0, which should not be processed.
Output
For each test case, print one line containing the word “possivel” (without the quotation marks), if it is possible to throw the ball at an integer speed less than or equal to V, in a way that it falls into the hole, or “impossivel” otherwise.
| Sample Input | Sample Output |
|
14 3 |
possivel |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <locale>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define FOR(i, a, b) for (int i = a; i < = b; ++i)
#define RFOR(i, b, a) for (int i = b; i >= a; --i)
#define REP(i, N) for (int i = 0; i < N; ++i)
#define MAX 110
#define pb push_back
#define mp make_pair
using namespace std;
const double pi = acos(-1.0);
struct pt;
typedef pair < pt, pt> line;
typedef vector<pt> polygon;
typedef pair < pt, int> ddi;
typedef pair dd;
typedef pair < string, string> ss;
int readInt()
{
bool minus = false;
int result = 0;
char ch = getchar_unlocked();
while (true) {
if (ch == '-')
break;
if (ch >= '0' && ch < = '9')
break;
ch = getchar_unlocked();
}
if (ch == '-')
minus = true;
else
result = ch - '0';
while (true) {
ch = getchar_unlocked();
if (ch < '0' || ch > '9')
break;
result = result * 10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}
int matrix[MAX][MAX];
int main()
{
int d, v;
while (scanf("%d %d", &d, &v) && d + v) {
bool flag = false;
for (int k = v; k >= 1; k--) {
int temp = 0;
while (v) {
for (int i = 0; i < v; i++) {
temp += v;
if (temp == d) {
printf("possivel\n");
flag = true;
break;
}
}
if (flag)
break;
v--;
}
if (flag)
break;
v = k;
}
if (!flag)
printf("impossivel\n");
}
return 0;
}
Input
13 3
12 3
5 3
30 4
0 0
Output
possivel
impossivel
possivel
possivel