Bài C - Codeforces Round #530 (Div.2)

Bài C:
Đề bài: Andrey nhận 1 tâm bưu thiếp từ Irina. Nó chỉ chứa các từ "Hello,Andrey!" và một xâu lạ bao gồm các kí tự latin thường, bông tuyết (snowflakes) và que kẹo (candy canes). Andrey nghĩ rằng xâu này là một mật mã và quyết định giải mã nó (decrypt it).
  Andrey chú ý rằng các bông tuyết và các que kẹo luôn đứng sau các ký tự, vì vậy anh ấy cho rằng tin nhắn được mã hóa như sau. Que kẹo có nghĩa là kí tự phía nó sẽ bị xóa đi hoặc giữ lại. Một bông tuyết có nghĩa là kí tự trước nó có thể được xóa đi, để lại hoặc lặp lại vài lần.
Ví dụ, xét chuỗi sau:

Xâu này có thể được giải mã: <<>happynewyear>. Vì điều này, các que kẹo và bông tuyết được sử dụng như sau:

+ Que kẹo 1: Xóa đi ký tự w,

+ Bông tuyết 1: lặp lại ký tự p hai lần.

+Que kẹo 2: Xóa đi ký tự n

+ Bông tuyết 2: Xóa đi ký tự w

+ Bông tuyết 3: Để lại ký tự e.

Xin lưu ý rằng cùng một chuỗi có thể mã hóa các tin nhắn khác nhau. Ví dụ, xâu trên có thể được mã hóa thành <<hayewyar>>, <<happpppyne>>, và các tin nhắn khác.

Andrey biết rằng tin nhắn từ Irina thường có chiều dài là k. Giúp anh ta tìm hiểu xem chuỗi đã cho có thể mã hóa một thông điệp gồm k chữ cái hay không, và nếu vậy hãy đưa ra một ví dụ về thông báo như vậy.

Đầu vào: 

+ Dòng đầu tiên chứa xâu nhận được từ bưu thiếp. Xâu chỉ chứa các ký tự Latin thường, cũng như các ký tự <<*>> và <<?>> tượng trưng cho bông tuyết và que kẹo, lần lượt. Các ký tự này chỉ xuất hiện sau các chữ cái. Độ dài của xâu không vượt quá 200.

+ Dòng thứ hai chứa một số nguyên k (1<=k<=200), chiều dài tin nhắn được yêu cầu.

Đầu ra:

In ra một tin nhắn bất kỳ có độ dài là k thỏa mãn xâu đã cho được mã hóa, hoặc in ra <<Impossoble>> nếu không tồn tại tin nhắn nào thỏa mãn.

Đầu vào:

hw?ap*yn?eww*ye*ar

12

Đầu ra:

happynewyear

/**/

Đầu vào:

ab?a

2

Đầu ra:

aa

/**/

Đầu vào:

ab?a

3

Đầu ra:

aba

/**/

Đầu vào:

ababb

5

Đầu ra:

ababb

Đầu vào:

ab?a

1

Đầu ra:

Impossible.

Hướng dẫn:

 Nếu xâu ở trong bưu thiếp không chứa bất kỳ kí tự bông tuyết và que kẹo nào, thì k phải bằng chiều dài của xâu đó, và trong trường hợp k không bằng chiều dài của xâu thì in ra <<Impossible>>

Chúng ta gọi các ký tự trong tin nhắn là bắt buộc nếu nó không được theo sau bởi bông tuyết hoặc que kẹo. Rõ ràng k phải ít nhất bằng số các ký tự bắt buộc này, ngược lại in ra <<Impossible>>

 Trong trường hợp có bông tuyết trong tin nhắn, chúng ta có thể lặp lại ký tự phía trước nó đủ số lần để được chiều dài bằng k, và loại bỏ các phần tử không bắt buộc.

Trong trường hợp không có bông tuyết nào, chỉ có que kẹo, chúng ta sử dụng các phần tử được theo sau bởi các que kẹo cho đến chúng ta được chiều dài k mong muốn. Trong trường hợp không đủ, kết quả là <<Impossible>>.

Lời giải:

#include <cstdio>
using namespace std;

char s[500], fuck[500];
int type[500], tot, k;

int main()
{
 bool unlimited = false;
 scanf("%s%d", fuck, &k);
 for (int i = 0; fuck[i] != 0; i++)
 {
  if (fuck[i] == '?')
  {
   type[tot] = 1;
  }
  else if (fuck[i] == '*')
  {
   type[tot] = 2;
   unlimited = true;
  }
  else
  {
   s[++tot] = fuck[i];
  }
 }
 int lbound = 0, rbound = 0;
 for (int i = 1; i <= tot; i++)
  if (type[i] == 0) lbound++, rbound++;
  else if (type[i] == 1) rbound++;
 if (lbound > k || (unlimited == false && k > rbound))
 {
  puts("Impossible");
 }
 else
 {
  for (int i = 1; i <= tot; i++)
  {
   if (type[i] == 0)
    printf("%c", s[i]);
   else if (type[i] == 1)
   {
    if (lbound < k)
    {
     k--;
     printf("%c", s[i]);
    }
   }
   else if (type[i] == 2)
   {
    while (lbound < k)
    {
     k--;
     printf("%c", s[i]);
    }
   }
  }
 }
 return 0;
}