Advertisement
Guest User

Untitled

a guest
Nov 20th, 2015
193
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.50 KB | None | 0 0
  1. Задача : Спанч Боб и шутка
  2.  
  3. Пока Патрик бегал по магазинам, Спанч Боб решил немного подшутить над своим другом. Порывшись в его вещах, проказник обнаружил последовательность a1, a2, ..., am длины m, составленную из целых чисел от 1 до n, не обязательно различных. Далее Спанч Боб придумал последовательность f1, f2, ..., fn длины n и получил для каждого числа ai число bi = fai. Исходную последовательность Спанч Боб, разумеется, стёр.
  4.  
  5. Сложно передать словами, как же расстроился Патрик когда вернулся из магазина! Скажем лишь, что Спанч Боб быстро пожалел о содеянном и пытается восстановить исходную последовательность. Помогите ему это сделать или определите, что это невозможно.
  6.  
  7. Входные данные
  8. В первой строке входных данных находятся два целых числа n и m (1 ≤ n, m ≤ 100 000) — длины последовательностей fi и bi соответственно.
  9.  
  10. Во второй строке содержатся n целых чисел, определяющих последовательность f1, f2, ..., fn (1 ≤ fi ≤ n).
  11.  
  12. В последней строке записаны m целых чисел, определяющих последовательность b1, b2, ..., bm (1 ≤ bi ≤ n).
  13.  
  14. Выходные данные
  15. Если существует ровно одна последовательность ai, такая что bi = fai для всех i от 1 до m, то выведите "Possible". Далее выведите m целых чисел a1, a2, ..., am.
  16.  
  17. Если существует несколько подходящих последовательностей ai, то выведите "Ambiguity".
  18.  
  19. Если Спанч Боб ошибся в своих вычислениях, и ни одной подходящей последовательности ai не существует, то выведите "Impossible".
  20.  
  21. Примеры тестов
  22. входные данные
  23. 3 3
  24. 3 2 1
  25. 1 2 3
  26. выходные данные
  27. Possible
  28. 3 2 1
  29. входные данные
  30. 3 3
  31. 1 1 1
  32. 1 1 1
  33. выходные данные
  34. Ambiguity
  35. входные данные
  36. 3 3
  37. 1 2 1
  38. 3 3 3
  39. выходные данные
  40. Impossible
  41. Примечание
  42. В первом примере 3 заменяется на 1 и наоборот, а 2 никогда не изменяется. Ответ существует, и он единствененный.
  43.  
  44. Во втором примере все числа заменяются на единицу, поэтому однозначно восстановить исходную последовательность невозможно.
  45.  
  46. В третьем примере fi ≠ 3 для всех i, поэтому никакая последовательность ai не перейдёт в такую bi и можно точно сказать, что Спанч Боб где-то ошибся.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement