TopCoder SRM 437 Div 1

어제 밤 12시에 열린 매치..~
야비군훈련 가서 하루죙일 추위에 떨다가 돌아와서 머리 띵한 상태에서 참여했다..~
250점은 쉬운문제인데도 불구하고 뭔가 함정이 있는지.. 다들 줄줄이 fail했다..
그래도 나는 pass할 줄 알았는데 나도 챌 당했다.. 알고보니 어처구니없는 코딩 실수를.. ㅠ_ㅠ 아 열받아..
요즘들어 컨디션이 안좋은건지.. 아니면 벌써 노화가 오는건지 코딩이 자꾸 꼬인다.. 쩝..
결국 0점으로 마감.. ㅠ_ㅠ

[250] TheSwap

Problem Statement
     
There is nothing more beautiful than just an integer number.
You are given an integer n. Write down n in decimal notation with no leading zeroes, and let M be the number of written digits. Perform the following operation exactly k times:
Choose two different 1-based positions, i and j, such that 1 <= i < j <= M. Swap the digits at positions i and j. This swap must not cause the resulting number to have a leading zero, i.e., if the digit at position j is zero, then i must be strictly greater than 1.
Return the maximal possible number you can get at the end of this procedure. If it's not possible to perform k operations, return -1 instead.
Definition
   
Class:
TheSwap
Method:
findMax
Parameters:
int, int
Returns:
int
Method signature:
int findMax(int n, int k)
(be sure your method is public)
   
 
Constraints
-
n will be between 1 and 1,000,000, inclusive.
-
k will be between 1 and 10, inclusive.
Examples
0)
 
   
16375
1
Returns: 76315
The optimal way is to swap 1 and 7.
1)
 
   
432
1
Returns: 423
In this case the result is less than the given number.
2)
 
   
90
4
Returns: -1
We can't make even a single operation because it would cause the resulting number to have a leading zero.
3)
 
   
5
2
Returns: -1
Here we can't choose two different positions for an operation.
4)
 
   
436659
2
Returns: 966354
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

n이 주어지고 임의의 두개 digit을 swap할 수 있다.. 단 swap 결과로 인해 leading zero가 생기면 안된다.. 이러한 swap 을 딱 k번 할 때 만들 수 있는 가장 큰 수 구하기..

문제 보자마자 대략 큰 수가 앞으로 나오도록 swap을 해보려고 했는데.. 어떤 방법으로 해도 최적이 되는 방법을 찾는게 쉽지 않았다.. 그래서 그냥 backtracking을 시도..~ 삽질끝에 submit했는데.. 시간복잡도를 대충 계산해보니 무려 O((6*5)^10)  -_-;; 기겁을 하고 다시 memorization해서 같은 상태를 두번이상 계산하지 않도록 고쳐서 resubmit..~ 가능한 모든 상태공간은 N*K 이다..

챌 당한 이유는 단순한 코딩 실수였는데.. cnt+1 을 그냥 cnt라고 적어놨었다.. 젠장.. ㅠ_ㅠ
이거 찾은놈 대단하네..

어쨋든 backtracking의 진수를 보여준 좋은 문제..~

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 #define max(x, y) ((x) > (y) ? (x) : (y))
  8
  9 int max1, K;
 10 char check[1000001][11];
 11
 12 void dfs(int n, int cnt)
 13 {
 14     int len, i, j, p;
 15     char buf[100], buf2[100];
 16     if (cnt == K) {
 17         max1 = max(max1, n);
 18         return ;
 19     }
 20     sprintf(buf, "%d", n);
 21     len = strlen(buf);
 22     strcpy(buf2, buf);
 23     for (i = 0; i < len; i++) {
 24         for (j = i+1; j < len; j++) {
 25             if (i == 0 && buf[j] == '0')
 26                 continue;
 27             strcpy(buf2, buf);
 28             buf2[i] = buf[j];
 29             buf2[j] = buf[i];
 30             p = atoi(buf2);
 31             if (!check[p][cnt+1]) {
 32                 check[p][cnt+1] = 1;
 33                 dfs(atoi(buf2), cnt+1);
 34             }
 35         }
 36     }
 37 }
 38
 39 class TheSwap {
 40 public:
 41
 42 int findMax(int n, int k)
 43 {
 44     K = k;
 45     max1 = -1;
 46     memset(check, 0, sizeof(check));
 47     check[n][0] = 1;
 48     dfs(n, 0);
 49 printf("max1 = %d\n", max1);
 50     return max1;
 51 }
 52
 53 };

[500] TheInteger

Problem Statement
     
There is nothing more beautiful than just an integer number.
You are given an integer n. Return the smallest integer greater than or equal to n that contains exactly k distinct digits in decimal notation.
Definition
   
Class:
TheInteger
Method:
find
Parameters:
long long, int
Returns:
long long
Method signature:
long long find(long long n, int k)
(be sure your method is public)
   
 
Constraints
-
n will be between 1 and 10^18, inclusive.
-
k will be between 1 and 10, inclusive.
Examples
0)
 
   
47
1
Returns: 55
Here, k is 1, so we're looking for a number whose digits are all equal. The smallest such number that is greater than or equal to 47 is 55.
1)
 
   
7
3
Returns: 102
We need three distinct digits here.
2)
 
   
69
2
Returns: 69
69 already consists of two different digits.
3)
 
   
12364
3
Returns: 12411
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

n과 k가 주어질 때 n보다 크거나 같으면서 k 종류개의 digit으로만 이루어진 가장 작은 수 구하기..


to be updated..



[1000] TheSum

Problem Statement
     
There is nothing more beautiful than just an integer number.
You are given integers a, b and c. Write each of them down in decimal notation with no leading zeros. The following operations can be performed on each of the written numbers:
Insert a single digit at any position of the number (possibly at the beginning or at the end).
Delete a single digit from the number.
Replace a single digit in the number with some other digit.
An operation can only be performed if it results in a positive number with at least one digit and no leading zeros.
Each operation has an associated cost - insCost, delCost and repCost, respectively. Return the minimal possible total cost of operations needed to satisfy the equality a+b=c.
Definition
   
Class:
TheSum
Method:
minCost
Parameters:
int, int, int, int, int, int
Returns:
int
Method signature:
int minCost(int a, int b, int c, int insCost, int delCost, int repCost)
(be sure your method is public)
   
 
Constraints
-
a, b, and c will each be between 1 and 1,000,000,000, inclusive.
-
insCost, delCost and repCost will each be between 0 and 1,000,000, inclusive.
Examples
0)
 
   
44
77
11
1
1
1
Returns: 1
We just need to insert the digit 2 between the two 1's.
1)
 
   
44
77
11
4
4
1
Returns: 2
This is the same situation as above, but with different costs. This time, the insert and delete operations are much more expensive, and it is cheaper to make two replacements instead. For example, we can turn the numbers into 44+17=61 for a total cost of 2.
2)
 
   
100
100
10000
1000000
1000000
0
Returns: 1000000
Every possible way requires at least one insert or delete operation.
3)
 
   
23456765
19876
927547301
7744
9876
9977
Returns: 48697
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

to be updated..