시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 235 66 46 27.879%

문제

틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 두 번째 사람이 O를 놓는다. 어느 때든지 한 사람의 말이 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하면 게임은 즉시 끝난다. 게임판이 가득 차도 게임은 끝난다.

게임판의 상태가 주어지면, 그 상태가 틱택토 게임에서 발생할 수 있는 최종 상태인지를 판별하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입력의 마지막에는 문자열 "end"가 주어진다.

출력

각 테스트 케이스마다 한 줄에 정답을 출력한다. 가능할 경우 "valid", 불가능할 경우 "invalid"를 출력한다.

예제 입력 1

XXXOO.XXX
XOXOXOXOX
OXOXOXOXO
XXOOOXXOX
XO.OX...X
.XXX.XOOO
X.OO..X..
OOXXXOOXO
end

예제 출력 1

invalid
valid
invalid
valid
valid
invalid
invalid
invalid
W3sicHJvYmxlbV9pZCI6Ijc2ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyZjFcdWQwZGRcdWQxYTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDJmMVx1ZDBkZFx1ZDFhMCBcdWFjOGNcdWM3ODRcdWM3NDAgXHViNDUwIFx1YmE4NVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViYzg4XHVhYzA4XHVjNTQ0XHVhYzAwXHViYTcwIFx1YjlkMFx1Yzc0NCBcdWIxOTNcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NDAgMyZ0aW1lczszIFx1YWNhOVx1Yzc5MFx1ZDMxMFx1Yzc3NFx1YmE3MCwgXHVjYzk4XHVjNzRjXHVjNWQwXHViMjk0IFx1YmU0NFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVhYzAxXHVhYzAxIFggXHViNjEwXHViMjk0IE8gXHViOWQwXHVjNzQ0IFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3MCBcdWIxOTNcdWIyOTRcdWIzNzAsIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBYXHViOTdjIFx1YjE5M1x1YWNlMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBPXHViOTdjIFx1YjE5M1x1YjI5NFx1YjJlNC4gXHVjNWI0XHViMjkwIFx1YjU0Y1x1YjRlMFx1YzljMCBcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzU4IFx1YjlkMFx1Yzc3NCBcdWFjMDBcdWI4NWMsIFx1YzEzOFx1Yjg1YywgXHViMzAwXHVhYzAxXHVjMTIwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyAzXHVjZTc4XHVjNzQ0IFx1Yzc4N1x1YjI5NCBcdWIzNzAgXHVjMTMxXHVhY2Y1XHVkNTU4XHViYTc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWM5ODlcdWMyZGMgXHViMDVkXHViMDljXHViMmU0LiBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NzQgXHVhYzAwXHViNGRkIFx1Y2MyOFx1YjNjNCBcdWFjOGNcdWM3ODRcdWM3NDAgXHViMDVkXHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWQzMTBcdWM3NTggXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHVhZGY4IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWQyZjFcdWQwZGRcdWQxYTAgXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjIFx1YmMxY1x1YzBkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1Yzg4NSBcdWMwYzFcdWQwZGNcdWM3NzhcdWM5YzBcdWI5N2MgXHVkMzEwXHViY2M0XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzQwIDlcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YmE3MCwgJiMzOTtYJiMzOTssICYjMzk7TyYjMzk7LCAmIzM5Oy4mIzM5OyBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LiAmIzM5Oy4mIzM5O1x1Yzc0MCBcdWJlNDhcdWNlNzhcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTU4XHViYTcwLCA5XHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM1ZDBcdWMxMWMgXHVjODFjXHVjNzdjIFx1YzcxNyBcdWM5MDQgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwXHVjNzU4IFx1YzIxY1x1YzExY1x1Yzc3NFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOVx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgJnF1b3Q7ZW5kJnF1b3Q7XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMFx1YjJhNVx1ZDU2MCBcdWFjYmRcdWM2YjAgJnF1b3Q7dmFsaWQmcXVvdDssIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU2MCBcdWFjYmRcdWM2YjAgJnF1b3Q7aW52YWxpZCZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzY4MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRpYy1UYWMtVG9lIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgZ2FtZSBvZiB0aWMtdGFjLXRvZSwgdHdvIHBsYXllcnMgdGFrZSB0dXJucyBtYXJraW5nIHNxdWFyZXMgb2YgYW4gaW5pdGlhbGx5IGVtcHR5IDMmdGltZXM7MyBncmlkIHdpdGggZWl0aGVyIFgmcnNxdW87cyBvciBPJnJzcXVvO3MuIFRoZSBmaXJzdCBwbGF5ZXIgYWx3YXlzIG1hcmtzIHNxdWFyZXMgdXNpbmcgWCZyc3F1bztzLCB3aGVyZWFzIHRoZSBzZWNvbmQgcGxheWVyIGFsd2F5cyBtYXJrcyBzcXVhcmVzIHVzaW5nIE8mcnNxdW87cy4gSWYgYXQgYW55IHBvaW50IGR1cmluZyB0aGUgZ2FtZSBlaXRoZXIgcGxheWVyIG1hbmFnZXMgdG8gbWFyayB0aHJlZSBjb25zZWN1dGl2ZSBzcXVhcmVzIGluIGEgcm93LCBjb2x1bW4sIG9yIGRpYWdvbmFsIHdpdGggaGlzXC9oZXIgc3ltYm9sLCB0aGUgZ2FtZSB0ZXJtaW5hdGVzLjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIGJvYXJkIGNvbmZpZ3VyYXRpb24sIHlvdXIgZ29hbCBpcyB0byBkZXRlcm1pbmUgd2hldGhlciB0aGUgYm9hcmQgY29uZmlndXJhdGlvbiByZXByZXNlbnRzIHRoZSBwb3NzaWJsZSBmaW5hbCBzdGF0ZSBvZiBhIHZhbGlkIHRpYy10YWMtdG9lIGdhbWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgdGVzdCBmaWxlIHdpbGwgY29udGFpbiBtdWx0aXBsZSBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIDkgY2hhcmFjdGVycywgd2hpY2ggcmVwcmVzZW50IHRoZSA5IHNxdWFyZXMgb2YgYSB0aWMtdGFjLXRvZSBncmlkLCBnaXZlbiBvbmUgcm93IGF0IGEgdGltZS4gRWFjaCBjaGFyYWN0ZXIgb24gdGhlIGxpbmUgd2lsbCBlaXRoZXIgYmUgJmxzcXVvO1gmcnNxdW87LCAmbHNxdW87TyZyc3F1bzsgKHRoZSBsZXR0ZXIgTyksIG9yICZsc3F1bzsuJnJzcXVvOyAoaW5kaWNhdGluZyBhbiB1bmZpbGxlZCBzcXVhcmUpLiBUaGUgZW5kLW9mLWZpbGUgaXMgbWFya2VkIGJ5IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgd29yZCAmbGRxdW87ZW5kJnJkcXVvOy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBpbnB1dCB0ZXN0IGNhc2UsIHdyaXRlIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBlaXRoZXIgdGhlIHdvcmQgJmxkcXVvO3ZhbGlkJnJkcXVvOyBvciAmbGRxdW87aW52YWxpZCZyZHF1bzsgaW5kaWNhdGluZyB3aGV0aGVyIHRoZSBnaXZlbiBib2FyZCBjb25maWd1cmF0aW9uIGlzIHRoZSBmaW5hbCBzdGF0ZSBvZiBzb21lIHBvc3NpYmxlIHRpYy10YWMtdG9lIGdhbWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

University > Stanford Local ACM Programming Contest > SLPC 2006 7번

  • 문제를 번역한 사람: kks227
  • 데이터를 추가한 사람: zmtn94