1232: Business => Зимовий мотив


Submit solution


Points:15
Time limit:1.0s
Memory limit:250M
Author:

Problem type

Василько не мріє бути програмістом – він хоче стати мільйонером. І не десь там у далекому майбутньому, а вже цього року. Для втілення своєї мрії Василько організував фірму, яка під Новий рік буде займатися поставкою новорічних ялинок. Оскільки мільйон треба заробити уже цього року, Василько вирішив обійтися без посередників. Бізнес-план вийшов дивовижно простий: сам рубаю, сам доставляю і сам продаю. Василько сміливо взявся за справу, але коли отримав угоду на вирубку ялинок, то задумався. За один раз йому дозволили вивозити рівно K (0<= K <=10000) ялинок і партія Зелених домоглася певних обмежень на вирубку: ялинки можна рубати тільки рухаючись на схід або на південь; починати вирубку слід в одному кутку і закінчувати у будь-якому іншому. Ділянки мають форму прямокутника із сторонами N , M (1<= N , M <=100) , сторони якого були орієнтовані чітко на захід, схід, північ та південь. Василько зразу ж помітив, що забезпечити собі гарний результат вирубки можна лише тоді, коли починаєш рубати із північно-західного кутка і закінчуєш у південно-східному :) «Зелені» добре подумали над тим, щоб виконати угоду по вирубці йому було складно. Василько це побачив і пошкодував, що не став спочатку програмістом.

Допоможіть Василькові правильно провести вирубку і стати мільйонером, або повідомте, що на цій ділянці краще не рубати.

Формат вихідних даних

У першому рядку вхідного потоку дано три цілих числа N , M , K , розділених пропусками. Далі у N рядках міститься по M символів: «.» - це вільне місце, а « # » - позначає місце знаходження ялинки.

Формат вихідних даних

У вихідний потік у випадку наявності правильного варіанту вирубки вивести послідовність координат, які виводити по одній у кожному рядку. Перша координата завжди (1,1), остання – ( N , M ). В іншому випадку вивести повідомлення « To not cut !»

Приклад вхідних даних

4 4 3
....
#...
###.
####

Приклад вихідних даних

1 1
2 1
2 2
2 3
3 3
3 4
4 4

Приклад вхідних даних

3 4 1
#...
..#.
#.##

Приклад вихідних даних

To not cut!

Comments


  • 0
    maks00x
     commented on Oct. 25, 2018

    В примере 1 допущена ошибка в выводе: предпоследний — не "3 4", а "4 3"


    • 0
      zvit
       commented on Oct. 25, 2018

      ні, там все вірно: вирубати можна лише 3 ялинки


      • 0
        maks00x
         commented on Oct. 25, 2018

        У вас виходить:

        • (1; 1) — нема ялинки
        • (2; 1) — нема ялинки
        • (2; 2) — нема ялинки
        • (2; 3) — є ялинка
        • (3; 3) — є ялинка
        • (3; 4) — є ялинка
        • (4; 4) — є ялинка

        чи ви в передостанньому плутаєте x і y, так от x — спершу, а y — другий, подивіться в вхідні дані.


        • 0
          zvit
           commented on Oct. 26, 2018 edited

          перше число - номер рядка, друге - номер стовпця