Tutorial is loading...
First accepted Div1: 00:00:58 kriii
First accepted Div2: 00:00:59 Baneling3
Author's solution
int a, b;
scanf ( "%d%d", &a, &b );
int ans = 1;
for ( int j = 1; j <= min( a, b ); j++ )
ans *= j;
printf ( "%d\n", ans );
Tutorial is loading...
First accepted Div1: 00:03:30 Egor.Lifar
First accepted Div2: 00:04:43 Baneling3
Author's solution
const int maxn = 1050;
vector < int > ans;
vector < int > newAns;
char t1[maxn];
char t2[maxn];
int n, m;
scanf ( "%d%d\n", &n, &m );
gets( t1 );
gets( t2 );
for ( int j = 0; j < n; j++ )
ans.pb( j );
for ( int j = 0; j < m - n + 1; j++ ) {
newAns.clear();
for ( int i = 0; i < n; i++ )
if ( t1[i] != t2[i + j] )
newAns.pb( i );
if ( newAns.size() < ans.size() )
ans = newAns;
}
int sz = ans.size();
printf( "%d\n", sz );
for ( int j = 0; j < sz; j++ )
printf( "%d ", ans[j] + 1 );
Tutorial is loading...
First accepted Div1: 00:08:30 nuip
First accepted Div2: 00:10:19 ColdSu
Author's solution
const int maxn = 200500;
const int inf = ( 2e9 ) + 2;
vector < pair < pair < int, int >, pair < int, int > > > queries;
int bestCost[maxn];
int l[maxn];
int r[maxn];
int cost[maxn];
int solution( int n, int needLen ) {
queries.clear();
for ( int j = 0; j < n; j++ ) {
queries.pb( mp( mp( l[j], -1 ), mp( r[j], cost[j] ) ) );
queries.pb( mp( mp( r[j], 1 ), mp( l[j], cost[j] ) ) );
}
for ( int j = 0; j < maxn; j++ )
bestCost[j] = inf;
ll ans = 2LL * inf;
sort( queries.begin(), queries.end() );
int sz = queries.size();
for ( int j = 0; j < sz; j++ ) {
int type = queries[j].f.s;
if ( type == -1 ) {
int curLen = queries[j].s.f - queries[j].f.f + 1;
if ( curLen <= needLen )
ans = min( ans, 1LL * queries[j].s.s + 1LL * bestCost[needLen - curLen] );
}
if ( type == 1 ) {
int curLen = queries[j].f.f - queries[j].s.f + 1;
bestCost[curLen] = min( bestCost[curLen], queries[j].s.s );
}
}
return ans >= inf ? -1 : ans;
}
Tutorial is loading...
First accepted Div1: 00:15:47 arsijo
First accepted Div2: 00:18:01 ColdSu
Author's solution
const int maxn = 5000500;
int isPrime[maxn];
ll dp[maxn];
int main()
{
int t, l, r;
scanf ( "%d%d%d", &t, &l, &r );
for ( int j = 2; j < maxn; j++ )
isPrime[j] = j;
for ( int j = 2; j * j < maxn; j++ )
if ( isPrime[j] == j )
for ( int i = j * j; i < maxn; i += j )
isPrime[i] = min( j, isPrime[i] );
dp[1] = 0;
for ( int j = 2; j < maxn; j++ ) {
dp[j] = 1LL * inf * inf;
for ( int x = j; x != 1; x /= isPrime[x] )
dp[j] = min( dp[j], 1LL * dp[j / isPrime[x]] + 1LL * j * ( isPrime[x] - 1 ) / 2LL );
}
int ans = 0;
int cnt = 1;
for ( int j = l; j <= r; j++ ) {
dp[j] %= base;
ans = ( 1LL * ans + 1LL * cnt * dp[j] ) % base;
cnt = ( 1LL * cnt * t ) % base;
}
printf ( "%d\n", ans );
}
Tutorial is loading...
First accepted Div1: 00:43:18 Pepe.Chess
First accepted Div2: 01:05:21 CountOlaf
Author's solution
import java.io.*;
import java.util.*;
public class Main implements Runnable {
static class InputReader {
BufferedReader reader;
StringTokenizer tokenizer;
InputReader(InputStream in) {
reader = new BufferedReader(new InputStreamReader(in), 1 << 20);
tokenizer = null;
}
String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
e.printStackTrace();
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
static long[] unique(long[] arr) {
Arrays.sort(arr);
int newLen = 0;
for (int i = 0; i < arr.length; i++) {
if (i + 1 == arr.length || arr[i] != arr[i + 1]) {
arr[newLen++] = arr[i];
}
}
return Arrays.copyOf(arr, newLen);
}
static class SuffixArray {
int[][] classes;
String s;
int maxH;
SuffixArray(String s) {
this.s = s;
maxH = 0;
while ((1 << maxH) <= s.length()) maxH++;
classes = new int[maxH][];
for (int h = 0; h < maxH; h++) {
classes[h] = new int[s.length()];
}
for (int i = 0; i < s.length(); i++) {
classes[0][i] = s.charAt(i) - 'a';
}
for (int h = 1; h < maxH; h++) {
long[] values = new long[s.length() - (1 << h) + 1];
int valuesLen = 0;
for (int i = 0; i + (1 << h) <= s.length(); i++) {
int leftPart = classes[h - 1][i];
int rightPart = classes[h - 1][i + (1 << (h - 1))];
long curValue = ((long)leftPart << 30) ^ rightPart;
values[valuesLen++] = curValue;
}
values = unique(values);
for (int i = 0; i + (1 << h) <= s.length(); i++) {
int leftPart = classes[h - 1][i];
int rightPart = classes[h - 1][i + (1 << (h - 1))];
long curValue = ((long)leftPart << 30) ^ rightPart;
classes[h][i] = Arrays.binarySearch(values, curValue);
}
}
}
int getLCP(int i, int j) {
int res = 0;
for (int h = maxH - 1; h >= 0; h--) {
if (i + (1 << h) <= s.length() && j + (1 << h) <= s.length() && classes[h][i] == classes[h][j]) {
res += (1 << h);
i += (1 << h);
j += (1 << h);
}
}
return res;
}
}
@Override
public void run() {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
int n = in.nextInt();
String s = in.next();
int m = in.nextInt();
String t = in.next();
int x = in.nextInt();
int[][] dp = new int[x + 1][n + 1];
for (int i = 0; i <= x; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = Integer.MIN_VALUE;
}
}
String q = s + "#" + t;
SuffixArray sarr = new SuffixArray(q);
dp[0][0] = 0;
for (int cnt = 0; cnt <= x; cnt++) {
for (int prefS = 0; prefS <= n; prefS++) {
if (dp[cnt][prefS] == Integer.MIN_VALUE) continue;
//System.err.println("cnt = " + cnt + ", prefS = " + prefS + ", value = " + dp[cnt][prefS]);
if (prefS + 1 <= n && dp[cnt][prefS + 1] < dp[cnt][prefS]) {
dp[cnt][prefS + 1] = dp[cnt][prefS];
}
if (cnt + 1 <= x) {
int prefT = dp[cnt][prefS];
int lcp = sarr.getLCP(prefS, prefT + n + 1);
if (dp[cnt + 1][prefS + lcp] < prefT + lcp) {
dp[cnt + 1][prefS + lcp] = prefT + lcp;
}
}
}
}
boolean ok = false;
for (int cnt = 0; cnt <= x; cnt++) {
if (dp[cnt][n] == m) {
ok = true;
}
}
out.println(ok ? "YES" : "NO");
out.close();
}
public static void main(String[] args) {
new Thread(null, new Main(), "1", 1L << 28).run();
}
}
Tutorial is loading...
First accepted Div1: 00:16:33 webmaster
First accepted Div2: 01:12:52 Nisiyama_Suzune
Author's solution
const int maxn = 105;
vector < pair < int, int > > edge[maxn];
int used[maxn];
int from[maxn];
int where[maxn];
ld dist[maxn];
void dfs( int v, ld prevTime ) {
used[v] = true;
int sz = edge[v].size();
ld bestTime = 2.0L / sz;
ld nextTime = prevTime + bestTime;
if ( nextTime >= 2.0L )
nextTime -= 2.0L;
for ( int j = 0; j < sz; j++ ) {
int id = edge[v][j].f;
int to = edge[v][j].s;
if ( used[to] )
continue;
ld toTime;
if ( nextTime <= 1.0L ) {
from[id] = to;
where[id] = v;
dist[id] = 1.0L - nextTime;
toTime = nextTime + 1.0L;
} else {
from[id] = v;
where[id] = to;
dist[id] = 2.0L - nextTime;
toTime = nextTime - 1.0L;
}
dfs( to, toTime );
nextTime = nextTime + bestTime;
if ( nextTime >= 2.0L )
nextTime -= 2.0L;
}
}
int main()
{
int n;
scanf ( "%d", &n );
for ( int j = 1; j < n; j++ ) {
int u, v;
scanf ( "%d%d", &u, &v );
edge[u].pb( mp( j, v ) );
edge[v].pb( mp( j, u ) );
}
dfs( 1, 0 );
printf( "%d\n", n - 1 );
for ( int j = 1; j < n; j++ ) {
printf( "%d %d %d %d ", 1, j, from[j], where[j] );
cout << fixed << setprecision( 10 ) << dist[j] << endl;
}
}
