Во всех задачах ввод осуществляется из файла
INPUT.TXT, а вывод в файл OUTPUT.TXT. Формат входного файла соответствует спецификации, дополнительные проверки не нужны. Время теста указано для 486+ >=100МГц. Запрещается открывать для ввода-вывода другие файлы, выводить содержимое теста на экран, изменять вектора прерываний. Программа main() должна вернуть 0 (return 0;)!1. NO COMMENT (5 сек. на тест)
Фирма
Willisoft решила сделать открытыми исходные тексты своей всемирно известной программы Mistakes-2000. Но перед опубликованием президент фирмы приказал удалить все комментарии в исходных текстах, что проще и быстрее всего сделать, написав специальную программу. Программа Mistakes-2000 была написана на языке С++, в котором имеются две следующие возможности для комментирования:/*
любой текст от символов /* до */ // любой текст после // до конца строкиЕсли части текста программы были на разных строках, то они должны остаться на разных строках. Символы начала комментария внутри другого комментария игнорируются (комментарии не могут быть вложенными). Символы начала комментариев игнорируются и внутри строк в двойных кавычках. Внутри таких строк может встречаться символ двойной кавычки, если перед ним стоит символ
'\' (обратная косая черта). Например, " Строка с символами \" между \" и \" " . Символ '\' используется в С++ для введения в строку специальных символов, например, самой обратной косой черты: " \\" . Идентификаторы в языке С++ составляются из строчных и прописных латинских букв, символа _ (подчеркивания) и цифр. Для упрощения задачи символьные константы (буквы в одинарных кавычках, например: 'A') в программе отсутствуют.После удаления комментариев из строки нужно
:Во входном файле исходный текст синтаксически правильной программы.
В выходной файл вывести тот же текст без комментариев, согласно требованиям.
Пример
INPUT.TXT:/***************************************
Программа Mistakes-2000
(c) Willisoft, 1980, 1984-1989, 2000
****************************************/
#include <stdio.h>
int/* для возврата кода ошибки*/main(void)
{ char *str;
int age;
// Ввод имени
printf("Введи свое имя:");
scanf("%s", str); /* Память для str не выделена! */
// Ввод возраста
printf("Введи свой возраст:");
scanf("%d", d); // Пропущен &
printf("%s,\n ваш возраст в секундах %d\n", /* В году 365.25 дней
*/ str, d*60*60*24*365); // Результат будет правилен только для
/* 32-битной версий компилятора */
return 0;
}
OUTPUT.TXT
для примера:#include <stdio.h>
int main(void)
{ char *str;
int age;
printf("Введи свое имя:");
scanf("%s", str);
printf("Введи свой возраст:");
scanf("%d", d);
printf("%s,\n ваш возраст в секундах %d\n",
str, d*60*60*24*365);
return 0;
}
2. Как научить компьютер решать японские кроссворды
(20 сек. на тест)
Японские
"кроссворды" становятся все более популярными. В этой головоломке требуется восстановить зашифрованную черно-белую картинку, закрашивая клетки в соответствии с числовыми показателями. Число слева от строки (над столбцом) означает, что в данной строке (столбце) необходимо закрасить в черный цвет соответствующее число подряд идущих клеток. Если чисел несколько, то и отрезков будет несколько (в том же порядке), причем между ними должен быть зазор хотя бы в одну белую клетку.Перебирая все варианты закраски строки, можно увидеть, что некоторые клетки всегда будут раскрашены в черный цвет, а некоторые – в белый. Например
, в строке длиной 11 возможно 10 размещений отрезков 1, 4 и 2 (здесь и далее символ ‘#’ означает черную клетку, а символ ‘.’ (точка) – белую):#.####.##.. #.####..##. #.####...## #..####.##. #..####..## #...####.## .#.####.##. .#.####..## .#..####.## ..#.####.##
Всегда черными будут
5-я и 6-я клетки строки, остальные могут оказаться как белыми, так и черными (такие клетки будем обозначать символом ‘?’). Обратите внимание, что несколько раз выполняется размещение отрезков 4 и 2, начиная с 4-й клетки, а также с 5-й клетки. Если анализ этих размещений был уже проведен, то повторная их проверка не дает новой информации. Таким образом, не выполняя повторного анализа, можно существенно ускорить проверку всех размещений, особенно при большом числе отрезков. Если уже известно расположение некоторых черных и белых клеток, то варианты размещений, не соответствующие расположению этих клеток, отбрасываются.Выполняя такой анализ несколько раз, сначала для всех строк, а затем для всех столбцов, мы постепенно восстановим зашифрованную картинку. Процесс восстановления можно считать законченным, когда исчезнут все
‘?’ или не будет новых изменений. Далее показан процесс решения головоломки, первая картинка каждого шага получается после анализа строк, а вторая – столбцов.1 шаг
42
24832133
11????????
3????????
5???##???
5???##???
11????????
11????????
22????????
31????????
5???##???
42
24832133
11????.???
3??##.???
5??###???
5??###???
11??#?.???
11??#..???
22??##.???
31??###???
5???##???
2 шаг
42
24832133
11????.???
3.###....
5??###??.
5??###??.
11?.#..???
11?.#..???
22..##.?#?
31..###.??
5???##???
42
24832133
11.#?#.?..
3.###....
5?####?..
5?####?..
11?.#..???
11?.#..???
22..##.?##
31..###.??
5..?##???
3 шаг
42
24832133
11.#.#....
3.###....
5?####?..
5?####?..
11?.#..???
11?.#..???
22..##..##
31..###.??
5..?####?
42
24832133
11.#.#....
3.###....
5?####...
5?####...
11?.#....?
11?.#....?
22..##..##
31..###.#?
5..#####?
4 шаг
42
24832133
11.#.#....
3.###....
5#####...
5#####...
11?.#....?
11?.#....?
22..##..##
31..###.#.
5..#####.
42
24832133
11.#.#....
3.###....
5#####...
5#####...
11..#....#
11..#....#
22..##..##
31..###.#.
5..#####.
Во входном файле в первой строке содержится два целых числа
N и M. N – количество строк в головоломке (1 <= N <= 60), M – количество столбцов (1 <= M <= 70). Далее следует N строк с информацией об отрезках, содержащихся в каждой строке головоломки. Это последовательность натуральных чисел (не более 12 чисел), разделенных одним пробелом и заканчивающаяся 0. Далее следует M строк с аналогичной информацией об отрезках, содержащихся в каждом столбце головоломки. Все головоломки, использующиеся для тестирования, имеют решение и оно единственное. Кроме того, все использованные головоломки могут быть решены с помощью указанного итерационного алгоритма, без использования перебора вариантов с откатом.В выходной файл вывести решение головоломки
(N строк по M символов), обозначая символом ‘#’ черную клетку, а символом ‘.’ (точка) – белую.Пример
INPUT.TXT:9 8 1 1 0 3 0 5 0 5 0 1 1 0 1 1 0 2 2 0 3 1 0 5 0 2 0 4 0 8 0 4 3 0 2 2 0 1 0 3 0 3 0
OUTPUT.TXT
для примера:.#.#.... .###.... #####... #####... ..#....# ..#....# ..##..## ..###.#. ..#####.
3. Цифровой квадрат
(10 сек. на тест)
Эта головоломка была придумана Hirofumi Fujiwara. В квадрате 9
x9 нужно расставить цифры от 1 до 9, таким образом, чтобы в каждой строке, в каждом столбце и в каждом маленьком квадрате 3x3 цифры от 1 до 9 встречались по одному разу.В головоломке задается расположение некоторых цифр, необходимо расставить согласно правилам остальные цифры. Составьте программу для решения этой головоломки.
Во входном файле 9 строк по 9 символов в строке, соответствующие клеткам квадрата. Если цифра в клетке задана, то соответствующий символ входного файла это цифра от 1 до 9. Если цифра в клетке не задана, то указывается символ
‘.’ (точка).В выходной файл вывести одно из решений головоломки (также 9 строк по 9 символов). Если решение найти не удается, то вместо решения вывести слово
"IMPOSSIBLE" (без кавычек, прописными буквами!).Пример
INPUT.TXT:.....2.3. 374..6.2. .....8.1. 258...... ......... ......493 .4.1..... .2.8..675 .6.5.....
OUTPUT.TXT
для примера:185742936 374916528 692358714 258493167 439671852 716285493 543167289 921834675 867529341