준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 k개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다.
문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로릉 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다. 또한 편의상 서울은 반드시 1번 도시, 포천은 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.
입력
첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.
출력
첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.
예제 입력 1
4 4 1
1 2 10
2 4 10
1 3 1
3 4 100
예제 출력 1
1
C++ code
#include <stdio.h>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef long long ll;
const ll inf = LLONG_MAX;
typedef struct
{
vector<int> to, cost;
}Road;
typedef struct
{
ll city, cost, kk;
}pq_elem;
bool operator<(pq_elem x, pq_elem y)
{
return x.cost > y.cost;
}
int main(void)
{
int n, m, k, size;
vector<Road> road;
vector<vector<ll>> ans;
priority_queue<pq_elem, vector<pq_elem>> pq;
scanf("%d %d %d", &n, &m, &k);
road.resize(n+1);
ans.resize(n+1, vector<ll>(k+1, inf));
for (int i = 0; i < m; i++)
{
int s, e, c;
scanf("%d %d %d", &s, &e, &c);
road[s].to.push_back(e);
road[s].cost.push_back(c);
road[e].to.push_back(s);
road[e].cost.push_back(c);
}
pq.push(pq_elem{1, 0, 0});
ans[1][0] = 0;
while (pq.size())
{
ll city = pq.top().city, cost = pq.top().cost, kk = pq.top().kk;
pq.pop();
size = road[city].to.size();
for (int i = 0; i < size; i++)
{
pq_elem temp;
temp.city = road[city].to[i];
temp.cost = cost + road[city].cost[i];
temp.kk = kk;
if (ans[temp.city][temp.kk] > temp.cost)
{
ans[temp.city][temp.kk] = temp.cost;
pq.push(temp);
}
temp.cost = cost;
temp.kk++;
if (temp.kk <= k && ans[temp.city][temp.kk] > temp.cost)
{
ans[temp.city][temp.kk] = temp.cost;
pq.push(temp);
}
}
}
ll minans = ans[n][0];
for (int i = 1; i <= k; i++)
minans = min(minans, ans[n][i]);
printf("%lld\n", minans);
return 0;
}
L보다 크거나 같고, U보다 작거나 같은 모드 정수의 각 자리의 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 L과 U이 주어진다. U은 0보다 크거나 같고, 2,000,000,000보다 작거나 같은 정수이고, L은 0보다 크거나 같고, U보다 작거나 같은 정수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력 1
10 14
예제 출력 1
15
C++ code
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
ll f(int x)
{
vector<int> a(10, 0);
int left = 1;
int right = x;
int base = 1;
while (left <= right)
{
while(right % 10 != 9 && left <= right)
{
int temp = right;
while (temp)
{
a[temp % 10] += base;
temp /= 10;
}
right--;
}
if (right < left)
break;
while (left % 10 != 0 && left <= right)
{
int tmp = left;
while (tmp)
{
a[tmp % 10] += base;
tmp /= 10;
}
left++;
}
left /= 10;
right /= 10;
for (int i = 0; i < 10; i++)
a[i] += (right - left + 1) * base;
base *= 10;
}
ll ret = 0;
for (int i = 0; i <= 9; i++)
ret += (a[i]*i);
return ret;
}
int main(void)
{
int lower, upper;
scanf("%d %d", &lower, &upper);
printf("%lld", f(upper)-f(lower-1));
return 0;
}
구간 [A,B]란 A보다 크거나 같고, B보다 작거나 같은 모든 정수가 있는 구간이다. 이때, A와 B는 모두 양수이고, B는 A보다 크다.
구간 [A,B]가 Unlucky가 되기 위해선 구간에 속한 모든 정수가 Lucky Set에 없어야 한다.
Lucky Set과 N이 주어질 때, N을 포함하는 Unlucky 구간의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 Lucky Set에 포함된 숫자의 개수 L이 주어진다. 둘째 줄에는 L개의 수가 주어진다. 이 수는 1,000보다 작거나 같은 자연수이고, L은 50보다 작거나 같은 자연수이다. 그리고 중복되지 않는다. 마지막 줄에는 N이 주어진다. N은 Lucky Set에서 가장 큰 수보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력 1
4
1 7 14 10
2
예제 출력 1
4
C++ code
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
int n, left = 0, right, m;
vector<int> Lucky;
scanf("%d", &n);
right = n - 1;
for (int i = 0; i < n; i++)
{
int temp;
scanf("%d", &temp);
}
scanf("%d", &m);
sort(Lucky.begin(), Lucky.end());
while(left <= right)
{
int mid = (left + right) / 2;
if (Lucky[mid] < m)
left = mid + 1;
else if (Lucky[mid] > m)
right = mid - 1;
else
{
printf("0");
return 0;
}
}
int temp = Lucky[left];
left = Lucky[right];
right = temp;
printf("%d", (m - left - 1) * (right - m) + (right - m - 1));
return 0;
}
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.
사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.
셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수와 각 파티마다 오는 사람의 수는 모두 0 이상 50 이하의 정수이다.