Начало
Соревнования
Задачи заочного тура личного первенства 2000
1. NO COMMENT
АвтоматыОлимпиадные задачи на русском языке
| 04/09/2000 | Заочный тур личного первенства (1) |
| 19/09/2007 | Занятие 2 (D) |
| 05/05/2012 | Занятие 17 (B) |
| 12/03/2014 | Занятие 16 (E) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Фирма Willisoft решила сделать открытыми исходные тексты своей всемирно известной программы Mistakes-2000. Но перед опубликованием президент фирмы приказал удалить все комментарии в исходных текстах, что проще и быстрее всего сделать, написав специальную программу. Программа Mistakes-2000 была написана на языке С++, в котором имеются две следующие возможности для комментирования:
/* любой текст от символов /* до */ // любой текст после // до конца строки
Если части текста программы были на разных строках, то они должны остаться на разных строках. Символы начала комментария внутри другого комментария игнорируются (комментарии не могут быть вложенными). Символы начала комментариев игнорируются и внутри строк в двойных кавычках. Внутри таких строк может встречаться символ двойной кавычки, если перед ним стоит символ '\' (обратная косая черта). Например, "Строка с символами \" между \" и \"". Символ '\' используется в С++ для введения в строку специальных символов, например, самой обратной косой черты: "\\". Идентификаторы в языке С++ составляются из строчных и прописных латинских букв, символа '_' (подчеркивания) и цифр. Для упрощения задачи символьные константы (буквы в одинарных кавычках, например: 'A') в программе отсутствуют.
После удаления комментариев из строки нужно:
- удалить все пробелы в конце строки (остальные пробелы не удаляются)
- удалить пустые (не содержащие текста) строки
- если при удалении комментария два идентификатора (ключевых слова) или числа соединяются, то вставить один пробел. Например, "int/*целое*/a;" должно превратиться в "int a;"
Во входном файле исходный текст синтаксически правильной программы общим размером не 1500 символов.
В выходной файл вывести тот же текст без комментариев, согласно требованиям.
Пример ввода
/***************************************
Программа 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;
}
Вывод для примера
#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. Как научить компьютер решать японские кроссворды
Реализация заданного алгоритмаРекурсивный перебор
Олимпиадные задачи на русском языке
| 04/09/2000 | Заочный тур личного первенства (2) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Японские "кроссворды" становятся все
более популярными. В этой головоломке требуется восстановить зашифрованную
черно-белую картинку, закрашивая клетки в соответствии
с числовыми показателями. Число слева от строки (над столбцом) означает, что
в данной строке (столбце) необходимо закрасить в черный цвет соответствующее
число подряд идущих клеток. Если чисел несколько, то и отрезков будет
несколько (в том же порядке), причем между ними должен быть зазор хотя
бы в одну белую клетку.
Перебирая все варианты закраски строки, можно увидеть, что некоторые
клетки всегда будут раскрашены в черный цвет, а некоторые – в белый.
Например, в строке длиной 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` символов),
обозначая символом '#' черную клетку, а символом '.'
(точка) – белую.
Пример ввода
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
Вывод для примера
.#.#.... .###.... #####... #####... ..#....# ..#....# ..##..## ..###.#. ..#####.
3. Цифровой квадрат
Рекурсивный переборСокращение перебора с помощью идеи
Олимпиадные задачи на русском языке
| 04/09/2000 | Заочный тур личного первенства (3) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Эта головоломка была придумана Hirofumi Fujiwara.
В квадрате `9\ times\ 9` нужно расставить цифры от 1 до 9 таким образом,
чтобы в каждой строке, в каждом столбце и в каждом маленьком квадрате
`3\ times\ 3` цифры от 1 до 9 встречались по одному разу.
В головоломке задается расположение некоторых цифр, необходимо
расставить согласно правилам остальные цифры. Составьте программу
для решения этой головоломки.
Во входном файле 9 строк по 9 символов в строке, соответствующие
клеткам квадрата. Если цифра в клетке задана, то соответствующий
символ входного файла это цифра от 1 до 9. Если цифра в клетке
не задана, то указывается символ ‘.’ (точка).
В выходной файл вывести одно из
решений головоломки (также 9 строк по 9 символов).
Если решение найти не удается, то вместо решения
вывести слово "IMPOSSIBLE" (без кавычек, прописными буквами).
Пример ввода
.....2.3. 374..6.2. .....8.1. 258...... ......... ......493 .4.1..... .2.8..675 .6.5.....
Вывод для примера
185742936 374916528 692358714 258493167 439671852 716285493 543167289 921834675 867529341
