본문 바로가기

PKU & UVa problems

PKU 3074. Sudoku 스도쿠 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5294 Accepted: 1578 설명 스도쿠에서는 9 × 9 크기의 격자가 3 × 3 크기의 더 작은 격자들로 나뉘어져있습니다. 예를 들면, . 2 7 3 8 . . 1 . . 1 . . . 6 7 3 5 . . . . . . . 2 9 3 . 5 6 9 2 . 8 . . . . . . . . . . . 6 . 1 7 4 5 . 3 6 4 . . . . . . . 9 5 1 8 . . . 7 . . 8 . . 6 5 3 4 . 격자 안에 몇몇개의 숫자가 주어졌을 때, 당신은 남은 칸들에 1부터 9까지의 숫자들을 집어넣어야 하는데 이때 1부터 9까지의 각 숫자들은 (1) 9개의 3 × 3 격.. 더보기
PKU 3074. Sudoku Sudoku Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5294 Accepted: 1578 Description In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example, . 2 7 3 8 . . 1 . . 1 . . . 6 7 3 5 . . . . . . . 2 9 3 . 5 6 9 2 . 8 . . . . . . . . . . . 6 . 1 7 4 5 . 3 6 4 . . . . . . . 9 5 1 8 . . . 7 . . 8 . . 6 5 3 4 . Given some of the numbers in the.. 더보기
PKU 3364. Black and white painting 흑백 채색 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2092 Accepted: 1396 설명 당신은 현대 그림이 많이 전시되어 있는 Centre Pompidou 를 방문중입니다. 특히 당신은 마치 체스판처럼 오로지 검은색과 흰색의 사각형들로만 이루어진 한 그림을 주목합니다 (맞닿은 사각형들은 같은 색이 아닙니다). 그런데 이 그림을 그린 화가는 그림을 그릴 때 problem A 의 도구를 사용하지 않았습니다. 너무도 심심했던 당신은, 이 작품 속에 얼마나 많은 8 × 8 크기의 체스판이 들어갈 수 있는지 알고 싶어졌습니다. 체스판의 오른쪽 제일 아래칸은 반드시 흰 색이어야 합니다. 입력 입력은 여러 개의 테스트 케이스들로 이루어집니다. 각 .. 더보기
PKU 3364. Black and white painting Black and white painting Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2092 Accepted: 1396 Description You are visiting the Centre Pompidou which contains a lot of modern paintings. In particular you notice one painting which consists solely of black and white squares, arranged in rows and columns like in a chess board (no two adjacent squares have the same colour). By the way, the .. 더보기
UVa 628. Passwords 628 - PasswordsTime limit: 3.000 seconds 비밀번호 여러 서버에 여러개의 계정을 둔 사람은 당연히 여러 가지의 비밀번호를 기억해야 합니다. 그리고 어떤 사람이 비밀번호를 잊어버린 상황을 충분히 상상할 수 있을겁니다. 그/그녀 가 기억하고 있는 것은 오직 단어 x, y 그리고 z 와 두 개의 숫자입니다: 하나는 시작하는 숫자이고 다른 하나는 끝나는 숫자입니다. 당신은 이제 주어진 단어와 규칙을 기반으로 하여 비밀번호의 가능성이 있는 모든 것을 찾아내는 프로그램을 작성해야 합니다. 예를 들어 주어진 3 개의 단어: x, y, z 와 주어진 규칙이 0#0 라면, 이 규칙은 의 형태로 나타나야 합니다. 입력 첫 번째 줄은 사전에 있는 단어들의 숫자를 나타냅니다(n). 각 단어들은 .. 더보기
UVa 628. Passwords 628 - PasswordsTime limit: 3.000 seconds Passwords Having several accounts on several servers one has to remember many passwords. You can imagine a situation when someone forgets one of them. He/she remembers only that it consisted of words x, y and z as well as two digits: one at the very beginning and the other one at the end of the password. Your task is to write a program which will generate.. 더보기
PKU 3132. Sum of Different Primes 서로 다른 두 소수의 합 Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 2398 Accepted: 1474 설명 어떤 양정수는 한 가지 이상의 서로 다른 소수들의 합으로 나타낼 수 있습니다. 주어진 두 개의 양정수 n 과 k 를 놓고 볼 때, 당신은 n 이라는 양정수를 k 개의 서로 다른 소수들의 합으로 나타내는 방법을 찾아내야 합니다. 다음에 나오는 예시를 보면 확실하겠지만, 같은 소수 집합으로 합의 순서만 바꾸는 것은 같은 방법을 썼다고 간주합니다. 예를 들어 8 은 3 + 5 와 5 + 3 으로 표현 될 수 있지만 이 두 방법은 구별할 수 없기 때문에 하나의 방법입니다. 만약 n 과 k 가 각각 24 와 3 이라면 답은 2가 되는데 그 이유.. 더보기
PKU 3132. Sum of Different Primes Sum of Different Primes Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 2398 Accepted: 1474 Description A positive integer may be expressed as a sum of different prime numbers (primes), in one way or another. Given two positive integers n and k, you should count the number of ways to express n as a sum of k different primes. Here, two ways are considered to be the same if they sum up .. 더보기
PKU 2291. Rotten Ropes 썩은 밧줄 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4023 Accepted: 2620 설명 어떤 무거운 물체를 들어올리기 위해서 같은 길이인 n 개의 밧줄이 있다고 생각해봅시다. 이 때 각 밧줄들과 연결시켜 물체를 들어올리기 때문에 각 밧줄이 버틸수 있는 무게인 t 를 넘는 물건을 들어올리려고 하면 밧줄은 끊어집니다. 그러나 우리는 무거운 물체를 여러 개의 밧줄로 평행하게 묶어서 모든 밧줄을 끌어올리는 방법을 쓰면 무거운 물체도 들어올릴 수 있습니다. w 의 무게를 가진 무거운 물건을 들어올리기 위해 k 개의 밧줄을 사용한다면, 각 밧줄에 w/k 만큼의 무게가 주어진다고 가정합니다. 하지만 밧줄이 버틸수 있는 무게인 t 를 놓고 볼 때, .. 더보기
PKU 2291. Rotten Ropes Rotten Ropes Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4023 Accepted: 2620 Description Suppose we have n ropes of equal length and we want to use them to lift some heavy object. A tear-off weight t is associated to each rope, that is, if we try to lift an object, heavier than t with that rope, it will tear off. But we can fasten a number of ropes to the heavy object (in parallel.. 더보기
PKU 2181. Jumping Cows 점프하는 소들 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4560 Accepted: 2761 설명 농부 John의 소들은 동요에 나오는 것 처럼 달을 뛰어넘고 싶어합니다. 그러나 불행하게도 소들은 뛸 수 없습니다. 그 지역에 사는 주술사가 달을 뛰어넘고 싶어하는 소들의 부탁을 들어주기 위해 P (1 더보기
PKU 2181. Jumping Cows Jumping Cows Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4560 Accepted: 2761 Description Farmer John's cows would like to jump over the moon, just like the cows in their favorite nursery rhyme. Unfortunately, cows can not jump. The local witch doctor has mixed up P (1 더보기
PKU 3032. Card Trick 속임수 카드놀이 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2541 Accepted: 1854 설명 마술사가 카드 뭉치를 잘 섞고서 전부 뒤집은 채로 잡은 뒤 다음 단계를 수행합니다: 맨 위에 있는 카드를 가장 아래로 옮깁니다. 새로이 맨 위에 있는 카드를 테이블 위로 꺼냅니다. 그 카드는 스페이드 에이스입니다. 맨 위에 있는 두 장의 카드를 맨 밑으로 옮깁니다. 그 다음 맨 위에 있는 카드를 테이블 위로 꺼냅니다. 그 카드는 스페이드 2 입니다. 맨 위에 있는 세 장의 카드를 맨 밑으로 옮기고… 이렇게 맨 위에 있는 n장의 카드를 맨 밑으로 옮기고 맨 위에 있는 카드를 테이블 위로 꺼내면 그 카드는 스페이드의 n번째 카드입니다. 이 트릭은 .. 더보기
PKU 3032. Card Trick Card Trick Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2541 Accepted: 1854 Description The magician shuffles a small pack of cards, holds it face down and performs the following procedure: The top card is moved to the bottom of the pack. The new top card is dealt face up onto the table. It is the Ace of Spades. Two cards are moved one at a time from the top to the bottom. The next.. 더보기
PKU 3176. Cow Bowling 볼링치는 소 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7685 Accepted: 5014 설명 소들은 진짜 볼링공을 굴려서 볼링을 치진 않습니다. 대신 각자 번호를 맡아서(번호의 범위는 0부터 99까지입니다) 자리를 잡고 볼링핀처럼 삼각형 모양으로 서있지요: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5그러면 다른 소들이 삼각형의 맨 윗부분에서 시작해서, 아래쪽에 있는 가까운 두 마리 소 중 한 마리에게 움직입니다. 이러한 움직임을 가장 아래쪽에 내려갈 때까지 계속해서, 각 소의 점수는 지나온 경로의 소들의 번호들을 합한 값이 됩니다. (당연하지만) 합한 값이 제일 큰 소가 그 프레임의 우승자가 됩니다. 삼각형 대형의 줄 수는 N 개(1 더보기
PKU 3176. Cow Bowling Cow Bowling Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7685 Accepted: 5014 Description The cows don't use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5Then the other cows traverse the triangle starting from its tip and moving "down" to on.. 더보기
PKU 3085. Quick Change 재빠른 거스름돈 주기 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3979 Accepted: 2914 설명 J.P. Flathead의 가게에서 계산을 할 싼 인력을 고용했습니다. 보통 고등학생들을 고용하는데, 이 알바들은 손님들에게 거스름돈을 줄 때 실수가 많습니다. Flathead는 자기가 직접 계산을 해서 거스름돈을 줄 때 실수하는 금액보다, 알바들이 손님들에게 거스름돈을 줄 때 실수하는 금액이 더 많다는 것을 알게 되었습니다. Flathead는 당신이 손님들에게 줄 거스름돈에 들어가는 quarter($0.25), dime($0.10), nickel($0.05), penny($0.01) 4개의 동전들이 각각 몇개씩인지를 계산하는 프로그램을 .. 더보기
PKU 3085. Quick Change Quick Change Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3979 Accepted: 2914 Description J.P. Flathead’s Grocery Store hires cheap labor to man the checkout stations. The people he hires (usually high school kids) often make mistakes making change for the customers. Flathead, who’s a bit of a tightwad, figures he loses more money from these mistakes than he makes; that is, the emp.. 더보기
PKU 2260. Error Correction 오류 수정 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3990 Accepted: 2641 설명 0과 1로만 이루어진 어떤 행렬의 각 행과 각 열의 합이 짝수만 나올 때 이 행렬을 같은 특성을 지닌 행렬이라고 말합니다. 즉 모든 행과 열이 짝수 비트로 이루어졌을때를 말합니다. 4 x 4 행렬중에 이러한 예를 들어보면: 1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1 행의 합들은 각각 2, 0, 4, 2입니다. 열의 합들은 각각 2, 2, 2, 2입니다. 당신이 해야 할 일은 주어진 집합이 같은 특성을 지녔는지를 확인하는 프로그램을 작성하는 것입니다. 만약 같은 특성을 지닌 행렬이 아니라면, 단 하나의 비트를 바꿈으로써 그 행렬이 같은 .. 더보기
PKU 2260. Error Correction Error Correction Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3990 Accepted: 2641 Description A boolean matrix has the parity property when each row and each column has an even sum, i.e. contains an even number of bits which are set. Here's a 4 x 4 matrix which has the parity property: 1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1 The sums of the rows are 2, 0, 4 and 2. The sums of the columns a.. 더보기
UVa 341. Non-Stop Travel 341 - Non-Stop TravelTime limit: 3.000 seconds 안멈추는 여행 David는 운전할 때 정지 신호와 양보신호, 그리고 신호등의 삼색 신호에 따라 기다리는 것을 싫어합니다. 이러한 짜증을 줄이기 위해서 평소에 자주 가는 곳들의 지도를 준비한 뒤 각 지역들의 교차로마다 평균적으로 얼마나 멈추게 되는지를 초단위로 잽니다. David는 이제 당신의 도움을 받아서, 각 지역의 특정한 두 지점을 놓고, 그가 한 지점에서 다른 한 지점으로 갈 때까지 걸리는 지연시간을 최소로 할 수 있는 방법을 찾고 싶어합니다. 이 때, 지연시간을 최소로 하기 위하여 총 운전거리가 늘어나는 것은 상관하지 않습니다. 입력 각 지역에서 David는 당신에게 지도를 줄겁니다. 지도에 나와있는 데이터의 첫번.. 더보기
UVa 341. Non-Stop Travel 341 - Non-Stop TravelTime limit: 3.000 seconds Non-Stop Travel David hates to wait at stop signs, yield signs and traffic signals while driving. To minimize this aggravation, he has prepared maps of the various regions in which he frequently drives, and measured the average delay (in seconds) at each of the various intersections in these regions. He wants to find the routes between specified poi.. 더보기
PKU 1050. To the Max 제일 크게 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 20504 Accepted: 10588 설명 부호에 상관없는 2차원 평면상의 정수집합체를 주고, 그 안에서 전체 크기 안에 들어가는 1*1 또는 그보다 조금 더 큰 직사각형 모양의 부분집합체를 잡습니다. 직사각형의 합은 직사각형 안에 들어가는 모든 원소의 합을 의미합니다. 가장 합이 큰 직사각형이라는 것은, 직사각형으로 이루어지는 모든 부분집합체들 중 원소들의 합이 가장 큰 직사각형을 의미합니다. 예를 들어 다음 집합체에서 가장 합이 큰 직사각형은 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 왼쪽 아래 부분에 있고 9 2 -4 1 -1 8 그 합은 15입니다. 입력.. 더보기
PKU 1050. To the Max To the Max Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 20504 Accepted: 10588 Description Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is.. 더보기
PKU 1422. Air Raid 공습 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 2879 Accepted: 1701 설명 어떤 도시가 있는데, 이 도시의 모든 도로는 일방통행이고 각 도로는 서로 다른 교차로와 연결되어있습니다. 또한 이 길들은 아무리 길을 따라 걸어도 한 번 출발했던 교차로로 다시 돌아올 수 없는, 순환하지 않는 길들입니다. 이러한 가정 하에 당신은 프로그램을 작성하여 만약 낙하부대가 이 도시에 작전을 펼쳤을 때 모든 낙하부대원은 하나 이상의 교차로를 지나야만 하고, 모든 교차로를 한 명 이상의 낙하부대원이 지나가도록 하는 최소한의 낙하부대원 수를 구해야 합니다. 모든 낙하부대원들은 교차로에 착지한 후 도시의 길을 따라 다른 교차로를 찾아갈 수 있습니다. 각.. 더보기
PKU 1422. Air Raid Air Raid Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 2879 Accepted: 1701 Description Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an intersection and walking through town's streets you can never reach the same intersection i.e. the town's streets form no cycles. With these assumptions .. 더보기
PKU 2844. 합과 곱. 스풰샬 스퉤이지~ N개짜리 정수 수열 A1, A2, ... , AN가 있습니다. 우리는 이를 이용해 이들의 합 S와 곱 P를 쉽게 구할 수 있지요(.... 웃기고 있네;;;). 주어진 N과 S, P를 이용해 수열 A1, A2, ... , AN를 구할 수 있을까요? 입력 한 줄에 N, S, P 세개만 입력됩니다. N은 1000000을 넘지 않으며, S와 P는 150000000을 넘지 않습니다. 출력 해답이 존재하지 않는다면 "No Solution"을, 존재한다면 해당 수열을 출력하여 주세요. 입력 예시sample input#1 2 4 3 sample input#2 4 4 2 출력 예시sample output#1 1 3 sample output#2 No solution 출처 POJ Monthly--2006.06.25, Yan.. 더보기
PKU 2844. Sum and Product. 스풰샬 스퉤이지~ For a sequence of N integers A1, A2, ... , AN, we can calculate their sum S and product P easily. With given N, S and P, can you find out the sequence A1, A2, ... , AN? Input The input only contains a line with three integers N, S and P. Here N is positive and not more than 1000000, and the absolute values of S and P do not exceed 150000000. Output Just output "No solution" if there is no such s.. 더보기
PKU 2245. Lotto. 복권 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3799 Accepted: 2458 설명 독일식 복권은 {1,2,...,49} 중 6개의 숫자를 고릅니다. 비록 당첨확률을 높여주는 방법은 아니지만, 대중적인 선택방법에는, 49개의 숫자들 중 어떤 수 k (k > 6)를 포함하는 부분집합 S를 선택하여 그 안에서 숫자들을 고르는 것입니다. 예를 들어 k=8 이고 S = {1,2,3,5,8,13,21,34} 라면 [1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ... [3,5,8,13,21,34] 등 가능한 선택하는 방법은 28개가 되겠습니다. 당신은 이제 k 와 집합 S를 받으.. 더보기
PKU 2245. Lotto Lotto Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3799 Accepted: 2458 Description In the German Lotto you have to select 6 numbers from the set {1,2,...,49}. A popular strategy to play Lotto - although it doesn't increase your chance of winning - is to select a subset S containing k (k > 6) of these 49 numbers, and then play several games with choosing numbers only from S. For exa.. 더보기

티스토리툴바