본문 바로가기

pku

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 .. 더보기
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.. 더보기
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 2245. Lotto. AC #include int list[49], lotto[49], n; void print() { int i; for(i=0; i 더보기
PKU 2551. Ones. AC 오버플로우를 방지하기 위해 (a * b) % c = ((a % c) * (b % c)) % c (a + b) % c = ((a % c) + (b % c)) % c 를 사용했습니다. #include #include int rem(int i, int n) { static int result; if(i==0) { result=10%n; return result; } result=((10%n)*result)%n; return result; } int main() { int n, count; long long k; while(scanf("%d", &n)!=EOF) { if((n&1)==0) continue; if(n%5==0) continue; k=0; for(count=0; ; count++) { k=((k%n.. 더보기
PKU 2551. Ones. TLE 21을 예로들면 1 = 1 1 + 10 = 11 1 + 10 + 100 = 105 + 6 1 + 10 + 100 + 1000 = 105 + 21 + 966 + 19 1 + 10 + 100 + 1000 + 10000 = 105 + 21 + 966 + 21 + 9996 + 2 1 + 10 + 100 + 1000 + 10000 + 100000 = 105 + 21 + 966 + 9996 + 21 + 99981 #include #include int main() { int n, count; long long k; while(scanf("%d", &n)!=EOF) { k=0; for(count=0; ; count++) { k+=pow(10, count); k%=n; if(k==0) break; } printf("%.. 더보기
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 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.. 더보기
PKU 2390. Bank Interest 은행 이자 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8868 Accepted: 5327 설명 Farmer John은 작년에 돈을 좀 벌었습니다. 그래서 그 돈을 어딘가에 투자하고 싶은데, 투자해서 얼마의 이익이 나올지 알고 싶어합니다. 그는 그가 이용하는 은행에서 매년 적립되는 이율 R (0부터 20 사이의 정수)을 알고 있습니다. 지금 그가 가진 돈은 100부터 1,000,000 사이의 정수 M 입니다. 근데, 그는 총 Y (0부터 400까지) 년에 걸쳐서 돈을 투자하려고 합니다. 그가 저축한 돈이 미래에 총 얼마가 되서 돌아올지를 알려주세요. 반올림 없이 정수 부분만 나타내세요. 부호가 있는 32비트형 정수로 테스트 데이터에 대한 답이 .. 더보기
PKU 2390. Bank Interest Bank Interest Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8868 Accepted: 5327 Description Farmer John made a profit last year! He would like to invest it well but wonders how much money he will make. He knows the interest rate R (an integer between 0 and 20) that is compounded annually at his bank. He has an integer amount of money M in the range 100..1,000,000. He knows how many .. 더보기
PKU 2871. A Simple Question of Chemistry 간단한 화학문제 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4199 Accepted: 2809 설명 당신은 연구실에서 매우 열정적인 대학원생이지만, 대학교 학부생 시절의 101 화학연구실이 어땠는지를 잊어버린 선배 밑에서 화학을 연구중입니다. 그 선배가 획기적인 아이디어를 하나 떠올렸는데, 당신이 연구실에서 하루종일 혼합물의 온도를 관찰하는 것입니다. 그렇게 하면 어떤 변화가 있는지 전부 기록하는 것이지요. 컴퓨터 과학자가 될 거기 때문에, 당신은 그 과정을 자동으로 하는 방법을 알고 있으므로 프로그램을 작성하여 연구실에서 랩톱으로 작동하게 할 것입니다. (랩톱은 가끔 연구실의 화학물질로 인해 녹습니다.) 당신은 연구실에 들어온 뒤에 당신이 .. 더보기