Занятие 7. Списки

Задача «Кегельбан»

Условие

N кеглей выставили в один ряд, занумеровав их слева направо числами от 1 до N. Затем по этому ряду бросили K шаров, при этом i-й шар сбил все кегли с номерами от li до ri включительно. Определите, какие кегли остались стоять на месте.

Программа получает на вход количество кеглей N и количество бросков K. Далее идет K пар чисел li, ri, при этом 1≤ li≤ ri≤ N.

Программа должна вывести последовательность из N символов, где j-й символ есть “I”, если j-я кегля осталась стоять, или “.”, если j-я кегля была сбита.

Тесты

Входные данные Правильный ответ Что вывела программа Результат 
10 3
8 10
2 5
3 6
 
I.....I...
 

				
			

			
			

				
				
5 2
1 2
4 4


				
..I.I

				

				
			

			
			

				
				
10 3
3 5
4 6
10 10


				
II....III.

				

				
			

			
			

				
				
5 0


				
IIIII

				

				
			

			
			

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


				
.....

				

				
			

			
			

				
				
20 1
1 20


				
....................

				

				
			

			
			

				
				
20 3
3 8
13 17
6 9


				
II.......III.....III

				

				
			

			
			

				
				
15 4
1 1
1 4
6 8
7 9


				
....I....IIIIII

				

				
			

			
		
	

	




  
Нужна подсказка?

  
  

    Подсказка 1
    
Отмечаем покрытие интервалами сбитых кеглей.

    
  

  
  

    Подсказка 2
    
Ввод нумерует кегли с 1, список — с 0.