Problem: ethanstring (2018 quals)

Ethan's doing his very first programming assignment: implementing a
`contains()` function. This function takes two strings, **A** and **B**, and
returns `true` if **A** is a substring of **B**, and `false` otherwise.

Here's the algorithm that Ethan has come up with. Note that |**A**| denotes
the length of **A**, and the individual characters of the strings are
1-indexed.

  1. Set _i_ and _j_ to each be equal to 1.
  2. If _i_ > |**A**|, return `true`.
  3. If _j_ > |**B**|, return `false`.
  4. If **Ai** = **Bj**, increment _i_ and _j_ by 1 each, and return to Step 2.
  5. If _i_ = 1, increment _j_ by 1, and return to Step 2.
  6. Set _i_ to be equal to 1, and return to Step 2.

As the TA in charge of grading Ethan's assignment, this doesn't look quite
right to you. To make sure Ethan doesn't get any more credit than he deserves,
you'd like to find some inputs for which his algorithm returns `false` even
though it should return `true`.

The professor teaching this class has provided you with a half-written list of
test cases. In particular, it's a list of inputs for the **A** parameter, and
you're free to come up with your own inputs for the **B** parameter. For each
given string **A**, you want to find a string **B** that will cause Ethan's
algorithm to return the wrong output (`false` instead of `true`), if possible.
**A** will only contain uppercase alphabetic characters, and **B** must follow
the same constraint. The test cases shouldn't be too large, so **B** must also
contain at most 10,000 characters.

### Input

Input begins with an integer **T**, the number of given strings. Then, **T**
lines follow. Each line contains a single string, **A**.

### Output

For the _i_th given string, print a line containing "Case #_i_: " followed by
any valid string **B** that will cause Ethan's algorithm to return the wrong
value, or "Impossible" if no such string exists.

### Constraints

1 ≤ **T** ≤ 100  
1 ≤ |**A**| ≤ 2,000  

### Explanation of Sample

In the first case, _i_ and _j_ will have these values in order the first 10
times the algorithm is at Step 2:

    i j
    ---
    1 1
    2 2
    1 2
    1 3
    1 4
    1 5
    2 6
    3 7
    4 8
    1 8

Please note that other outputs for example cases 1 and 3 would also be
accepted.



Sample input:
4
ABACUS
FACEBOOK
XYZXZYX
FBFBF


Sample output:
Case #1: ASUCABABACUSA
Case #2: Impossible
Case #3: XZYXYZXYZXZYXYZXYZYX
Case #4: Impossible



Code: // Ethan Searches for a String
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	string A,B;
	int i,j;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			cin >> A;
			// check for a valid prefix to repeat
			B="Impossible";
				Fox1(i,Sz(A)-1)
					if (A[i]==A[0])
					{
							Fox(j,Sz(A))
								if (A[j]!=A[j%i])
									B=A.substr(0,i)+A;
						break;
					}
			// output
			printf("Case #%d: ",t);
			cout << B << endl;
		}
	return(0);
}